基于隨機游走的改進標簽傳播算法

鄭文萍，岳香豆，楊 貴

（1.山西大學計算機與信息技術(shù)學院，太原 030006；2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原 030006）

（?通信作者電子郵箱wpzheng@sxu.edu.cn）

0 引言

在現(xiàn)實生活中，網(wǎng)絡無處不在。例如，在社會學中網(wǎng)絡表示人與人之間的關(guān)系［1］；在生物學中網(wǎng)絡可以用于研究生物體內(nèi)的代謝過程［2-3］；除此之外，網(wǎng)絡還在物理學［4］、醫(yī)學［5］、信息科學等方面都有很廣泛的應用。網(wǎng)絡可以被建模為圖，圖中的節(jié)點表示系統(tǒng)中的各個實體，而邊表示為實體間的關(guān)系。真實世界網(wǎng)絡通常由一系列功能模塊組成，具有很復雜的連接模式，其具有的一個非常重要的潛在特征是社區(qū)結(jié)構(gòu)（community structure）。通常情況下，網(wǎng)絡中的社區(qū)內(nèi)部的節(jié)點間連接較為緊密，而社區(qū)間節(jié)點的連接相對稀疏［6］。社區(qū)發(fā)現(xiàn)算法可以對網(wǎng)絡中的社區(qū)進行識別，將網(wǎng)絡分成不同的功能單元，以便于更好地揭示網(wǎng)絡的隱藏結(jié)構(gòu)。它可以廣泛地應用于公眾情緒分析、用戶流失率預測、商品推薦等。

最近幾年，社區(qū)發(fā)現(xiàn)算法被廣泛地提出，引起了研究者們廣泛的興趣。研究者利用了生物學、物理學、社會科學、應用數(shù)學和計算機科學等不同學科的知識開發(fā)了很多社區(qū)檢測的算法［7］。根據(jù)求解策略的不同，可以將這些社區(qū)發(fā)現(xiàn)算法分為兩類：基于優(yōu)化的算法和基于啟發(fā)式的算法［8］。其中，基于優(yōu)化的算法是設(shè)置一個或多個目標函數(shù)，然后不斷地對這些目標函數(shù)進行優(yōu)化，直到得到最優(yōu)解，其代表性的方法是譜聚類方法［9］和模塊最大化方法。譜聚類的方法是將社區(qū)檢測問題轉(zhuǎn)化為優(yōu)化二項式的問題，通過拉普拉斯矩陣的特征值和特征向量來對網(wǎng)絡進行表示并對網(wǎng)絡進行近似最優(yōu)劃分?；谀K性最大化方法是將模塊性設(shè)為目標函數(shù)，并不斷地對模塊性進行優(yōu)化，直到模塊性達到最大值的方法，如Girvan-Newman（GN）算法［10］、快速Newman（Fast Newman，F(xiàn)N）算法［11］以及BGLL（Blondel VD，Guillaume JL，Lambiotte R and Lefebvre E）算法［12］等。

