李 源，范曉林，孫 晶，趙宇海

1(北方工業(yè)大學(xué) 信息學(xué)院，北京 100144) 2(東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽 110819)

1 引 言

圖模型的提出使現(xiàn)實(shí)世界萬物得以被描述和分析，這使得圖模型可以被應(yīng)用到許多不同領(lǐng)域，例如社交網(wǎng)絡(luò)，生物網(wǎng)絡(luò)以及協(xié)作網(wǎng)絡(luò)等.給定一個圖G=(V，E)，其V中的頂點(diǎn)代表感興趣的實(shí)體，E中的邊代表實(shí)體之間的關(guān)系.則本文研究的密集子圖(Densest Subgraph，DS)是圖G中最稠密或具有最高密度的子圖[1].而密集子圖發(fā)現(xiàn)可以解決現(xiàn)實(shí)生活中的許多問題，比如它可以被用于事件檢測，生物分析以及社區(qū)發(fā)現(xiàn)等方面.具體地，在事件檢測方面，發(fā)現(xiàn)的密集子圖是社交網(wǎng)絡(luò)中的“稠密部分”，可代表一個事件[2]；在生物分析方面，密集子圖可以幫助生物學(xué)的研究人員鑒定基因組DNA[3]和基因注釋圖[4]中的調(diào)控基序；在社區(qū)發(fā)現(xiàn)方面，密集子圖可以在社交媒體中找到具有相同興趣的社區(qū)[5]，可根據(jù)社區(qū)的特性實(shí)現(xiàn)產(chǎn)品的精準(zhǔn)推薦和營銷.因此密集子圖發(fā)現(xiàn)這一關(guān)鍵問題值得被深入研究.

目前為止，密集子圖發(fā)現(xiàn)已經(jīng)在簡單靜態(tài)圖和特定動態(tài)圖中被廣泛研究.1)對于簡單靜態(tài)圖中的密集子圖發(fā)現(xiàn)主要有基于邊密度、h-團(tuán)密度和模式密度的研究[6]，其主要是先定義團(tuán)[7]或模式，再從圖中檢測其最高密度的子圖；還有一種是最優(yōu)類團(tuán)[8]，它提取了比基于邊密度更密集、直徑更小的子圖；當(dāng)然，還有其它的密集子圖發(fā)現(xiàn)方法，比如k-truss[9]，k-(r，s)核[10]，k-plexes[11]等.2)特定動態(tài)圖中的密集子圖發(fā)現(xiàn)方法有:McGregor等人[12]提出了在動態(tài)圖數(shù)據(jù)模型上逼近密集子圖的方法，其增加了對動態(tài)圖的挖掘分析；Wang等人[13]提出了基于頻繁結(jié)構(gòu)的動態(tài)圖中密集子圖挖掘的方法；閆靚[14]等人提出了基于滑動窗口模型的top-k密集子圖發(fā)現(xiàn)的方法.這使得密集子圖發(fā)現(xiàn)能夠應(yīng)用到更多復(fù)雜的場景中，但上述方法檢測到的密集子圖并非全都顯著有效.

以上圖模型仍是對同構(gòu)信息網(wǎng)絡(luò)的分析，每個頂點(diǎn)和邊沒有特定的類型信息.而隨著圖模型以及各項(xiàng)技術(shù)的發(fā)展，近些年出現(xiàn)的異構(gòu)信息網(wǎng)絡(luò)(Heterogeneous Information Network，HIN)[15]和屬性圖[16]讓密集子圖發(fā)現(xiàn)有了更進(jìn)一步的研究，HIN是包括不同類型的實(shí)體和關(guān)系；屬性圖是每種類型的實(shí)體和關(guān)系都有自己的屬性信息.Fang等人[16]就提出了在屬性圖中進(jìn)行社區(qū)搜索的算法.接著，Shin等人[17]提出了在異構(gòu)信息網(wǎng)絡(luò)中發(fā)現(xiàn)高密子圖的算法.另外，Chen等人[18]最先提出了一種新穎的非參數(shù)掃描統(tǒng)計(jì)(Non-Parametric Scan Statistics，NPSS)的方法，它無需假設(shè)任何的先驗(yàn)分布，就可以快速準(zhǔn)確地檢測出新興的統(tǒng)計(jì)顯著連通子圖；Nguyen等人[19]將非參數(shù)掃描統(tǒng)計(jì)方法運(yùn)用到了社交媒體的流數(shù)據(jù)中，這讓檢測到的子圖具有統(tǒng)計(jì)顯著性.

以上這些方法的問題是:1)HIN僅分析了特定類型的實(shí)體及關(guān)系，沒有將實(shí)體及關(guān)系的屬性考慮在內(nèi)；屬性圖雖考慮了實(shí)體及關(guān)系的屬性，但是其屬性是沒有時序關(guān)系的，不能從時間維度來縱向分析，這使得圖模型的描述不夠詳細(xì)，其上發(fā)現(xiàn)的密集子圖不夠準(zhǔn)確；2)經(jīng)過實(shí)驗(yàn)研究測試，使用上述提到的密集子圖發(fā)現(xiàn)方法，很難在實(shí)際應(yīng)用場景中發(fā)現(xiàn)最顯著有效的密集子圖；3)在基于h-團(tuán)密度的密集子圖發(fā)現(xiàn)方法和已發(fā)表的通過密集子圖檢測統(tǒng)計(jì)顯著事件的文獻(xiàn)[20]中，發(fā)現(xiàn)的密集子圖僅是包含在(kmax，Ψ)-核中.當(dāng)圖中包含有較多Steiner連通度[21]為1的邊時，所檢測出的密集子圖就偏大，不夠緊湊.

