基于貢獻(xiàn)函數(shù)的重疊社區(qū)劃分算法

劉功申 孟 魁 郭弘毅 蘇 波 李建華

?

基于貢獻(xiàn)函數(shù)的重疊社區(qū)劃分算法

劉功申 孟 魁*郭弘毅 蘇 波 李建華

(上海交通大學(xué)電子信息與電氣工程學(xué)院 上海 200240)

現(xiàn)實(shí)世界中的網(wǎng)絡(luò)結(jié)構(gòu)呈現(xiàn)出重疊社區(qū)的特征。在研究經(jīng)典的標(biāo)簽算法的基礎(chǔ)上，該文提出基于貢獻(xiàn)函數(shù)的重疊社區(qū)發(fā)現(xiàn)算法。算法將每個(gè)節(jié)點(diǎn)用三元組(閾值、標(biāo)簽、從屬系數(shù))集合來表示。節(jié)點(diǎn)的閾值是每次迭代過程中標(biāo)簽淘汰的依據(jù)，該值由多元線性方程自動(dòng)計(jì)算而來。從屬系數(shù)用于衡量當(dāng)前節(jié)點(diǎn)與標(biāo)簽所標(biāo)識(shí)社區(qū)的相關(guān)度，從屬系數(shù)的值越大說明該節(jié)點(diǎn)與標(biāo)簽所標(biāo)識(shí)社區(qū)的關(guān)聯(lián)性越強(qiáng)。在每一次迭代的過程中，算法依據(jù)貢獻(xiàn)函數(shù)計(jì)算每個(gè)節(jié)點(diǎn)的從屬系數(shù)，并生成新的三元組集合。然后依據(jù)標(biāo)簽決策規(guī)則淘汰標(biāo)簽，進(jìn)行從屬系數(shù)規(guī)范化。通過對(duì)真實(shí)的復(fù)雜網(wǎng)絡(luò)和LFR(Lancichinetti Fortunato Radicchi)自動(dòng)生成的網(wǎng)絡(luò)進(jìn)行測試可知，該算法的社區(qū)劃分準(zhǔn)確率高，而且劃分結(jié)果穩(wěn)定。

復(fù)雜網(wǎng)絡(luò)；社區(qū)發(fā)現(xiàn)；重疊社區(qū)

1 引言

經(jīng)典的社區(qū)發(fā)現(xiàn)算法假設(shè)某個(gè)節(jié)點(diǎn)僅僅屬于一個(gè)特定社區(qū)，這種假設(shè)顯然和現(xiàn)實(shí)不完全相符。在現(xiàn)實(shí)世界的復(fù)雜網(wǎng)絡(luò)系統(tǒng)中，存在一些節(jié)點(diǎn)同時(shí)屬于不同的社區(qū)，這便是所謂的重疊社區(qū)結(jié)構(gòu)[1]。針對(duì)重疊社區(qū)的挖掘問題，Palla等人[2]提出了針對(duì)重疊社區(qū)的派系過濾(Clique Percolation Method, CPM)算法，該算法將社區(qū)視作由一些互相連通的完全子圖構(gòu)成的集合。將節(jié)點(diǎn)數(shù)目為的完全子圖定義為-clique，當(dāng)兩個(gè)-clique之間擁有個(gè)公共節(jié)點(diǎn)時(shí)，則認(rèn)為這兩個(gè)-clique是相鄰的。自從Palla提出Clique概念以來，許多研究者便不斷嘗試提出新的基于Clique思想的社區(qū)發(fā)現(xiàn)算法[3]。

Gregory[4]在GN算法的基礎(chǔ)上提出了能發(fā)現(xiàn)重疊社區(qū)的CONGA (Cluster-Overlap Newman Girvan Algorithm)算法，其主要思想是將邊介數(shù)較高的節(jié)點(diǎn)再分裂成多個(gè)副本。對(duì)于分裂后的節(jié)點(diǎn)，采取經(jīng)典的社區(qū)發(fā)現(xiàn)算法進(jìn)行挖掘社區(qū)結(jié)構(gòu)。由于某些節(jié)點(diǎn)在算法運(yùn)行過程中分裂成多個(gè)副本，這些副本在后續(xù)運(yùn)行過程中可能被劃分到不同的社區(qū)，并最終實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)可以同時(shí)屬于多個(gè)社區(qū)的目的。

