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

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

1 引 言

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

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

以上圖模型仍是對(duì)同構(gòu)信息網(wǎng)絡(luò)的分析，每個(gè)頂點(diǎn)和邊沒(méi)有特定的類(lèi)型信息.而隨著圖模型以及各項(xiàng)技術(shù)的發(fā)展，近些年出現(xiàn)的異構(gòu)信息網(wǎng)絡(luò)(Heterogeneous Information Network，HIN)[15]和屬性圖[16]讓密集子圖發(fā)現(xiàn)有了更進(jìn)一步的研究，HIN是包括不同類(lèi)型的實(shí)體和關(guān)系；屬性圖是每種類(lèi)型的實(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)的方法，它無(wú)需假設(shè)任何的先驗(yàn)分布，就可以快速準(zhǔn)確地檢測(cè)出新興的統(tǒng)計(jì)顯著連通子圖；Nguyen等人[19]將非參數(shù)掃描統(tǒng)計(jì)方法運(yùn)用到了社交媒體的流數(shù)據(jù)中，這讓檢測(cè)到的子圖具有統(tǒng)計(jì)顯著性.

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

1)基于簡(jiǎn)單靜態(tài)圖的密集子圖發(fā)現(xiàn)方法.簡(jiǎn)單靜態(tài)圖類(lèi)似于同構(gòu)信息網(wǎng)絡(luò)，其上的密集子圖發(fā)現(xiàn)方法主要有基于邊密度，h-團(tuán)密度和模式密度的方法.基于邊密度的密集子圖發(fā)現(xiàn)方法[6]如下:給定一個(gè)無(wú)向圖G=(V，E)，n=|V|，m=|E|，則邊密度為m/n.其上的密集子圖發(fā)現(xiàn)是找到圖G中所有可能子圖中邊密度最大的；它的另一版本是最優(yōu)類(lèi)團(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)然，簡(jiǎn)單靜態(tài)圖上還有其它的密集子圖發(fā)現(xiàn)方法，比如k-truss[9]，k-(r，s)核[10]，k-plexes[11]等.

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

近些年來(lái)，由于圖模型的應(yīng)用場(chǎng)景越來(lái)越復(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)高密子圖的算法，其主要思想是定義一個(gè)衡量頂點(diǎn)和邊密集度的指標(biāo)，然后啟發(fā)式地不斷優(yōu)化這個(gè)值.Shi[25]等人提出了在異構(gòu)信息網(wǎng)絡(luò)上通過(guò)結(jié)合排序和聚類(lèi)來(lái)發(fā)現(xiàn)其稠密部分.另外，本文的研究?jī)?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ù)中，通過(guò)異常檢測(cè)盡早地識(shí)別特殊事件，盡早地做出對(duì)應(yīng)措施.因此將此方法應(yīng)用到本文的研究中將更有意義.

3 基本概念及問(wèn)題定義

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

3.1 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 問(wèn)題定義

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

其中pmin(xt)=minj=1,…,qip(fi，j(xt))代表在當(dāng)前時(shí)間實(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í)會(huì)偏向于具有更多屬性的實(shí)體[18].而用屬性之間不同時(shí)刻下統(tǒng)計(jì)值的最小值來(lái)交叉驗(yàn)證得到當(dāng)前時(shí)刻最終的統(tǒng)計(jì)值，這樣的統(tǒng)計(jì)值p(xT)在原假設(shè)下是服從[0，1]上的均勻分布的.

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

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

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

(3)

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

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

(4)

其中pmin(xq)=minj=1，…，qip(fi，j(xq))代表了同類(lèi)型實(shí)體所有屬性的最小值.實(shí)體x的統(tǒng)計(jì)值p(x)表示同類(lèi)型實(shí)體屬性的最小值pmin(xq)小于等于當(dāng)前實(shí)體屬性的最小值pmin(x)的概率.同樣地，以這種方式計(jì)算的統(tǒng)計(jì)值也服從[0，1]上的均勻分布.最終得到了HAN中每個(gè)實(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)算法.接下來(lái)，本節(jié)首先詳細(xì)闡述如何測(cè)量子圖的統(tǒng)計(jì)顯著性.

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

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

