異構屬性網(wǎng)絡中統(tǒng)計顯著密集子圖發(fā)現(xiàn)算法研究

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

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

1 引 言

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

目前為止，密集子圖發(fā)現(xiàn)已經(jīng)在簡單靜態(tài)圖和特定動態(tài)圖中被廣泛研究.1)對于簡單靜態(tài)圖中的密集子圖發(fā)現(xiàn)主要有基于邊密度、h-團密度和模式密度的研究[6]，其主要是先定義團[7]或模式，再從圖中檢測其最高密度的子圖；還有一種是最優(yōu)類團[8]，它提取了比基于邊密度更密集、直徑更小的子圖；當然，還有其它的密集子圖發(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]提出了基于頻繁結構的動態(tài)圖中密集子圖挖掘的方法；閆靚[14]等人提出了基于滑動窗口模型的top-k密集子圖發(fā)現(xiàn)的方法.這使得密集子圖發(fā)現(xiàn)能夠應用到更多復雜的場景中，但上述方法檢測到的密集子圖并非全都顯著有效.

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

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

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

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

本文的主要貢獻如下:

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

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

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

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

2 相關工作

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

1)基于簡單靜態(tài)圖的密集子圖發(fā)現(xiàn)方法.簡單靜態(tài)圖類似于同構信息網(wǎng)絡，其上的密集子圖發(fā)現(xiàn)方法主要有基于邊密度，h-團密度和模式密度的方法.基于邊密度的密集子圖發(fā)現(xiàn)方法[6]如下:給定一個無向圖G=(V，E)，n=|V|，m=|E|，則邊密度為m/n.其上的密集子圖發(fā)現(xiàn)是找到圖G中所有可能子圖中邊密度最大的；它的另一版本是最優(yōu)類團[8]，提取了比基于邊密度更密集、直徑更小的子圖.基于h-團密度的密集子圖發(fā)現(xiàn)方法同邊密度的方法，是找到h-團密度最大的子圖.Epasto等人[22]提出了在演化圖上的基于邊密度的密集子圖發(fā)現(xiàn)方法.由于在大圖上發(fā)現(xiàn)精確的密集子圖效果不佳，Charikar[23]和Bahmani[24]等人分別提出了求解密集子圖的貪婪近似算法.當然，簡單靜態(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ù)流計算模型中發(fā)現(xiàn)密集子圖的方法，其動態(tài)圖是通過一系列邊的插入和刪除來處理的.另外，Wang等人[13]提出了基于頻繁結構的動態(tài)圖中密集子圖發(fā)現(xiàn)算法，其動態(tài)圖是通過頂點和邊的插入和刪除來處理的.閆靚[14]等人提出了一種基于滑動窗口模型的top-k最密集子圖發(fā)現(xiàn)的動態(tài)算法，有效地解決了圖的動態(tài)更新.

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

3 基本概念及問題定義

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

3.1 基本概念

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

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

圖1 HAN結構和實例

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

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

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

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

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

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

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

圖2 HAN實例的簡化版

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

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

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

3.2 問題定義

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

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

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

4 HAN中頂點的統(tǒng)計值

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

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

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

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

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

(1)

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

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

(2)

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

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

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

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

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

(3)

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

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

(4)

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

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

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

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

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

(5)

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

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

(6)

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

(7)

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

在復雜應用場景中，僅僅發(fā)現(xiàn)密集子圖是遠遠不夠的，因為密集子圖缺少在實際場景中的顯著有效性，因此本文提出近似統(tǒng)計顯著密集子圖發(fā)現(xiàn)算法.

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

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

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

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

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

算法1.ASSDSD算法

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

每種實體類型中種子頂點個數(shù)，K(默認為5)；

種子頂點的最大擴展數(shù)，Z(默認為log(|V|))；

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

1.計算每個頂點v的團核數(shù)，即coreGw(v，Ψ)；

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

3.計算每條邊的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，Ψ)的顯著頂點；

8. Forz∈[1，…Z]do

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

10.mincore是當前子圖R最小的團核數(shù)；

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

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

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算法

輸入：當前子圖R，Gw中的頂點集V和邊集E；

輸出：R中最大Steiner連通度的鄰居頂點集；

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，當前子圖R；R中最小的團核數(shù)，mincore；

輸出：密集子圖Sd；

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

2.Sd=R；

3.ifmaxcore≥mincorethen

4. forv∈SRdo

5. ifcoreGw(v，Ψ)=maxcorethen

6.Sd=Sd∪{v}；

7.返回Sd；

6 實驗結果與分析

6.1 實驗環(huán)境配置

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

6.2 實驗所用數(shù)據(jù)集

為了有效地構建HAN模型及評估所提出的算法，本文選擇微博上的謠言事件進行評估.因為微博提供了官方的辟謠服務，所以本文收集了從2019年12月1日-2020年4月30日的微博謠言數(shù)據(jù).收集數(shù)據(jù)的統(tǒng)計信息如表1所示.

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

6.3 實驗評估指標

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

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

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

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

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

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

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

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

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

本次實驗通過隨機去掉數(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)于其它的算法.這是因為ASSDSD算法所考慮的子圖更加緊湊且具有統(tǒng)計顯著性.而在runtime上會花費更多的時間，是因為檢測子圖考慮了更多的限制條件.

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

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

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

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

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

本次實驗設置初始參數(shù)αmax=0.05.圖4展示了不同種子頂點數(shù)下ASSDSD算法和NPHGS算法的4種指標對比.首先，可以看到在平均的lead time、lag time、coefficient下，本文所提出的ASSDSD算法都優(yōu)于NPHGS算法.這主要是因為ASSDSD算法綜合了子圖統(tǒng)計顯著性和密集性的考慮，讓檢測的子圖更加有效和緊湊.另外，運行時間也變快了.它的主要原因是因為所提出的算法在每次迭代中忽略了沒有出現(xiàn)在密集子圖中的頂點，讓每次檢測時都對頂點做了篩選.

圖4 不同種子頂點數(shù)下的指標對比

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

本次實驗給ASSDSD算法和NPHGS算法設置了初始參數(shù)K=15.圖5顯示了ASSDSD算法和NPHGS算法的4種指標對比.通過圖5可以看到對于不同的αmax，本文提出的ASSDSD算法在4種指標下均是優(yōu)于NPHGS算法.這主要是因為本文綜合考慮了子圖的內容和結構內聚性.

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

圖5 不同αmax下的指標對比

3)不同的h-團

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

圖6 不同h-團下的指標對比

7 總結與展望

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