鄭少強,趙中英,2,3,馮慧子,李 超,2

1(山東科技大學 計算機科學與工程學院,山東 青島 266590) 2(中國科學院 深圳先進技術研究院,廣東 深圳 518055) 3(桂林電子科技大學 廣西可信軟件重點實驗室,廣西 桂林 541004) E-mail:zyzhao@sdust.edu.cn或 lichao@sdust.edu.cn

1 引 言

社會網(wǎng)絡是指個體間交互形成相對穩(wěn)定的社會關系,這種關系通常被形式化表示成圖的形式,圖中節(jié)點表示個體,邊表示個體之間存在的某種聯(lián)系.社區(qū)是社會網(wǎng)絡最重要的組成單元結構,也是分析社會網(wǎng)絡規(guī)律、性能等方面重要的參考依據(jù).所謂社區(qū)發(fā)現(xiàn),是指把網(wǎng)絡中聯(lián)系緊密或具有相似特征的節(jié)點劃分為一個簇,即同一社區(qū)內部節(jié)點間鏈接稠密,不同社區(qū)之間的鏈接稀疏.研究網(wǎng)絡的社區(qū)結構有助于揭示網(wǎng)絡的組織結構、拓普信息等特性,具有十分重要的意義[1],因此,社會網(wǎng)絡中的社區(qū)發(fā)現(xiàn)引起學術界與產業(yè)界學者的廣泛關注[2-4].

目前,針對社區(qū)發(fā)現(xiàn)的研究方法層出不窮,依據(jù)采用的求解策略問題,可分為基于優(yōu)化的社區(qū)發(fā)現(xiàn)方法和基于啟發(fā)式的社區(qū)發(fā)現(xiàn)方法.基于優(yōu)化的方法是通過設置目標函數(shù)來實現(xiàn)社區(qū)劃分,代表性方法有譜方法和模塊性最大化方法[5-7]等;基于啟發(fā)式策略的方法是通過設置啟發(fā)式規(guī)則尋找最優(yōu)社區(qū)劃分,代表性算法有GN算法[8]和WH算法[9]等.此外像基于層次聚類的社區(qū)發(fā)現(xiàn)方法也能有效劃分社區(qū)結構,但這種方法一般具有較高的時間復雜度,不適用大規(guī)模網(wǎng)絡挖掘.2007年,Raghavan等人[10]提出一種基于標簽傳播的快速社區(qū)發(fā)現(xiàn)算法LPA(Label Propagation Algorithm),該算法具有線性的時間復雜度,在處理大規(guī)模網(wǎng)絡時具有較高的時間效率,并且不需要優(yōu)化預定義的目標函數(shù),預知社區(qū)數(shù)量等先驗知識,因此得到學者的廣泛關注.但LPA算法在更新節(jié)點標簽過程中存在不確定性,導致結果準確性和穩(wěn)定性常不能達到預期效果.目前不同學者對原始的LPA算法進行改進,其中LPAm[11]算法是一種帶約束的標簽傳播算法,它將LPA等價為一個優(yōu)化問題來發(fā)現(xiàn)社區(qū)結構;COPRA算法[12]可以通過標簽傳播發(fā)現(xiàn)重疊社區(qū)結構,COPRA算法為每個節(jié)點保留若干個社區(qū)標簽,并進行標簽傳播最終節(jié)點得到多個標簽節(jié)點信息;趙卓翔[13]等人對初始網(wǎng)絡的部分節(jié)點進行分析處理,并且從部分節(jié)點進行標簽傳播,在LPA算法的基礎上提高了社區(qū)發(fā)現(xiàn)質量,黃佳鑫[14]等人在節(jié)點重要性和影響力的基礎上對其標簽傳播的過程進行優(yōu)化,該方法雖然提高了社區(qū)發(fā)現(xiàn)的質量,但同時增加了算法運行時間.

本文主要工作是在標簽傳播算法基礎上,融合考慮節(jié)點度數(shù)和聚集系數(shù)對網(wǎng)絡節(jié)點的初始標簽進行分配,從而減少初始節(jié)點標簽分配數(shù)量,提高標簽傳播的穩(wěn)定性和社區(qū)發(fā)現(xiàn)質量,在此基礎上減少標簽傳播過程的迭代次數(shù).