基于啟發(fā)式的方法是設(shè)置一個啟發(fā)式規(guī)則并利用這個規(guī)則來尋找社區(qū)的最優(yōu)分。Palla 等［13］在2005 年提出的派系過濾算法是啟發(fā)式方法中的一種代表性方法。2007 年，Raghavan 等［14］提出的標簽傳播算法（Label Propagation Algorithm，LPA）是社區(qū)發(fā)現(xiàn)算法中最快的算法之一。該算法受到流行病傳播的啟發(fā)，通過節(jié)點標簽的迭代傳播直到收斂來檢測社區(qū)。由于該算法具有線性的時間復雜度并且過程比較簡單，因此可以用于大型網(wǎng)絡的社區(qū)發(fā)現(xiàn)。LPA 首先給網(wǎng)絡中的每個節(jié)點賦予唯一的初始標簽，然后按照隨機產(chǎn)生的節(jié)點序列對節(jié)點進行遍歷，將鄰域中出現(xiàn)頻率最高的標簽作為當前節(jié)點的社區(qū)標簽，此過程迭代進行，直到所有節(jié)點的標簽達到穩(wěn)定。由于LPA 在社區(qū)劃分中存在隨機過程，使得劃分結(jié)果有很大的不穩(wěn)定性，現(xiàn)有很多方法對其進行了改進。為了找到重疊社區(qū)，提出了重疊社區(qū)傳播檢測算法（Community Overlap PRopagation Algorithm，COPRA）［15］和基于信息通信的LPA（Speaker-listener LPA，SLPA）算法［16］。除此之外，Barber 等［17］提出了一種基于模塊度優(yōu)化的LPA（modularity-specialized LPA，LPAm）來避免LPA 在運行過程中形成一個大的社區(qū)。LPAm 在LPA 中加入約束條件，通過設(shè)定目標函數(shù)來約束迭代傳播的過程，然后將社區(qū)模塊性值作為另一個目標函數(shù)，將社區(qū)檢測問題最終轉(zhuǎn)化為目標函數(shù)的優(yōu)化問題，但是在算法過程中，最終的結(jié)果可能會陷入局部極大值的情況。針對此問題，Liu 等［18］提出了LPAm+對LPAm進行改進，在LPAm 的基礎(chǔ)上加入了合并不同社區(qū)并使得模塊最大化的過程，使得算法可以重新達到一個最大局部極值。Li 等［19］提出了一種兩階段的標簽傳播算法LPA-S（Stepping community detection Algorithm based on Label Propagation）：在算法的第一階段對節(jié)點對之間的相似性進行計算，標簽在該節(jié)點鄰域內(nèi)相似性較大的節(jié)點間進行傳播，得到初始的社區(qū)劃分；在第二階段將初始劃分后的社區(qū)看為節(jié)點，并進行社區(qū)間相似性的計算，合并相似社區(qū)，最終所得社區(qū)具有最大的目標函數(shù)。鄭文萍等［20］在2018 年提出了一種基于標簽傳播的兩階段社區(qū)發(fā)現(xiàn)算法（Two-Stage community detection Algorithm based on Label Propagation，LPA-TS）：該方法定義了節(jié)點的參與系數(shù)，確定節(jié)點的更新順序，并在標簽傳播中根據(jù)節(jié)點的相似性來更新節(jié)點標簽，得到初始劃分；在第二階段按照參與系數(shù)來進行社區(qū)的合并，得到最終的社區(qū)劃分效果。宋琛等［21］在2016 年提出一種基于隨機游走相似度矩陣的改進標簽傳播算法，通過隨機游走得到節(jié)點的相似度矩陣，并在節(jié)點標簽更新時，按照相似度矩陣中概率來對節(jié)點的鄰居節(jié)點的標簽進行選擇和更新。在這些改進算法中，可以看出大部分算法都是只對標簽傳播算法的標簽更新規(guī)則進行改進，沒有考慮節(jié)點初始標簽和更新順序的隨機性對算法結(jié)果穩(wěn)定性的影響。本文將綜合考慮節(jié)點標簽的初始化和節(jié)點更新順序?qū)撕瀭鞑ニ惴ǖ挠绊憽?/p>

針對節(jié)點初始標簽和更新順序隨機性導致社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定的問題，本文提出了一種基于隨機游走的改進標簽傳播算法（improved Label Propagation Algorithm based on Random Walk，LPARW），減少了由于標簽更新順序的隨機性和在算法初始階段給每個節(jié)點都賦予標簽而導致的算法的不穩(wěn)定性。通過將LPARW 與經(jīng)典的社區(qū)發(fā)現(xiàn)算法在真實網(wǎng)絡數(shù)據(jù)集上進行實驗比較，發(fā)現(xiàn)LPARW 在標準互信息（Normalized Mutual Information，NMI）、調(diào)整蘭德系數(shù)（Adjusted Rand Index，ARI）、模塊性等方面都表現(xiàn)得比較好。

基于改進LPA的準確性與穩(wěn)定性，本文的主要工作如下：

1）通過計算隨機游走的位置概率分布來對節(jié)點重要性進行一個初始的度量。

