基于網絡表示學習的非單一維度的社區發現算法

陳婉杰　盛益強

摘 要：針對現有的社區發現算法難以解決網絡的多維性問題的現象，提出一種基于網絡表示學習的非單一維度的社區發現算法。該算法從節點屬性特征和網絡結構特征兩個維度考慮節點的差異性，首先根據節點屬性相似度計算得到節點轉移概率，結合小世界模型的六度分離理論設置網絡節點隨機游走路徑的長度。依據轉移概率選擇節點的鄰居節點，得到節點的游走路徑，然后用神經網絡模型訓練節點的游走路徑得到節點的網絡特征向量，將節點網絡特征向量的相似度重置為節點連接邊的權重，在Louvain算法的基礎上完成社區劃分。最后，在Facebook和Giraffe兩個數據集上進行了實驗，選用基于初始網絡結構的Louvain算法和基于單一維度的社區發現算法作為對比算法。實驗結果表明，在Giraffe數據集中，相比于Louvain算法，基于節點屬性的社區發現算法的模塊度指標提升了2.7%，基于網絡結構的社區發現算法的模塊度指標提升了3.0%，提出的非單一維度的社區發現算法的模塊度指標提升了3.7%。所提算法聚焦于網絡的多維性，有效提升了社區發現算法的模塊度。

關鍵詞：節點屬性;網絡結構;可擴展性;社區發現;網絡表示學習;節點差異性

中圖分類號： TP391.4模式識別與裝置文獻標志碼：A

Non-unidimensional community detection algorithm based on network representation learning

CHEN Wanjie1，2， SHENG Yiqiang 1，2*

（1. National Network New Media Engineering Research Center （Institute of Acoustics， Chinese Academy of Sciences）， Beijing 100190， China;

2. University of Chinese Academy of Sciences， Beijing 100049， China）

Abstract： Focusing on the issue that it is difficult for the existing community detection algorithms to solve the multidimensionality problem of the network， a non-unidimensional community detection algorithm based on network representation learning was proposed. The algorithm considered the difference of nodes from the two dimensions of node attribute feature and network structure feature. Firstly， the node transition probability was calculated according to the node attribute similarity. The length of the random walk path of the network node was set according to the six-degree separation theory of the small world model. After obtaining the walking path of the node by selecting its neighbor nodes according to the transition probability， the walking path of the node was trained by the neural network model to achieve the network feature vectors. The similarity of the network feature vectors of the node was reset as the weight of the connected edge， and the community partition was completed based on the Louvain algorithm. Finally， experiments were conducted on two datasets， Facebook and Giraffe with the Louvain algorithm based on the initial network structure and the unidimensional community detection algorithm as comparison algorithms. Experimental results show that on the Giraffe dataset， compared to the Louvain algorithm， the community detection algorithm based on the node attribute has the modularity increased by 2.7%， the community detection algorithm based on the network structure has the modularity increased by 3.0%， and the proposed non-unidimensional community detection algorithm has the modularity increased by 3.7%. The proposed algorithm focuses on the multidimensionality of the network and improves the modularity of the community detection algorithm effectively.

Key words： node attribute; network structure; extensibility; community detection; network representation learning; node difference

0 引言

隨著互聯網的飛速發展和移動終端的普及應用，復雜網絡在生活中的很多領域均得到了快速的發展，如社交媒體領域、學術信息領域以及生物學領域等。隨著網絡規模的擴大，對復雜網絡的分析也越來越重要，在真實世界的復雜網絡中，通過網絡中個體構成的社區來觀察網絡中節點的交互行為是清晰的，是全局化的，而通過個體行為觀察節點之間的交互則通常是帶有噪聲和片面的。復雜網絡中很多行為只能通過社區去發現，在個體層面難以觀察到，這是因為個體行為往往具有很強的波動性，而社區行為一般相對穩定，不易改變，因此對復雜網絡進行社區發現是有必要的。

識別復雜網絡中個體所在的社區不僅具有一定的理論價值，也有著廣泛的應用前景。例如電商平臺通過識別出相似興趣類別的用戶社區，可以挖掘出潛在的購買者，當社區內成員點擊或者購買了某一件商品后，便可為相同社區的其他用戶推薦類似商品，從而可以提升商品推薦的準確率，更好地為用戶服務。社交網絡平臺如微博、知乎、微信和Facebook等，用戶存在點贊、關注以及評論等多種類型的互動關系，根據這些行為，社區發現可以獲得網絡的模塊化結構，從而可以對具有相似特征的社區進行好友推薦，幫助用戶發現更多的潛在好友。在信息傳播領域中，發現社區的中心節點，合理地發揮中心節點的作用，不僅可以提高節點傳播的影響力，加速信息傳播，也可以在病毒出現時及時抑制病毒的進一步擴散。

