異質信息網絡中基于元路徑的社團發現算法研究

鄭玉艷，王明省，石 川，王 銳

(1. 北京郵電大學 計算機學院，北京 100876；2. 廣州市城市規劃勘測設計院 地理信息中心，廣東 廣州 510060)

0 引言

互聯網技術的迅猛發展使得社會網絡分析得到了廣泛的研究。當前的社會網絡分析主要基于同質信息網絡，即關系網絡中節點或邊具有相同的類型。例如，圖1(a)的作者合作網，節點類型都是作者，邊的類型都是合作關系。然而，隨著在線社會媒體、信息物理系統的大量出現，對象相互關聯形成的復雜網絡很難用同質信息網絡建模，而是需要建模成異質信息網絡。這種網絡包含不同類型的對象，對象之間的關系表示了不同的交互語義。例如，圖1(b)表示了科技文獻數據中包含的對象和它們之間的關聯。通過抽象對象和它們之間的關系可以構建如圖1(c)所示的網絡模式。該數據的對象類型包括作者、論文、會議和術語，這些對象之間存在不同語義的關系： 作者和論文之間的撰寫關系，論文和會議之間的發表關系，論文和術語之間的包含關系。元路徑可以捕捉這些豐富的語義信息[1-2]，從而產生更有意義的知識發現。自從數據挖掘領域專家Jiawei Han和Philip S.Yu等于2009年開始倡導異質信息網絡分析的研究[3]，指出異質信息網絡無處不在，對這類網絡進行分析是數據挖掘領域重要的研究方向[4]，異質信息網絡分析就吸引了越來越多的研究者的關注，成為逐漸興起的研究熱點。在數據挖掘、數據庫、信息檢索等相關領域的一流的國際會議上出現了越來越多的關于異質信息網絡分析的文章，例如文獻[1,5-6]。目前，異質信息網絡中的很多數據挖掘任務(如相似性度量、聚類、分類等)都已被研究。

圖1 由科技文獻數據構建的同質和異質信息網絡。

社團發現是根據已經觀察到的網絡的結構信息及對象的屬性信息來預測網絡的社團結構，它是社會網絡分析的一個重要任務[7]。通過社團發現可以將一個大的網絡劃分為多個小的節點的集合，使得同一個集合中的節點之間的關聯相對緊密，而不同集合中的節點之間的關聯相對稀疏。我們稱這些小的節點的集合為社團。社團發現可以幫助我們更好地理解網絡的拓撲結構及社團的進化過程。社團發現已有很多應用，例如，在文獻網絡中，可以探測作者的社團結構，進而預測作者之間未來的合作關系；在推薦系統中，可以探測出用戶的社團結構，將屬于同一個社團的其他用戶購買過的商品推薦給當前用戶。

目前，同質信息網絡中的社團發現已經被深入研究，其中最常用的社團發現算法有基于標簽傳遞的算法[8-11]和基于模塊度優化的算法[12]。基于標簽傳遞的算法簡單、易于實現，并且擁有線性的時間復雜度，但是由于節點更新順序的隨機性等原因，使得該算法的結果隨機性較大；而基于模塊度優化的算法通過不斷優化模塊度，能夠保證得到較穩定的社團探測結果。這些方法都是針對同質信息網絡進行的，針對異質信息網絡進行的社團發現研究相對較少，而實際的網絡化數據往往包含多種類型的對象和關系，建模成異質信息網絡可以更全面地包含這些豐富的信息，進行更準確的社團發現。

本文主要研究異質信息網絡中的社團發現問題，關鍵在于如何充分利用異質信息網絡包含的豐富的結構信息和語義信息來進行更準確的社團發現。例如，在文獻網絡中，要充分利用網絡中包含的論文作者關系、論文會議關系等來提高社團發現的準確率。因此，本文提出了在異質信息網絡中進行社團發現的方法HCD，通過使用異質信息網絡的獨特屬性——元路徑，來捕捉異質信息網絡中豐富的語義信息。HCD主要包括基于單條元路徑的社團發現算法HCD_sgl和融合多條元路徑的社團發現算法HCD_all兩部分。首先，將異質信息網絡基于給定的元路徑映射為同質信息網絡。然后，根據設定的規則找出在網絡中有較大影響力的種子節點，構建種子節點網絡，并選擇有較高準確性和穩定性的社團發現算法確定種子節點的社團標簽。之后再根據網絡結構及節點間的相似性，確定非種子節點的社團標簽。最后在各條元路徑對應的同質信息網絡中執行改進后的標簽傳遞算法，得到基于每條元路徑的社團發現結果，將基于各條元路徑的社團發現結果進行整合，得到異質信息網絡中的社團發現結果，并在真實數據集和人工數據集上驗證了所提方法的有效性。