2）引入了節(jié)點相似性的計算，在隨機游走的基礎(chǔ)上，確定了種子節(jié)點。

3）只給種子節(jié)點賦予標簽，通過特定的傳播規(guī)律來對種子節(jié)點的標簽在網(wǎng)絡中進行擴散，使得標簽傳播算法得到的社區(qū)劃分結(jié)果更加穩(wěn)定。

1 背景知識

用G=(V，E)來表示一個網(wǎng)絡圖，其中，V={v1，v2，…，vn}表示網(wǎng)絡中所有節(jié)點的集合，每個節(jié)點由vi表示，n表示網(wǎng)絡中的節(jié)點數(shù)；E={e1，e2，…，em}表示邊的集合，即為節(jié)點與節(jié)點之間的聯(lián)系。在集合E中的每條邊都在集合V中有一對節(jié)點與之對應。根據(jù)網(wǎng)絡中的邊是有向的還是無向的以及邊上是否有權(quán)重，可以將網(wǎng)絡分為加權(quán)有向圖、加權(quán)無向圖、無權(quán)有向圖以及無權(quán)無向圖。本文主要對無權(quán)無向圖進行研究。通常，使用鄰接矩陣An×n來對圖進行表示，其中：

無權(quán)無向圖的鄰接矩陣是對稱矩陣，即aij=aji。節(jié)點的度是復雜網(wǎng)絡中節(jié)點屬性的最重要的概念。一個節(jié)點的度即為與這個節(jié)點直接相連的節(jié)點的數(shù)量，而與這個節(jié)點直接相連的節(jié)點即為該節(jié)點的鄰域，即NG(vi)={vj|(vi，vj)∈E}。節(jié)點的相似性度量有很多種度量方法，可以大致地分為基于局部信息的節(jié)點相似性指標和基于全局的節(jié)點相似性指標。其中，在基于局部信息的節(jié)點相似性指標中最常用的是基于節(jié)點之間的公共鄰居來對節(jié)點的相似性進行度量，如公共鄰居（Common Neighbors，CN）指標、Salton 指標［22］和Jaccard 指標［23］等?；诠?jié)點之間公共鄰居相似性指標認為，任意兩個節(jié)點之間的相似性取決于其公共鄰居數(shù)，二者的公共鄰居越多，則它們就越相似，從而這兩個節(jié)點間有連邊的可能性也越大。

Jaccard 相似性是利用兩個節(jié)點之間的交集和并集的比例來定義的，比值越高，則證明這兩個節(jié)點有更高的相似性，由式（3）表示：

2 基于隨機游走的改進標簽傳播算法

基于標簽傳播算法的不穩(wěn)定性，本文提出了一種基于隨機游走的改進標簽傳播算法（LPARW），通過隨機游走得到的每個節(jié)點的到達概率即為節(jié)點的重要性，對重要性進行降序排序從而確定節(jié)點的標簽更新順序。根據(jù)節(jié)點標簽更新順序?qū)?jié)點進行遍歷，使用相似性公式對節(jié)點之間相似性進行計算，選擇出最終的種子節(jié)點，對每個種子節(jié)點賦予初始的標簽。最后，將剩余的節(jié)點進行標簽傳播得到最終的社區(qū)劃分結(jié)果。LPARW 通過確定節(jié)點的更新順序，減少了傳統(tǒng)的標簽傳播算法由于節(jié)點標簽更新順序的隨機性而導致的最終劃分結(jié)果的不確定性。傳統(tǒng)LPA在初始化階段對每個節(jié)點都賦予唯一的社區(qū)標簽，在標簽傳播過程中，一些重要節(jié)點的社區(qū)標簽可能會被覆蓋，進而導致社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定。為了改進此情況，本文算法LPARW 只對選擇出的種子節(jié)點賦予社區(qū)標簽，并在網(wǎng)絡中進行標簽傳播。由于種子節(jié)點對應網(wǎng)絡中的重要節(jié)點，其性能比較穩(wěn)定，因而也提高了社區(qū)發(fā)現(xiàn)結(jié)果的穩(wěn)定性。