網絡的發展帶來了信息的多樣性，如今復雜網絡包含的信息已不僅只是網絡的結構信息，網絡中的節點也具有豐富的屬性，如Facebook數據集不僅包含網絡中節點以及節點的連接邊信息，還包含節點的屬性信息，如年齡、性別、公司、生日、姓名等屬性特征。有研究表明，實際網絡中有直接連接關系的節點，通常其節點屬性信息的相似度會更高[1-2]。為了驗證該觀點，以Facebook數據集和Giraffe數據集為例，可以看出，具有連接關系的節點屬性相似度大于0.6、0.7和0.8的邊的占比情況，如表1所示。Facebook數據集中有61%的連接邊對應節點的屬性相似度超過60%，Giraffe數據集中更有61%的連接邊對應節點的屬性相似度超過80%，這也論證了結合節點屬性信息和網絡結構進行社區發現的重要意義。

傳統社區發現算法大多基于網絡結構進行社區發現，面對網絡的多維性問題，針對單個維度的社區發現算法研究已到達一定瓶頸。充分利用網絡中節點的多維度特征，實現不同維度的信息的融合，不僅可以提高社區發現對當前網絡的適應性，也可以充分利用網絡節點不同維度層面的差異性，更好地挖掘節點的隱含特征。

隨著信息化程度的提高，復雜網絡規模越來越大。實際復雜網絡中，大部分節點與網絡中的其他節點之間的直接聯系是非常有限的。選用合理的社區發現算法，充分利用節點屬性與網絡結構特征，在保證社區發現準確率的前提下，從網絡中的局部節點結構便可挖掘出網絡的隱含的特征信息，將極大地改善傳統社區發現算法，從網絡的全局信息挖掘網絡潛在特征的低效問題，同時可以提高社區發現算法的可擴展性。

近幾十年以來，社區發現作為網絡科學中的一項基礎研究，很多研究人員對社區發現算法進行了深入的探索，取得了很多突破性的成果。但隨著網絡的發展，針對目前社會網絡結構中網絡的特點，社區發現的研究面臨著如下問題和挑戰。

1）網絡的多維性以及網絡節點的差異性。

針對單一維度網絡結構的傳統社區發現算法因為信息的缺乏，在社區發現的效率和準確率上均受到了限制。隨著信息化程度的提高，信息維度的增加使網絡呈現出多維性，所謂網絡的多維性是指網絡中的節點之間邊的連接關系有多種類型，而由這些節點及不同類型的邊所組成的“維度”不同的網絡就稱為多維度網絡。在各種復雜的網絡尤其是社會網絡中，不同節點之間也是有差異的，而傳統社區發現算法，并沒有考慮這一點，大多數網絡分析的方法，忽略了節點之間的差異性，認為整個網絡中所有的節點有著相同的地位。實際的網絡中，不僅節點自身的屬性特征有很大的差異性，每一個節點的隱含網絡結構特征也都是不一樣的。因此如何利用網絡的多維度信息針對社區發現中網絡節點的差異性挖掘節點的隱含特征，從而更好地完成社區劃分是當前社區發現的研究面臨的一個重要問題。

2）可擴展性。

當今網絡發達，網絡每時每刻都有新節點加入，復雜網絡的規模越來越大，而現有的社區發現算法大多都基于全局信息去挖掘網絡的隱含信息，例如：獲取Girvan-Newman算法中依據“邊介數”信息進行社區發現需要遍歷整個網絡;Kemighan-Lin算法為了完成社區劃分必須要提前知道社區的個數或者平均規模等，在有新節點加入時，依然需要遍歷整個網絡去挖掘節點的隱含網絡結構特征，從而造成算法的低效與浪費。而實際上，復雜網絡尤其是社會網絡大多是稀疏的，網絡中的大部分個體與網絡中的其他節點之間的直接聯系是非常有限的，因此面對日益增長的節點規模，能否通過只依賴網絡中的局部節點結構挖掘出網絡的隱含的特征信息，在有新節點加入時，能否只對新節點所在的局部網絡進行處理，增強算法的可擴展性是當前亟需要解決的一個問題。

針對現有社區發現算法難以解決網絡的多維性問題、節點的差異性問題以及可擴展性問題，本文聚焦于網絡多維性問題，提出了一種基于網絡表示學習的非單一維度的社區發現算法。

該算法將節點屬性信息作為先驗信息，根據用戶屬性相似度重新計算節點之間轉移概率，在node2vec算法的基礎上，借助自然語言處理領域的特征學習方式，將文本的處理方式遷移至網絡結構中。同時，結合小世界模型的六度分離理論設置網絡節點游走路徑的長度，通過對網絡的局部結構進行分析，從而挖掘出局部網絡的隱含特征。當網絡中有新節點加入時，不需要遍歷整個網絡進行社區發現，只用計算與新節點有直接連接關系的節點之間的屬性相似度，然后根據本文提出的算法在新節點附近按照根據屬性相似度計算得到的概率進行游走。得到游走路徑后，用神經網絡模型訓練得到節點的隱含特征向量，最后根據新得到的節點向量計算相似度后，使用Louvain社區發現算法完成社區劃分。