文獻(xiàn)[5]采用了非負(fù)矩陣分解來發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu)，采用非負(fù)矩陣分解在重疊社區(qū)發(fā)現(xiàn)任務(wù)上具有很好的準(zhǔn)確性和良好的解釋性。文獻(xiàn)[6]提出了基于非負(fù)矩陣分解的圖規(guī)范化方法，在該方法中使用了能反映節(jié)點(diǎn)間相似度的度量方法，實(shí)驗(yàn)證明這種方法能提高社區(qū)劃分的準(zhǔn)確度。文獻(xiàn)[7]提出了一種基于非負(fù)矩陣的半監(jiān)督社區(qū)劃分方法，該方法利用了標(biāo)簽的先驗(yàn)知識(shí)進(jìn)行訓(xùn)練，在劃分工程中歸并標(biāo)簽。

Raghavan等人[8]提出的基于標(biāo)簽傳播的社區(qū)發(fā)現(xiàn)算法(Label Propagation Algorithm, LPA)具有非常好的時(shí)間復(fù)雜度，這促使Gregory[9]將LPA算法從非重疊社區(qū)拓展到了重疊社區(qū)，提出了基于標(biāo)簽傳播的重疊社區(qū)發(fā)現(xiàn)算法。Gregory的算法[9]繼承了傳統(tǒng)標(biāo)簽的優(yōu)秀的時(shí)間復(fù)雜度指標(biāo)，在不同的網(wǎng)絡(luò)數(shù)據(jù)上具有較好的測試結(jié)果。但是，該算法也具有明顯的劣勢(shì)：(1)繼承了傳統(tǒng)標(biāo)簽傳播算法的缺點(diǎn)—隨機(jī)性。(2)算法執(zhí)行時(shí)需要事先設(shè)置參數(shù)，而且的不同取值對(duì)算法的結(jié)果影響非常大。但如何選擇合適的值是個(gè)難題。

本文在分析現(xiàn)有算法的基礎(chǔ)上，提出基于貢獻(xiàn)函數(shù)的重疊社區(qū)劃分標(biāo)簽傳播算法(Overlapping- Communities Recognition Algorithm based on Contribution Function, OCRA-CF)。通過引入貢獻(xiàn)函數(shù)，克服了Gregory算法的隨機(jī)行為，使算法結(jié)果更加穩(wěn)定。同時(shí)能夠自動(dòng)計(jì)算各個(gè)節(jié)點(diǎn)的閾值，避免了Gregory所提算法中值選擇問題。此外，OCRA-CF還具有較好的擴(kuò)展性及并行計(jì)算優(yōu)勢(shì)。

2 算法設(shè)計(jì)

OCRA-CF算法的創(chuàng)新改進(jìn)在于：(1)為每個(gè)節(jié)點(diǎn)自動(dòng)計(jì)算閾值，該閾值反映了某個(gè)節(jié)點(diǎn)屬于多個(gè)社區(qū)的可能程度。(2)采用貢獻(xiàn)函數(shù)計(jì)算從屬系數(shù)。貢獻(xiàn)函數(shù)反映了鄰居節(jié)點(diǎn)的貢獻(xiàn)情況。(3)采用較穩(wěn)定的規(guī)則進(jìn)行標(biāo)簽淘汰，最大程度地提高了算法結(jié)果的穩(wěn)定性。

2.1重要函數(shù)

在每一次迭代的過程中，算法將決定每一個(gè)節(jié)點(diǎn)的所有鄰接點(diǎn)的標(biāo)簽以及該標(biāo)簽對(duì)下一輪的貢獻(xiàn)度。算法的核心由4個(gè)因素構(gòu)成：閾值計(jì)算、貢獻(xiàn)函數(shù)、從屬系數(shù)和選擇規(guī)則。在本文中，每個(gè)節(jié)點(diǎn)擁有獨(dú)特的閾值，并且實(shí)現(xiàn)了閾值的自動(dòng)計(jì)算。從屬系數(shù)都經(jīng)過規(guī)范化處理過程，某個(gè)節(jié)點(diǎn)的所有從屬系數(shù)的值相加為1。同樣地，貢獻(xiàn)函數(shù)的取值也經(jīng)過規(guī)范化處理，某個(gè)節(jié)點(diǎn)的貢獻(xiàn)函數(shù)的值相加也是1。最后，根據(jù)選擇規(guī)則來決策保留那些標(biāo)簽或者淘汰那些標(biāo)簽。

