社交網絡中基于影響力的緊密子圖發現算法

簡興明，游進國，梁月明，賈連印

(昆明理工大學 信息工程與自動化學院，昆明 650500)

1 引 言

對于社會團體中的成員，社交網絡影響力主要研究他們之間的意見或行動相互作用或相互影響的現象.社交網絡影響力分析對于理解信息、觀念和創新跨社交網絡傳播的方式有很大的用處.隨著越來越多的人參與社交網絡，社交網絡以多種形式呈現出來，比如：聊天工具上用戶之間的好友關系、DBLP上作者之間的合著關系、電影中演員之間的合作關系、科學家之間的合作關系等.分析與挖掘社交網絡中的社交網絡影響力可以為社交網絡中的人們如何相互作用和相互影響，以及為什么不同主體的想法和意見在社交網絡中的傳播方式不同提供了新的見解.

社交網絡研究的發展和社交網絡規模的進一步擴大，對數據挖掘領域提出了更多的要求.如預測某一作家下次的合著對象，朋友圈的好友推薦等.在社交網絡中，人與人之間的關系就是一個龐大的交互網絡，在社交網絡中尋找交流頻繁的群體可以幫助廣告商更有效地投放發布信息；在科研合作關系圖中，緊密子圖可以發現諸如研究領域中具有緊密合作關系的團隊，這類團隊可能具有更強的綜合競爭力；在商品交易網絡中，尋找具有緊密關系的客戶群，可以更快的打入市場，具有更高的商業價值.

在社交網絡的大多數應用中，邊一般用來描述實體之間的關系.由于社交網絡規模龐大且關系稀疏，頂點及邊的存在性并不明確，所以緊密子圖自然成為研究這些網絡的重要模型.然而到目前為止，緊密子圖的相關的研究工作并不多，而且大多是關于無向圖的.但是在真實社交網絡中，人與人之間的關系通常是相互的.例如對社交網絡影響力的分析，如圖1在成員b與成員d的合作中，b可以影響d，而同時d也對b也產生了影響，而且b與d的合作也對整個社交網站中其它的成員頂點產生了影響.本文同樣是在社交網絡中尋找較密集的子圖，但本文是基于社交網絡環境下的數據規模較大和網絡拓撲結構動態變化的特征，結合社會網絡中頂點的相似度來分配權重，設計了一種基于影響力動態演化傳播的緊密子圖發現算法，再自適應地設定緊密閾值，發現緊密子圖，這在實際中具有更好的實用性.

圖1 加權圖Fig.1 Weighted graph

2 相關工作

2.1 社交網絡影響力分析和緊密子圖發現

近年來社交網絡影響力的分析越來越重視.[1]介紹了一種社交網絡中影響力最大化算法.[2]提出了一種級聯病毒式營銷的算法.[3]提出了以前K個最有影響力的節點為主的病毒營銷模式.[4]在特定的一顆小小的種子集合上，利用用戶的隱含的社交網絡產生一個朋友圈的集群.[5]提出了一種信息可以通過社交網絡拓撲結構傳播的模型.[6]結合自身的影響力和各種活動的影響力來解決異構社交網絡中聚類的問題.

然而到目前為止，緊密子圖的相關的研究工作才剛剛開始，而且主要是針對無向圖的.[7]提出了一種多目標跟蹤的緊密子圖發現算法.[8]提出了一種結合圖的結構特征和節點屬性的緊密子圖發現算法.對不確定圖的緊密查找算法主要包括計算不確定圖中的最可靠子圖[9]，對不確定圖進行TOP-K稠密子圖挖掘[10]，挖掘不確定圖中的頻繁模式[11]，極大頻繁模式[12]，從不確定圖中發現K緊密子圖[13].然而將緊密子圖應用到社交網絡的卻很少.[14]提出了一種社交網絡中連接緊密的子圖結構的社團發現算法.