本文的主要工作如下：

1）將節點屬性信息作為先驗信息，從節點屬性和網絡結構屬性信息兩個維度考慮了節點的差異性，改善了傳統社區發現算法因為信息的缺乏只針對單一維度網絡結構進行社區發現從而導致效率和準確率均受到限制的問題。

2）現有社區發現算法大多只考慮了邊的連接性，即節點之間是否有直接連接關系，本文提出的算法可以計算出任意兩個節點之間的加權相似度，不再局限只可以計算有連接關系的節點之間的相似度，因此一定程度上解決了社會網絡的稀疏性問題。

3）從基于用戶屬性相似度的節點轉移概率和基于六度分離理論設置的游走路徑長度兩個方面對隨機游走算法進行約束，改善了傳統隨機游走算法在網絡轉移過程中具有較強隨機性的缺點，提高了社區發現算法的準確率。

4）通過對網絡的局部結構進行分析，即可挖掘出局部網絡的隱含特征，提高了算法的可擴展性，改善了傳統社區發現算法從全局網絡角度考慮挖掘網絡隱含特征造成的低效與浪費的問題。

實驗結果表明，在Giraffe數據集中，相較于Louvain算法，基于節點屬性的社區發現算法模塊度指標提升2.7%，基于網絡結構的社區發現算法模塊度指標提升3.0%，本文提出的非單一維度的社區發現算法，模塊度指標提升3.7%。

1 相關工作

隨著復雜網絡的發展，復雜網絡分析中的社區發現問題成為一大研究熱點，眾多學者從不同的角度對該問題進行了深入的研究，下面介紹社區發現問題相關的經典算法以及當前該領域的一些新的研究方法。

Girvan等[3]提出了一種分裂的層次算法GN（Girvan Newman），基于邊介數的相關概念對網絡結構進行劃分。邊介數的定義是經過網絡中某條邊的任意兩個點之間最短路徑的數目，該算法通過迭代地移除網絡中邊介數最大的連接，以此完成劃分。該算法優點是劃分社區的結果很準確，但是缺點是算法時間復雜度在節點規模比較大時過高，因此不太適合處理大規模的網絡結構圖。Newman等[4]提出了模塊度的概念，模塊度主要作為評價社區劃分質量的指標，可以用來衡量社區結構的強度，模塊度越大，表示社區劃分的結果越好，社區內部邊越緊密?，F在模塊度在本身社區劃分的結果是未知的情況下已經漸漸成為衡量社區發現的重要標準。Kernighan和Lin[5]提出了一種貪婪算法，也被稱為Kernighan-Lin法，該算法把網絡視為圖結構，通過圖分割的相關算法，不斷迭代和交換不同社區內的節點，優化社區結構，調整社區之間連接邊的數量，目的就是使社區內連接邊的數量與社區之間連接邊的數量的差值增大，從而獲得社區劃分的結果。該算法的缺點是如果劃分社區之前不了解社區的實際規模，將無法知道使該方法結束的停止條件。為了改善前面提到的GN算法當節點規模變大時算法時間復雜度過高的缺陷，Newman[6]提出了一種快速分裂的層次算法FN（Fast Newman），該算法的思想是首先將網絡的節點視為單個的社區，然后合并社區，合并的原則就是使模塊度增量達到最大值時的兩個社區作為新社區，不斷地迭代調整直到整個網絡被合并為一個單獨的社區。FN算法在模塊度達到最大時獲得的劃分結果成為社區發現的最終劃分結果。該算法在保證社區劃分質量的前提下，降低了算法的時間復雜度。 Blondel等[7]提出了Louvain算法，這是一種基于模塊度的算法，該算法主要包括兩個部分：第一部分是首先將每個節點視為單個的社區，嘗試將單個社區加入可以讓模塊度增加最大的社區里面，一直遍歷網絡，直到網絡中的節點都穩定下來;第二部分是壓縮一個社區為一個節點，節點權重為原始社區內部節點權重的和，重復第一個過程，直到模塊度成為一個穩定值。Louvain算法在網絡規模比較大時依然可以取得很好的劃分效果，而且時間復雜度很低，因此常被用于大規模網絡中的社區劃分。