(5)

其中S表示一個(gè)連通子圖，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)的個(gè)數(shù)，Vα(S)=∑v∈V(S)I(p(v)≤α)是S中統(tǒng)計(jì)值小于等于置信水平α(α>0)的頂點(diǎn)的個(gè)數(shù).φ(α，Vα(S)，V(S))指的是非參數(shù)掃描統(tǒng)計(jì)方法，即把在水平α處有顯著意義的頂點(diǎn)的個(gè)數(shù)Vα(S)與它的期望E[Vα(S)]作比較，又因?yàn)樵谠僭O(shè)沒(méi)有特殊情況發(fā)生時(shí)，統(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ì)值小于α的觀察個(gè)數(shù)占總個(gè)數(shù)比例與其期望值的差異.KL被定義為:

(7)

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

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

具體地，首先由第4節(jié)得到一個(gè)統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)Gw={C，V，E，p}，其每個(gè)頂點(diǎn)的權(quán)重p表示它的統(tǒng)計(jì)值，統(tǒng)計(jì)值越小越顯著.然后在統(tǒng)計(jì)權(quán)重網(wǎng)絡(luò)中通過(guò)非參數(shù)掃描統(tǒng)計(jì)識(shí)別到統(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]，所以本文的問(wèn)題也是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í)體類(lèi)型中的種子個(gè)數(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中.具體地，首先通過(guò)(k，Ψ)-核分解[6]計(jì)算Gw中每個(gè)頂點(diǎn)v的團(tuán)核數(shù)coreGw(v，Ψ)，并根據(jù)團(tuán)核數(shù)按非增順序排列頂點(diǎn)(行1-2)；再計(jì)算每條邊的Steiner連通度[21](行3).然后從剩余子圖RD中的每種實(shí)體類(lèi)型中選擇一個(gè)種子頂點(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ò)展時(shí)，迭代就終止了(行14-16).通過(guò)這樣的算法，最終得到的子圖保證具有最大顯著分?jǐn)?shù)A(S)和團(tuán)核數(shù)coreGw(v，Ψ).

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

算法1.ASSDSD算法

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

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

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

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

1.計(jì)算每個(gè)頂點(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中類(lèi)型為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)；//詳見(jiàn)算法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)；//詳見(jiàn)算法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ù)集對(duì)所提出的算法進(jìn)行有效性和高效性的評(píng)估.本實(shí)驗(yàn)所用的軟硬件環(huán)境如下:Windows 7旗艦版操作系統(tǒng)，Intel(R)Core(TM)i5-3337U的CPU，主頻1.8GHz，8G內(nèi)存，1T硬盤(pán)；開(kāi)發(fā)平臺(tái)為JetBrains PyCharm 2019，開(kāi)發(fā)語(yǔ)言為Python 3.

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

為了有效地構(gòu)建HAN模型及評(píng)估所提出的算法，本文選擇微博上的謠言事件進(jìn)行評(píng)估.因?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)評(píng)估指標(biāo)

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

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

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

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

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

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

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

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

6.4.1 4個(gè)算法的有效性和高效性分析

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

圖3 4個(gè)算法有效性和高效性對(duì)比

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

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

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

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

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

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

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

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

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

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

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

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

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

7 總結(jié)與展望

密集子圖發(fā)現(xiàn)已經(jīng)被廣泛研究.針對(duì)現(xiàn)有的簡(jiǎn)單圖模型和不同圖模型下發(fā)現(xiàn)的密集子圖不夠緊湊，缺乏顯著有效性的問(wè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)證了本文提出模型和算法的有效性和高效性.對(duì)于未來(lái)的密集子圖發(fā)現(xiàn)問(wèn)題研究，由于圖模型的不斷發(fā)展，還需設(shè)計(jì)更通用的方法滿足不斷發(fā)展的需求.