針對以上問題，本文提出了以下解決方案:1)為了詳細(xì)地描述圖模型并使密集子圖發(fā)現(xiàn)算法能適用于更多規(guī)模和復(fù)雜的場景.本文提出一種異構(gòu)屬性網(wǎng)絡(luò)(Heterogeneous Attribute Network，HAN)的新模型，HAN是以圖結(jié)構(gòu)的形式詳細(xì)刻畫和建模某一連續(xù)時間內(nèi)現(xiàn)實(shí)世界萬物及萬物之間的關(guān)系.HAN包括類型、實(shí)體、關(guān)系和帶有時序關(guān)系的屬性信息，其中類型包括實(shí)體類型和關(guān)系類型，每個實(shí)體和關(guān)系都有自己所屬的特定類型，每個實(shí)體和關(guān)系又都有帶有時序關(guān)系的屬性信息，因此所提出的新模型更詳細(xì)地描述了現(xiàn)實(shí)世界萬物；2)為了使發(fā)現(xiàn)的密集子圖具有統(tǒng)計(jì)顯著性，本文則提出先通過收集一段時間粒度(比如:時、天、周)的連續(xù)時間的數(shù)據(jù)，在構(gòu)建HAN的基礎(chǔ)上，然后計(jì)算每個頂點(diǎn)的統(tǒng)計(jì)值[18]來處理HAN的動態(tài)性和異構(gòu)性，再用非參數(shù)掃描統(tǒng)計(jì)的方法測量子圖的顯著有效性；3)在基于h-團(tuán)密度的密集子圖發(fā)現(xiàn)算法和通過密集子圖檢測統(tǒng)計(jì)顯著事件算法中加入Steiner連通度的度量，使發(fā)現(xiàn)的密集子圖更加緊湊.

綜上，本文提出在異構(gòu)屬性網(wǎng)絡(luò)中通過非參數(shù)掃描統(tǒng)計(jì)和基于(k，Ψ)-核的方法對高Steiner連通度的統(tǒng)計(jì)顯著密集子圖進(jìn)行檢測.具體地，首先提出新模型異構(gòu)屬性網(wǎng)絡(luò)，其包括類型、實(shí)體、關(guān)系和帶有時序關(guān)系的屬性信息；其次，通過比較每個頂點(diǎn)的歷史屬性信息和當(dāng)前屬性信息，或同類型中頂點(diǎn)屬性信息的對比計(jì)算每個頂點(diǎn)的統(tǒng)計(jì)值，從而形成統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)(Statistical Weighted Network，SWN)；然后，運(yùn)用非參數(shù)掃描統(tǒng)計(jì)的方法測量SWN中連通子圖的統(tǒng)計(jì)顯著性；最后，由于在HAN中發(fā)現(xiàn)高Steiner連通度的統(tǒng)計(jì)顯著密集子圖是NP-難的，于是提出了基于(k，Ψ)-核的局部擴(kuò)展的近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法，其內(nèi)部的頂點(diǎn)都至少包含在k個h-團(tuán)中，內(nèi)部的邊Steiner連通度都至少為2.

本文的主要貢獻(xiàn)如下:

1)異構(gòu)屬性網(wǎng)絡(luò).提出了一種新穎的異構(gòu)屬性網(wǎng)絡(luò)模型，其詳細(xì)地描述和建模了某一連續(xù)時間內(nèi)的現(xiàn)實(shí)世界萬物，解決了以往圖模型的限制.

2)統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò).通過比較HAN中頂點(diǎn)的歷史屬性信息和當(dāng)前屬性信息，或同類型頂點(diǎn)屬性信息對比，計(jì)算出頂點(diǎn)的統(tǒng)計(jì)值，形成統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò).

3)近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法.由于此問題是NP-難的，于是本文在HAN中提出有效地局部擴(kuò)展的近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法.

本文第2節(jié)對現(xiàn)有的密集子圖發(fā)現(xiàn)問題和圖模型的相關(guān)工作進(jìn)行介紹；第3節(jié)給出本文所用的相關(guān)概念以及本文所解決的問題定義；第4節(jié)詳細(xì)闡述HAN中頂點(diǎn)統(tǒng)計(jì)值的計(jì)算，從而形成統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)；在此基礎(chǔ)上，第5節(jié)詳細(xì)介紹測量統(tǒng)計(jì)顯著性的非參數(shù)掃描統(tǒng)計(jì)方法和近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法；第6節(jié)通過在真實(shí)HAN數(shù)據(jù)集上的實(shí)驗(yàn)分析算法的有效性和高效性；第7節(jié)則總結(jié)全文.

2 相關(guān)工作

密集子圖發(fā)現(xiàn)問題已經(jīng)被廣泛研究[1]，下面將對現(xiàn)有的密集子圖發(fā)現(xiàn)工作進(jìn)行總結(jié).本節(jié)首先介紹基于簡單靜態(tài)圖、特定動態(tài)圖中密集子圖發(fā)現(xiàn)的方法.