本文其他章節安排如下： 第一節介紹了與本文相關的工作；第二節詳細地闡述了本文提出的基于元路徑的社團發現方法HCD；第三節對實驗及結果進行了詳細描述；第四節總結全文并對下一步工作進行了展望。

1 相關工作

社團發現作為社會網絡分析的一個重要任務，得到了廣泛的研究。目前，已經有大量的社團發現算法被提出。這些算法主要分為如下四種類型： 基于圖劃分的社團發現算法，基于模塊度優化的社團發現算法，基于遺傳算法的社團發現算法和基于標簽傳遞的社團發現算法。

(1) 基于圖劃分的社團發現算法是將圖劃分為多個組成部分，使得各個組成部分內部之間的連接盡可能的多，各個部分之間的連接盡可能的少。例如，Kernighan-Lin算法[13]通過將圖劃分成多個子集來最小化圖劃分過程中邊權值的損失，其中每個子集的大小等于預先設置好的一個值。Newman[14]通過將隨機分塊模型映射到最小割圖劃分問題來進行社團發現。

(2) 基于模塊度優化的社團發現算法主要是將Newman等[12]提出的用于衡量社團發現質量的評價指標模塊度作為優化目標，采取不同的優化方法使模塊度不斷增大，從而得到最終的社團發現結果。它主要有聚合和分裂兩種類型，Newman提出的快速社團聚類算法[15]是經典的聚合算法，該算法通過沿著模塊度增長最多的方向合并社團來優化模塊度。Newman和Girvan提出的GN算法[16]屬于分裂算法。該算法不斷地移除邊介數最大的邊，直到每個節點都成為獨立的社團。在移除邊的過程中，對應模塊度最大時的社團結構即為最終的社團發現結果。Blondel等[17]提出了一種新的算法BGLL，它通過兩個階段不斷迭代進而獲得最終的社團發現結果。第一階段不斷將節點移入能使模塊度增長最大的那個社團來獲得社團探測的結果，第二階段將探測出的社團當作一個新的節點，重新構造網絡。

(3) 遺傳算法是模擬生物進化規律而演化來的一類啟發式搜索算法。遺傳算法在開始時有一組候選解，通過計算各個候選解的適應度函數，淘汰掉適應度低的那些候選解，并通過交叉變異操作生成新的候選解，直到找到問題的近似最優解。近年來，遺傳算法被應用到社團發現和社團分析的研究當中。Pizzuti提出了GA-Net算法[18]，該算法提出了community score的概念并將其作為適應度函數進行優化得到社團發現的結果。Liu等[19]使用遺傳算法和聚類來探測網絡中潛在的社團結構，該算法最初將網絡分為兩部分，之后再不斷地分割子圖，并在子圖中應用嵌套的遺傳算法進行社團發現。Tasgin等[20]通過遺傳算法來優化模塊度函數，從而進行社團發現。

(4) 基于標簽傳遞的社團發現算法的基本思想是： 一個節點的社團標簽是由它的所有鄰居節點的標簽所決定的。標簽傳遞算法LPA是由Raghavan等[8]提出，開始時，每個節點都擁有一個獨一無二的標簽。之后每個節點都參考它的鄰居節點擁有的標簽來更新自身的標簽，經過多輪的標簽傳播直至每個節點的標簽都是它的鄰居節點中擁有最多的那個標簽，這時擁有相同標簽的節點形成一個社團。Xie等[9]通過考慮節點的歷史標簽對標簽傳遞算法進行了擴展，使其可以用于探測重疊社團。Hu[10]對標簽傳遞算法進行了改進，提出了一個帶權重的標簽傳遞算法，在標簽傳遞的過程中使用節點間的相似性為標簽加權。Gregory[11]通過設置節點和社團之間的歸屬系數使得每個節點可以屬于多個社團，并且提出了一個判斷標簽傳遞是否收斂的終止條件，使得標簽傳遞能夠在有限的步驟中收斂。