近年來，基于深度學習的發展，結合神經網絡對圖結構的分析也取得了很多成果：Deepwalk算法[8]首次將深度學習應用于圖的網絡結構分析，在根據隨機游走得到節點的游走序列后，借助自然語言處理中word2vec算法[9-10]的思想，將節點游走序列類比于文本處理中的句子，將序列中的節點類比于文本處理中的單詞，使用skip-gram模型[10]學習得到網絡中節點的向量表示;node2vec算法[11]在Deepwalk的基礎上進行了改進，Deepwalk算法在得到節點序列時就是普通的隨機游走，而node2vec算法借助參數可以控制隨機游走時更偏向于深度優先搜索還是廣度優先搜索;大網絡內聚集模型（CLuster Affiliation Model for BIGNetworks， BIGCLAM）算法[12]用一個非負向量作為一個節點的網絡表示，該算法認為兩個節點向量表示的內積越大，兩個節點產生直接連接關系的可能性也就越大;結構化深度網絡嵌入（Structural Deep Network Embedding， SDNE）算法[13]首次將深層神經網絡模型用于節點的網絡表示學習，模型的第一個模塊是有監督的自編碼神經網絡對一階鄰居關系的建模，第二個模塊是無監督的自編碼神經網絡對二階鄰居關系的建模，從而保留了網絡的一級相似度和二級相似度。

無論是傳統社區發現算法還是結合深度學習模型的網絡表示學習算法，均是只考慮了圖的網絡結構信息，也有一些社區發現算法同時結合節點屬性信息與網絡結構特征。社交網絡嵌入（Social Network Embedding， SNE）算法[14]中神經網絡的輸入向量是節點的ID與其他屬性向量的拼接，通過訓練模型，提取到網絡節點的特征表示。也有學者提出了將原始無向無權網絡結構和屬性信息直接相融合，缺點是只考慮了節點之間邊的存在性，沒有進一步挖掘網絡結構的隱含信息。Zhang等[15]提出了通過對節點屬性信息進行K核映射[16]的思路，先得到節點屬性的表示向量，然后通過Deepwalk算法將網絡結構信息編碼到節點屬性表示向量中，實現了兩者的融合。溫雯等[17]提出了基于頂點信息為先驗信息的圖嵌入（Graph embedding by incorporating prior knowledge on Vertex Information， GeVI）算法，調整skip-gram模型的優化函數中條件概率分布為網絡結構表示向量和節點屬性特征向量的乘積，從優化函數角度實現了兩方面信息的融合。Yang等[18]提出了和文本信息相關的深度隨機游走（Text-Associated Deep Walk， TADW）算法，該算法首先證明了Deepwalk算法等價于上下文矩陣的分解，通過將節點屬性特征嵌入矩陣分解，借助矩陣分解框架實現了節點屬性信息和網絡結構信息的融合。Huang 等[19]提出了加速屬性網絡嵌入（Accelerated Attributed Network Embedding， AANE）算法，通過對節點屬性相似性矩陣進行矩陣分解得到節點的向量表示，并在優化函數中增加了基于節點連接關系的約束項。Yang等[20]提出了Planetoid模型，利用標簽信息，將標簽相同但不具有連接關系的節點連接在一起，從而學習出包含節點標簽屬性信息的圖表示?；诠濣c文本信息的圖嵌入（Context-Aware Network Embedding， CANE）算法[21]通過對具有直接連接關系的節點的文本信息利用卷積神經網絡[22]進行編碼，選擇直接相連的節點彼此之間相關性最大的卷積結果作為節點的表示向量。相關主題模型（Relational Topic Model， RTM）算法[23]使用文檔主題生成模型 LDA（Latent Dirichlet Allocation）[24]對文本進行建模，該算法認為有直接連接關系的節點有著相似的主題分布;基于潛在概率的文本網絡嵌入（Probabilistic LAtent document Network Embedding， PLANE）方法[25]在RTM算法的基礎上，采用可視化的方法學習得到文本的主題以及節點的表示，這兩種方法要求網絡中節點的內容必須是文本，因此如果不是文本類型的節點屬性，則不能處理;除了這兩種算法外，也有一些算法[26]依賴節點文本內容屬性完成網絡表示學習，它們均基于網絡中節點的文本內容屬性，而沒有充分利用節點的除文本屬性外的其他描述性屬性特征。

分析以上算法，可以將其分為三種類型：第一種是只考慮文本內容屬性信息未考慮網絡節點描述屬性特征的，這類算法的不足之處是無法處理非文本類型的節點屬性特征，因此算法不具有普適性;第二種是只考慮了節點部分描述屬性，例如SNE算法只考慮了節點的屬性ID，沒有考慮其他屬性信息，同時網絡結構中邊的信息沒有得到充分利用;其他結合節點屬性信息的方法，大多是先得到節點屬性表示向量，再與網絡結構表示向量相融合，這種融合方式較為低效。為了提高節點通過網絡表示學習所得向量的質量，可以考慮充分利用節點的描述型屬性特征，使算法具有普適性。同時也可以先融合節點屬性信息和網絡結構信息再去訓練得到節點表示的向量，使節點屬性特征和網絡結構特征可以更好地互相補充和制約，以提高節點網絡表示學習所得向量的質量，可以更好地進行社區發現。