1)基于簡單靜態(tài)圖的密集子圖發(fā)現(xiàn)方法.簡單靜態(tài)圖類似于同構(gòu)信息網(wǎng)絡(luò)，其上的密集子圖發(fā)現(xiàn)方法主要有基于邊密度，h-團(tuán)密度和模式密度的方法.基于邊密度的密集子圖發(fā)現(xiàn)方法[6]如下:給定一個無向圖G=(V，E)，n=|V|，m=|E|，則邊密度為m/n.其上的密集子圖發(fā)現(xiàn)是找到圖G中所有可能子圖中邊密度最大的；它的另一版本是最優(yōu)類團(tuán)[8]，提取了比基于邊密度更密集、直徑更小的子圖.基于h-團(tuán)密度的密集子圖發(fā)現(xiàn)方法同邊密度的方法，是找到h-團(tuán)密度最大的子圖.Epasto等人[22]提出了在演化圖上的基于邊密度的密集子圖發(fā)現(xiàn)方法.由于在大圖上發(fā)現(xiàn)精確的密集子圖效果不佳，Charikar[23]和Bahmani[24]等人分別提出了求解密集子圖的貪婪近似算法.當(dāng)然，簡單靜態(tài)圖上還有其它的密集子圖發(fā)現(xiàn)方法，比如k-truss[9]，k-(r，s)核[10]，k-plexes[11]等.

2)基于特定動態(tài)圖中的密集子圖發(fā)現(xiàn)方法.McGregor等人[12]提出了在動態(tài)圖數(shù)據(jù)流計(jì)算模型中發(fā)現(xiàn)密集子圖的方法，其動態(tài)圖是通過一系列邊的插入和刪除來處理的.另外，Wang等人[13]提出了基于頻繁結(jié)構(gòu)的動態(tài)圖中密集子圖發(fā)現(xiàn)算法，其動態(tài)圖是通過頂點(diǎn)和邊的插入和刪除來處理的.閆靚[14]等人提出了一種基于滑動窗口模型的top-k最密集子圖發(fā)現(xiàn)的動態(tài)算法，有效地解決了圖的動態(tài)更新.

近些年來，由于圖模型的應(yīng)用場景越來越復(fù)雜化，異構(gòu)信息網(wǎng)絡(luò)[15]和屬性圖[16]逐漸進(jìn)入研究者們的視野，F(xiàn)ang等人[16]提出了在屬性圖進(jìn)行社區(qū)搜索的方法，其主要是搜索滿足關(guān)鍵詞內(nèi)聚和結(jié)構(gòu)內(nèi)聚的子圖.Shin等人[17]提出了在異構(gòu)信息網(wǎng)絡(luò)中發(fā)現(xiàn)高密子圖的算法，其主要思想是定義一個衡量頂點(diǎn)和邊密集度的指標(biāo)，然后啟發(fā)式地不斷優(yōu)化這個值.Shi[25]等人提出了在異構(gòu)信息網(wǎng)絡(luò)上通過結(jié)合排序和聚類來發(fā)現(xiàn)其稠密部分.另外，本文的研究內(nèi)容還增加了連通子圖統(tǒng)計(jì)顯著性的分析.Chen[18]等人提出了在異構(gòu)社交媒體中統(tǒng)計(jì)顯著連通子圖發(fā)現(xiàn)的方法，其發(fā)現(xiàn)的子圖不僅是連通的，而且是最顯著的.Nguyen等人[19]將非參數(shù)掃描統(tǒng)計(jì)方法運(yùn)用到了社交媒體的流數(shù)據(jù)中，通過異常檢測盡早地識別特殊事件，盡早地做出對應(yīng)措施.因此將此方法應(yīng)用到本文的研究中將更有意義.

3 基本概念及問題定義

本節(jié)主要介紹一些基本概念及其符號表達(dá)，闡述異構(gòu)屬性網(wǎng)絡(luò)的定義及密集子圖的相關(guān)定義，并對本文解決的主要問題給出具體定義.

3.1 基本概念

本文用C={C1，…，Cn}表示實(shí)體類型集，則V={V1∪…∪Vn}為實(shí)體集，這里的Ci代表實(shí)體Vi的類型；同樣，D?C×C={D1，…，Dm}表示關(guān)系類型集，則E?V×V={E1∪…∪Em}為關(guān)系集，這里Ei的關(guān)系類型為Di.然后，HAN的定義如下:

定義1.(HAN).一個HAN模型是一個有向圖G={Q，V，E，f}，由類型、實(shí)體、關(guān)系和屬性信息組成.這里的Q=C∪D={Q1，…，Qn+m}表示實(shí)體和關(guān)系總類型集合，實(shí)體和關(guān)系的屬性信息f={f1，…，fn+m}是一組映射函數(shù):fi:Qi→Rqi，其表示Qi類型t時刻的元素xt的qi維特征向量fi(xt).以微博為例，圖1(a)詳細(xì)闡述了HAN模型的結(jié)構(gòu).

圖1 HAN結(jié)構(gòu)和實(shí)例