2.1 種子節(jié)點的確定

在LPARW 中，考慮到LPA 選擇標簽時的隨機性，將每個節(jié)點賦予初始標簽進行傳播時會增強算法最后劃分的社區(qū)結(jié)果的隨機性，而且原始的LPA 中節(jié)點的標簽更新的次序是隨機的，會很大程度上影響社區(qū)劃分的最終結(jié)果。因此，在標簽初始化的過程中只為選擇的種子節(jié)點賦予標簽可以減少初始標簽的個數(shù)，也可以避免由于標簽更新順序不同而造成的社區(qū)劃分結(jié)果的不穩(wěn)定性，進而擴大有用標簽的影響力，提高社區(qū)發(fā)現(xiàn)的準確率。

馬爾可夫聚類（Markov CLustering，MCL）算法［24］是對隨機游走進行仿真。MCL 在復雜網(wǎng)絡中是一個動態(tài)的過程，游走者以一定的概率不斷從一個節(jié)點移動到另一個節(jié)點。根據(jù)隨機游走方法，如果一個節(jié)點作為隨機游走結(jié)束時到達的節(jié)點的概率越高，則意味著這個節(jié)點的影響力越大。LPARW 使用隨機游走最終的可能位置分布來衡量網(wǎng)絡中節(jié)點的重要性。在隨機游走的過程中，布朗粒子到達其鄰居節(jié)點的概率由式（4）來表示：

利用式（4）可得到節(jié)點的一步游走的概率分布矩陣。對每個節(jié)點多步隨機游走的可能概率分布進行疊加可得到網(wǎng)絡最終的隨機游走概率矩陣。若節(jié)點的概率分布越高，則證明該節(jié)點與更多的節(jié)點相似，而一個節(jié)點與越多的節(jié)點相似，則證明這個節(jié)點的重要性越大。每一步的位置分布概率可以由指示向量I和矩陣P的乘積表示。t步之后，游走者位置分布概率可由式（5）表示：

其中，I0為單位向量。將It進行降序排序，可得到更新序列。序列中越靠前的節(jié)點作為種子節(jié)點的可能性越大；相反，序列中越靠后的節(jié)點影響力越小，其作為種子節(jié)點的概率也越小。

將所有節(jié)點按照影響力大小進行排序，得到節(jié)點的更新序列。按照節(jié)點的更新序列對節(jié)點的標簽進行更新，可以減少原始LPA中由于更新序列的隨機性而導致的社區(qū)發(fā)現(xiàn)結(jié)果的不穩(wěn)定性。

基于種子節(jié)點的社區(qū)發(fā)現(xiàn)算法的缺點是需要提前確定種子的個數(shù)，而社區(qū)發(fā)現(xiàn)算法中，社區(qū)的個數(shù)往往都是未知的，因此種子節(jié)點的確定是非常困難的。LPARW 不需要提前確定種子的數(shù)量，該算法通過使用相似性度量來對節(jié)點的相似性進行度量從而確定最終的種子節(jié)點。在本文中使用節(jié)點的公共鄰居來對兩個節(jié)點的相似性進行度量：兩個節(jié)點的公共鄰居數(shù)越多，則這兩個節(jié)點結(jié)構(gòu)越相似，屬于同一個社區(qū)的可能性越大，這樣得到的劃分結(jié)果更符合原來的社區(qū)分布，而眾所周知，節(jié)點的度是刻畫單個節(jié)點屬性的最簡單而又最重要的概念之一［25］。無向網(wǎng)絡中節(jié)點的度被定義為與節(jié)點直接有邊連接的其他節(jié)點的數(shù)目。本文給出了節(jié)點之間計算相似性的計算公式，由式（6）表示。

其中：NG(vi)為節(jié)點vi的一階鄰居節(jié)點的集合；NG(vj)為節(jié)點vj的鄰居節(jié)點的集合；dvi為節(jié)點vi的度。