本文主要方法與上述研究的不同之處在于以下兩點：

1）充分利用了節點的屬性信息和網絡結構信息，將網絡結構轉化為向量表示，采用將節點屬性信息作為先驗信息，根據用戶屬性相似度重新計算節點之間轉移概率的方式引入節點屬性信息，從而進一步挖掘網絡結構的隱含信息。

2）本文提出的算法通過計算節點基于網絡表示學習得到的特征向量，用特征向量之間的相似度重置原始網絡，然后使用Louvain社區發現算法完成社區劃分，避免了將原始無向無權網絡結構和屬性信息直接相融合，只考慮了節點之間邊的存在性的缺點。

2 融合節點屬性和網絡結構的社區發現算法

基于node2vec網絡表示學習算法，聚焦于網絡的多維性，本文提出了一種同時考慮節點屬性特和網絡結構兩個維度特征的社區發現算法。在node2vec算法的基礎上，引入節點屬性信息后，借助自然語言處理領域的特征學習方式，將文本的處理方式遷移至網絡結構中，同時結合小世界模型的六度分離理論設置網絡節點游走路徑的長度，通過對網絡的局部結構進行分析，從而挖掘出局部網絡的隱含特征。當網絡中有新節點加入時，不需要遍歷整個網絡進行社區發現，只用計算與新節點有直接連接關系的節點之間的屬性相似度，然后根據本文提出的算法在新節點附近按根據屬性相似度計算得到的概率進行游走，得到游走路徑后，用神經網絡模型訓練即可得到節點的隱含特征向量，從而提高了算法的可擴展性。本文算法流程如圖1所示。

該算法首先加載圖的網絡結構數據，記錄圖中節點以及節點的連接關系;然后根據節點屬性特征計算節點之間相似度，用節點屬性相似度初始化節點之間連邊的權重;重構原始網絡為無向有權網絡，根據式（3）計算節點之間轉移概率，根據轉移概率采樣選擇當前節點的鄰居節點，當前節點每個鄰居節點被選中的概率等于式（3）計算的轉移概率的值。結合小世界模型，設置適當的游走路徑長度，得到新的網絡結構圖中每個節點的游走路徑;利用skip-gram模型采用隨機梯度下降法和反向傳播算法對節點進行訓練，生成每個節點最優的向量表示，根據網絡節點的向量表示計算節點的相似度;最后使用社區發現算法完成社區的劃分，并使用模塊度對算法效果進行評估。

2.1 基于用戶屬性的節點轉移概率

將用戶屬性用向量表示，計算用戶屬性之間相似度，如果節點屬性為種類類型或者布爾型特征，選用Jaccard系數計算節點屬性相似度，計算式如式（1）所示;如果節點屬性為連續數值型，選用余弦相似度計算節點屬性相似度，計算式如式（2）所示，將節點屬性的相似度作為節點之間的權重，重構原始網絡。

S=J（A，B）=|A∩B||A∪B|（1）

其中：S表示節點屬性相似度;A表示樣本A，B表示樣本B，J（A，B）表示樣本A和樣本B交集個數和并集個數的比值。

屬性特征如果是連續數值型特征，可選用余弦相似度作為衡量標準。余弦相似度計算式如式（2）所示：

S=cos（X，Y）=∑ni=1（Xi×Yi）∑ni=1（Xi）2×∑ni=1（Yi）2（2）

其中：S表示節點屬性相似度;X表示樣本X，Y表示樣本Y，cos（X，Y） 表示樣本X和樣本Y的余弦相似度;n表示樣本特征向量維度;Xi表示樣本X第i維特征，Yi 表示樣本Y第i維特征。

假設當前節點是v，訪問鄰居節點x的概率如式（3）所示：

p（v，x）=wv，xZ（3）

其中Z為歸一化因子。wv，x 計算式如式（4）所示：

wv，x=S/p，dtx=0

1，dtx=1

S/q，dtx=2 （4）

其中：S為節點屬性相似度;t表示上一個節點;v表示當前節點;x為要訪問的鄰居節點;dtx 表示節點t和節點x的最短距離;參數p控制重復訪問剛剛訪問過的頂點的概率，p只在dtx=0 時起作用，dtx=0 表示下一次要訪問的節點正是之前剛剛訪問過的頂點。 因此如果p值較大，則訪問剛剛訪問過的頂點的概率會變低;反之會變高。參數q則控制著游走的方向是向外還是向內，若q值較大，則隨機游走傾向于訪問和t接近的頂點，游走路徑偏向于廣度優先搜索;反之，如果q較小，則隨機游走過程傾向于訪問遠離t的頂點，游走路徑偏向于深度優先搜索。

2.2 結合小世界模型的隨機游走

