異構信息網絡概率模型研究及社區發現算法

殷浩瀟，李川

（四川大學計算機學院，成都　610065）

異構信息網絡概率模型研究及社區發現算法

殷浩瀟，李川

（四川大學計算機學院，成都610065）

國家自然科學基金（No.61103043）；國家“十二五”科技支撐計劃項目（No.2012BAG04B02）

0　引言

信息網絡將現實中復雜系統的實體抽象為網絡中的節點，并把實體之間的聯系抽象為網絡圖中的邊，用以刻畫網絡系統中有價值的性質和潛在的規律。進一步地，若信息網絡中包含了多種類型的節點和不同類型的邊，則稱為異構信息網絡，它能夠蘊含更加豐富的信息，更加逼近現實世界系統。挖掘其中的社區結構，有助于進行社會網絡分析、研究群體行為和社區效應，具有重要的理論意義與應用價值。例如，在基于興趣劃分的社區中，根據目標產品的特點，針對可能感興趣的社區網絡中的客戶進行定向廣告投放，推薦一系列相關的產品，從而提高點擊轉化率，提高交易成功率[1]；對科研合作網絡進行社區發現，可以發現合作關系緊密的學者及其研究興趣的變化趨勢等。

常見的社區發現算法或社會網絡聚類算法多是基于同構網絡[2]或特定類型的網絡[3-6]，并且多是通過分析拓撲結構來進行[2]。然而，通過網絡拓撲結構很難全面地發現網絡中潛在的社區結構，其原因有：（1）局限性，通過拓撲結構的方法多是基于同構網絡，而現實中多是復雜的異構網絡，難以實用；（2）不能充分利用異構網絡中多種類型節點和邊所蘊含的豐富信息。

針對以上問題，本文提出了基于異構信息網絡信息維統計量的社區發現方法（Dir-Com），首先通過引入模塊度最大化曲線的層次化狄利克雷過程自適應地學習社區數目,然后通過對異構信息網絡進行信息維上卷，用上卷后信息維的概率分布來表征某個社區，再通過計算后驗概率進行社區發現。

1　異構信息網絡信息維上卷

一個異構信息網絡G是包含了多種類型的節點和多種類型的邊的網絡。不同于傳統的社區發現方法只局限于同構網絡，本文針對異構信息網絡進行社區劃分，結果是生成一個異構的子圖。本文中將某個對象在某個社區中的分布頻數定義為與該對象信息維度在該聚類中的分布頻數。例如若某個作者在數據挖掘領域發表了4篇論文，則該作者在數據挖掘領域中的分布頻數就是4。對于如何計算某個對象的分布頻數，本文采用信息維上卷的方法。

定義1（信息維）設待分析圖結構為G（V，E）=G（V，θ（ID））。其中，V是圖中點的集合，E表示邊的集合，函數θ為圖G的邊信息決定函數。設變量ID={I1，I2，…，Im}是目標節點待考察的維度集合。這m個信息屬性構成的維度集合只能決定圖的邊集，不能改變圖的拓撲結構，稱ID為信息維。

信息維上卷則是將相同類型的節點與目標對象連接的邊權值進行累加。上卷過后就得到某個節點Ai在各個社區C={C1，C2…}中的分布頻數的向量。

根據貝葉斯統計理論，假設節點在不同社區的頻數概率分布服從一個先驗分布，即待估的參數，每得到一次新的觀測結果，則會更新分布參數，從而進行修正來擬合潛在的分布。本文采用狄利克雷分布來表示信息維的分布。

2　概率模型

狄利克雷分布是一組連續多變量概率分布，是多變量普遍化的Beta分布，其概率分布如下：

狄利克雷分布常作為貝葉斯非參數估計中多項分布的先驗概率[10]。

多元變量的情況，考慮到對于多項分布的似然函數為：

則根據貝葉斯參數估計理論，選擇狄利克雷分布作為多項分布共軛先驗分布。那么估計參數μ時，我們用p（μ）表示概率分布函數，用p（μ|D）表示觀測值D的似然函數。根據后驗=似然*先驗，有：

從這個形式可以看出，后驗也是狄利克雷分布。把這個后驗歸一化后得到:

3　異構網絡中的社區發現

假設在度量空間上的分布G0和一個參數α，如果對于度量空間的任意一個可數劃分（有限或無限），都有下列式子成立：