2.1.1閾值計(jì)算 每個(gè)節(jié)點(diǎn)的閾值和該節(jié)點(diǎn)可能所屬的社區(qū)數(shù)相關(guān)。事實(shí)上，節(jié)點(diǎn)的閾值就是該節(jié)點(diǎn)所屬社區(qū)數(shù)的倒數(shù)。因此，估算社區(qū)數(shù)是閾值計(jì)算的核心任務(wù)。但在未執(zhí)行完該社區(qū)劃分算法之前，不可能知道每個(gè)節(jié)點(diǎn)實(shí)際屬于幾個(gè)社區(qū)，因此，只能采用估算的方法來預(yù)測節(jié)點(diǎn)可能屬于幾個(gè)社區(qū)。本文提出了為每個(gè)節(jié)點(diǎn)估算所屬社區(qū)數(shù)量的方法，該方法主要包括估算社區(qū)度和計(jì)算社區(qū)數(shù)兩個(gè)步驟。

(1)估算社區(qū)度： 所謂社區(qū)度就是衡量節(jié)點(diǎn)屬于多個(gè)社區(qū)的可能程度。社區(qū)度是本文為每個(gè)節(jié)點(diǎn)計(jì)算的一個(gè)數(shù)值，該值越大說明該節(jié)點(diǎn)同時(shí)屬于多個(gè)社區(qū)的可能性就越大，反之亦然。

本文把經(jīng)典網(wǎng)絡(luò)的標(biāo)準(zhǔn)劃分結(jié)果作為先驗(yàn)知識(shí)，把每個(gè)節(jié)點(diǎn)的靜態(tài)特征數(shù)據(jù)作為后驗(yàn)知識(shí)，通過多元線性回歸模型擬合出估算社區(qū)數(shù)的方程。社區(qū)數(shù)估算函數(shù)為

(2)計(jì)算社區(qū)數(shù)： 計(jì)算社區(qū)數(shù)的工作就是根據(jù)已知的社區(qū)度估算出該節(jié)點(diǎn)可能同時(shí)屬于的社區(qū)數(shù)量。根據(jù)美國認(rèn)知科學(xué)家George的研究，人類短期記憶一般一次只能記住5~9個(gè)事物，也就是常說的“7加減2”原則。近年來對(duì)社區(qū)網(wǎng)絡(luò)的數(shù)據(jù)統(tǒng)計(jì)分析的結(jié)論也證實(shí)，現(xiàn)實(shí)社會(huì)中的自然人或者網(wǎng)絡(luò)中的虛擬人(即社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn))盡管有較多的圈子存在，但短期內(nèi)頻繁交往的圈子數(shù)約為個(gè)?；诖耍疚陌衙總€(gè)節(jié)點(diǎn)可能屬于社區(qū)數(shù)的最大值定為9，并按節(jié)點(diǎn)的社區(qū)度為每個(gè)節(jié)點(diǎn)賦予區(qū)間上的整數(shù)值。

2.1.4標(biāo)簽決策 標(biāo)簽決策是標(biāo)簽選擇或淘汰的規(guī)則。在算法的每輪迭代中，對(duì)于每一個(gè)節(jié)點(diǎn)，需要按照一定的規(guī)則在集合中選擇標(biāo)簽或淘汰標(biāo)簽。

2.2參數(shù)擬合

2.3 算法流程

算法的整個(gè)流程包括4個(gè)步驟：計(jì)算網(wǎng)絡(luò)靜態(tài)特征值、計(jì)算閾值、節(jié)點(diǎn)賦初值和迭代過程。其中，迭代過程是算法的核心部分，同時(shí)也是時(shí)間復(fù)雜度最高的部分。

(1)計(jì)算網(wǎng)絡(luò)靜態(tài)特征值： 網(wǎng)絡(luò)靜態(tài)特征值是指節(jié)點(diǎn)的度(degree)、介數(shù)(betweenness)[10]、接近度(closeness)[11]、權(quán)威度(authority)[12]等。本文的實(shí)驗(yàn)部分使用這幾個(gè)參數(shù)完成了算法。作為對(duì)本文的擴(kuò)展，在實(shí)際工程中還可以增加其他參數(shù)，或者僅僅使用其中的部分參數(shù)。