小世界模型也即六度分離理論，該理論的主要思想是在社會網絡中，任意兩個不認識的人都可以通過“朋友的朋友”建立起一種聯系，這中間一般需要通過5個朋友。研究表明，除了社會網絡以外，也有很多其他領域的網絡有類似的“六度分離”結構，如金融經濟領域中的商業網絡結構、大自然生態系統中的食物鏈，甚至人類的腦神經元結構等都存在這樣的現象。

本文引入了節點的屬性信息重構網絡后，節點之間會有潛在的連接關系，本文認為被節點屬性信息重構后的網絡結構具有“六度分離”屬性，因此結合小世界模型的思想，設置游走路徑長度為l，其中3

2）基于節點屬性相似度的社區發現（Community Detection based on Node Attribute Similarity， CD-NAS）算法[28]。該算法的特點是不考慮節點的網絡結構特征，單一地根據節點的屬性計算節點之間的相似度，然后將節點之間相似度作為節點之間連接權重，根據節點屬性相似度進行社區發現。

3）基于網絡結構特征相似度的社區發現（Community Detection based on Network Structure Feature Similarity， CD-NSFS）算法[11]，對網絡結構特征的處理有兩種方式，可以和基于初始結構的Louvain社區發現算法的處理方法一樣即直接根據連接關系來處理，也可以先根據網絡表示學習算法得到網絡中節點的特征向量，然后根據節點的特征向量計算節點之間的相似度，然后根據節點網絡結構特征相似度劃分社區。

3.4 結果分析

將節點屬性作為先驗信息，先根據節點屬性計算節點的相似度，Facebook數據集節點屬性的相似度如表3所示，Giraffe數據集節點屬性的相似度如表4 所示。

將節點屬性相似度作為節點之間邊的權重，重構原始網絡，得到Facebook數據集節點用網絡表示學習方法得到節點的特征向量一共100維，同時得到Giraffe數據集節點用網絡表示學習方法得到節點的特征向量一共100維，利用t分布隨機鄰域嵌入（t-distributed Stochastic Neighbor Embedding， t-SNE）工具對節點特征向量進行降維處理。Facebook數據集根據網絡表示學習算法得到的節點特征向量計算的相似度如表5所示，包含源節點、目標節點以及節點屬性為先驗信息的節點之間網絡結構特征的相似度。

源節點目標節點節點屬性相似度11460.94828137911890.85361916912290.97834576912010.97897261612040.9834241831600.98559850512150.9765135851350.9832997811910.98142946112380.966038461

Giraffe數據集根據網絡表示學習算法得到的節點特征向量計算的相似度如表6所示，包含源節點、目標節點以及節點屬性為先驗信息的節點之間網絡結構特征的相似度。

選用基于初始網絡結構的Louvain算法進行對比實驗，即：如果網絡中節點有連邊，權重設置為1;無連邊，權重設置為0。對比實驗選用的算法有：1）Louvain算法;2）只依賴用戶屬性特征的社區發現（CD-NAS）算法[28];3）只依賴網絡結構特征的社區發現（CD-NSFS）算法[11];4）本文提出的基于網絡表示學習的非單一維度的社區發現算法，也即將節點屬性作為先驗信息的基于網絡表示學習的社區發現（Community Detection based on Network Representation Learning between nodes With Node Attribute as priori information， CD-NRLWNA）算法。Facebook數據集四種算法的模塊度和運行時間對比結果如表7所示，Giraffe數據集四種算法的模塊度和運行時間對比結果如表8所示。

從表7～8可以看出，無論是在Facebook數據集上，還是在Giraffe數據集上，本文提出的算法效果都是最好的。在Giraffe數據集上，相較于Louvain算法，基于節點屬性的社區發現算法模塊度指標提升了2.7%，基于網絡結構的社區發現算法模塊度指標提升了3.0%，而依據本文提出的非單一維度的社區發現算法，其模塊度指標提升了3.7%。同時，因為網絡節點規模和網絡結構的復雜度不同，Facebook數據集運行時間均高于Giraffe數據集。和一般的加權融合節點屬性和網絡結構的社區發現算法不同的是，本文提出的算法在用網絡表示學習算法學習節點的網絡結構特征之前，先用節點屬性作為先驗信息，實驗結果表明這種算法比基于單純節點屬性特征或基于網絡結構特征進行社區發現算法效果都更好。

3.5 參數敏感性分析

在本節中，對本文提出的將節點屬性作為先驗信息的基于網絡表示學習的社區發現算法進行了參數敏感性分析。本次實驗選擇Giraffe數據集測試，評價指標為模塊度。本節分析了在算法中起重要作用的兩個參數，分別是隨機游走路徑長度和特征維度，其他參數選用默認參數，每個節點的隨機游走次數為num=50，超參數p=0.25、q=4，滑動窗口w=30，迭代次數n=5。