以上這些方法都是針對同質信息網絡的。近些年，出現了一些在異質信息網絡中進行聚類的相關工作。Sun等[21]提出了一種帶有用戶引導的聚類算法 PathSelClus，其聚類結果根據用戶選擇的元路徑的不同而不同，而且PathSelClus需要事先指定簇的個數。Luo等[22]首次提出關系路徑的概念來評價同種類型節點之間的相似性，通過利用標記信息來學習不同關系路徑的權重，提出了一種半監督的聚類算法SemiRPClus。

2 基于元路徑的社團發現方法

2.1 基本思想

相比于同質信息網絡，異質信息網絡具有很多新的特性，這些新的特性為數據挖掘任務帶來很多新的挑戰。異質信息網絡中不同類型的對象和關系包含有豐富的語義信息，元路徑可以捕捉這些信息。元路徑是定義在網絡模式上的一條路徑[1]。以圖1(c)為例，連接作者的兩條元路徑： “作者—論文—作者”表示作者的合作關系，“作者—論文—會議—論文—作者”表示作者在相同會議上發表論文的關系?；诘谝粭l元路徑，則經常合作出版論文的作者更可能在一個社團；基于第二條元路徑，則那些經常在同一個會議上發表論文的作者更可能在一個社團。可見，選擇不同的元路徑，作者之間的相似性是不同的，進而會導致不同的社團發現結果。因而，基于異質信息網絡的社團發現應該充分考慮各條元路徑所包含的不同的語義信息。另外，勞逆等[23]指出，對于一個給定的網絡，可能存在的元路徑數目與路徑長度成指數增長，而且，Sun等[1]指出很長的元路徑并不是很有意義。因此，在社團發現任務中，我們需要選定合適長度的元路徑。

基于這個想法，本文提出了異質信息網絡中基于元路徑的社團發現方法HCD，它包括兩部分，第一部分是基于單條元路徑的社團發現算法HCD_sgl，第二部分HCD_all是將基于各條元路徑的社團發現結果進行融合，得到異質信息網絡中的最終的社團發現結果。下面我們詳細闡述這兩部分。

2.2 基于單條元路徑的社團發現算法HCD_sgl

基于單條元路徑的社團發現算法主要包括兩個階段。第一階段是基于單條元路徑的初始社團劃分，即根據預先設計的方法確定在該條元路徑下所有節點的初始標簽；第二階段是基于單條元路徑的最終社團劃分，即采用改進的標簽傳遞算法得到所有節點的最后標簽，進而得到最終的社團發現結果。下面詳細介紹這兩個階段。

2.2.1 基于單條元路徑的初始社團劃分

基于單條元路徑的初始社團劃分方法主要包括以下三步。①確定滿足一定數目的重要種子的節點集合。②根據模塊度優化算法獲取較為準確的種子節點標簽。③根據網絡結構和種子節點的社團標簽確定非種子節點的社團標簽。

第一步選擇種子節點的具體方法如下。首先，根據給定的元路徑，通過矩陣相乘將異質信息網絡映射為相應的同質信息網絡。然后，求出在該同質信息網絡中所有節點的節點度，并將所有節點按照節點度由大到小排序。對于節點度相同的節點，再按照節點的本地向心性由大到小排序。最后，選取節點序列中前seedNum個節點構成種子節點集合，并構建種子節點網絡。這里，seedNum為控制種子節點個數的參數，可以通過實驗確定最合適的種子節點個數。選擇度大的節點是因為其在社團中有很多節點與其關聯，擁有較大的影響力。節點的本地向心性是指相對于它的鄰居節點，其在本地的小社團中地位的重要性，用節點的所有鄰居節點度的累加和來表示,如式(1)所示。

(1)