我們說，G滿足參數為G0和α的狄利克雷過程，即：G～DP（α，G0）。

進一步地，層次狄利克雷過程定義如下：

基礎分布G0的離散性保證了多個隨機測度之間共享原子[15]，從而很好地適應了社區發現中的社區重疊和覆蓋的問題。

如何根據數據分布來自適應地確定社區的數目K是社區發現或聚類的關鍵問題。常用的確定K的方法有：（1）根據經驗人工設定[1]，該方法不適用于規模大或動態網絡；（2）交叉驗證法，通過設置不同的K值訓練后驗證比較求得最佳值，該方法時間復雜度較高。

Blei等人[14]提出過一個方法，采用設置不同的K數值，畫出K-perplexity曲線，然后找到曲線中的縱軸最高點便是K數量的最佳值。受到該方法啟發，本文采用層次狄利克雷過程模型進行多次迭代后統計出現次數最多的多個K值，再畫出K-log（modularity）曲線，然后通過求導求得極值點作為最佳的K值。

其中采用狄利克雷過程計算K值的算法如下：算法1自適應聚類數目確定算法

輸入：信息維進行上卷后的異構信息網絡G（V，θ（ID）），閾值γ

輸出：社區數目K

針對異構信息網絡中的社區發現問題本文提出了Dir-Com算法，該模型基于狄利克雷分布，構建模型的過程就是進行估計參數的過程。若假設某個目標節點的每個屬性維度j都有一個概率pjk在社區Ck中生成，則該概率分布就是一個多項分布，根據貝葉斯理論，選取狄利克雷分布作為屬性維度在不同社區的先驗概率分布，即多項分布的共軛先驗分布。那么，節點i屬于社區k的概率為：

根據以上公式計算節點i屬于某個社區的最大后驗概率，然后將其歸入某一社區，同時根據社區中信息維的分布情況，更新分布參數。

4　算法描述

基于狄利克雷過程的異構信息網絡社區發現算法如下：

步驟 1：采用層次狄利克雷過程，設置迭代次數> 1500，取1000次之后的結果，得到出現次數最多的多個K值，計算出K-log（modularity）曲線，然后找到曲線中的縱軸最高點便是K數量的最佳值。

步驟2：根據上一步計算得出的最佳社區數目K，對信息網絡中的異構節點集合A做可數劃分（A1，A2，…，Ak），對于所有劃分Ai，根據狄利克雷分布，通過訓練數據迭代計算其分布參數。

步驟3：對于測試數據，根據最大后驗概率來確定其屬于哪個劃分（社區），并返回步驟2更新分布參數。

5　實驗及結果分析

空手道俱樂部網絡數據是用于社區挖掘算法的常用數據集之一，這里選用同構信息網絡目的在于驗證本文算法對于同構網絡同樣具有很好的社區發現效果。百度貼吧數據集則包含了百度微信貼吧用戶的屬性及興趣標簽數據。數據集的具體信息如表1。

表1　數據集信息

對比算法：基于Jaccard距離的Kmeans算法。對比標準：模塊度（Modularity），其定義為[17]：

模塊度可以用來衡量社團發現結果的好壞，在給定網絡的情況下，模塊度越大，說明社團發現的結果越合理。

如圖1（a）所示，可以觀測到在百度數據中，約2000次迭代之后K的值在一個穩定的區間里浮動。這里選擇2000次迭代之后出現次數多的5個的K值作為候選集，畫出K-log（modularity）曲線如圖1（b）所示，求出曲線極值點作為社區的數目K。

圖1　百度貼吧數據實驗結果

如圖2 所示，對比基于Jaccard相似性的K-means算法，本文算法得到的結果具有更好的模塊度和穩定性，而K-means算法的結果盡管很少幾個結果模塊度較高，但其他結果的模塊度非常不理想，甚至有很多負值。分析其原因，多是由于K-means算法選擇需要初始隨機種子點，不同的隨機種子點會得到完全不同的結果，從而導致聚類結果不穩定。本文算法由于采用層次狄利克雷過程，通過多次迭代構建目標節點信息維與社區之間的概率分布模型，并根據貝葉斯參數估計理論進行參數學習，最大程度地擬合潛在的真實社區分布情況，從而獲得更好的社區發現效果。

圖2　社區發現效果對比