LPARW 中，遍歷節(jié)點更新序列，將當前節(jié)點與更新序列在其之前的節(jié)點進行相似性的計算：若當前節(jié)點與更新序列在其之前的某個節(jié)點是相鄰節(jié)點，且相似性指標小于閾值，如果該節(jié)點的標簽為空值，則將序列在其之前的節(jié)點選擇為種子節(jié)點；否則不選為種子節(jié)點。在Karate網(wǎng)絡中LPARW 選擇出的種子節(jié)點如圖1所示。

圖1 Karate網(wǎng)絡上得到的種子節(jié)點Fig.1 Seed nodes obtained on Karate network

2.2 標簽的更新策略

傳統(tǒng)的LPA在標簽更新過程根據(jù)其鄰域中標簽數(shù)量最多的標簽來更新自己的標簽。當鄰域中最大數(shù)量的標簽數(shù)有多個的時候，則隨機選擇一個標簽作為自己的標簽。這樣會使得標簽產(chǎn)生震蕩，導致社區(qū)發(fā)現(xiàn)結(jié)果的不穩(wěn)定性和隨機性，并且在原始的標簽傳播算法的初始階段每個節(jié)點都有標簽，在傳播過程中會導致不重要的標簽有可能會影響標簽傳播算法的最終的社區(qū)劃分的結(jié)果。

LPARW 將種子節(jié)點的節(jié)點標號作為種子節(jié)點的標簽，其余節(jié)點的標簽設(shè)為空值。在第一次的標簽傳播的過程中，根據(jù)當前節(jié)點的標簽和種子節(jié)點的鄰居節(jié)點的公共鄰域的個數(shù)以及該節(jié)點本身的度數(shù)來決定該節(jié)點是否接受種子節(jié)點的標簽，而不是像傳統(tǒng)的LPA將節(jié)點標簽的重要性考慮為相同的，由此可以減少標簽的隨機選擇而導致的最終劃分結(jié)果的不穩(wěn)定性。當節(jié)點鄰域內(nèi)滿足條件的種子節(jié)點只有一個時，則節(jié)點選擇該種子節(jié)點的標簽作為節(jié)點的標簽，若滿足條件的種子節(jié)點有多個時，則選擇出現(xiàn)次數(shù)最多的標簽作為節(jié)點的標簽。在對所有種子節(jié)點的一階鄰域標簽傳播完成后，剩余的標簽為空的節(jié)點根據(jù)公式進行標簽的更新。

2.3 算法描述

首先，將網(wǎng)絡中所有節(jié)點的標簽都賦為空值；然后，根據(jù)隨機游走生成的隨機序列對這個隨機序列進行降序排序，將該序列作為標簽傳播過程中節(jié)點標簽的更新序列。根據(jù)節(jié)點的更新序列來對節(jié)點進行遍歷。在遍歷過程中，將當前節(jié)點和在更新序列中位于當前節(jié)點前面的所有節(jié)點的公共鄰域的數(shù)量以及其本身的度進行相似性的比較，若有節(jié)點vi-1與當前節(jié)點vi是相鄰的節(jié)點且相似性大于選定的閾值，節(jié)點vi-1的標簽為空值時，則將節(jié)點vi-1選為種子節(jié)點并將其節(jié)點標號作為節(jié)點vi的標簽，依次循環(huán)，選出所有的種子節(jié)點并完成種子節(jié)點直接鄰域的標簽傳播過程。在第一次標簽更新完成后，對剩余標簽為空的節(jié)點按照原始的標簽傳播算法的更新標簽過程進行更新。以上標簽更新過程迭代進行，直到標簽達到穩(wěn)定。下面給出LPARW的社區(qū)發(fā)現(xiàn)過程。

算法1 基于隨機游走的改進標簽傳播算法。

輸入 網(wǎng)絡G=(V，E)，閾值λ；

輸出 網(wǎng)絡的劃分結(jié)果。

步驟1 根據(jù)馬爾可夫隨機游走，生成可能作為游走終止節(jié)點的概率分布矩陣，按照式（5）形成節(jié)點集合的降序序列B={i1，i2，…，in}。

步驟2 對1 ≤j≤n，令L(ij)={}；令t=1，seed={}。