其中，N(i)為節點i的鄰居節點的集合。ki為節點i的度。kn(i)表示節點i的本地向心性，較小的值代表了較大的本地向心性，較大的值代表了較小的本地向心性。

第二步確定種子節點的標簽采用的是文獻[17]中的基于模塊度優化的算法，主要包括社團探測和網絡重構兩個階段，這兩個階段相互迭代，直到網絡的模塊度不再發生變化，此時就確定了種子節點的標簽。其中，在社團探測階段，我們先假設每個種子節點都屬于不同的社團，然后對節點i，遍歷它的所有鄰居節點，分別計算將節點i移入它的第j個鄰居節點所在的社團所產生的模塊度的增量，這樣，對節點i的所有鄰居節點就得到了一個模塊度增量的向量。然后選取這個向量的最大值。若為正，則將節點i移入對應鄰居所在的社團;若為負，則節點i仍留在其原來的社團。循環遍歷網絡中的所有節點并執行上述節點移動過程，直到任何節點的移動都無法使得整個網絡的模塊度增加。這時，得到了本地最優的社團結構，社團探測階段結束。在網絡重構階段，將社團探測階段獲得的社團作為下一層社團發現的新的節點，重新構造網絡，新網絡中節點之間邊的權重為該節點在原來網絡中對應社團之間所有有邊相連的節點對之間的邊的權重之和。節點到自身的邊的權重為原來網絡中社團內部節點之間邊的權重之和。

第三步確定非種子節點的標簽，過程如下： 首先，遍歷全部的非種子節點，判斷其鄰居節點中是否存在種子節點。若該非種子節點的鄰居中存在種子節點，則先獲取它的全部種子節點鄰居所屬的社團集合，再計算非種子節點屬于各個社團的可能性，最后將可能性最大的那個社團標簽作為非種子節點的社團標簽。非種子節點屬于某個社團的可能性是指非種子節點與鄰居中屬于這個社團的種子節點的相似度之和；若該非種子節點的鄰居中不存在種子節點，則查找所有種子節點，找到與該節點相似性最大的節點，并把其標簽作為該非種子節點的標簽。非種子節點i的社團標簽按照式(2)的方法確定。

(2)

其中，Seed表示種子節點的集合，S表示節點相似性矩陣，Sij表示節點i和節點j之間的相似性。社團標簽的集合為L，節點i的社團標簽為Ci，節點i的鄰居集合為N(i)。

通過以上三個步驟，網絡中的全部節點都擁有了一個初始標簽，其偽代碼如算法1所示。

算法1 基于單條元路徑的初始社團劃分

2.2.2 基于單條元路徑的最終社團劃分

基于單條元路徑對社團進行最終劃分時，我們采用了改進的標簽傳遞算法，它主要是對傳統的標簽傳遞算法進行修改，使得在每一輪標簽更新時，能同時考慮該節點可能擁有的多個社團標簽，以便可以進行重疊社團發現。在更新時，每個節點屬于各個社團的歸屬度按式(3)計算。

(3)

為了避免保留的社團標簽數目過多，我們刪去歸屬度小于1/v的標簽，若都小于1/v，則保留最大的那個，同時需對歸屬度進行標準化，v是每個節點最多擁有的標簽數。為了確保算法能收斂到一個穩定狀態，受文獻[11]的啟發，我們將mt=mt-1作為標簽傳遞算法的終止條件，mt表示第t輪標簽更新后屬于各個社團的最小節點數，確定方法如式(4)所示。

(4)

其中，ct為第t輪標簽更新后屬于各個社團的節點個數，確定方法如式(5)所示。it為第t輪標簽更新后剩下的社團標簽集合，如式(6)所示。(c,i)表示屬于社團c的節點數為i。

(5)

其中，L是社團標簽集合，Vt是全部目標類型節點的集合。

(6)

經過上面兩個階段，我們得到了基于單條元路徑的社團發現結果，其偽代碼如算法2所示。

算法2 基于單條元路徑的社團發現算法HCD_sgl

2.3 融合多條元路徑的社團發現算法HCD_all