本文同樣是在社交網絡中尋找緊密子圖，但本文是根據社交網絡拓撲中頂點間的相似度來分配權重，改進PageRank算法計算每一個頂點潛在的影響力，自適應地設定緊密閾值，再發現緊密子圖，這在實際中具有更好的實用性.據目前研究所知，這項工作是第一個通過動態的結合社交網絡圖中的個人影響力和成員頂點間的共同影響力，來解決影響力在社交網絡中的緊密子圖發現問題.

2.2 基本的PageRank算法及其改進和應用

(1)

那么第一步之后隨機瀏覽者的概率分布向量為M·Rank.反復使用轉移矩陣M左乘向量Rank，直到得到隨機瀏覽者的分布逼近一個極限概率分布Rank*.隨機瀏覽者的瀏覽過程實際上是一個典型的馬爾可夫過程.只有滿足圖是強連通圖和圖不存在終止點兩個條件時，隨機瀏覽者的概率分布才趨于收斂.

在實際過程中，隨機瀏覽者并不一定會按照網頁的鏈接結構前進.所以該算法以一個小的概率β允許隨機瀏覽者跳轉到鏈接外的其它頁面上，根據之前的迭代過程，修改轉移矩陣M，公式為

M′=βM+(1-β)D/n

(2)

其中D是n階的全1矩陣，M′為新的轉移矩陣.PageRank算法提出來以后，很多學者對它進行了改進.[15]將Google的網頁排名算法PageRank應用到在線社交網絡中.[16]間接修改了PageRank平均分配權重的方式，提出了一種有效防止主題漂移的領域相關自適應的算法.本文同樣是采用不平均分配權重的方法，以M′頂點間的有向相似性來分配權重，以為轉移矩陣，改進PageRank算法計算每一個頂點的潛在的社交網絡影響力.

3 模型

3.1 問題引入

本文將在線社交網絡及其中的關系抽象為圖，形式化描述如下：

定義1.(社交網絡圖)社交網絡圖是一個三元組SG(U,E,R)，U是圖中的節點集合，即社會網絡中用戶集合，E是邊的集合，R是權重，對于無向邊Euv，其中u,v∈U，且有權重Ruv=Rvu.

給定一個無向社交網絡圖SG(U,E,R).如圖1所示：頂點a-f表示社交網絡中6個不同的人，頂點之間的邊表示成員之間在社交網絡中有合作關系，頂點之間的邊上的權重代表成員頂點之間的合作的強度，權重值越大說明兩個人的關系越緊密.與成員頂點a合作的有成員頂點b和c，所以與成員頂點a的合作總強度為(Rab+Rac)=0.8而與成員頂點f合作的有成員頂點d.成員頂點f的合作總強度為(Rdf)=0.4.所以使用文獻[10]或文獻[13]中的方法進行緊密子圖發現，緊密子圖發現結果如圖2所示.

圖2 緊密子圖發現Fig.2 Result of close subgraph

對此，本文提出了新的加權圖的緊密子圖發現算法.本文對加權圖的緊密子圖發現算法的目標包括：(1)緊密子圖簡潔、顯著；(2) 緊密子圖包含的發現算法不僅要考慮邊上權值的大小，還應考慮頂點所在網絡的拓撲結構.

3.2 問題陳述

社交網絡圖表示為SG=(U，E，R)，其中U是代表的社交網絡的成員頂點集合，E表示了對成員協作網絡之間的協作關系的邊集，R代表兩個社交網絡頂點之間的權重，代表社交網絡中頂點之間的合作強度.