此HAN選擇的實(shí)體類型有用戶{昵稱ID，地區(qū)，陽光信用，關(guān)注數(shù)，粉絲數(shù)，發(fā)博數(shù)}、博文{關(guān)鍵詞，情感分析，地區(qū)，點(diǎn)贊數(shù)，轉(zhuǎn)發(fā)數(shù)，評論數(shù)}、話題{關(guān)鍵詞}、鏈接{提及數(shù)}；同時關(guān)系類型有用戶-用戶{關(guān)注類型}、用戶-博文(發(fā)布，轉(zhuǎn)發(fā)，評論，提及){時間}、用戶-話題{時間}、用戶-鏈接{時間}、博文-鏈接{提及數(shù)}、博文-話題{提及數(shù)}、鏈接-話題{時間}.每個實(shí)體和關(guān)系還有它們對應(yīng)的屬性及屬性值.另外，本文將屬性信息分為兩類，分別為動態(tài)屬性和靜態(tài)屬性.動態(tài)屬性表示隨時間變化的屬性，靜態(tài)屬性表示不隨時間變化.特別地，每個實(shí)體和關(guān)系后大括號中的內(nèi)容是它們所對應(yīng)的屬性信息.圖1(b)是關(guān)于武漢出現(xiàn)不明原因新冠肺炎這一HAN實(shí)例.

定義2.(h-團(tuán)，Ψ).在無向圖G=(V，E)中，一個h-團(tuán)(h≥2)是一個子圖S=(Vs，Es)，這里的Vs有h個頂點(diǎn)，并且Vs∈V，?u，v∈Vs，(u，v)∈E.

定義3.(h-團(tuán)度).在無向圖G=(V，E)中，圖G中的頂點(diǎn)v關(guān)于h-團(tuán)的團(tuán)度，即degG(v，Ψ)是包含v的h-團(tuán)的個數(shù).

定義4.(h-團(tuán)密度).在無向圖G=(V，E)中，圖G中關(guān)于h-團(tuán)Ψ(VΨ，EΨ)的h-團(tuán)密度，即ρ(G，Ψ)=η(G，Ψ)/|V|，這里的η(G，Ψ)是圖G中Ψ的個數(shù).

定義5.((k，Ψ)-核).一個(k，Ψ)-核，即Hk是在圖G=(V，E)滿足?v∈Hk，degHk(v，Ψ)≥k的最大的子圖，這里的k(k≥0)是個整數(shù)，Ψ是h-團(tuán).

Hk有k階，頂點(diǎn)v∈V的團(tuán)核數(shù)，即coreG(v，Ψ)是包含v的(k，Ψ)-核的最高階.kmax是最大團(tuán)核數(shù).

例如，圖2是圖1(b)的簡化版，便于分析(k，Ψ)-核.讓Ψ為3-團(tuán)，圖2中最左下頂點(diǎn)的團(tuán)度為3，圖2的3-團(tuán)密度為5/7.另外，圖2中每個矩形上大括號中的數(shù)字代表了矩形包圍的(k，Ψ)-核中的k.因?yàn)閳D2最左下的4個頂點(diǎn)組成的子圖是4-團(tuán)，它中的每個頂點(diǎn)都有3個3-團(tuán)參與，故它為(3，Ψ)-核.

圖2 HAN實(shí)例的簡化版

定義6.(連通度).在無向圖G=(V，E)中，V中兩個不同頂點(diǎn)u和v之間的邊連通度，即λ(u，v)是其移除將u和v斷開連接的最小的邊數(shù).圖G的連通度λ(G)=minu，v∈Vλ(u，v)是圖G中任意兩個不同頂點(diǎn)的最小連通度.

定義7.(Steiner連通度).在無向圖G=(V，E)中，V中兩個不同頂點(diǎn)u和v的Steiner連通度，即sc(u，v)是(u，v)的任意最大連通Steiner子圖(Steiner Maximum-Connected Subgraph，SMCS)的連通度.

SMCS是圖G中的一個子圖Suv，其滿足λ(Suv)是最大的.例如，圖2的連通度是1，邊上的值是對應(yīng)頂點(diǎn)間的邊Steiner連通度.

3.2 問題定義

基于以上的定義，本文給出了在異構(gòu)屬性網(wǎng)絡(luò)中局部擴(kuò)展的近似統(tǒng)計(jì)顯著密集子圖的問題定義.

問題.給定一個HAN為G=(Q，V，E，f)和h-團(tuán)Ψ(VΨ，EΨ)(h≥2)，首先得到統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)Gw，然后從Gw中識別具有最高h(yuǎn)-團(tuán)密度ρ(Gw，Ψ)和較高Steiner連通度的統(tǒng)計(jì)顯著密集子圖S.

接下來的章節(jié)，首先闡述HAN中頂點(diǎn)統(tǒng)計(jì)值的計(jì)算，然后闡述近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法.

4 HAN中頂點(diǎn)的統(tǒng)計(jì)值

本節(jié)通過計(jì)算每個實(shí)體的統(tǒng)計(jì)值來解決HAN中不同實(shí)體類型的異構(gòu)性和HAN的動態(tài)性.首先，不需要任何的假設(shè)，為每個屬性建立基線分布來表示它的正常行為；然后，再為每個實(shí)體估計(jì)一個統(tǒng)計(jì)值，該統(tǒng)計(jì)值表示實(shí)體的顯著程度，該值越小就越顯著.

為了估計(jì)每個實(shí)體屬性的基線分布，需要收集一個分布估計(jì)訓(xùn)練樣本數(shù)據(jù).首先定義一個時間粒度(比如:時、天、周)，然后收集HAN連續(xù)相同時間粒度的一段歷史觀測數(shù)據(jù).本文將歷史觀測數(shù)據(jù)分為兩類:充足觀測數(shù)據(jù)和非充足觀測數(shù)據(jù).以下是這兩種歷史觀測數(shù)據(jù)統(tǒng)計(jì)值計(jì)算的詳細(xì)介紹.