異質信息網絡中不同的元路徑具有不同的語義信息，因此基于單條元路徑進行的社團發現可能并不能完整地描述整個網絡的社團結構。鑒于此，我們融合多條元路徑的社團發現結果，從而使得基于單條元路徑不能發現的社團特征可以在基于其他元路徑的社團發現結果中得到補充。

融合多條元路徑的社團發現算法包括以下兩個階段。第一階段首先遍歷基于各條元路徑的社團發現結果，針對每個節點形成一個標簽序列，用來顯示該節點在各個社團發現結果中的社團標簽。如果一些節點在基于各條元路徑的社團發現結果中都擁有相同的社團標簽，即它們擁有相同的標簽序列，則認為它們一定屬于同一個社團，形成了一個相同社團的約束。

第二階段為網絡重構階段。找到這些相同社團的約束后，將這些一定屬于同一個社團的節點集合看作下一層社團發現的一個新節點，重新構造網絡。然后在新構造的網絡中進行模塊度的優化，當網絡的模塊度不再變化時，算法終止，得到最終的社團發現結果。算法3是融合多條元路徑的社團發現算法HCD_all的偽代碼。

算法3 融合多條元路徑的社團發現算法HCD_all

3 實驗與結果

我們在DBLP數據集上驗證了算法HCD_sgl和HCD_all的有效性，在人工數據集的非重疊社團數據上驗證了算法HCD_sgl的有效性，在重疊社團數據上又進一步驗證了HCD_sgl可以用于重疊社團發現，并對算法HCD_sgl中的參數seedNum進行了相關討論。

3.1 數據集

(1) DBLP數據集： 本實驗使用文獻[24]中的DBLP數據集的子網絡，該數據集包含數據庫、數據挖掘、信息檢索、人工智能四個研究領域(社團類型)的20個會議、14 376篇論文、14 475位作者和8 920個術語。其中含有標簽的數據有4 057位作者、100篇論文和全部20個會議，標明了它們所屬的社團類型(研究領域)。對數據進行預處理得到全部具有標簽的數據集包含2 052位作者、3 100篇論文、20個會議和3 925個術語。

(2) 人工數據集： 該數據集分為兩部分，一部分是規模較大的非重疊社團數據，用于比較HCD_sgl與其他算法在非重疊社團發現中的效果。另一部分是規模較小的重疊社團數據，用來驗證HCD_sgl進行重疊社團發現的效果。

圖2 非重疊社團網絡示意圖[25]

重疊社團數據集的網絡中也包含A和B兩種節點，A類和B類節點也都有四個社團，分別為A1、A2、A3、A4和B1、B2、B3、B4。每個A類節點的社團含有64個節點，每個B類節點的社團含有128個節點。A 類節點共有256個，B類節點共有512個。除了以上生成規則外，從社團A1中隨機選擇八個節點，使其到社團B2的邊的生成概率為pstrong，因此這八個節點是社團A1和A2的共同節點。同樣地，找到社團A2和A3，A3和A4，A1和A4的八個共同節點。

3.2 評價標準

實驗中我們使用標準化互信息(NMI)[26]和模塊度(modularity)[12,27]作為評價社團發現好壞的標準。計算分別如式(7)、式(8)所示。

(7)

其中，H(A)和H(B)分別是A和B的熵，I(A,B)是A和B的互信息，NMI用來衡量兩個聚類結果的相近程度，取值范圍是[0,1]，值越大，表示社團發現的結果越好。

(8)

3.3 對比方法

因為算法開始基于給定的元路徑將異質信息網絡映射成同質信息網絡，所以本文中我們選取了同質信息網絡中三個經典的社團發現算法進行對比，譜聚類算法(spectral clustering，SC)[28]、基于模塊度優化的BGLL算法[17]和標簽傳遞算法LPA[8]。分別介紹如下。

(1)譜聚類算法(spectralclustering，SC)[28]： 該算法是一種基于圖論的聚類方法，它先利用相似性矩陣的特征值把數據降維，再進行聚類。本文通過使用基于元路徑的相似性算法使得譜聚類算法可以應用在異質信息網絡中進行社團發現。

(2)BGLL算法[17]： 該算法是一個基于模塊度最優化的啟發式算法，包括社團探測和網絡重構兩個階段。第一階段通過節點交換進行社團劃分，獲取本地最優的模塊度；第二階段把第一階段探測出的社團結構當作新節點重新構造更高層次的網絡。兩個階段的不斷迭代，直至不會產生更高層次的社團結構。