定義2(影響力圖)影響力圖是一個四元組IG=(U,E,T,W)，其中U在社交網絡圖SG中有相同的定義.每條邊Euv，連接成員頂點u,v∈U.Tuv代表邊Euv上SG中成員頂點u在多大程度上與成員頂點v相似.給定一個社交網絡圖SG，一個影響力圖IG的社交網絡影響力為基礎的緊密子圖發現算法的問題是對于成員頂點u∈U，遍歷其鄰接點v∈U，并計算頂點間的相似度Tuv，并生成社交網絡圖上以相似度為基礎的兩個頂點間的影響力大小.對于頂點u∈U,Wu表示成員頂點u所包含的影響力總量，則Wuv表示SG中成員頂點u與成員頂點v間的綜合影響力的大小，例如一次購買或出版活動.所期望的影響力圖結果應達到以下兩個屬性之間的良好平衡：(1)在每一個社交網絡中兩個成員頂點的影響力是相互的，例如A可以影響B，同時B也影響A；(2)在社交網絡的影響力圖中，影響力應該在它們之間的相似度和社交網絡拓撲結構間取得平衡.

4 基于影響力的緊密子圖發現

本節將介紹如何在共同影響力模型下計算頂點間的緊密度.首先，利用頂點間的權重來計算社會網絡圖中的成員頂點之間的相似度.其次，使用PageRank技術，以成員頂點之間的相似度為權重，在社交網絡圖中計算每個頂點的潛在的影響力，構成一個共同的影響力的模型.最后，基于共同影響力的模型，計算并生成社交網絡圖上以影響力為基礎的緊密子圖.

4.1 相似度的計算

對于給定的社交網絡圖SG(U,E,R)中，本文根據頂點間的合作關系和合作強度計算影響力圖IG=(U,E,T,W)中的相似度T.

目前，大多數的算法都是直接使用邊的權重作為社交網絡中成員頂點之間的相似度或者作為成員頂點之間的距離[9-13].邊的權重雖然可以直觀的衡量成員頂點之間的合作強度，但社交網絡中兩個成員頂點之間的相似度還應考慮到邊的權重所占的比例.文獻[6]提出了一種計算方法，該方法先計算每個成員頂點的總強度，然后通過邊的權重計算相鄰兩個成員頂點的相似度.該計算方法的優點在于在計算兩個成員頂點之間的相似度時綜合考慮了每一個成員頂點的工作強度及合作強度所占的比例，而且在兩個成員頂點總強度相差較大時，兩個成員頂點之間的相似度較小.計算相似度的算法如下：

對于u,v∈U，遍歷u所有的鄰接頂點l∈U和v所有的鄰接頂點k∈U，來計算鄰接頂點間的相似度.那么對于相似度Tuv，當∑l∈uRlu=0或∑k∈URkv=0時，有Tuu=1或Tvv=1，否則有

(3)

在影響力圖IG=(U,E,T,W)中，對于任意的u,v∈U，都有Tuv=Tvu.Tuv即為兩點之間的相似度.

4.2 影響力的傳播

一個在某一領域有很多優質作品的作家可以有很多的合作者，他們之間彼此影響并影響著該領域中的大多數人.為了有效地測量在社交網絡圖中的頂點成員的緊密度，本文首先定義社交網絡中的影響力傳播方式.通過第2.2節中的公式(1)和4.1節中的公式(3)，通過計算兩點之間的相似度來改進轉移矩陣M.對于轉移矩陣Muv，有

(4)

然后本文使用2.2節中的公式(2)和本節中的公式(3)、(4)來計算新的轉移矩陣M′.

M′=βM+(1-β)D/n

(5)

對于社交網絡圖SG(U,E,R)和影響力圖IG=(U,E,T,W)，通過本節中的公式(3)、(4)和(5)得到的任意兩點u,v之間的相似度Tuv以及新的轉移矩陣M′.在此，以第1節中的圖1為例.

表1 圖1的鄰接矩陣WTable 1 Adjacent matrix W of Fig.1

根據本節中的公式(3)處理后的鄰接矩陣為表2所示：

表2 圖1的相似度矩陣TTable 2 Similar matrix T of Fig.1

根據上表和本節中的公式(4)、公式(5)，采用阻尼系數為0.85處理后的轉移矩陣M′為表3所示：