4.1 充足觀測數(shù)據(jù)統(tǒng)計(jì)值的計(jì)算

充足觀測數(shù)據(jù)集由XT={x1，…，xT}表示，其中xi為第i時間粒度實(shí)體x的數(shù)據(jù).首先，通過比較屬性的歷史觀測值與當(dāng)前觀測值計(jì)算每個實(shí)體中所有屬性的統(tǒng)計(jì)值；然后，通過交叉檢驗(yàn)來計(jì)算這個實(shí)體的統(tǒng)計(jì)值.在原假設(shè)沒有特殊情況發(fā)生時，這個統(tǒng)計(jì)值解釋了從歷史觀測值中隨機(jī)選擇的樣本大于等于當(dāng)前觀測值的概率.

實(shí)體屬性的統(tǒng)計(jì)值:實(shí)體x∈Qi類型的屬性j∈[1，qi]的統(tǒng)計(jì)值定義為:

(1)

其中fi，j(xT)是指當(dāng)前時間T下實(shí)體x所屬Q(mào)i類型第j維的屬性.實(shí)體x屬性的統(tǒng)計(jì)值p(fi，j(xT))表示歷史觀測值fi，j(xt)大于等于當(dāng)前觀測值fi，j(xT)的概率.

實(shí)體的統(tǒng)計(jì)值:實(shí)體x∈Qi類型的統(tǒng)計(jì)值定義為:

(2)

其中pmin(xt)=minj=1,…,qip(fi，j(xt))代表在當(dāng)前時間實(shí)體x所有屬性統(tǒng)計(jì)值的最小值.實(shí)體x的統(tǒng)計(jì)值p(xT)表示歷史屬性的最小值pmin(xt)小于等于當(dāng)前屬性的最小值pmin(xT)的概率.

不將實(shí)體屬性的統(tǒng)計(jì)值p(fi，j(xT))和所有屬性統(tǒng)計(jì)值的最小值pmin(xT)作為最終的統(tǒng)計(jì)值，是因?yàn)樯鲜鰞煞N統(tǒng)計(jì)值在進(jìn)行非參數(shù)掃描統(tǒng)計(jì)時會偏向于具有更多屬性的實(shí)體[18].而用屬性之間不同時刻下統(tǒng)計(jì)值的最小值來交叉驗(yàn)證得到當(dāng)前時刻最終的統(tǒng)計(jì)值，這樣的統(tǒng)計(jì)值p(xT)在原假設(shè)下是服從[0，1]上的均勻分布的.

4.2 非充足觀測數(shù)據(jù)統(tǒng)計(jì)值的計(jì)算

對于非充足觀測數(shù)據(jù)，本文比較同類型間實(shí)體的差異.同類型實(shí)體的觀測數(shù)據(jù)表示為XQi={x1，…，x|Qi|}.在原假設(shè)沒有特殊情況發(fā)生時，這個統(tǒng)計(jì)值反映了同類型中隨機(jī)選擇的不同于當(dāng)前考慮的實(shí)體的觀測值大于等于當(dāng)前考慮實(shí)體觀測值的概率.

實(shí)體屬性的統(tǒng)計(jì)值:實(shí)體x∈Qi類型的屬性j∈[1，qi]的統(tǒng)計(jì)值定義為:

(3)

其中fi，j(x)是指同類型中實(shí)體x∈Qi類型的第j維的屬性.實(shí)體x屬性的統(tǒng)計(jì)值p(fi，j(x))表示同屬Q(mào)i類型的其它實(shí)體的觀測值大于等于當(dāng)前所考慮實(shí)體x觀測值的概率.

實(shí)體的統(tǒng)計(jì)值:實(shí)體x∈Qi類型的統(tǒng)計(jì)值定義為:

(4)

其中pmin(xq)=minj=1，…，qip(fi，j(xq))代表了同類型實(shí)體所有屬性的最小值.實(shí)體x的統(tǒng)計(jì)值p(x)表示同類型實(shí)體屬性的最小值pmin(xq)小于等于當(dāng)前實(shí)體屬性的最小值pmin(x)的概率.同樣地，以這種方式計(jì)算的統(tǒng)計(jì)值也服從[0，1]上的均勻分布.最終得到了HAN中每個實(shí)體的統(tǒng)計(jì)值，形成統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)Gw={C，V，E，p}.

5 近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法

本節(jié)提出在統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)中局部擴(kuò)展的近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法.接下來，本節(jié)首先詳細(xì)闡述如何測量子圖的統(tǒng)計(jì)顯著性.

5.1 非參數(shù)掃描統(tǒng)計(jì)

為了測量子圖的統(tǒng)計(jì)顯著性，本文在統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)中使用非參數(shù)掃描統(tǒng)計(jì)[26]的方法.其方法定義如公式(5)所示:

(5)

其中S表示一個連通子圖，A(S)指的是S的統(tǒng)計(jì)顯著分?jǐn)?shù).αmax(αmax<1)是最大的統(tǒng)計(jì)顯著水平，這意味著S至少有1-αmax的統(tǒng)計(jì)顯著性.V(S)是S中所有頂點(diǎn)的個數(shù)，Vα(S)=∑v∈V(S)I(p(v)≤α)是S中統(tǒng)計(jì)值小于等于置信水平α(α>0)的頂點(diǎn)的個數(shù).φ(α，Vα(S)，V(S))指的是非參數(shù)掃描統(tǒng)計(jì)方法，即把在水平α處有顯著意義的頂點(diǎn)的個數(shù)Vα(S)與它的期望E[Vα(S)]作比較，又因?yàn)樵谠僭O(shè)沒有特殊情況發(fā)生時，統(tǒng)計(jì)值是服從[0，1]上的均勻分布的，即E[Vα(S)]=αV(S).