步驟3t=t+1，j=1；如果t>n，轉(zhuǎn)步驟5。

步驟4j=j+1，如果j≥t，轉(zhuǎn)步驟3。

步驟4.1 若邊(it，ij)?E，則轉(zhuǎn)步驟4；

步驟4.2 根據(jù)式（6）計算節(jié)點it與節(jié)點ij的相似性，如果s(it，ij)<λ，則轉(zhuǎn)步驟4；

步驟4.3 如果ij∈seed，則令L(it) ∪{j}；

步驟4.4 如果ij∈seed且L(ij)={}，則令seed=seed∪{ij}，L(ij)={j}，L(it)=L(it) ∪{j}；

步驟4.5 如果ij∈seed且L(ij) ≠{}，則令L(it)=L(it)∪L(ij)；

步驟4.6 轉(zhuǎn)步驟4。

步驟5 若網(wǎng)絡中存在節(jié)點v有多個標簽，選擇其鄰域內(nèi)出現(xiàn)次數(shù)最多的標簽作為v的標簽。

步驟6 若網(wǎng)絡中存在標簽為空的節(jié)點v，按照式（6）計算v與種子集seed中相鄰節(jié)點相似性。若s(v，w) ≥λ，則令L(v)=L(v)∪L(w)。若有多個種子節(jié)點滿足條件，則選擇標簽出現(xiàn)次數(shù)最多的作為自己的標簽。如果對節(jié)點v不存在滿足條件的相鄰種子節(jié)點，則保持v的標簽為空。

步驟7 設(shè)當前網(wǎng)絡中標簽為空的節(jié)點集為-V。

步驟8 對-V中節(jié)點v，選擇其鄰居節(jié)點中出現(xiàn)次數(shù)最多的標簽作為v的標簽。重復此步驟，直到-V中節(jié)點的標簽不再變化，得到最終的社區(qū)劃分結(jié)果。

3 實驗與結(jié)果分析

實驗平臺是Intel Xeon CPU（3.10 GHz），32 GB 內(nèi)存，Windows 10 系統(tǒng)，所有算法均采用Python 實驗。為了驗證LPARW 的準確性和穩(wěn)定性，將LPARW 在Karate、Dolphin、Football、Polbooks、blogs、Router、rt_ksa、Router_views、PGP 等網(wǎng)絡上進行實驗，并與LPA、LPAm、LPAm+和LPA-S 等標簽傳播的經(jīng)典算法和改進算法進行比較。

3.1 評價指標