表3 圖1的轉移矩陣M′Table 3 Transfer matrix M′ of Fig.1

為了計算方便，本文初始化概率分布向量為一個所有分量均為1的n維向量Rank.反復使用轉移矩陣M′左乘向量Rank，直到得到概率分布向量的分布逼近一個極限概率分布Rank*.這時Rank*就代表社交網絡中頂點的潛在的影響力的分布的列向量，即影響力圖IG中的W的列向量.

4.3 以統一的影響力為基礎的緊密度測量

通過4.2節得到了成員頂點影響力分布的列向量Rank*，本節使用兩點之間影響力的大小來衡量兩點之間的緊密度.對于影響力圖IG=(U,E,T,W)，本文使用成員頂點的潛在的影響力乘以該成員頂點與其它頂點間的相似度，來計算兩點之間影響力的大小.Wuv定義如下，

(6)

目前的大多數算法都是將數據直接或者間接處理為頂點間的權重進行聚類或者緊密子圖發現的.而本文綜合了網絡間的拓撲結構，聯合頂點間的相似度，使用公式(6)計算成員頂點間的共同影響力，來發現緊密子圖.

如圖3，的數值為根據4.2中的轉移矩陣M′計算得出的頂點的潛在的影響力Wu；括號中的數值即為兩點之間影響力流動的數值Wuv，為了方便表示，本文去掉了頂點間影響力小于0.05的表示.當社交網絡中的影響力分布趨于一個動態平衡時，本文通過設定閾值，根據頂點間的影響力的大小來計算兩點之間的緊密度了.

圖3 影響力圖Fig.3 Influence graph圖4 緊密子圖Fig.4 Close subgraph

當本文設置閾值為0.3，由于Wac小于0.3所以本文稱，在社交網絡影響力閾值為0.3，其中閾值0.3下的緊密子圖如圖4所示.

5 算法

為了解決社交網絡中的緊密子圖發現的問題，本文提出了新的緊密子圖發現算法.首先，本文介紹一種新穎的頂點間的有向相似度.其次，本文通過頂點度量方面的有向相似度來分配權重，改進PangeRank算法計算每一個頂點潛在的影響力.最后，本文通過設置閾值，量化兩點之間的影響力得分發現社交網絡中的緊密子圖.分別描述如下：

5.1 緊密閾值的設置

本文將分別設置緊密度閾值β來運行生成基于影響力的緊密子圖.通過閾β值的設定可以更好的把握成員頂點之間的緊密程度，從而更好的發現緊密子圖.

5.2 影響力的傳播與計算與影響力圖的生成

根據相似度分配每一個頂點的影響力到其它的節點，通過K次迭代傳播，兩次迭代后Rank向量的歐氏距離小于一定值時，稱社交網絡的影響力趨于穩定.趨于穩定后的Rank向量即為社交網絡中成員頂點的潛在影響力.對于影響力圖的生成，有如下定義.

5.3 緊密子圖發現

對于5.2中的生成的影響力圖IG=(U,E,T,W)，設定一個閾值β，通過不斷調整β的值來發現基于社交網絡的緊密子圖.在影響力圖IG中，我們通過比較Wuv與β來進行緊密子圖的查找.如果兩個成員頂點的值大于β，在基于影響力的緊密子圖查找算法中，就保留社交網絡圖SG中這條邊；否則，剪掉這條邊.在此，我們稱為influence-based close subgraph algorithm.算法過程如下：

圖5 產生緊密子圖算法描述Fig.5 Description of close subgraph algorithm

5.4 算法時間復雜度分析

本算法包含三個步驟.(1)計算成員頂點間的相似度.(2)使用改進的PageRank算法計算每一個頂點潛在的影響力.(3)使用成員頂點的影響力和成員頂點間的相似度計算每兩個成員頂點間的共同影響力.其中，計算成員頂點間的相似度復雜度為O(|U||E|).使用成員頂點間的相似度計算成員頂點間的共同影響力的相似度為O(|E|).