模塊度隨隨機游走路徑的變化如表9所示，模塊度隨特征維度的變化如表10所示。

從表9可以看出，如果隨機游走的長度取值過小，則隨機游走得到的節點序列均是初始節點的鄰居節點，不能有效地展現網絡的實際結構，具有很大的局限性;隨著游走長度的增加，模塊度的值開始明顯提高，但是當游走路徑長度增加到一定程度時，模塊度的值便不再增加，主要是因為算法在收集到節點的序列后，會像自然語言處理方法中對文本句子的處理一樣，限定句子的長度，那么相應的序列長度也是固定的，當游走長度足夠長時，已經足以獲取網絡的全局性特征，因此算法也相對穩定。此外，還可以看出，當模塊度為10時，模塊度最大，也驗證了引入節點信息和小世界模型進行社區發現的必要性。

從表10可以看出，特征維度從20維到128維之間，模塊度一直在增加;從128維到200維，特征維度基本不再變化。這是因為當特征維度到一定程度時，已經可以完全表示出網絡結構的信息，如果特征維度繼續增大，會造成信息冗余。特征維度如果過低，則不能有效地表示出網絡的結構特征;但是特征維度如果設置過大，不僅會造成信息冗余，也會增加算法運行時間。因此設置一個合適的特征維度對算法效果有很重要的影響。

Facebook數據集和Giraffe數據集使用Louvain算法和根據將節點屬性作為先驗信息的基于網絡表示學習的社區發現（CD-NRLWNA）算法得到的社區發現效果如圖5～6所示，其中相同顏色的屬于同一個社區。

從圖5～6可以直觀地看出，和Giraffe數據集相比，Facebook數據集得到的社區結構更明確，社區劃分更清晰，這和前面得出的Facebook數據集模塊度明顯高于Giraffe數據集的結果也是一致的。另一方面，和Louvain算法效果進行對比，本文提出的算法不僅對于網絡邊緣一些節點的社區歸屬社區劃分的結果更合理，同時社區劃分的粒度更細，社區內部的結構更緊湊，更精確地發現了一些Louvain算法沒有發現的潛在社區，如圖中黑色圓圈標記所示，被Louvain算法識別為一個大社區的節點集合，用本文提出的算法可以被劃分為更細粒度的社區，驗證了本文算法的有效性。

4 結語

從節點屬性和網絡特征兩個維度出發，聚焦于網絡的多維性，本文提出了一種基于網絡表示學習的非單一維度的社區發現算法。該算法將節點屬性作為先驗信息，然后基于node2vec算法，結合網絡表示學習進行社區發現，最后使用模塊度對算法效果進行評估。實驗結果表明本文提出的算法能更好地挖掘節點的隱含特征，社區劃分的結果更準確。

社區發現作為復雜網絡分析中一個重要的研究課題，我們接下來的研究方向主要是進一步結合圖神經網絡的相關知識對節點屬性信息和網絡結構的融合進行研究。此外，現在網絡中的節點不僅僅是代表一個人或者一個網頁，節點之間的連接也不僅僅只代表節點的連接關系，如社交網絡中節點用戶可能有多種行為，如“點贊” “關注”或者“評論”，因此針對網絡中節點角色的差異性如何把這些不同的信息結合起來，也是接下來的一個研究方向。

參考文獻 （References）

[1]MCPHERSON M， SMITH-LOVIN L， COOK J M. Birds of a feather： homophily in social networks [J]. Annual Review of Sociology， 2001， 27： 415-444.

[2]AIELLO L M， BARRAT A， SCHIFANELLA R， et al. Friendship prediction and homophily in social media [J]. ACM Transactions on the Web， 2012， 6（2）： 373-382.

[3]GIRVAN M， NEWMAN M E J. Community structure in social and biological networks [J]. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826.

[4]NEWMAN M E J， GIRVAN M. Finding and evaluating community structure in networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（2 Pt 2）： Article No. 026113.

[5]KERNIGHAN B W， LIN S. A efficient heuristic procedure for partitioning graphs [J]. Bell System Technical Journal， 1970， 49 （2）： 291-307.

[6]NEWMAN M E J. Fast algorithm for detecting community structure in networks [J]. Physical Review E， Statistical， Nonlinear， and Soft Matter Physics， 2004， 69（6 Pt 2）： Article No. 066133.

[7]BLONDEL V D， GUILLAUME J L， LAMBIOTTE R， et al. Fast unfolding of communities in large networks [J]. Journal of Statistical Mechanics： Theory and Experiment， 2008， 2008： Article No. P10008.