(3)標簽傳遞算法(LPA)[8]： 該算法通過多輪的標簽傳遞和更新，直至各個節點的社團標簽都不再變化，最終使得每個節點的社團標簽都是其鄰居節點中包含最多的那個社團標簽。

本文基于指定的元路徑將異質信息網絡映射成為同質信息網絡，再將BGLL算法和LPA算法應用其中。

3.4 有效性實驗

3.4.1 基于單條元路徑的社團發現有效性實驗

我們分別在DBLP數據集和人工數據集上進行非重疊社團發現實驗，驗證算法HCD_sgl的有效性，參數v設為1，seedNum設為700，譜聚類算法和標簽傳遞算法均重復100次取平均值。

在DBLP數據集上，我們采用元路徑APCPA對作者進行社團發現。譜聚類算法和HCD_sgl算法均使用PathSim[1]和HeteSim[29-30]作為相似性計算方法，PathSim和HeteSim都是異質信息網絡中比較重要的兩種相似性度量方法。實驗結果如表1和表2所示。

在人工數據集的非重疊社團數據上，我們通過改變Din的值，來生成不同的網絡，并且選擇元路徑ABA對A類節點進行社團發現。對于每個Din隨機生成10個網絡，對于每一個網絡，運行算法10次求均值，結果如圖3所示。其中，Din代表了社團的模糊程度，較大的Din對應的社團結構更明顯，而較小的Din對應的社團結構更模糊，由于LPA算法的效果很差，因此這里只比較了HCD_sgl算法與BGLL算法、SC算法的效果。

表1 相似性計算方法為PathSim時各社團發現算法的聚類結果

表2 相似性計算方法為HeteSim時各社團發現算法的聚類結果

從表1和表2中，我們可以看出，基于兩種不同的相似性計算方法，HCD_sgl的聚類效果比其他三個算法好。LPA算法效果是最差的，這是因為其初始標簽過多，造成最終的社團發現結果中的標簽數也較多，從而影響了社團發現效果。并且由于LPA算法在進行標簽選擇時存在隨機性，導致每一輪最終的社團標簽都較為不同，而HCD_sgl通過引入種子節點控制了社團標簽個數，通過本文提出的確定種子節點和非種子節點初始標簽的方法以及對傳統標簽傳遞過程的改進，消除了算法的隨機性，使得算法可以獲得較穩定的結果。BGLL的表現較HCD_sgl略差一點，原因可能在于使用模塊度作為優化目標，這種方法偏向于找到較大的社團結構，因此會忽略一些較小的社團。譜聚類算法需要預先設定簇的個數k，而簇的個數直接影響了社團發現的結果。

從圖3可以看出，隨著社團結構越來越明顯，不同算法進行社團發現的模塊度都在增加，即算法的效果都在提升。SC算法的效果是最差的，HCD_sgl算法在不同模糊度的網絡中進行社團發現的準確性都是最好的，可以取得比BGLL算法更好的效果。

圖3 人工數據集中社團發現效果隨社團模糊度變化圖

3.4.2 融合多條元路徑的社團發現有效性實驗

為了驗證HCD_all算法的有效性，我們分別選取APA、APCPA和APTPA三條元路徑來運行HCD_sgl算法，融合這三條元路徑運行HCD_all算法，算法中使用 PathSim來計算相似性，seedNum的值設為700。實驗結果如表3所示。

表3 基于單條元路徑的社團發現與融合多條元路徑的社團發現效果比較

從表3可以看出，算法HCD_sgl基于不同的元路徑的社團發現效果是不同的，說明不同的元路徑能捕捉不同的語義信息。并且基于元路徑APCPA的社團發現效果是最好的，較其他兩條元路徑有明顯的優勢，這說明元路徑APCPA能夠更好地捕捉當前網絡的語義信息。融合了三條元路徑的HCD_all算法在兩個評價指標上都比HCD_sgl效果好，說明不同的元路徑捕捉到的語義信息可以相互補充，從而達到更好的社團發現效果。算法HCD_all的效果相比APCPA的效果提升并不明顯，原因是元路徑APCPA捕捉了主要的語義信息，而其他兩條元路徑捕捉的語義信息相對較少。另外，這些捕捉到的相對較少的語義信息對整體的社團發現效果提升是有幫助的，表明其捕捉到了必要的信息，也進一步說明融合多條元路徑的必要性。