6　結語

本文提出了基于異構信息網絡信息維統計量的社區發現算法（Dir-Com），該算法對異構信息網絡進行信息維上卷后，學習信息維的狄利克雷分布參數來表征某個社區，再利用最大后驗概率來計算社區發現，在自適應地確定社區數目這個問題上，本文采用了引入K-log（modularity）曲線的狄利克雷過程，并通過實驗驗證了算法的有效性和穩定性。

[1]唐磊.社會計算：社區發現和社會媒體挖掘[M]．北京：機械工業出版社，2012.

[2]張永輝，李川，唐常杰，等.基于結構分析的信息網絡社區趨勢預測[J].計算機科學與探索，2015（4）:403-409.

[3]C Li，WK Cheung，etc.The Author-Topic-Community Model for Author Interest Profiling and Community Discovery[J].Knowledge& Information Systems，2014，44:1-25.

[4]M Sachan，D Contractor，etc.Probabilistic Model for Discovering Topic Based Communities in Social Networks[C].ACM International Conference on Information&Knowledge Management，2011:2349-2352.

[5]Y Sun，Y Yu，etc.Ranking-Based Clustering of Heterogeneous Information Networks with Star Network Schema[C].In KDD'04，2009: 797-806.

[6]D Zhou，E Manavoglu，etc.Probabilistic Models for Discovering E-communities[C].International Conference on World Wide Web，2006:173-182.

[7]劉軍.社會網絡分析導論[M].北京：社會科學文獻出版社，2004.

[8]李航.統計學習方法[M].北京：清華大學出版社，2012.

[9]C.Bishop.Pattern Recognition and Machine Learning[M].Springer，2007.

[10]Dirichlet Distribution.http://en.wikipedia.org/wiki/dirichletdistribution.

[11]D.Blei，A.Ng，etc.Latent Dirichlet Allocation[J].JMLR，2003:993-1022.

[12]D Koller，N Friedman.Probabilistic Graphical Models:Principles and Techniques[M].MIT Press，2009，42（2）:161-168.

[13]G Heinrich.Parameter Estimation for Text Analysis[J].Technical Report，2004.

[14]Li X，Bilmes J.A Bayesian Divergence Prior for Classifier Adaptation[J].J Mach Learn Res，2007，2:275-282.

[15]梅素玉，王飛，周水庚.狄利克雷過程混合模型、擴展模型及應用[J].科學通報，2012，57（34）:3243-3257.

[16]Teh Y，Jordan M，etc.Hierarchical Dirichlet Processes[J].J Am Stat Assoc，2005，101:1566-1582.

[17]Newman M E J，Girvan M.Finding and Evaluating Community Structure in Networks[J].Physical Review E，2004，69（2）:026113.

Heterogeneous Information Network;Community Discovery;Dirichlet Distribution

Research on Probabilistic Model of Heterogeneous Information Network and Community Discovery Algorithm

YIN Hao-xiao，LI Chuan
（College of Computer Science，Sichuan University，Chengdu 610065）

殷浩瀟（1989-），男，四川瀘州人，碩士研究生，研究方向為數據挖掘、信息網絡

2015-12-22

2016-01-30

傳統的社區發現方法多是基于同構網絡和拓撲結構，為此，提出基于異構信息網絡信息維統計量的社區發現算法，該算法通過對異構信息網絡進行信息維上卷后構建概率模型，采用引入模塊度最大化曲線的層次化狄利克雷過程自適應地確定社區數目，然后通過狄利克雷分布來表征某個社區，再通過計算最大后驗概率來進行社區發現。實驗表明，所提出算法相比基于拓撲結構的算法具有更好的社區發現效果和穩定性。

異構信息網絡；社區發現；狄利克雷分布

李川（1977-），男，河南鄭州人，博士，副教授，碩士生導師，研究方向為數據庫、數據挖掘

As traditional community discovery methods are based on the homogeneous network and topology structure,presents a community discovery algorithm based on information dimension statistics of heterogeneous information network.This algorithm rolls up information dimension to build probabilistic model,uses hierarchical Dirichlet process with modularity maximization curve to adaptively determine the number of communities,characterizes communities with Dirichlet distribution and discovers communities by calculating the maximum posterior probability.Experiments show that compared with the algorithm based on topological structure,the proposed algorithm has better community discovery effect and stability.