(2)計(jì)算節(jié)點(diǎn)閾值： 通過式(1)和式(2)，為每個(gè)節(jié)點(diǎn)估算出社區(qū)數(shù)，那么，該節(jié)點(diǎn)的閾值()就是社區(qū)數(shù)的倒數(shù)。

(3)節(jié)點(diǎn)賦初始值： 迭代開始前為每個(gè)節(jié)點(diǎn)賦值一個(gè)標(biāo)簽，且從屬系數(shù)為1。每個(gè)節(jié)點(diǎn)初始狀態(tài)包含如下兩項(xiàng)內(nèi)容：(只包含一個(gè)三元組)和貢獻(xiàn)函數(shù)表。

(4)迭代過程： 每一輪迭代主要包括3項(xiàng)任務(wù)，即從屬系數(shù)計(jì)算、標(biāo)簽決策和終止條件判斷。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

在社區(qū)發(fā)現(xiàn)算法的研究領(lǐng)域中，有兩種方式對(duì)算法進(jìn)行評(píng)價(jià)。一種是使用現(xiàn)實(shí)世界的網(wǎng)絡(luò)數(shù)據(jù)集對(duì)算法進(jìn)行測試。由于真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性，任何劃分都不具有絕對(duì)的正確性，因此，需要通過一些社區(qū)評(píng)價(jià)指標(biāo)作為評(píng)價(jià)標(biāo)準(zhǔn)。典型的評(píng)價(jià)指標(biāo)包括經(jīng)典算法所提出的函數(shù)和Mod模塊度[13]等。實(shí)驗(yàn)采用了許多具有代表性和研究價(jià)值的真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集。其中包括著名的空手道俱樂部數(shù)據(jù)集(Karate_Club，簡稱Karate)、海豚網(wǎng)絡(luò)數(shù)據(jù)集(Dolphin_Social，簡稱Dolphin)、美國大學(xué)生職業(yè)足球聯(lián)盟數(shù)據(jù)集(American_Football，簡稱Football)、SNS數(shù)據(jù)集(Social_Community，簡稱S_C)、豆瓣數(shù)據(jù)集(Douban)、PGP數(shù)據(jù)集(PGP)、安然郵件系統(tǒng)數(shù)據(jù)集(Eron_mail，簡稱Eron)等。Z_follow是匿名發(fā)布者在北郵人(sns.byr.edu.cn)上的所有Follow節(jié)點(diǎn)組成的SNS網(wǎng)絡(luò)。Z_Friends是所有Follow的Follow節(jié)點(diǎn)形成的SNS網(wǎng)絡(luò)。根據(jù)數(shù)據(jù)提供者的說明，Z_Friends網(wǎng)絡(luò)的模塊度是0，也就是說，這個(gè)社區(qū)不存在小的社區(qū)結(jié)構(gòu)。Bupt是整個(gè)北郵人SNS網(wǎng)絡(luò)的所有節(jié)點(diǎn)形成的社區(qū)。

另一種方式是利用人工構(gòu)造數(shù)據(jù)集對(duì)算法進(jìn)行評(píng)價(jià)。在利用人工構(gòu)造數(shù)據(jù)集時(shí)，可以通過設(shè)定節(jié)點(diǎn)數(shù)、邊數(shù)、每個(gè)節(jié)點(diǎn)的平均度數(shù)、重疊度等控制變量來生成結(jié)構(gòu)固定的網(wǎng)絡(luò)。由于生成的網(wǎng)絡(luò)結(jié)構(gòu)固定，因此可以有針對(duì)性地對(duì)算法進(jìn)行評(píng)價(jià)。此外，還可以通過改變一到兩個(gè)構(gòu)造社區(qū)的參數(shù)變量，來針對(duì)性地測試算法的對(duì)不同網(wǎng)絡(luò)的適應(yīng)性。Lancichinetti等人[14]提出的LFR基準(zhǔn)程序是目前公認(rèn)的構(gòu)造人工網(wǎng)絡(luò)的程序。

3.2式(1)的參數(shù)估計(jì)

式(1)為典型的多元線性方程，本文采用多元線性回歸模型擬合該方程的參數(shù)。參數(shù)的估計(jì)過程主要包括：數(shù)據(jù)準(zhǔn)備和線性回歸過程。