因此BJ統(tǒng)計(jì)量[27]可以直接將Vα(S)和V(S)作比較，BJ統(tǒng)計(jì)量的數(shù)學(xué)形式為:

(6)

這里的KL是Kullback-Liebler散度，意味著統(tǒng)計(jì)值小于α的觀察個數(shù)占總個數(shù)比例與其期望值的差異.KL被定義為:

(7)

5.2 近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法

在復(fù)雜應(yīng)用場景中，僅僅發(fā)現(xiàn)密集子圖是遠(yuǎn)遠(yuǎn)不夠的，因?yàn)槊芗訄D缺少在實(shí)際場景中的顯著有效性，因此本文提出近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法.

具體地，首先由第4節(jié)得到一個統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)Gw={C，V，E，p}，其每個頂點(diǎn)的權(quán)重p表示它的統(tǒng)計(jì)值，統(tǒng)計(jì)值越小越顯著.然后在統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)中通過非參數(shù)掃描統(tǒng)計(jì)識別到統(tǒng)計(jì)顯著密集子圖.為了使子圖更緊湊，增加了邊Steiner連通度的考量，文獻(xiàn)[21]則提出了計(jì)算連通圖中任意一條邊的Steiner連通度的方法.

由于在統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)中發(fā)現(xiàn)統(tǒng)計(jì)顯著的連通子圖是NP-難的[19]，所以本文的問題也是NP-難的.而且在大的網(wǎng)絡(luò)中發(fā)現(xiàn)精確的基于h-團(tuán)密度的密集子圖是不切實(shí)際的，又因?yàn)?kmax，Ψ)-核作為密集子圖具有1/VΨ的近似比保證.

因此基于(k，Ψ)-核，本文提出一種高效地發(fā)現(xiàn)top-r不連通的統(tǒng)計(jì)顯著密集子圖近似算法.偽代碼如算法1所示，它將統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)Gw作為輸入；每種實(shí)體類型中的種子個數(shù)為K；種子頂點(diǎn)的最大擴(kuò)展數(shù)為Z.輸出top-r的統(tǒng)計(jì)顯著密集子圖，以S表示.

算法1的主要思想是從種子頂點(diǎn)局部擴(kuò)展到其邊Steiner連通度最大的鄰居頂點(diǎn)，然后迭代地增加滿足統(tǒng)計(jì)值和團(tuán)核數(shù)限制的頂點(diǎn)到當(dāng)前子圖R中.具體地，首先通過(k，Ψ)-核分解[6]計(jì)算Gw中每個頂點(diǎn)v的團(tuán)核數(shù)coreGw(v，Ψ)，并根據(jù)團(tuán)核數(shù)按非增順序排列頂點(diǎn)(行1-2)；再計(jì)算每條邊的Steiner連通度[21](行3).然后從剩余子圖RD中的每種實(shí)體類型中選擇一個種子頂點(diǎn)，并將它加入到當(dāng)前子圖R中(行7).其次，由算法2計(jì)算出R中有最大邊Steiner連通度的鄰居頂點(diǎn)(行11)，再迭代地在R和它的鄰居頂點(diǎn)中擴(kuò)展具有最高顯著分?jǐn)?shù)A(S)的子圖S[19]，然后由算法3將子圖S收縮至密集子圖Sd，Sd中最大的團(tuán)核數(shù)不小于當(dāng)前子圖R中的最小的團(tuán)核數(shù)(行9-13).在每次迭代中，Sd被更新為R.當(dāng)R不能被進(jìn)一步擴(kuò)展時，迭代就終止了(行14-16).通過這樣的算法，最終得到的子圖保證具有最大顯著分?jǐn)?shù)A(S)和團(tuán)核數(shù)coreGw(v，Ψ).

正確性分析.算法1本質(zhì)上是從種子頂點(diǎn)開始局部擴(kuò)展并發(fā)現(xiàn)近似統(tǒng)計(jì)顯著密集子圖，這些子圖具有最大的顯著分?jǐn)?shù)和團(tuán)核數(shù)且邊Steiner連通度至少為2.而對于每個當(dāng)前子圖R，它通過算法2得到當(dāng)前邊Steiner連通度最大的鄰居頂點(diǎn)；通過HSS函數(shù)[19]計(jì)算得到有最大顯著分?jǐn)?shù)的頂點(diǎn)，該函數(shù)已在5.1節(jié)中證明；最后通過算法3將最大團(tuán)核數(shù)不小于當(dāng)前子圖R中的頂點(diǎn)加入.而迭代停止標(biāo)準(zhǔn)(行14)確保了當(dāng)前子圖R是局部的近似統(tǒng)計(jì)顯著密集子圖，即剩余圖中頂點(diǎn)沒有滿足是和當(dāng)前子圖R連通且滿足邊Steiner連通度、顯著分?jǐn)?shù)和團(tuán)核數(shù)的頂點(diǎn).

算法1.ASSDSD算法

輸入:一個統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)Gw={C，V，E，p}；

每種實(shí)體類型中種子頂點(diǎn)個數(shù)，K(默認(rèn)為5)；