[8]PEROZZI B， AL-RFOU R， SKIENA S. Deepwalk： online learning of social representations [C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2014： 701-710.

[9]MIKOLOV T， SUTSKEVER I， CHEN K， et al. Distributed representations of words and phrases and their compositionality [C]// Proceedings of the 2013 International Conference on Neural Information Processing Systems. New York： Curran Associates Inc.， 2013： 3111-3119.

[10]MIKOLOV T， CHEN K， CORRADO G， et al. Efficient estimation of word representations in vector space [EB/OL]. [2019-05-20]. https：//arxiv.org/abs/1301.3781.

[11]GROVER A， LESKOVEC J. Node2vec： scalable feature learning for networks [C]// Proceeding of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2016： 855-864.

[12]YANG J， LESKOVEC J. Overlapping community detection at scale： a nonnegative matrix factorization approach [C]// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM， 2013： 587-596.

[13]WANG D， CUI P， ZHU W. Structural deep network embedding [C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Detection and Data Mining. New York： ACM， 2016： 1225-1234.

[14]LIAO L， HE X， ZHANG H， et al. Attributed social network embedding [J]. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（2）： 2257-2270.

[15]ZHANG D， YIN J， ZHU X， et al. User profile preserving social network embedding [C]// Proceedings of the 26th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2017： 3378-3384.

[16]RAHIMI A， RECHT B. Random features for large-scale kernel machines [C]// Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. New York： Curran Associates Inc.， 2008： 1177-1184.

[17]溫雯，黃家明，蔡瑞初，等.一種融合節點先驗信息的圖表示學習方法[J].軟件學報，2018，29（3）：786-798.（WEN W， HUANG J M， CAI R C， et al. Graph embedding by incorporating prior knowledge on vertex information [J]. Journal of Software， 2018，29（3）： 786-798.）

[18]YANG C， LIU Z， ZHAO D， et al. Network representation learning with rich text information [C]// Proceeding of the 24th International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2015： 2111-2117.

[19]HUANG X， LI J， HU X. Accelerated attributed network embedding [C]// Proceedings of the 2017 SIAM International Conference on Data Mining. Philadelphia： SIAM， 2017： 633-641.

[20]YANG Z， COHEN W W， SALAKHUTDINOV R. Revisiting semi-supervised learning with graph embeddings [C]// Proceeding of the 33rd International Conference on Machine Learning. New York： JMLR， 2016： 40-48.

[21]TU C， LIU H， LIU Z， et al. CANE： context-aware network embedding for relation modeling [C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics. Stroudsburg： Association for Computational Linguistics， 2017： 1722-1731.

[22]YANG H W， HSU H C， YANG C K， et al. Differentiating between morphologically similar species in genus Cinnamomum （Lauraceae） using deep convolutional neural networks [J]. Computers and Electronics in Agriculture， 2019， 162： 739-748.

[23]CHANG J， BLEI D M. Relational topic models for document networks [C]// Proceedings of the 12th International Conference on Artificial Intelligence and Statistics. Florida： PMLR， 2009： 81-88.

[24]GYAMFI K S， BRUSEY J， HUNT A， et al. A dynamic linear model for heteroscedastic LDA under class imbalance [J]. Neurocomputing， 2019， 343： 65-75.

[25]LE T M V， LAUW H W. Probabilistic latent document network embedding [C]// Proceedings of the 2014 IEEE International Conference on Data Mining. Piscataway： IEEE， 2014： 270-279.

[26]LI H， WANG H， YANG Z， et al. Variation autoencoder based network representation learning for classification [C]// Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics， Student Research Workshop. Stroudsburg： Association for Computational Linguistics， 2017： 56-61.

[27]李南星，盛益強，倪宏.基于LM算法的MLP模型及其應用[J].網絡新媒體技術，2018，7（1）：59-63.（LI N X， SHENG Y Q， NI H. A multilayer perceptron model based on Levenberg-Marquardt algorithm with its applications [J]. Journal of Network New Media， 2018， 7（1）： 59-63.）

[28]LUSSEAU D， SCHNEIDER K， BOISSEAU O J， et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations ： can geographic isolation explain this unique trait？ [J]. Behavioral Ecology and Sociobiology， 2003， 54（4）： 396-405.

This work is partially supported by the Special Fund for Strategic Pilot Technology of Chinese Academy of Sciences （XDC02070100）.

CHEN Wanjie， born in 1993， M. S. candidate. Her research interests include data mining， intelligent processing.

SHENG Yiqiang， born in 1978， Ph. D.， associate research fellow. His research interests include intelligent networking， data mining.

收稿日期：2019-06-14;修回日期：2019-09-10;錄用日期：2019-09-23。

基金項目：中國科學院戰略性科技先導專項課題（XDC02070100）。

作者簡介：陳婉杰（1993—），女，河南南陽人，碩士研究生，主要研究方向：數據挖掘、智能處理; 盛益強（1978—），男，北京人，副研究員，博士，主要研究方向：智能網絡、數據挖掘。

文章編號：1001-9081（2019）12-3467-09 DOI：10.11772/j.issn.1001-9081.2019061009