殷浩瀟，李川

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

異構(gòu)信息網(wǎng)絡概率模型研究及社區(qū)發(fā)現(xiàn)算法

殷浩瀟，李川

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

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

0　引言

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

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

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

1　異構(gòu)信息網(wǎng)絡信息維上卷

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

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

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

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

2　概率模型

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

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

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

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

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

3　異構(gòu)網(wǎng)絡中的社區(qū)發(fā)現(xiàn)

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

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

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

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

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

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

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

輸入：信息維進行上卷后的異構(gòu)信息網(wǎng)絡G（V，θ（ID）），閾值γ

輸出：社區(qū)數(shù)目K

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

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

4　算法描述

基于狄利克雷過程的異構(gòu)信息網(wǎng)絡社區(qū)發(fā)現(xiàn)算法如下：

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

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

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

5　實驗及結(jié)果分析

空手道俱樂部網(wǎng)絡數(shù)據(jù)是用于社區(qū)挖掘算法的常用數(shù)據(jù)集之一，這里選用同構(gòu)信息網(wǎng)絡目的在于驗證本文算法對于同構(gòu)網(wǎng)絡同樣具有很好的社區(qū)發(fā)現(xiàn)效果。百度貼吧數(shù)據(jù)集則包含了百度微信貼吧用戶的屬性及興趣標簽數(shù)據(jù)。數(shù)據(jù)集的具體信息如表1。

表1　數(shù)據(jù)集信息

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

模塊度可以用來衡量社團發(fā)現(xiàn)結(jié)果的好壞，在給定網(wǎng)絡的情況下，模塊度越大，說明社團發(fā)現(xiàn)的結(jié)果越合理。

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

圖1　百度貼吧數(shù)據(jù)實驗結(jié)果

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

圖2　社區(qū)發(fā)現(xiàn)效果對比

6　結(jié)語

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

[1]唐磊.社會計算：社區(qū)發(fā)現(xiàn)和社會媒體挖掘[M]．北京：機械工業(yè)出版社，2012.

[2]張永輝，李川，唐常杰，等.基于結(jié)構(gòu)分析的信息網(wǎng)絡社區(qū)趨勢預測[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]劉軍.社會網(wǎng)絡分析導論[M].北京：社會科學文獻出版社，2004.

[8]李航.統(tǒng)計學習方法[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-），男，四川瀘州人，碩士研究生，研究方向為數(shù)據(jù)挖掘、信息網(wǎng)絡

2015-12-22

2016-01-30

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

異構(gòu)信息網(wǎng)絡；社區(qū)發(fā)現(xiàn)；狄利克雷分布

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

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.