2 相關工作

2.1 聚集系數(shù)概念

復雜網(wǎng)絡中,節(jié)點的聚集系數(shù)(Node Clustering Coefficient)是考慮節(jié)點的鄰居節(jié)點間關系緊密程度的重要參考依據(jù)之一,節(jié)點的聚集系數(shù)可以表示為該節(jié)點的所有鄰居節(jié)點間的實際連邊數(shù)與所有可能存在連邊數(shù)的比值.

一般地,假設在一個無向無權的復雜網(wǎng)絡中節(jié)點i的度為ki,表示節(jié)點i有k個鄰接點,而這些鄰接點之間所有可能存在的連邊數(shù)為k·(k-1)/2.如果節(jié)點i的鄰接點之間的實際連邊數(shù)為E(i),用CC(i)表示該節(jié)點的點聚集系數(shù),則表示為:

(1)

顯然,節(jié)點聚集系數(shù)反應了節(jié)點的鄰居節(jié)點之間的關系.聚集系數(shù)越大,說明節(jié)點近鄰之間的關系越密切,他們屬于同一個社區(qū)的概率也就越大,反之聚集系數(shù)越小則它們聯(lián)系越疏遠,屬于同一個社區(qū)的概率也越小.

2.2 標簽傳播基本思想

標簽傳播算法[10](Label Propagation Algorithm)是一種啟發(fā)式的算法,其啟發(fā)規(guī)則是不斷在節(jié)點及近鄰間傳遞標簽信息,經過多次迭代,屬于同一社區(qū)節(jié)點的標簽將趨于一致.其核心思想是給所有的節(jié)點標記唯一標簽,對每個節(jié)點,它的標簽代表所屬社區(qū),對節(jié)點進行標簽傳播的過程,即是對每個節(jié)點的標簽進行更新,其標簽選擇權主要取決于該節(jié)點的鄰居節(jié)點的標簽分布情況,選取鄰居節(jié)點標簽數(shù)最多的節(jié)點來更新自己節(jié)點的標簽,依次迭代直到所有節(jié)點的標簽不再發(fā)生變化,最終標簽相同的節(jié)點屬于同一個社區(qū),從而達到劃分社區(qū)目的.

2.3 標簽傳播步驟

1)網(wǎng)絡初始化階段,為網(wǎng)絡中每個節(jié)點分配唯一的標簽,表示該節(jié)點所屬的社區(qū)編號;

2)對圖中的所有節(jié)點以隨機的順序進行標簽的迭代更新.在每次迭代過程中,每個節(jié)點的標簽由其鄰居節(jié)點的標簽中數(shù)目最多的那個標簽來決定,如果鄰居節(jié)點中有數(shù)目相同的最多個標簽存在,則在這些數(shù)量相同的標簽中隨機選取一個作為該節(jié)點的標簽;

3)反復迭代,直到其所有節(jié)點都擁有鄰居節(jié)點中數(shù)目最多的標簽為止;

4)具有相同標簽的節(jié)點就可以歸在同一個社區(qū)中,完成社區(qū)劃分,算法結束.

3 LPA_D_CC算法

在社會網(wǎng)絡中,節(jié)點度被認為是重要的評價指標之一,它能夠直觀衡量節(jié)點在網(wǎng)絡中的重要性,一般來說,節(jié)點度數(shù)越大,說明節(jié)點在網(wǎng)絡中的重要性越明顯,其相鄰節(jié)點數(shù)越多,形成社區(qū)的概率越大.而在社會網(wǎng)絡中節(jié)點的鄰居節(jié)點之間的關系也同樣重要,如果一個節(jié)點與它鄰居節(jié)點之間可以形成穩(wěn)定的三角關系這說明節(jié)點之間存在緊密的聯(lián)系,且具有某種相同性質的可能性越大.

目前所做的工作中,大多數(shù)標簽傳播算法只考慮算法在標簽更新階段情況,未在網(wǎng)絡初始化過程中對節(jié)點的標簽進行處理,這種情況導致標簽傳播存在不穩(wěn)定因素.本文針對這一問題在網(wǎng)絡初始化階段對節(jié)點標簽賦值做一些改進措施,從而改善節(jié)點標簽傳播隨機性問題,同時減少傳播過程的迭代次數(shù),提高社區(qū)劃分的穩(wěn)定性和劃分質量.