種子頂點(diǎn)的最大擴(kuò)展數(shù)，Z(默認(rèn)為log(|V|))；

輸出:top-r統(tǒng)計(jì)顯著密集子圖，S；

1.計(jì)算每個頂點(diǎn)v的團(tuán)核數(shù)，即coreGw(v，Ψ)；

2.根據(jù)團(tuán)核數(shù)按非增的順序排列Gw中的頂點(diǎn)；

3.計(jì)算每條邊的Steiner連通度sc[21]；

4.αmax=0.05，S=φ，RD=V，R=φ；

5.Forc∈[1，…，n]do

6. Fori∈[1，…，K]do

7.R=R∪{vi}，vi是RD中類型為c的具有最大coreGw(vi，Ψ)的顯著頂點(diǎn)；

8. Forz∈[1，…Z]do

9. 以團(tuán)核數(shù)按遞增順序排列R中的頂點(diǎn)；

10.mincore是當(dāng)前子圖R最小的團(tuán)核數(shù)；

11.Vn=SC(R，V，E)；//詳見算法2

12. 〈S，A(S)〉=HSS(Vn，R，αmax)[19]；//A(S)是子圖S的最高顯著分?jǐn)?shù)，里面的頂點(diǎn)具有最小統(tǒng)計(jì)值

13.Sd=DS(S，R，mincore)；//詳見算法3

14. IfSdR≠φthen

15.R=Sd；

16. Else

17. Break；

18.RD=RDR，S=S∪{R}，R=φ；

19.返回top-r的S；

算法2.SC算法

輸入：當(dāng)前子圖R，Gw中的頂點(diǎn)集V和邊集E；

輸出：R中最大Steiner連通度的鄰居頂點(diǎn)集；

1. Forv∈Rdo

2.Vn={vn∈VR；(vn，v}∈E}；

3.scmax是v所有鄰邊中Steiner連通度最大值；

4. Forvn∈Vndo

5. If sc(v，vn)=scmaxthen

6.VN=VN∪{vn}；

7. 返回VN；

算法3.DS算法

輸入：最顯著的子圖S，當(dāng)前子圖R；R中最小的團(tuán)核數(shù)，mincore；

輸出：密集子圖Sd；

1.maxcore是SR中所有頂點(diǎn)的最小團(tuán)核數(shù)；

2.Sd=R；

3.ifmaxcore≥mincorethen

4. forv∈SRdo

5. ifcoreGw(v，Ψ)=maxcorethen

6.Sd=Sd∪{v}；

7.返回Sd；

6 實(shí)驗(yàn)結(jié)果與分析

6.1 實(shí)驗(yàn)環(huán)境配置

本文用真實(shí)的微博數(shù)據(jù)集對所提出的算法進(jìn)行有效性和高效性的評估.本實(shí)驗(yàn)所用的軟硬件環(huán)境如下:Windows 7旗艦版操作系統(tǒng)，Intel(R)Core(TM)i5-3337U的CPU，主頻1.8GHz，8G內(nèi)存，1T硬盤；開發(fā)平臺為JetBrains PyCharm 2019，開發(fā)語言為Python 3.

6.2 實(shí)驗(yàn)所用數(shù)據(jù)集

為了有效地構(gòu)建HAN模型及評估所提出的算法，本文選擇微博上的謠言事件進(jìn)行評估.因?yàn)槲⒉┨峁┝斯俜降谋僦{服務(wù)，所以本文收集了從2019年12月1日-2020年4月30日的微博謠言數(shù)據(jù).收集數(shù)據(jù)的統(tǒng)計(jì)信息如表1所示.

表1 微博謠言數(shù)據(jù)集

6.3 實(shí)驗(yàn)評估指標(biāo)

由于本文增加了密集子圖統(tǒng)計(jì)顯著性的研究，所以本文選擇lead time和lag time來評估所發(fā)現(xiàn)子圖的統(tǒng)計(jì)顯著性.另外，還有coefficient和runtime指標(biāo)，4個指標(biāo)的具體概念如下:

1)lead time.這指的是密集子圖還沒有形成時，預(yù)測該子圖到密集子圖剛形成之間的天數(shù).

2)lag time.這指的是密集子圖剛形成到檢測到該統(tǒng)計(jì)顯著密集子圖之間的天數(shù).

3)coefficient.這是應(yīng)用在圖中精確率和召回率的結(jié)合體.由于密集子圖通常表達(dá)為事件或社區(qū)等，故令coefficient=|E∩E*|/|E∪E*|，這里的E是事件或社區(qū)相關(guān)的實(shí)體集，E*是算法檢測技術(shù)標(biāo)記的實(shí)體集.

4)runtime.本文所提出算法和對比算法的運(yùn)行時間.

接下來，首先比較4個算法的有效性和高效性，即ASSDSD算法、IncApp算法[6]、NPHGS算法[18]和HeProjI算法[25].然后，對比不同參數(shù)下算法的有效性和高效性.

6.4 微博謠言數(shù)據(jù)集中算法性能分析

密集子圖的統(tǒng)計(jì)顯著性評估需要時序關(guān)系，而IncApp算法和HeProjI算法所使用的圖模型是沒有時序關(guān)系的，故先評估4個算法的coefficient和runtime.

6.4.1 4個算法的有效性和高效性分析