本文基于影響力的緊密子圖發現算法是基于PageRank改進而來，反復使用轉移矩陣M′左乘向量Rank，直到得到概率分布向量的分布逼近一個極限概率分布Rank*.所以本算法的時間復雜度最壞為O(|U||E|).其中|U|為給定社交網絡的頂點數，|E|為給定社交網絡的邊數.

綜上，本算法的時間復雜度為O(|U||E|).

6 實驗結果及分析

6.1 實驗環境

本文的算法是采用Java實現的，實驗平臺是Java開發工具Eclipse.所有實驗都是在一臺PC機上運行的，PC機的配置如下：處理器Intel四核，2.4GHz，內存 8GB，Windows7操作系統.

6.2 實驗數據

第一組數據集來自小說維克多·雨果的悲慘世界的人物角色關系圖(co-appearances between characters)1，簡稱novel.頂點表示小說中出現的角色，邊表示兩個角色共同出場的次數.數據是以GML格式進行加載和使用的.圖中的頂點數是77個，邊數是254條.

第二組來自networks理論中作家的合著關系圖(co-authorships in networks)2，簡稱networks.圖中的頂點代表作家，邊代表作家之間存在的合著關系，邊的權重值表示作家之間的合作強度.數據是以GML格式進行加載和使用的.圖中的頂點數是1589個，邊數是2742條.

第三組來自arXiv中的科學家之間的合作關系圖(cooperation between scientists)3，簡稱arXiv.圖中的頂點代表科學家，邊代表科學家之間存在的合作關系，邊的權重值表示科學家之間的合作強度.數據是以GML格式進行加載和使用的.圖中的頂點數是12946個，邊數是23626條.

6.3 閾值的設置和初始化

本文將分別設置緊密度閾值β為0.1-0.7來運行生成基于影響力的緊密子圖.為了便于計算，本文初始化概率分布向量為一個所有分量均為1的n維向量Rank.

6.4 實驗結果及分析

本文將6.2中的實驗數據處理為實驗所用的數據.對于經典的PageRank算法，A，B頂點間有合作關系，則A有一條邊指向B，B也有一條邊指向A.對于基于影響力的改進PageRank算法，本文根據4.1節中的方法計算頂點間的相似度，以4.2節中的M′作為轉移矩陣.經典的PageRank算法、基于影響力的改進PageRank算法計算所得的影響力值對比如圖5所示，其中橫軸表示成員頂點的分布情況，縱軸則表示該頂點的影響力值.

從整體上看，在圖5(a)，圖5(b)和圖5(c)中的三組數據集中，當影響力在1附近時時，頂點數最多.影響力的分布具有明顯的層次結構，數量分布是“兩頭小，中間大”，且超過一定范圍的頂點數目很少.經對比可發現，三個數據集的影響力分布具有相似性.

圖6 數據集實驗結果對比Fig.6 Experiment result of datasets comparison

比較圖5(a)，圖5(b)和圖5(c)中的三組數據，不難發現，在經典的PageRank算法中，頂點的影響力的差異值要比基于影響力的改進PageRank算法頂點之間的差異更顯著.因為在基于影響力的緊密子圖發現算法中，較大的權值為合作的雙方所共享，所以頂點間的影響力差距并不顯著，從而有利于尋找圖中具有緊密關系的子圖.

目前大多數的緊密子圖發現算法，如文獻[7]-[11]都是基于特定場景下將數據處理頂點間邊的權重進行緊密子圖對比的.本文將數據處理為頂點間的相似度，以頂點間的相似度為邊的權重與基于影響力的緊密子圖發現算法進行了對比.在此，簡稱為similarity-based和influence-based算法.