3.1 主要思想及步驟

本文主要考慮標簽傳播初始階段,結合節(jié)點度數(shù)和聚集系數(shù)兩方面對初始化節(jié)點賦值進行處理.首先在給定網(wǎng)絡中計算節(jié)點度數(shù),并根據(jù)度數(shù)大小對節(jié)點進行排序.當節(jié)點度數(shù)相等時,分析節(jié)點的鄰居節(jié)點之間的關系,即聚集系數(shù)大小,根據(jù)兩個判定條件對網(wǎng)絡所有節(jié)點做影響力排序.然后對影響力高的節(jié)點,訪問該節(jié)點和它鄰居節(jié)點并將它們構成一個集合,對沒有訪問過的節(jié)點,繼續(xù)對影響力高的節(jié)點進行訪問,將它和它沒有被訪問過的鄰居節(jié)點構成集合,每個節(jié)點只能被訪問一次,依次訪問直到所有節(jié)點被訪問過為止,這樣構成若干個集合.對若干個集合內的節(jié)點賦相同標簽,集合之間標簽不同.根據(jù)網(wǎng)絡中已賦予的標簽節(jié)點進行標簽傳播,最終當所有節(jié)點標簽都擁有鄰居節(jié)點標簽數(shù)最大的標簽算法結束,標簽相同的節(jié)點屬于同一個社區(qū).該方法主要分為兩個階段,第一階段是網(wǎng)絡節(jié)點賦標簽的準備階段;第二階段是節(jié)點賦標簽和標簽傳播過程.

3.2 網(wǎng)絡節(jié)點準備階段

第一階段主要根據(jù)節(jié)點度數(shù)和聚集系數(shù)對網(wǎng)絡中節(jié)點影響力進行排序,并對所有節(jié)點劃分集合,為下一步的標簽傳播做準備.

算法1.基于度與聚集系數(shù)的節(jié)點影響力排序算法

輸入:網(wǎng)絡G(V,E)

輸出:網(wǎng)絡G的若干集合Si

1.網(wǎng)絡初始化G(V,E);

2.計算V(G)度數(shù)D(V)并排序

3.如果D(V)相等,根據(jù)節(jié)點聚集系數(shù)CC(V)排序;

4.FOR V IN S:

IF V 沒有被訪問過;

將 V 加入集合S中;

標記節(jié)點V;

FOR U IN V的鄰居節(jié)點:

IF U 沒有被訪問過:

將U加入集合S中;

標記加入過的節(jié)點U;

END

END

END

END

返回若干集合Si

3.3 社區(qū)劃分階段

第二階段是對網(wǎng)絡中所有節(jié)點賦標簽,對于若干個集合的節(jié)點,我們認為集合內節(jié)點在某方面具有相同的特性,將這些集合中的節(jié)點賦予相同標簽,利用標簽傳播原理根據(jù)每個節(jié)點鄰居的標簽數(shù)量決定自己標簽,依次迭代直到所有節(jié)點的標簽不再發(fā)生變化,完成社區(qū)劃分.

算法2.基于LPA的社區(qū)發(fā)現(xiàn)算法

輸入:若干個集合Si

輸出:網(wǎng)絡G的社區(qū)劃分

1.針對若干個集合Si;

2.將這些集合Si賦予不同標簽,集合中節(jié)點的標簽相同;

3.根據(jù)標簽傳播理論,對節(jié)點標簽進行傳播;

4.反復迭代直到節(jié)點標簽不再發(fā)生變化,算法結束;

5.標簽相同的節(jié)點屬于同一個社區(qū).

4 實驗結果與分析

4.1 實驗數(shù)據(jù)及運行環(huán)境

本文選用社會網(wǎng)絡中常用的四個數(shù)據(jù)集對算法進行分析驗證,實驗數(shù)據(jù)采取Mark Newman等人個人網(wǎng)頁上提供的網(wǎng)絡數(shù)據(jù)集,包括Karate club、Polbooks、Netscience和Power數(shù)據(jù)集.數(shù)據(jù)集詳細描述如下:

1)Karate Club空手道俱樂部網(wǎng)絡:Karate Club空手道俱樂部網(wǎng)絡數(shù)據(jù)集是Zachary用三年時間觀察了美國一所大學空手道俱樂部成員之間的關系構成的社會網(wǎng)絡.網(wǎng)絡中節(jié)點表示俱樂部成員,節(jié)點之間的連邊表示成員之間的朋友關系.該網(wǎng)絡包括34個節(jié)點、78條邊.

2)Polbooks:該數(shù)據(jù)集是V.Krebs從Amazon上銷售的美國政治相關書籍頁面上建立的網(wǎng)絡,網(wǎng)絡中的節(jié)點表示在Amazon在線書店上銷售的美國政治相關圖書,邊表示一定數(shù)量的讀者同時購買了這兩本書的情況.政治書籍網(wǎng)絡包括105個節(jié)點、441條邊.

3)Netscience:科學家共同作者網(wǎng)絡描述的是在網(wǎng)絡上科學家之間的合作關系,通過網(wǎng)絡上科學家合作實驗以及共同提出相關理論構成的關系網(wǎng)絡.網(wǎng)絡中節(jié)點表示網(wǎng)絡上的科學家,邊表示科學家之間的合作關系.該網(wǎng)絡是由1589個節(jié)點和2742條邊構成.

4)Power:美國西部地區(qū)電網(wǎng)拓撲數(shù)據(jù)集網(wǎng)絡,該網(wǎng)絡主要涉及美國西部地區(qū)發(fā)電設備之間的關系.網(wǎng)絡中的節(jié)點表示發(fā)電器、變壓器和變電站設備,網(wǎng)絡中的邊表示這些設備之間高壓輸電的關系.美國西部電網(wǎng)一共由4941個節(jié)點和6594條邊構成.

表1 實驗數(shù)據(jù)描述Table 1 Description of experimental data

所有實驗均運行于配置為AMD A4-3300M APU with Radeon(tm)HD Graphics 1.90GHz、2核處理器且內存為4GB的Windows機器上.算法均在pycharm 4.5環(huán)境上,用python2.7編程語言實現(xiàn).為避免實驗過程中偶然性的發(fā)生,我們取實驗運行100次的平均結果作為最終結果進行分析驗證.

4.2 評價指標

本文根據(jù)模塊度評價指標評價社區(qū)劃分情況,模塊度(Modularity)由Newman[15]等人提出,該度量是對于給定網(wǎng)絡的任意社區(qū)劃分都有一個評價值,以此判斷社區(qū)發(fā)現(xiàn)算法的優(yōu)劣.模塊度定義為社區(qū)內實際連接數(shù)目與對應隨機網(wǎng)絡同等連接情況下社區(qū)期望連接數(shù)目之差,用來定量地刻畫網(wǎng)絡中社區(qū)結構的優(yōu)劣,模塊度的形式化定義如下:

Q=∑i[eii-(ai)2]

(2)

其中,eii是節(jié)點在社區(qū)i內部的邊的權值所占的比例,ai表示與社區(qū)i中節(jié)點相關聯(lián)的所有邊的權值所占的比例,ai表示為:

(3)

其中,kv表示節(jié)點v的度,cv表示節(jié)點v所在的社區(qū),m表示網(wǎng)絡中總邊數(shù).模塊度Q的取值在0和1之間,Q值越接近1說明社區(qū)結構越明顯.

4.3 實驗結果

我們對改進的LPA_D_CC算法和原始的LPA算法在四種數(shù)據(jù)集上進行對比實驗,為驗證算法劃分質量和穩(wěn)定性等,我們從模塊度、迭代次數(shù)等方面進行分析與比較.

4.3.1 Karate數(shù)據(jù)集可視化效果

Karate數(shù)據(jù)集具有標準的社區(qū)劃分,其中34個成員節(jié)點主要分成以主管(節(jié)點0)和校長(節(jié)點32)為中心的兩個集合.我們將LPA算法和LPA_D_CC算法在Karate數(shù)據(jù)集上做可視化效果,如圖1所示,原始的LPA算法在社區(qū)劃分過程中并沒有合理地將這兩個主要節(jié)點作為影響力較大節(jié)點進行社區(qū)劃分,并分成四個社區(qū)集合.LPA_D_CC算法可以穩(wěn)定的將Karate數(shù)據(jù)集以節(jié)點0和32為中心劃分為兩個社區(qū),圖中不同顏色代表不同社區(qū).