此處采用標準互信息（NMI）與調(diào)整蘭德系數(shù)（ARI）對有標簽的各算法在有標簽網(wǎng)絡上的社區(qū)發(fā)現(xiàn)結(jié)果進行評價。NMI被廣泛地用于檢測社區(qū)劃分結(jié)果的好壞。如果算法社區(qū)劃分的結(jié)果與真實社區(qū)結(jié)果非常接近，則它的值接近于1，否則NMI 的值接近于0。ARI 是基于兩個方法在相同的社區(qū)劃分下，節(jié)點相同的概率。對于一個有n個節(jié)點的集合V，B={B1，B2，…，Bk'}表示一個網(wǎng)絡劃分結(jié)果，A={A1，A2，…，Ak}表示網(wǎng)絡原始劃分。NMI和ARI的定義如式（7）和式（8）所示。

對于無標簽數(shù)據(jù)集，本文采用模塊性進行度量。模塊度是一種衡量社區(qū)劃分質(zhì)量的標準，其基本想法是將隨機網(wǎng)絡作為零模型，比較所發(fā)現(xiàn)社區(qū)的模塊度與零模型網(wǎng)絡模塊度的差異，差異越大則社區(qū)發(fā)現(xiàn)質(zhì)量越好。模塊度Q的定義如式（9）所示。

其中：aij表示鄰接矩陣中的元素，若節(jié)點i和節(jié)點j之間有連邊，則aij等于1，否則等于表示隨機網(wǎng)絡中節(jié)點i和節(jié)點j的連邊數(shù)的期望值。

3.2 結(jié)果分析

為了驗證LPARW 的性能，在空手道俱樂部（Zachary’s Karate Club）、海豚社交網(wǎng)絡（Dolphins Social Network）［26-27］、大學生足球網(wǎng)絡（American College Football Network）［28］和Polbooks 這4 個帶標簽的真實網(wǎng)絡和blogs、Router、rt_ksa、Router_views、PGP這5個無標簽的真實網(wǎng)絡上，與基于LPA改進的算法LPAm、LPAm+、LPA-S 和LPA-TS 等比較。數(shù)據(jù)集基本情況如表1所示。

表1 真實網(wǎng)絡數(shù)據(jù)集基本信息Tab.1 Basic information of real network datasets

由于標簽傳播算法社區(qū)發(fā)現(xiàn)結(jié)果不穩(wěn)定，因此將本文算法及對比算法在每個網(wǎng)絡上分別運行30 次，計算最終所得社區(qū)的NMI、ARI 和模塊度Q等評價指標的平均值作為最終算法性能，比較結(jié)果如表2 所示，其中K表示算法最終發(fā)現(xiàn)的社區(qū)個數(shù)。由于對比算法LPA、LPAm、LPAm+、LPA-S和LPA-TS等各次運行結(jié)果所得的社區(qū)個數(shù)相差較大，無法用具體值描述，表2中用“—”表示。

表2 給出了各個算法在有標簽的網(wǎng)絡數(shù)據(jù)集中的實驗對比結(jié)果。由表2 可以看出，在Karate 和Dolphins 網(wǎng)絡中，LPARW 的NMI 和ARI 值達到了1，即算法的社區(qū)發(fā)現(xiàn)結(jié)果與原始的劃分完全一致。同時，在其余兩個網(wǎng)絡中，LPARW 的NMI 和ARI 值也達到了最高，并且該算法發(fā)現(xiàn)的社區(qū)個數(shù)是非常穩(wěn)定的。因此可以看出，本文算法在有標簽的網(wǎng)絡數(shù)據(jù)集中表現(xiàn)良好。

表2 帶標簽真實網(wǎng)絡實驗結(jié)果對比Tab.2 Comparison of experiment results in labeled real networks

圖2 給出了本文算法在Karate 網(wǎng)絡上的劃分結(jié)果。由圖2可以看出，LPARW 將Karate網(wǎng)絡穩(wěn)定地劃分為兩個社區(qū)，這與原始的網(wǎng)絡劃分是一致的。該網(wǎng)絡是由34 個節(jié)點組成的，網(wǎng)絡中的節(jié)點表示俱樂部的所有成員，邊表示這些成員之間的關(guān)系?？梢钥闯觯琇PARW 的劃分結(jié)果與原始社區(qū)的標簽完全一致。

圖2 LPARW在Karate網(wǎng)絡上的劃分結(jié)果Fig.2 Division result of Karate network by LPARW

圖3 給出了本文算法LPARW 在Dolphins 網(wǎng)絡上的劃分結(jié)果。Dolphins是人們通過對新西蘭神奇灣的62只海豚進行長期的觀察而得到的網(wǎng)絡。其中，節(jié)點表示海豚，邊表示海豚之間的相互聯(lián)系。經(jīng)過長期觀察，海豚的活動群體分成兩個群體，并且每個群體在不同的活動范圍內(nèi)活動，所以Dolphins網(wǎng)絡有兩個社區(qū)，LPARW 可以穩(wěn)定地劃分出兩個社區(qū)。由圖3 可以看出，LPARW 算法的劃分結(jié)果與原始網(wǎng)絡的社區(qū)劃分結(jié)果是完全一致的。

圖3 LPARW在Dolphins網(wǎng)絡上的劃分結(jié)果Fig.3 Division result of Dolphins network by LPARW

圖4 給出了Polbooks 網(wǎng)絡的原始劃分，圖5 給出了本文算法在Polbooks 網(wǎng)絡上的劃分結(jié)果。Polbooks 網(wǎng)絡節(jié)點表示在Amazon 在線書店上銷售的與美國政治相關(guān)的圖書，邊表示兩本圖書是否被同一用戶購買過。這些圖書被分為3 類：“自由派”“保守派”和“中間派”。

圖4 Polbooks網(wǎng)絡原始的劃分結(jié)果Fig.4 Original division results of Polbooks network

圖5 LPARW在Polbooks網(wǎng)絡上的劃分結(jié)果Fig.5 Division result of Polbooks network by LPARW

圖6 給出了原始的Football 網(wǎng)絡的劃分結(jié)果。Football 網(wǎng)絡是美國高校代表隊參加2000 年的賽季比賽的比賽情況。其中，節(jié)點表示高校的橄欖球代表隊，若兩支球隊之間至少有過一次比賽的話，則這兩個球隊之間有一條邊。由于每個球隊屬于不同的聯(lián)盟，共有12 個聯(lián)盟，所以，F(xiàn)ootball 網(wǎng)絡會被劃分為12個不同的社區(qū)。

圖7 給出了LPARW 在Football 網(wǎng)絡上的社區(qū)劃分結(jié)果。由表2 可以看出，LPARW 相較其他的算法有更高的NMI 和ARI 值，該算法可以將網(wǎng)絡的社區(qū)穩(wěn)定地劃分為13 個不同的社區(qū)。LPARW 相較其他算法的劃分結(jié)果是最接近原始的劃分結(jié)果的。

表3 給出了LPARW 在5 個真實的沒有標簽的網(wǎng)絡上與其余5種LPA、LPAm、LPAm+、LPA-S、LPA-TS經(jīng)典算法在Q值上的對比?？梢詮谋? 中很明顯地看出，在大部分的數(shù)據(jù)集上，LPARW的Q值最高，且社區(qū)個數(shù)穩(wěn)定，算法性能最好。

圖6 Football網(wǎng)絡原始的劃分結(jié)果Fig.6 Original division results of Football network

圖7 LPARW在Football網(wǎng)絡上的劃分結(jié)果Fig.7 Division result of Football network by LPARW

表3 無標簽真實網(wǎng)絡Q值對比Tab.3 Comparison of Q value in unlabeled real networks

4 結(jié)語

本文提出了一種基于隨機游走的改進標簽傳播算法，由于考慮到在原始的標簽傳播中若給每個節(jié)點都分配標簽，會增加其余標簽對最終社區(qū)劃分結(jié)果的影響，增加算法的不穩(wěn)定性，所以LPARW 在標簽傳播過程的賦予初始標簽階段只給影響力大節(jié)點賦予標簽，然后對其余節(jié)點進行標簽的傳播，這樣會增加算法的穩(wěn)定性，優(yōu)化算法的最終社區(qū)劃分的結(jié)果。在確定影響力大的節(jié)點時，LPARW 使用了隨機游走和相似性指標。在生成更新序列時，LPARW 采用隨機游走，并對每個節(jié)點的可能概率分布進行疊加后生成更新序列，固定了節(jié)點標簽的更新順序。在對節(jié)點更新序列進行遍歷階段，確定了種子節(jié)點及種子節(jié)點直接鄰域的節(jié)點的標簽。將剩余的沒有標簽的節(jié)點進行遍歷并按照選擇鄰域節(jié)點的標簽的最大值來確定標簽。通過以上步驟，得到了最終的社區(qū)劃分結(jié)果。通過與經(jīng)典的社區(qū)發(fā)現(xiàn)算法LPA、LPAm、LPAm+、LPA-S和LPATS 等在4 個有標簽的真實網(wǎng)絡數(shù)據(jù)集以及5 個無標簽的真實網(wǎng)絡數(shù)據(jù)集上進行分析比較，實驗結(jié)果表明，本文算法在NMI、ARI和模塊度Q等方面的指標均優(yōu)于其余的經(jīng)典的標簽傳播社區(qū)發(fā)現(xiàn)算法，表明該算法有很好的社區(qū)劃分效果。在今后的工作中，對于該算法如何應用于重疊社區(qū)將進行進一步的研究。