(1)數(shù)據(jù)準(zhǔn)備： 國內(nèi)外科研人員對(duì)Karate, Football和Dolphins網(wǎng)絡(luò)進(jìn)行了充分研究，給出了公認(rèn)的劃分結(jié)果[15]。本文基于這些公認(rèn)的劃分結(jié)果，每個(gè)節(jié)點(diǎn)準(zhǔn)備一個(gè)標(biāo)準(zhǔn)值，并設(shè)計(jì)了一個(gè)算法來計(jì)算該值。該算法主要由以下3個(gè)部分組成：

(a)節(jié)點(diǎn)連接的社區(qū)數(shù)： 節(jié)點(diǎn)和社區(qū)的連接定義為：“如果節(jié)點(diǎn)和社區(qū)中的任意節(jié)點(diǎn)有邊相連，則稱節(jié)點(diǎn)和社區(qū)有連接”。根據(jù)標(biāo)準(zhǔn)的社區(qū)劃分，能方便地統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)分別和多少社區(qū)有連接(記為)。

(c)指向差異： 指向差異是指某個(gè)節(jié)點(diǎn)和多個(gè)社區(qū)連接情況的差異度量。對(duì)于節(jié)點(diǎn)而言，如果該節(jié)點(diǎn)和個(gè)社區(qū)有連接，且分別有條邊連接到社區(qū)。當(dāng)無明顯差異時(shí)，更傾向于被當(dāng)作個(gè)社區(qū)的橋接點(diǎn)，也就是重疊節(jié)點(diǎn)。反之，當(dāng)差異較大時(shí)，更傾向于被劃分到值較大的那個(gè)社區(qū)，也就是說不是重疊節(jié)點(diǎn)。圖1(a)圖和圖1(c)的節(jié)點(diǎn)都傾向于作為社區(qū)的節(jié)點(diǎn)，而圖1(b)的節(jié)點(diǎn)更傾向于作為和的橋接點(diǎn)。

圖1 指向差異示意圖

因此，指向差異的計(jì)算表示為

最后，綜合上述3部分指標(biāo)，每個(gè)節(jié)點(diǎn)的參考值計(jì)算公式為

(2)多元線性回歸： Karate, Football和Dolphins網(wǎng)絡(luò)標(biāo)準(zhǔn)劃分參見文獻(xiàn)[15]。靜態(tài)值的計(jì)算方法同2.3節(jié)。由于數(shù)據(jù)太多，表1僅給出了3個(gè)網(wǎng)絡(luò)的部分參數(shù)(分別給出了5個(gè)節(jié)點(diǎn)的數(shù)據(jù))，其他節(jié)點(diǎn)的數(shù)據(jù)略去。根據(jù)表1的數(shù)據(jù)，可以把式(1)的參數(shù)確定下來：

(8)

3.3式(4)的參數(shù)估計(jì)

估算數(shù)據(jù)時(shí)，使用了人工生成網(wǎng)絡(luò)作為標(biāo)準(zhǔn),數(shù)據(jù)集是由Lancichinetti等人[14]開發(fā)的LFR基準(zhǔn)程序生成的人工數(shù)據(jù)集。表2中代表節(jié)點(diǎn)數(shù)；代表網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度數(shù)；代表節(jié)點(diǎn)的最大度數(shù)；代表最小的社區(qū)規(guī)模，代表最大的社區(qū)規(guī)模；代表構(gòu)成這個(gè)網(wǎng)絡(luò)的混合參數(shù)。值越大，網(wǎng)絡(luò)內(nèi)部的社區(qū)結(jié)構(gòu)將越不明顯。我們生成了4類人工網(wǎng)絡(luò)用作參數(shù)估計(jì)：(1)小網(wǎng)絡(luò)小社區(qū)；(2)小網(wǎng)絡(luò)大社區(qū)；(3)大網(wǎng)絡(luò)小社區(qū)；(4)大網(wǎng)絡(luò)大社區(qū)。

表1標(biāo)準(zhǔn)網(wǎng)絡(luò)的靜態(tài)特征值列表(部分)

網(wǎng)絡(luò)節(jié)點(diǎn)度介數(shù)接近度權(quán)威度式(4)值 Karate1160.4376352810.5689655170.0714127290.066131548 290.0539366880.4852941180.0534272310.283107528 3100.1436568060.5593220340.0637190652.226199031 460.0119092710.4647887320.0424227370.270443437 530.0006313130.3793103450.015260960.520041765 Dolphin160.0190825960.3465909090.0228330682.750868499 280.2133244360.3719512200.0074762740.650780668 340.0090728120.2824074070.0070642181.187597919 430.0023737970.3080808080.0140965461.850075725 5100.2489795920.0052039120.822860534 Football1120.0324899490.4237918220.0100923242.032694610 2120.0176211130.4130434780.0091323661.626829027 3120.0131224970.4071428570.0110170181.539988579 4120.0230700990.4206642070.0100686271.626829027 5110.0106638690.4028268550.0095893771.753784351