圖1 Karate數(shù)據(jù)中的社區(qū)可視化Fig.1 Visualization of communities detected in Karate data

4.3.2 社區(qū)發(fā)現(xiàn)數(shù)量

為了驗證社區(qū)劃分的穩(wěn)定性,我們從社區(qū)劃分數(shù)量方面分析,如表2所示,原始LPA算法在社區(qū)劃分數(shù)量方面起伏較大,并隨著網(wǎng)絡規(guī)模增大方差變大,穩(wěn)定性效果差.LPA_D_CC算法社區(qū)劃分數(shù)量方面比較穩(wěn)定,社區(qū)數(shù)量變化浮動小,社區(qū)劃分數(shù)量的隨機性弱,表現(xiàn)出算法的穩(wěn)定性.

表2 社區(qū)數(shù)量對比Table 2 Quantitative comparison of communities

表3 迭代次數(shù)對比Table 3 Comparison of iterations

4.3.3 迭代次數(shù)

原始LPA算法在傳播過程中,每次迭代都可能面臨隨機選擇標簽情況,這將導致社區(qū)劃分結果不穩(wěn)定,盡量減少迭代次數(shù)能有效降低社區(qū)隨機性產生.原始LPA算法與本文提出的LPA_D_CC算法在社區(qū)劃分過程中的迭代次數(shù)對比結果如表3所示.從表3可以看出,LPA_D_CC算法在任何情況下的迭代次數(shù)都小于LPA算法,并且迭代次數(shù)變化幅度小,遠遠優(yōu)于原始LPA算法.

4.3.4 模塊度評價

為了驗證算法能夠降低隨機性造成模塊度較低的影響,本次實驗從模塊度變化范圍和平均模塊度方面做了分析.從表4可以看出,LPA算法雖然在少數(shù)情況下模塊度值要高于LPA_D_CC算法,但大部分時間LPA_D_CC算法模塊度值優(yōu)勢明顯.從平均模塊度(圖2)角度分析LPA_D_CC算法平均模塊度值都高于LPA算法,并且LPA_D_CC算法方差小,具有較好的穩(wěn)定性,顯著提高了社區(qū)劃分質量.

表4 模塊度對比Table 4 Comparison of modularity values

5 總結與展望

目前在復雜網(wǎng)絡中關于社區(qū)發(fā)現(xiàn)方面還有很多值得研究的問題,例如算法在大型數(shù)據(jù)集中社區(qū)發(fā)現(xiàn)質量和效率問題,社區(qū)本身的定義問題等等.傳統(tǒng)的標簽傳播算法需要給每個節(jié)點賦予不同的初始標簽,這導致傳播過程中時常存在不穩(wěn)定因素,影響社區(qū)劃分質量.本文提出的算法分為兩個階段,第一階段根據(jù)網(wǎng)絡中節(jié)點的度數(shù)和聚集系數(shù),對網(wǎng)絡中節(jié)點做影響力排序,并將影響力高的節(jié)點和它鄰居節(jié)點劃分一個集合,重復此步驟直到網(wǎng)絡被劃分為若干個集合,此時可以對網(wǎng)絡做一個粗劃分.第二階段對若干個集合賦標簽,并依靠標簽傳播算法進行調整得到最終的社區(qū)結構.實驗結果表明,本文提出的算法能有效減少迭代次數(shù),同時保證社區(qū)劃分的準確性和穩(wěn)定性,并且生成的社區(qū)質量模塊度指標優(yōu)于LPA算法.總體而言,所提出的LPA_D_CC算法有效解決了傳統(tǒng)LPA算法的魯棒性差等問題.在將來的工作中,我們將嘗試在異構網(wǎng)絡中對同一個節(jié)點賦多個標簽,旨在研究重疊社區(qū)發(fā)現(xiàn)等工作.

圖2 平均模塊度比較Fig.2 Comparison of the average modularity values