本文將基于影響力的緊密子圖發現算法與文獻[10]中的社交網絡中的Top-k緊密子圖挖掘算法進行了對比.在閾值β下，本文分別使用緊密子圖中連通子圖個數對比、平均每個連通子圖所含的頂點個數對比、最大連通子圖所含頂點個數對比和緊密子圖中的稠密度對比，來衡量圖的緊密程度.對于稠密度，本文定義為ρ=|L|/|U|，其中|L|表示緊密子圖中頂點間的相似度總和，|U|表示緊密子圖頂點的個數.

由圖7(a)、圖8(a)和圖9(a)對比結果可知，隨著社交網絡中閾值β的增加，兩種算法的結果中關于連通子圖的數量都是先增加后減少的.因為當閾值還較小時，有較多的點對會大于閾值β.所以連通子圖的個數也相對較少.隨著閾值β的逐漸增加，大于閾值β的點對數量會相對分散，所以連通子圖的個數會暫時增加.隨著閾值β的進一步增大，連通子圖的個數又隨之而減少.不難發現，在基于影響力的緊密子圖發現算法中，連通子圖個數則趨于平穩的緩慢增長或緩慢下降的.由圖7(b)、圖8(b)和圖9(b)對比結果可知：當閾值β緩慢增加時，平均每一個連通子圖中所含的頂點個數.由圖可知，基于影響力的緊密子圖發現算法擁有更好的效果.隨著閾值β的進一步增大，兩算法的結果逐漸接近.

1http://www-personal.umich.edu/～mejn/netdata

2https://snap.stanford.edu/index.html

3http://www.socialysis.org/data/dataset/dataset

圖7 networks數據集實驗結果對比Fig.7 Experiment results of the networks dataset

圖8 novel數據集實驗結果對比Fig.8 Experiment result of the novel dataset

當閾值為0.1時，arXiv數據集的節點個數較多，數據差異較大.為了方便表示，圖9(c)從0.2開始取值.在圖7(c)中，當閾值β為0.1時，基于影響力的緊密子圖發現算法中，最大的連通子圖包含316個成員頂點；top-k緊密子圖挖掘算法中，最大的連通子圖包含147個成員頂點.隨著閾值的進一步增加，兩算法的結果逐漸接近.

圖9 arXiv數據集實驗結果對比Fig.9 Experiment result of the arXiv dataset

在圖7(d)、圖8(d)和圖9(d)中，當閾值β較小時，較多的邊被包含在緊密子圖中，所以稠密度較大.但是基于影響力的緊密子圖發現算法頂點間的差距并不明顯，所以稠密度更高.隨著閾值β的進一步增加，兩算法的結果逐漸接近.

對比圖7、圖8和圖9中的networks數據集、novel數據集和arXiv數據集發現：三種數據集實驗結果的曲線趨勢大致上是一致的；但相對來說，novel和networks數據集的頂點較少，頂點間的聯系相對密集，結果也相對平緩；arXiv數據集中的頂點多，數據也相對稀疏，所以結果差異相對較大.

7 總結與展望

成員頂點間邊權重的計量方式的有效性是衡量聚類或者緊密子圖發現算法有效性的重要標準.本文提出了一種新的有效的緊密子圖發現算法，該算法先將數據集處理為成員頂點間的相似度，然后結合改進的PageRank算法計算成員頂點的共同影響力.使用novel數據集、networks數據集和arXiv數據集，將數據處理為頂點間的相似度，以頂點間的相似度為邊的權重算法與基于影響力的緊密子圖發現算法進行了對比.對比連通子圖個數、平均每個連通子圖所含頂點個數、最大連通子圖所含頂點個數、緊密子圖稠密度，說明本文的算法能提高緊密子圖發現的效果和效率.

本文使用的加權圖都是同構圖，即：圖中頂點的屬性是一致的，如科學家合作網絡中的數據，頂點代表的是科學家.現實生活中還存在異構圖，即頂點的屬性是不一致的，如：消費者購買商品，消費者和商品在圖中用不同的頂點表示，兩者之間存在的邊表示購買關系.所以，下一步將研究帶權重的異構社交網絡中緊密子圖的發現算法.