項(xiàng)目小網(wǎng)絡(luò)小社區(qū)小網(wǎng)絡(luò)大社區(qū)大網(wǎng)絡(luò)小社區(qū)大網(wǎng)絡(luò)大社區(qū) N1000100050005000 K20202020 maxk50505050 minc10201020 maxc5010050100 mu0.1~0.90.1~0.90.1~0.90.1~0.9

圖2 獨(dú)立參數(shù)運(yùn)行情況

3.4真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集測試

(1)準(zhǔn)確性評(píng)價(jià)： 對(duì)于真實(shí)網(wǎng)絡(luò)構(gòu)成的數(shù)據(jù)集，采用社區(qū)結(jié)構(gòu)參數(shù)評(píng)價(jià)算法結(jié)果的好壞。本文主要采用適用于重疊社區(qū)發(fā)現(xiàn)結(jié)果的評(píng)價(jià)函數(shù)Mod進(jìn)行算法結(jié)果的評(píng)估。

本文算法(OCRA-CF)是在傳統(tǒng)標(biāo)簽算法的基礎(chǔ)上改進(jìn)而來，盡管通過貢獻(xiàn)度函數(shù)大大降低了算法的不穩(wěn)定性，但還是保留了一定的標(biāo)簽算法固有的不穩(wěn)定性與隨機(jī)性。在針對(duì)真實(shí)數(shù)據(jù)集測試的過程中，本文在同一個(gè)數(shù)據(jù)集上先后運(yùn)行了10次算法。其中Mod值和社區(qū)數(shù)都是平均值。

經(jīng)與Karate, Dolphin和football數(shù)據(jù)集公認(rèn)的劃分結(jié)果進(jìn)行比對(duì)，OCRA-CF算法的社區(qū)劃分結(jié)果基本正確，幾乎沒有節(jié)點(diǎn)被錯(cuò)誤劃分。而對(duì)于大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)集，從表3中的Mod一列可以看出OCRA-CF算法的運(yùn)行結(jié)果也較為理想。Douban的數(shù)據(jù)來自于互聯(lián)網(wǎng)，節(jié)點(diǎn)之間的關(guān)聯(lián)度非常低，其社區(qū)結(jié)構(gòu)幾乎為0。Z_friends的數(shù)據(jù)也是沒有節(jié)點(diǎn)之間連接的數(shù)據(jù)，其社區(qū)結(jié)構(gòu)是0，符合數(shù)據(jù)發(fā)布者對(duì)數(shù)據(jù)的特征說明。

表3 OCRA-CF算法在不同數(shù)據(jù)集上的運(yùn)行情況

(2)橫向比較： 同樣使用上述的測試數(shù)據(jù)集，我們將OCRA-CF算法與幾個(gè)經(jīng)典算法進(jìn)行了對(duì)照測試，結(jié)果展示如表4和表5所示，其中，Gregory為文獻(xiàn)[9]的算法。

在表4中，OCRA-CF, CPM, Gregory和CFinder算法采用Mod作為評(píng)價(jià)指標(biāo)，而GN，Newman采用Q函數(shù)作為評(píng)價(jià)指標(biāo)，LFM采用EQ評(píng)價(jià)。表中的OUT表示該算法在24 h內(nèi)無法完成該數(shù)據(jù)的計(jì)算過程。從表4的數(shù)據(jù)可以看出，本文提出的OCRA-CF算法在各個(gè)數(shù)據(jù)集上表現(xiàn)都非常好。

在表5中，主要進(jìn)行運(yùn)行速度的比較，時(shí)間參數(shù)為s，從表中的結(jié)果可以看出，本文提出的OCRA- CF算法在各種數(shù)據(jù)集上的時(shí)間都較為理想。LFM算法在部分?jǐn)?shù)據(jù)集上也表現(xiàn)出了異常優(yōu)越的效果，但也有些數(shù)據(jù)的效果非常差，非常不穩(wěn)定。