本次實(shí)驗(yàn)通過隨機(jī)去掉數(shù)據(jù)集中的數(shù)據(jù)來評估不同數(shù)據(jù)大小下算法的有效性和高效性.圖3(a)和圖3(b)顯示了不同數(shù)據(jù)大小下的4個算法對比.x軸上的數(shù)字代表了目前數(shù)據(jù)大小占原始數(shù)據(jù)的百分比.可以看到不同數(shù)據(jù)大小下ASSDSD算法在coefficient上都優(yōu)于其它的算法.這是因?yàn)锳SSDSD算法所考慮的子圖更加緊湊且具有統(tǒng)計(jì)顯著性.而在runtime上會花費(fèi)更多的時間，是因?yàn)闄z測子圖考慮了更多的限制條件.

圖3 4個算法有效性和高效性對比

由于IncApp算法和HeProjI算法所使用的圖模型沒有時序關(guān)系，所以本次實(shí)驗(yàn)僅比較了ASSDSD算法和NPHGS算法的lead time和lag time.在圖3(c)和圖3(d)中評估了不同數(shù)據(jù)大小下的ASSDSD算法和NPHGS算法，可以看到ASSDSD算法都優(yōu)于NPHGS算法，因此檢測的子圖顯著性更高.

6.4.2 不同參數(shù)下算法的有效性和高效性分析

由于初始參數(shù)對算法的有效性和高效性有重要影響，故以下進(jìn)行不同參數(shù)下算法的有效性和高效性對比.而由于ASSDSD算法和NPHGS算法所使用的圖模型近似，其參數(shù)也近似，故僅對這兩個算法進(jìn)行不同參數(shù)下的指標(biāo)對比.共有的參數(shù)分別為:K，種子頂點(diǎn)的個數(shù)；αmax，最大的統(tǒng)計(jì)顯著性水平；Ψ，h-團(tuán).下面首先是不同種子頂點(diǎn)數(shù)下的指標(biāo)對比.

1)不同的種子頂點(diǎn)數(shù)(K)

本次實(shí)驗(yàn)設(shè)置初始參數(shù)αmax=0.05.圖4展示了不同種子頂點(diǎn)數(shù)下ASSDSD算法和NPHGS算法的4種指標(biāo)對比.首先，可以看到在平均的lead time、lag time、coefficient下，本文所提出的ASSDSD算法都優(yōu)于NPHGS算法.這主要是因?yàn)锳SSDSD算法綜合了子圖統(tǒng)計(jì)顯著性和密集性的考慮，讓檢測的子圖更加有效和緊湊.另外，運(yùn)行時間也變快了.它的主要原因是因?yàn)樗岢龅乃惴ㄔ诿看蔚泻雎粤藳]有出現(xiàn)在密集子圖中的頂點(diǎn)，讓每次檢測時都對頂點(diǎn)做了篩選.

圖4 不同種子頂點(diǎn)數(shù)下的指標(biāo)對比

2)不同的最大統(tǒng)計(jì)顯著性水平(αmax)

本次實(shí)驗(yàn)給ASSDSD算法和NPHGS算法設(shè)置了初始參數(shù)K=15.圖5顯示了ASSDSD算法和NPHGS算法的4種指標(biāo)對比.通過圖5可以看到對于不同的αmax，本文提出的ASSDSD算法在4種指標(biāo)下均是優(yōu)于NPHGS算法.這主要是因?yàn)楸疚木C合考慮了子圖的內(nèi)容和結(jié)構(gòu)內(nèi)聚性.

圖5也展示了隨著αmax的增大，對lead time、lag time、coefficient這3個指標(biāo)均沒有很大影響，僅有稍微提高.其原因是αmax是人工設(shè)置的，并且公式(5)可以自動優(yōu)化α.另外，運(yùn)行時間的提高是因?yàn)棣羗ax越大，更多的頂點(diǎn)需要被考慮.

圖5 不同αmax下的指標(biāo)對比

3)不同的h-團(tuán)

為了執(zhí)行所提出的ASSDSD算法，需要選擇h-團(tuán).因此，本次實(shí)驗(yàn)評估了在不同h-團(tuán)下的ASSDSD算法的性能指標(biāo).在圖6中，隨著h的增大，coefficient提高的原因是密集子圖通常表達(dá)為事件或社區(qū)，但是lead time、lag time和runtime是先增加后減少.這主要是因?yàn)楫?dāng)h設(shè)置的越大時，所檢測的子圖必須包含越密集的團(tuán)，這需要花費(fèi)更多的時間；然而當(dāng)h超過一定的范圍，HAN中或許沒有這么密集的團(tuán)，因此檢測會提前終止.

圖6 不同h-團(tuán)下的指標(biāo)對比

7 總結(jié)與展望

密集子圖發(fā)現(xiàn)已經(jīng)被廣泛研究.針對現(xiàn)有的簡單圖模型和不同圖模型下發(fā)現(xiàn)的密集子圖不夠緊湊，缺乏顯著有效性的問題.本文提出了異構(gòu)屬性網(wǎng)絡(luò)模型；并結(jié)合圖模型的內(nèi)容和結(jié)構(gòu)設(shè)計(jì)了基于(k，Ψ)-核的近似統(tǒng)計(jì)顯著密集子圖發(fā)現(xiàn)算法.最后，在大量真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本文提出模型和算法的有效性和高效性.對于未來的密集子圖發(fā)現(xiàn)問題研究，由于圖模型的不斷發(fā)展，還需設(shè)計(jì)更通用的方法滿足不斷發(fā)展的需求.