：

[1] Wang Y，Huang W J，Zong L，et al.Influence maximization with limit cost in social network[J].Science China Information Sciences，2013，56(7)：1-14.

[2] Domingos P，Richardson M.Mining the network value of customers[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2001：57-66.

[3] Ma H，Yang H，Lyu M R，et al.Mining social networks using heat diffusion processes for marketing candidates selection[C].ACM Conference on Information and Knowledge Management，ACM，2008：233-242.

[4] Roth M，Ben-David A，Deutscher D，et al.Suggesting friends using the implicit social graph[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Washington，Dc，Usa，July.DBLP，2010：233-242.

[5] Myers S A，Zhu C，Leskovec J.Information diffusion and external influence in networks[C].Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2012：33-41.

[6] Zhou Y，Liu L.Social influence based clustering of heterogeneous information networks[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，ACM，2013：338-346.

[7] Bozorgtabar B，Goecke R.Efficient multi-target tracking via discovering dense subgraphs[M].Elsevier Science Inc，2016,144:205-216.

[8] Sun Huan-liang，Lu Zhi，Liu Jun-ling，et al.Top- k attribute difference q-clique queries in graph data[J].Chinese Journal of Computers，2012，35(11)：2265-2274.

[9] Hintsanen P.The most reliable subgraph problem[M].Knowledge Discovery in Databases：PKDD 2007.Springer Berlin Heidelberg，2007：471-478.

[10] Zhu Rong，Zou Zhao-nian，Li Jian-zhong.Mining top-k dense subgraphs from uncertain graphs[J].Chinese Journal of Computers ，2016，39(8)：1570-1582.

[11] Zou Z，Li J，Gao H，et al.Mining frequent subgraph patterns from uncertain graph data[J].Journal of Software，2010，22(9)：1203-1218.

[12] Han M，Zhang W，Li J Z.RAKING：An efficient K-maximal frequent pattern mining algorithm on uncertain graph database[J].Chinese Journal of Computers，2010(8)：1387-1395.

[13] Han Meng，Li Jian-zhong，Zou Zhao-nian.Finding K close subgraphs in an uncertain graph[J].Journal of Frontiers of Computer Science & Technology，2011，5(9)：791-803.

[14] Yu Le.Research community detecting and evolution analysis in social network[D].Beijing：Beijing University of Posts and Telecommunications，2014.

[15] Shao Jing-jing，Feng Bo，Li Bo.A new algorithm of PageRank ranking technology[J].Journal of Huazhong Normal University(Natural Sciences)，2008，42(4)：504-508.

[16] Pan Hao，Tan Long-yuan.Adaptive PageRank algorithm search strategy for specific topics[J].Journal of Computer Applications，2008，28(9)：2192-2194.

附中文參考文獻：

[8] 孫煥良，盧 智，劉俊嶺，等.圖數據中Top-k屬性差異q-clique查詢[J].計算機學報，2012，35(11)：2265-2274.

[10] 朱 鎔，鄒兆年，李建中.不確定圖上的 Top-k 稠密子圖挖掘算法[J].計算機學報，2016，39(8)：1570-1582.

[13] 韓 蒙，李建中，鄒兆年.從不確定圖中發現K緊密子圖[J].計算機科學與探索，2011，5(9)：791-803.

[14] 于 樂.社會網絡中社團發現及網絡演化分析[D].北京：北京郵電大學，2014.

[15] 邵晶晶，馮 波，李 波.PageRank排名技術的新算法[J].華中師范大學學報(自科版)，2008，42(4)：504-508.

[16] 潘 昊，譚龍遠.領域相關自適應的PageRank算法搜索策略[J].計算機應用，2008，28(9)：2192-2194.