3.4.3 重疊社團發現有效性實驗

為了驗證HCD_sgl算法進行重疊社團發現的效果，我們在重疊社團數據集中進行實驗。HCD_sgl的參數v設為2，元路徑選取APA，相似性計算方法采用PathSim，seedNum的值設為700。

表4顯示了社團實際重疊部分的規模與HCD_sgl探測出的重疊規模。由表4可以看出，大多數社團的重疊部分都可以被HCD_sgl算法探測出來，證明了HCD_sgl的確可以用于重疊社團發現。

表4 重疊社團發現結果

3.5 效率實驗

為了更加綜合地說明提出方法的性能，我們在人工數據集不同的Din值對應的不同網絡上，分別執行BGLL和HCD_sgl算法 25次，記錄平均結果如表5所示。這里我們只與對比算法中有效性最好的BGLL算法進行了比較。由表5可以看出，在Din取不同值的情況下，HCD_sgl算法的效率總是比BGLL算法高，進一步說明提出方法相比其他基本方法的綜合的性能優勢。

表5 不同社團模糊度下算法的效率比較

3.6 參數討論

算法HCD_sgl中的參數seedNum對探測出的社團數目和最終的效果都具有一定的影響，為了更好地研究這種影響，我們在DBLP數據集中使用元路徑APCPA、相似性計算方法PathSim來進行參數實驗，實驗結果如圖4和圖5所示。

圖4 種子節點數取不同值時算法執行效果

圖5 種子節點數取不同值探測出的社團數目

從圖4可以看出，隨著seedNum的增加，評價標準模塊度和NMI表現出相似的變化趨勢。當seedNum的值小于5時，指標呈現出增長的趨勢，當seedNum的值接近于5時，效果就比較接近社團發現的最終結果了，這說明度較大且本地向心性高的種子節點在網絡中處于較為重要的地位，對社團發現起著關鍵性作用。當seedNum處于200～400之間時兩個指標都出現下降，可能是因為新引入的種子節點產生了干擾，當把該種子節點的標簽進一步傳遞給非種子節點時，將這種干擾擴大到了整個網絡當中。當seedNum處于700～800附近后，效果達到了最好并且趨于穩定，可能是因為新添加的種子節點使得網絡結構更加完整，從而使探測出的社團結構達到最優。

圖5顯示了seedNum取不同值時HCD_sgl探測出的社團數目的變化趨勢?？梢钥闯觯S著seedNum的增加，社團數目不斷增加，直至穩定，當seedNum為700時HCD_sgl可以探測出DBLP數據集中所有的四個社團。因此在其他實驗中將seedNum的值設為700。

4 總結與展望

本文研究了異質信息網絡中的社團發現問題，提出了一個利用豐富的結構信息和語義信息進行社團發現的方法HCD，它包括兩部分： 第一部分是基于單條元路徑的社團發現算法HCD_sgl，第二部分是融合多條元路徑的社團發現算法HCD_all。 HCD_sgl基于給定的元路徑將異質信息網絡映射為同質信息網絡，設計相應方法獲得節點的初始社團標簽，再利用改進的標簽傳遞算法，得到最終的社團發現結果。HCD_all融合基于不同的元路徑的HCD_sgl的社團發現結果，重新構造新的網絡，再利用模塊度優化算法獲得最終的社團發現結果。HCD方法在真實和人工數據集上均取得了較好的實驗效果。HCD_sgl能夠取得比傳統的標簽傳遞算法更好的社團發現結果。HCD_all融合了異質信息網絡中基于多條元路徑的結果，可以取得比基于單一元路徑的HCD_sgl算法更好的社團發現效果。本文提出的異質信息網絡中的社團發現方法HCD只是基于靜態網絡的，可以進一步考慮時間因素，進行動態的社團發現。