總之，OCRA-CF的優(yōu)勢(shì)主要有兩點(diǎn)：(1)時(shí)間復(fù)雜度低。經(jīng)典算法對(duì)于大型的數(shù)據(jù)集，都無法在實(shí)驗(yàn)允許的時(shí)間內(nèi)(這里設(shè)為24 h)得到社區(qū)發(fā)現(xiàn)結(jié)果。(2)社區(qū)劃分的模塊度適中。在各種數(shù)據(jù)集上都能獲得較好的模塊度評(píng)價(jià)指標(biāo)。

3.5人工數(shù)據(jù)集測試

用LFR基準(zhǔn)程序所產(chǎn)生的人工網(wǎng)絡(luò)擁有可控制的社區(qū)結(jié)構(gòu)的，因此可以用來對(duì)算法的劃分準(zhǔn)確度進(jìn)行測試。NMI是評(píng)價(jià)標(biāo)準(zhǔn)的社區(qū)結(jié)構(gòu)和算法輸出的劃分結(jié)構(gòu)之間的相似度的定量指標(biāo)。由于考慮到構(gòu)造的數(shù)據(jù)集要有相當(dāng)?shù)囊?guī)模才能具有測試的代表性，而GN或者CPM算法處理幾千節(jié)點(diǎn)的數(shù)據(jù)集時(shí)要耗費(fèi)很長時(shí)間，因此本文采用算法復(fù)雜度相對(duì)較低的LFM算法與CFinder算法作為比較對(duì)象。

在對(duì)比實(shí)驗(yàn)中，使用表2所列的參數(shù)生成了4組人工網(wǎng)絡(luò)。在結(jié)果的展示中，OCRA-CF算法、CFinder和LFM算法都取10次重復(fù)實(shí)驗(yàn)的最佳結(jié)果進(jìn)行比較。算法運(yùn)行結(jié)果所得的NMI如圖3所示。各個(gè)圖中的縱坐標(biāo)是NMI值，橫坐標(biāo)是的值。4個(gè)圖的網(wǎng)絡(luò)屬性分別為：(a)小網(wǎng)絡(luò)/小社區(qū)；(b)小網(wǎng)絡(luò)/大社區(qū)；(c)大網(wǎng)絡(luò)/小社區(qū)；(d)大網(wǎng)絡(luò)/大社區(qū)。

表4 不同算法劃分結(jié)果的模塊度比較

表5不同算法的速度比較(s)

圖3 針對(duì)人工數(shù)據(jù)集的準(zhǔn)確度比較

4 結(jié)論

在現(xiàn)實(shí)的社會(huì)網(wǎng)絡(luò)中，社區(qū)結(jié)構(gòu)重疊是普遍存在的現(xiàn)象，因此，面向重疊社區(qū)的自動(dòng)發(fā)現(xiàn)算法具有重要的研究意義和使用價(jià)值。本文提出的基于貢獻(xiàn)函數(shù)的重疊社區(qū)發(fā)現(xiàn)算法，即OCRA-CF算法，既繼承了傳統(tǒng)標(biāo)簽算法的速度優(yōu)勢(shì)，又能達(dá)到較好的劃分效果。通過在各種人工構(gòu)造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的進(jìn)行測試，可以看出OCRA-CF運(yùn)行結(jié)果較為理想，達(dá)到了可用的目標(biāo)。在實(shí)際工作中，本文算法具還有兩大優(yōu)勢(shì)：(1)由于OCRA-CF是基于經(jīng)典標(biāo)簽算法的改進(jìn)，所以，該算法能比較方便地移植到Hadoop或Spark等并行計(jì)算平臺(tái)，以適應(yīng)社交網(wǎng)絡(luò)的大數(shù)據(jù)需求。(2)OCRA-CF算法中使用的貢獻(xiàn)函數(shù)具有較強(qiáng)的擴(kuò)展性，可以通過調(diào)整采用的網(wǎng)絡(luò)參數(shù)多少以及參數(shù)對(duì)應(yīng)的權(quán)重獲得不同的貢獻(xiàn)函數(shù)，適應(yīng)不同的應(yīng)用場景。

[1] WANG Xiaofeng, LIU Gongshen, PAN Li,. Uncovering fuzzy communities in networks with structural similarity[J]., 2016, 210(1): 26-33.

[2] PALLA G, DERENVI I, FARKAS I,. Uncovering the overlapping community structure of complex networks in nature and society[J]., 2005, 435(7043): 814-818.

[3] LEE C, REID F, McDAID A,. Detecting highly overlapping community structure by greedy clique expansion [C]. ACM International Conference on Paper Presented at SNA-KDD Workshop, Washington DC, USA, 2010. arXiv: 1002.1827.

[4] GREGORY S. An algorithm to find overlapping community structure in networks[J]. LNCS, 2007, 4702(12): 91-102.

[5] SHI Xiaohua. Community detection in social network with pair wisely constrained symmetric non-negative matrix factorization[C]. Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, 2015: 541-546.

[6] LIU Xiao, WEI Yiming, WANG Jian,. Community detection enhancement using no-negative matrix factorization with graph regularization[J]., 2016, 30(20): 1650130.

[7] WANG Zhaoxian, WANG Wenjun, XUE Guixiang,. Semi-supervised community detection framework based on non-negative factorization using individual labels[C], The Sixth International Conference on Swarm Intelligence, Beijing, China, 2015, 349-359

[8] RAGHAVAN U N, ALBERT R, and KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J].&, 2007, 76(3 Pt 2): 036106.

[9] GREGORY S. Finding overlapping communities in networks by label propagation[J]., 2009, 12(10): 2011-2024.

[10] ULRIK B. A faster algorithm for betweenness centrality[J]., 2001, 25(2): 163-177.

[11] EPPSTEIN D and WANG J. Fast approximation of gentrality[J]., 2004, 8(1): 39-45.

[12] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J].(), 1999, 46(5): 604-632.

[13] NICOSIA V, MANGIONI G, CARCHIOLO V,. Extending the definition of modularity to directed graphs with overlapping communities[J].&, 2009, 2009(3): 3166-3168.

[14] LANCICHINETTI A, FORTUNATO S, and RADICCHI F. Benchmark graphs for testing community detection algorithms[J].&, 2008, 78(2): 046110.

[15] CAO Xiaochun, WANG Xiao, JIN Di,. Identifying overlapping communities as well as hubs and outliers via nonnegative matrix factorization[J]., 2013, 03: 2993. doi: 10.1038/srep02993.

Overlapping-communities Recognition Algorithm Based on Contribution Function

LIU Gongshen MENG Kui GUO Hongyi SU Bo LI Jianhua

(,,200240,)

Overlapping is one of the most important characteristics of real-world networks. Based on the classic labeling algorithm, the overlapping-community orientated label propagation algorithm based on contribution function is proposed. In this algorithm, each node is indicated by a set of triples (threshold, label, and coefficient). The threshold value of every node is used as a metric for labels decision, which is calculated automatically by multiple linear regression equation. The dependent coefficient is used to measure the relevance of the current node with the correspondent community which is marked by the label. A greater value of dependent coefficient means a stronger association between the node and the community. During each iteration process, the dependent coefficients are calculated through Contribution Function (CF) of each node, and new triples are produced. Then the labels in terms of decision rules are selected, and the dependent coefficients of the node are normalized. According to the tests with real-world networks and automatic generation of LFR (Lancichinetti Fortunato Radicchi) test network, the algorithm can divide communication with high accuracy and robust result.

Complex networks; Communities detecting; Overlapping communities

TP309

A

1009-5896(2017)08-1964-08

10.11999/JEIT161109

2016-10-18；

改回日期：2017-04-24；

2017-05-26

孟魁 mengkui@sjtu.edu.cn

國家973關(guān)鍵技術(shù)研究項(xiàng)目(2013CB329603)，國家自然科學(xué)基金(61472248)

The National 973 Key Basic Research Program of China (2013CB329603), The National Natural Science Foundation of China (61472248)

劉功申： 男，1974年生，副教授，研究方向?yàn)閮?nèi)容安全、自然語言理解.

孟 魁： 女，1973年生，高級(jí)工程師，研究方向?yàn)橐苿?dòng)安全、數(shù)據(jù)安全和社會(huì)網(wǎng)絡(luò).

郭弘毅： 男，1992年生，碩士生，研究方向?yàn)橥扑]系統(tǒng)研究.

蘇 波： 男，1971年生，副研究員，研究方向?yàn)樯鐣?huì)網(wǎng)絡(luò)分析.

李建華： 男，1965年生，教授、博士生導(dǎo)師，研究方向?yàn)殡娮优c通信工程、信息安全.