基于Monte-Carlo迭代求解策略的局部社區(qū)發(fā)現(xiàn)算法

李占利，李 穎，羅香玉，羅穎驍

（西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，西安 710600）

0 引言

人類社會和自然界里許多復(fù)雜系統(tǒng)都可以通過網(wǎng)絡(luò)加以描述，例如社會網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、生物網(wǎng)絡(luò)等［1-2］。一個典型的網(wǎng)絡(luò)由許多節(jié)點(diǎn)與節(jié)點(diǎn)之間的連邊構(gòu)成，其中節(jié)點(diǎn)代表復(fù)雜系統(tǒng)中不同的個體，邊代表個體間按照某種規(guī)則形成的關(guān)系。網(wǎng)絡(luò)的一個重要屬性是社區(qū)結(jié)構(gòu)［3-4］，Newman 等［5］把社區(qū)定義為網(wǎng)絡(luò)中的若干個內(nèi)部連接緊密的節(jié)點(diǎn)群組，節(jié)點(diǎn)與所在群組內(nèi)的節(jié)點(diǎn)連接緊密，與其他群組的節(jié)點(diǎn)連接稀疏。這些社區(qū)通常表示網(wǎng)絡(luò)內(nèi)個體間有意義的拓?fù)潢P(guān)系［6］，實(shí)際應(yīng)用中的社區(qū)發(fā)現(xiàn)在個性化推薦、信息傳播等方面具有重要的意義。

在一些應(yīng)用場景中，人們只關(guān)心特定節(jié)點(diǎn)所屬的社區(qū)［7］，因此局部社區(qū)發(fā)現(xiàn)受到眾多研究者的關(guān)注。與全局社區(qū)發(fā)現(xiàn)相比，它更關(guān)注局部的網(wǎng)絡(luò)結(jié)構(gòu)，能夠返回更加個性化的社區(qū)［8-9］。局部社區(qū)發(fā)現(xiàn)問題通常定義為：給定某一查詢節(jié)點(diǎn)，找到其所在的社區(qū)，該社區(qū)稱為目標(biāo)社區(qū)［10］。針對局部社區(qū)發(fā)現(xiàn)問題，目前已有大量算法，這類算法一般采用基于貪心策略［11］的逐步擴(kuò)張方式來發(fā)現(xiàn)目標(biāo)社區(qū)。初始化時社區(qū)僅包含查詢節(jié)點(diǎn)自身，然后每一步選擇一個新的節(jié)點(diǎn)加入社區(qū)中。在每一步中，都從社區(qū)鄰接節(jié)點(diǎn)集中選擇滿足某種約束條件且使目標(biāo)函數(shù)最大化的節(jié)點(diǎn)。其中約束條件一般要求社區(qū)質(zhì)量單調(diào)遞增，目標(biāo)函數(shù)一般用來表征候選節(jié)點(diǎn)加入后的社區(qū)質(zhì)量或社區(qū)鄰接節(jié)點(diǎn)（稱為候選節(jié)點(diǎn)集）與社區(qū)的緊密程度。在不同的算法中，無論社區(qū)質(zhì)量還是節(jié)點(diǎn)與社區(qū)間的緊密程度均有不同的定義方式。由于這類算法每一步都是基于貪心策略來選擇節(jié)點(diǎn)以擴(kuò)張社區(qū)，無法獲得整體最優(yōu)解。當(dāng)所有候選節(jié)點(diǎn)均不能滿足社區(qū)質(zhì)量單調(diào)遞增這一約束條件時，擴(kuò)張過程結(jié)束，未考慮到隨著節(jié)點(diǎn)后續(xù)的多次迭代加入而產(chǎn)生更好的解，算法過早停止迭代而致使查全率較低。

本文摒棄了依據(jù)目標(biāo)函數(shù)的最優(yōu)值來選取節(jié)點(diǎn)求得目標(biāo)局部社區(qū)的傳統(tǒng)思路，而采取Monte-Carlo 隨機(jī)策略［12］。賦予候選節(jié)點(diǎn)選擇概率并基于概率值隨機(jī)選擇節(jié)點(diǎn)來擴(kuò)張社區(qū)，從而能夠有效避免算法陷入局部最優(yōu)的不利情況；另外，由于隨機(jī)選擇節(jié)點(diǎn)的方式可能引入異質(zhì)節(jié)點(diǎn)，它們的存在會影響局部社區(qū)擴(kuò)張的方向，因此賦予已加入節(jié)點(diǎn)淘汰概率并基于概率值隨機(jī)淘汰節(jié)點(diǎn)，從而將局部社區(qū)發(fā)現(xiàn)的方向?qū)蜃罴选?/p>

本文的主要工作如下：

1）摒棄了現(xiàn)有局部社區(qū)發(fā)現(xiàn)算法所采用的基于貪心策略的逐步擴(kuò)張方式，提出基于Monte-Carlo 迭代求解的新策略。該策略在每輪迭代中隨機(jī)選擇節(jié)點(diǎn)加入，并隨機(jī)淘汰已加入節(jié)點(diǎn)，解決了因過早收斂無法獲得社區(qū)全部節(jié)點(diǎn)的問題。

2）提出并實(shí)現(xiàn)了一種基于Monte-Carlo 迭代求解策略的局部社區(qū)發(fā)現(xiàn)算法，該算法在社區(qū)擴(kuò)張階段根據(jù)對目標(biāo)函數(shù)的貢獻(xiàn)比例為所有候選節(jié)點(diǎn)賦予選擇概率；在節(jié)點(diǎn)淘汰階段根據(jù)節(jié)點(diǎn)間的相似度為已加入節(jié)點(diǎn)賦予淘汰概率。

3）在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集Karate［13］、Dolphin［14］和Citation［15］上，與局部緊密度擴(kuò)展（Local Tightness Expansion，LTE）算法［16］、Clauset 算法［17］、加權(quán)共同鄰居節(jié)點(diǎn)（Common Neighbors with Weighted Neighbor Nodes，CNWNN）算法［18］、模糊相似關(guān)系（FSR）算法［19］進(jìn)行對比，實(shí)驗(yàn)的結(jié)果表明，本文算法性能相較于傳統(tǒng)算法有大幅提升。

1 相關(guān)工作

目前局部社區(qū)發(fā)現(xiàn)算法大都采用基于貪心策略的逐步擴(kuò)張方式來發(fā)現(xiàn)目標(biāo)局部社區(qū)，每一步都從候選節(jié)點(diǎn)集中選擇滿足某種約束條件且使目標(biāo)函數(shù)最大化的節(jié)點(diǎn)。根據(jù)目標(biāo)函數(shù)和約束條件的不同，現(xiàn)有算法可分為四類：基于局部模塊度的算法、基于聚類結(jié)構(gòu)的算法、基于PPR（Personalized PageRank）的算法以及基于節(jié)點(diǎn)/邊的算法。

基于局部模塊度的算法利用局部模塊度衡量社區(qū)質(zhì)量并設(shè)計(jì)與之相關(guān)的目標(biāo)函數(shù)［17，20-21］。文獻(xiàn)［17，20］中均以局部模塊度增量為目標(biāo)函數(shù)，每一步都從候選節(jié)點(diǎn)集中選取模塊度增量值最大的節(jié)點(diǎn)加入局部社區(qū)，直至局部社區(qū)達(dá)到預(yù)定義的規(guī)模；不同的是，文獻(xiàn)［20］的約束條件有所不同：要求鄰接節(jié)點(diǎn)的模塊度增量ΔM非負(fù)，否則擴(kuò)張階段結(jié)束，進(jìn)入剪枝階段，從當(dāng)前局部社區(qū)中刪除使得模塊度增加的節(jié)點(diǎn)，直至沒有節(jié)點(diǎn)可被刪除為止。

基于聚類結(jié)構(gòu)的算法采用符合特定拓?fù)浣Y(jié)構(gòu)局部社區(qū)作為衡量社區(qū)內(nèi)聚度的衡量指標(biāo)。常見的局部社區(qū)聚類結(jié)構(gòu)包括k-core［6，22-23］、k-truss［24-25］、k-clique［26］。k-core要求社區(qū)中的每個節(jié)點(diǎn)都至少與該社區(qū)的其他k個節(jié)點(diǎn)相連，Cui 等［6］提出一種基于k-core 的帶閾值約束的社區(qū)搜索（Community Search with Threshold constraint，CST）算法，在每一步的擴(kuò)張中，在搜索空間不大于預(yù)設(shè)閾值的約束條件下，以候選節(jié)點(diǎn)與當(dāng)前社區(qū)內(nèi)節(jié)點(diǎn)的最大關(guān)聯(lián)數(shù)為目標(biāo)函數(shù)，選擇節(jié)點(diǎn)并更新社區(qū)內(nèi)節(jié)點(diǎn)的最小度數(shù)k直至所有的候選節(jié)點(diǎn)均不能使k增大為止。

基于PPR 的算法采用最大化概率的思想來發(fā)現(xiàn)局部社區(qū)［27-30］。Wu 等［28］首先使用重啟隨機(jī)游走（Random Work with Restart，RWR）算法計(jì)算每個節(jié)點(diǎn)相較于查詢節(jié)點(diǎn)的接近度值并以此賦予邊權(quán)重，然后以最大化社區(qū)查詢偏置密度為優(yōu)化目標(biāo)，得到最終的局部社區(qū)。Bain 等［29］首先使用基于多人約束的局部社區(qū)發(fā)現(xiàn)（Local Community Detection by the Multi-Walker Chain，MWC）求得網(wǎng)絡(luò)中所有節(jié)點(diǎn)的訪問概率向量，并據(jù)此計(jì)算各個節(jié)點(diǎn)的分?jǐn)?shù)，然后找到平均得分最大的Top-L個節(jié)點(diǎn)，在不超過L的閾值下，以最小化局部社區(qū)的阻斷率（conductance）為目標(biāo)，它被用于評估局部社區(qū)的緊密程度，值越小表明該局部社區(qū)越緊密，因此將具有最小阻斷率的子圖作為最終的局部社區(qū)。

基于節(jié)點(diǎn)/邊的算法采用候選節(jié)點(diǎn)與社區(qū)的緊密程度作為目標(biāo)函數(shù)［16，18-19，31-32］。Luo 等［31］提出了最近較大中心性節(jié)點(diǎn)（Nearest node with Greater Centrality，NGC）和基于最近較大中心性節(jié)點(diǎn)的局部社區(qū)發(fā)現(xiàn)（Local Community Detection based on NGC Nodes，LCDNN）算法的概念：對于每個節(jié)點(diǎn)，其NGC 節(jié)點(diǎn)是指中心性最強(qiáng)的最近節(jié)點(diǎn)。在該算法中，Nin為當(dāng)前局部社區(qū)C的鄰接節(jié)點(diǎn)集中那些NGC 節(jié)點(diǎn)在C中的節(jié)點(diǎn)集合，Nout為鄰接節(jié)點(diǎn)集中那些NGC 節(jié)點(diǎn)不在C中的節(jié)點(diǎn)集合，Nin、Nout以及C構(gòu)成已知的局部網(wǎng)絡(luò)。在大于當(dāng)前局部網(wǎng)絡(luò)平均模糊關(guān)系的前提下，以最大化節(jié)點(diǎn)與其NGC 節(jié)點(diǎn)的模糊關(guān)系為目標(biāo)，從Nin中選取節(jié)點(diǎn)加入當(dāng)前局部社區(qū)C。劉井蓮等［19］提出一種基于模糊相似關(guān)系（Fuzzy Similarity Relation，F(xiàn)SR）的局部社區(qū)發(fā)現(xiàn)算法，首先利用隸屬度函數(shù)來衡量節(jié)點(diǎn)與社區(qū)的緊密程度，然后在保證隸屬度大于閾值的前提下，以最大化候選節(jié)點(diǎn)與當(dāng)前局部社區(qū)內(nèi)節(jié)點(diǎn)的隸屬度為目標(biāo)，從候選節(jié)點(diǎn)集中選擇節(jié)點(diǎn)加入局部社區(qū)中。HqsMLCD（Multiple Local Community Detection via Highquality seed identification）［11］是一種基于高質(zhì)量種子的局部社區(qū)檢測算法，首先基于網(wǎng)絡(luò)嵌入方法找到高質(zhì)量的種子節(jié)點(diǎn)，然后以最大化候選節(jié)點(diǎn)的質(zhì)量分?jǐn)?shù)為目標(biāo)，從候選集中選取節(jié)點(diǎn)直至該局部社區(qū)的conductance（conductance指阻斷率，用來評估局部社區(qū)的緊密程度，值越小表明該局部社區(qū)越緊密）不能再變小為止。

2 問題描述

局部社區(qū)發(fā)現(xiàn)問題描述如下：對于網(wǎng)絡(luò)G=（V，E），V和E分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)集和邊集，給定某一查詢節(jié)點(diǎn)q（q∈V），找到其所在的社區(qū)C。

基于Monte-Carlo 迭代策略求解上述問題時，將網(wǎng)絡(luò)G中的節(jié)點(diǎn)分為三部分：已加入社區(qū)的節(jié)點(diǎn)集C、C的鄰接節(jié)點(diǎn)集N和未知節(jié)點(diǎn)集U。第i輪迭代開始時，已加入社區(qū)的節(jié)點(diǎn)集合為Ci-1，Ci-1的鄰接節(jié)點(diǎn)集為Ni，未知節(jié)點(diǎn)集為Ui。圖1為網(wǎng)絡(luò)的局部社區(qū)模型示意圖：黑色部分代表已加入社區(qū)節(jié)點(diǎn)，白色部分代表鄰接節(jié)點(diǎn)，灰色部分代表未知節(jié)點(diǎn)。第1輪迭代開始時，C0={q}，N1=。在每輪迭代中，按照一定的隨機(jī)策略從Ni中選擇一個節(jié)點(diǎn)加入社區(qū)，并在必要時按照一定的隨機(jī)策略從已加入社區(qū)中淘汰一個節(jié)點(diǎn)。

圖1 局部社區(qū)模型示意圖Fig.1 Shematic diagram of local community model

在按照上述思想求解局部社區(qū)時，需要解決以下四個關(guān)鍵問題：1）第i輪迭代中如何確定Ni中每個節(jié)點(diǎn)v（v∈Ni）的選擇概率PS（v）；2）如何判斷第i輪迭代是否需要進(jìn)行節(jié)點(diǎn)淘汰；3）若第i輪迭代需要刪除節(jié)點(diǎn)，如何確定Ci中每個節(jié)點(diǎn)p的淘汰概率PD（p）；4）如何設(shè)置迭代終止條件。

3 本文算法

本文提出了一種基于Monte-Carlo 迭代求解策略的局部社區(qū)發(fā)現(xiàn)算法，如算法1 所示。Com_Candidates為局部社區(qū)C每次發(fā)生變動后的點(diǎn)集及其對應(yīng)社區(qū)質(zhì)量所組成的集合。對于第i輪迭代，根據(jù)節(jié)點(diǎn)的選擇概率PS從Ni中隨機(jī)選取一個節(jié)點(diǎn)Candidate_Node加入至Ci中；同時判斷該輪是否需要執(zhí)行節(jié)點(diǎn)的刪除操作，若需要，根據(jù)節(jié)點(diǎn)的淘汰概率PD從Ci中隨機(jī)選擇一個節(jié)點(diǎn)Delete_Node刪除；重復(fù)以上步驟，直至滿足迭代終止條件，輸出Com_Candidates集合中社區(qū)質(zhì)量最高值對應(yīng)的點(diǎn)集Result_Com作為局部社區(qū)發(fā)現(xiàn)的結(jié)果。

算法1 基于Monte-Carlo 迭代求解策略的局部社區(qū)發(fā)現(xiàn)算法。

輸入 查詢節(jié)點(diǎn)q，圖G，節(jié)點(diǎn)刪除條件參數(shù)w，迭代終止條件參數(shù)h；

輸出 查詢節(jié)點(diǎn)q所在的局部社區(qū)Result_Com。

在算法1 中，函數(shù)Select_Node（）用來計(jì)算社區(qū)鄰接節(jié)點(diǎn)集Com_Nb中各個節(jié)點(diǎn)的選擇概率，并根據(jù)選擇概率隨機(jī)選擇一個節(jié)點(diǎn)（第6）行）；函數(shù)Cal_Com_Quality（）用來計(jì)算當(dāng)前社區(qū)的質(zhì)量（第8）行）；函數(shù)Judge_Quality（）用來判斷當(dāng)前輪次是否需要執(zhí)行節(jié)點(diǎn)的刪除操作（第9）行）；函數(shù)Eliminate_Node（）用來計(jì)算當(dāng)前社區(qū)點(diǎn)集Current_Com中各個節(jié)點(diǎn)的淘汰概率，并根據(jù)淘汰概率隨機(jī)選擇一個節(jié)點(diǎn)（第10）行）；函數(shù)Judge_Size（）用來判斷迭代是否應(yīng)該終止（第15）行）。

3.1 節(jié)點(diǎn)加入階段的選擇策略

局部社區(qū)C擴(kuò)張時，根據(jù)其鄰接節(jié)點(diǎn)集N中各個節(jié)點(diǎn)的選擇概率隨機(jī)選擇一個節(jié)點(diǎn)加入至C中（算法1 Select_Node（）函數(shù)），這一步的關(guān)鍵是確定N中各節(jié)點(diǎn)的選擇概率。

選擇概率決定了節(jié)點(diǎn)被加入到局部社區(qū)的可能性大小，選擇概率的值越大，則被加入到當(dāng)前局部社區(qū)C的可能性越大。本文根據(jù)當(dāng)前局部社區(qū)Ci的鄰接節(jié)點(diǎn)對目標(biāo)函數(shù)的貢獻(xiàn)比例計(jì)算選擇概率。具體地，以社區(qū)緊密度來度量社區(qū)質(zhì)量，并以社區(qū)緊密度增益來作為目標(biāo)函數(shù)。其中，社區(qū)緊密度［32］通過社區(qū)內(nèi)部相似度與社區(qū)外部相似度之比來度量，能夠較好地反映社區(qū)的結(jié)構(gòu)特性。社區(qū)內(nèi)部相似度是指社區(qū)內(nèi)部節(jié)點(diǎn)對的相似度之和，社區(qū)外部相似度是指社區(qū)內(nèi)部節(jié)點(diǎn)與該社區(qū)鄰接節(jié)點(diǎn)的相似度之和。節(jié)點(diǎn)對的相似度用兩節(jié)點(diǎn)的共同鄰居數(shù)與其各自度之積的平方根來度量。社區(qū)緊密度增益是指鄰接節(jié)點(diǎn)加入局部社區(qū)前產(chǎn)生的社區(qū)緊密度差值，在社區(qū)緊密度增益的基礎(chǔ)上給予候選節(jié)點(diǎn)以選擇概率，然后根據(jù)選擇概率隨機(jī)選取一個節(jié)點(diǎn)加入（算法2第4）～6）行）：假設(shè)第i輪迭代時當(dāng)前局部社區(qū)Ci的鄰接候選節(jié)點(diǎn)集為Ni，| |Ni表示候選節(jié)點(diǎn)的個數(shù)，則候選節(jié)點(diǎn)vc（vc∈Ni）的選擇概率PS（vc）可由式（1）計(jì)算得出。在特殊情況下，若鄰接節(jié)點(diǎn)對目標(biāo)函數(shù)均無貢獻(xiàn)，則從鄰接節(jié)點(diǎn)集中等概率隨機(jī)選擇一個節(jié)點(diǎn)加入當(dāng)前局部社區(qū)。

其中：兩相連節(jié)點(diǎn)(x，y)的相似度sim(x，y)可以通過式（5）計(jì)算得出。

其中：N（x）表示節(jié)點(diǎn)x的鄰接節(jié)點(diǎn)集，N（y）表示節(jié)點(diǎn)y的鄰接節(jié)點(diǎn)集。

具體如算法2 所示。

算法2 節(jié)點(diǎn)選擇函數(shù)Select_Node（）。

3.2 淘汰輪次i的確定

在算法迭代過程中，為避免隨機(jī)選擇導(dǎo)致擴(kuò)張方向偏離目標(biāo)社區(qū)，需要在恰當(dāng)?shù)妮喆蝘執(zhí)行節(jié)點(diǎn)的刪除操作。本文根據(jù)局部社區(qū)C的質(zhì)量Q（C）變動情況，提出了一種用于確定淘汰輪次i的策略。對于算法1 中的Judge_Quality（）函數(shù)，在求解目標(biāo)社區(qū)的過程中，記錄下其發(fā)生的每一次變動及其對應(yīng)的社區(qū)質(zhì)量值Q（C）。對于已執(zhí)行過節(jié)點(diǎn)選擇操作的迭代輪次i，若其相鄰前w輪的社區(qū)質(zhì)量值Q與第i輪的社區(qū)質(zhì)量值組成的（w+1）項(xiàng)序列{Qi-w，Qi-w+1，…，Qi-1，Qi}呈非遞增狀態(tài)，則說明當(dāng)前Ci中可能存在異質(zhì)節(jié)點(diǎn)，此時進(jìn)行節(jié)點(diǎn)的淘汰操作。

3.3 節(jié)點(diǎn)淘汰階段的選擇策略

當(dāng)社區(qū)質(zhì)量連續(xù)多次迭代無提升時，需要根據(jù)當(dāng)前社區(qū)C內(nèi)各個節(jié)點(diǎn)的淘汰概率隨機(jī)選擇一個節(jié)點(diǎn)刪除（算法1 Eliminate_Node（）函數(shù)），這一步的關(guān)鍵是確定C內(nèi)各節(jié)點(diǎn)的淘汰概率。

淘汰概率決定了當(dāng)前社區(qū)內(nèi)的節(jié)點(diǎn)被移除的可能性大小，淘汰概率的值越大，則被移除出當(dāng)前局部社區(qū)C的可能性越大。對于需要執(zhí)行淘汰操作的輪次i，本文根據(jù)Ci內(nèi)每個候選節(jié)點(diǎn)pm與其他節(jié)點(diǎn)pn的相似度的總和的倒數(shù)計(jì)算淘汰概率，然后根據(jù)淘汰概率隨機(jī)選取一個節(jié)點(diǎn)刪除（算法3第4）～6）行）。對于已執(zhí)行過節(jié)點(diǎn)選擇操作的輪次i對應(yīng)的局部社區(qū)集合Ci，候選節(jié)點(diǎn)pm的選擇概率PD（pm）可由式（6）計(jì)算得出。

其中：節(jié)點(diǎn)相似度sim(pm，pn)可通過式（5）計(jì)算得出。

具體如算法3 所示。

算法3 節(jié)點(diǎn)刪除函數(shù)Eliminate_Node（）。

3.4 迭代終止條件的設(shè)置

相鄰兩輪迭代后的社區(qū)規(guī)模大小比較有兩種情況：1）后一輪相較前一輪迭代結(jié)果的社區(qū)規(guī)模變大，說明后一輪次只選擇節(jié)點(diǎn)加入，不滿足節(jié)點(diǎn)淘汰的條件而未選擇節(jié)點(diǎn)刪除；2）后一輪和前一輪迭代結(jié)果的社區(qū)規(guī)模相同，說明先選擇節(jié)點(diǎn)加入，因滿足節(jié)點(diǎn)淘汰條件又選擇節(jié)點(diǎn)刪除。

本文根據(jù)局部社區(qū)C的規(guī)模L（C）變動情況，提出了一種用于設(shè)置迭代終止條件的策略。對于算法1 中的Judge_Size（）函數(shù)，在求解目標(biāo)局部社區(qū)的過程中，統(tǒng)計(jì)其每次變動后的社區(qū)規(guī)模L（C）。若連續(xù)h輪迭代的社區(qū)規(guī)模保持不變，則算法終止迭代。

3.5 時間復(fù)雜度分析

算法的時間的耗費(fèi)主要在計(jì)算各輪次的社區(qū)鄰接節(jié)點(diǎn)集中每個節(jié)點(diǎn)的社區(qū)緊密度增益上。假設(shè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的平均度為d，社區(qū)的平均規(guī)模為|C|。計(jì)算整個算法迭代輪次的時間復(fù)雜度為O（|C|），在每一輪迭代中，都需要計(jì)算社區(qū)鄰接節(jié)點(diǎn)集中每個候選節(jié)點(diǎn)的社區(qū)緊密度增益。計(jì)算各輪次局部社區(qū)鄰接節(jié)點(diǎn)集平均規(guī)模的時間復(fù)雜度為O（|C|d），在計(jì)算候選節(jié)點(diǎn)的緊密度增益時，需要計(jì)算社區(qū)的內(nèi)部和外部相似度。其中計(jì)算每一對節(jié)點(diǎn)相似度的時間復(fù)雜度為O（d），計(jì)算節(jié)點(diǎn)對數(shù)量的時間復(fù)雜度為O（|C|2d），所以計(jì)算各輪次緊密度增益的時間復(fù)雜度為O（|C|2d2）。因此，算法的時間復(fù)雜度為O（|C|4d3）。

4 實(shí)驗(yàn)與結(jié)果分析

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

為驗(yàn)證所提算法（以下簡稱Monte-Carlo 算法）的有效性，利用三個真實(shí)的公開數(shù)據(jù)集對傳統(tǒng)方法和Monte-Carlo 算法進(jìn)行比較。數(shù)據(jù)集描述如下：

1）Karate 數(shù)據(jù)集［13］。它是由美國大學(xué)空手道俱樂部成員之間的關(guān)系形成的網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含34 個節(jié)點(diǎn)和78 條邊，其中節(jié)點(diǎn)表示俱樂部的成員，邊代表成員之間的友誼，網(wǎng)絡(luò)中包含2 個社區(qū)。

2）Dolphin 數(shù)據(jù)集［14］。它是新西蘭海豚之間互動的社交網(wǎng)絡(luò)，該網(wǎng)絡(luò)包含62 個節(jié)點(diǎn)和159 條邊，其中節(jié)點(diǎn)表示海豚，邊代表海豚之間的頻繁互動，網(wǎng)絡(luò)中包含2 個社區(qū)。

3）Citation 數(shù)據(jù)集［15］。它是關(guān)于文獻(xiàn)間引用和被引用關(guān)系構(gòu)成的網(wǎng)絡(luò)。由于該網(wǎng)絡(luò)是一個不斷變動的網(wǎng)絡(luò)，本文選用某一個時刻的網(wǎng)絡(luò)作為算法的研究對象。

各數(shù)據(jù)集的參數(shù)如表1 所示。節(jié)點(diǎn)度是指和該節(jié)點(diǎn)相關(guān)聯(lián)的邊的條數(shù)，平均度數(shù)指網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的平均值。

表1 真實(shí)數(shù)據(jù)集介紹Tab.1 Introduction of real-world datasets

4.2 對比算法與評價指標(biāo)

本文將所提算法與以下4 個傳統(tǒng)局部社區(qū)發(fā)現(xiàn)算法進(jìn)行比較。

1）LTE 算法［16］。該算法定義了一種衡量節(jié)點(diǎn)對相似程度的指標(biāo)，并在此基礎(chǔ)上提出了使用社區(qū)緊密度來衡量社區(qū)質(zhì)量。在保證社區(qū)質(zhì)量的前提下，選擇與當(dāng)前社區(qū)內(nèi)部節(jié)點(diǎn)具有最大相似度的節(jié)點(diǎn)加入至局部社區(qū)以找到給定節(jié)點(diǎn)所在的局部社區(qū)。

2）Clauset 算法［17］。該算法通過最大化社區(qū)模塊度R來發(fā)現(xiàn)給定節(jié)點(diǎn)所在的局部社區(qū)。

3）CNWNN 算法［18］。該算法提出共同鄰居相似度指標(biāo)來衡量節(jié)點(diǎn)對的相似程度，并在此基礎(chǔ)上提出新的局部社區(qū)質(zhì)量度量方式。在保證社區(qū)質(zhì)量的前提下，選擇與當(dāng)前社區(qū)嵌入度最大的節(jié)點(diǎn)加入至局部社區(qū)以找到給定節(jié)點(diǎn)所在的局部社區(qū)。

4）FSR 算法［19］。該算法利用隸屬度函數(shù)來衡量節(jié)點(diǎn)與社區(qū)的緊密程度，在保證隸屬度大于閾值的前提下，以最大化候選節(jié)點(diǎn)與當(dāng)前局部社區(qū)內(nèi)節(jié)點(diǎn)的隸屬度為目標(biāo)，從候選節(jié)點(diǎn)集中選擇節(jié)點(diǎn)加入局部社區(qū)。

本文利用調(diào)和均值F-score 值（F1）來衡量算法的性能，如式（7）所示：

其中：CF是算法檢測到的局部社區(qū)節(jié)點(diǎn)集合；CT是給定查詢節(jié)點(diǎn)所屬的真實(shí)社區(qū)節(jié)點(diǎn)集合；精確率Pre（Precision）表示被正確識別的節(jié)點(diǎn)占所有實(shí)際被識別節(jié)點(diǎn)的比例；召回率Rec（Recall）表示被正確識別的節(jié)點(diǎn)占應(yīng)該被識別出的節(jié)點(diǎn)的比例；F1 是召回率和精確率的調(diào)和均值。

4.3 實(shí)驗(yàn)結(jié)果分析

4.3.1 算法性能對比結(jié)果

在整個算法的迭代過程中，參數(shù)w決定何時觸發(fā)節(jié)點(diǎn)的淘汰機(jī)制，設(shè)置合適的w能夠及時剔除當(dāng)前局部社區(qū)中的異質(zhì)節(jié)點(diǎn)，即控制實(shí)驗(yàn)結(jié)果的精確率（查準(zhǔn)率）；參數(shù)h決定何時停止算法的迭代，設(shè)置合適的h能夠給予候選節(jié)點(diǎn)更多進(jìn)入當(dāng)前局部社區(qū)的機(jī)會，即控制實(shí)驗(yàn)結(jié)果的召回率（查全率）。本文以Karate、Dolphin 和Citation 這三個數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果說明算法的有效性。在Karate 數(shù)據(jù)集上，設(shè)置w=1，h=2，實(shí)驗(yàn)結(jié)果如圖2（a）所示；在Dolphin 數(shù)據(jù)集上，設(shè)置w=2，h=3，實(shí)驗(yàn)結(jié)果如圖2（b）所示；在Citation 數(shù)據(jù)集上，設(shè)置w=3，h=4，實(shí)驗(yàn)結(jié)果如圖2（c）所示。

圖2 三個數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果對比Fig.2 Comparison of experimental results on three datasets

圖2 的實(shí)驗(yàn)結(jié)果表明，LTE、CNWNN、Clauset、FSR 和Monte-Carlo 算法在三個數(shù)據(jù)集上的平均F-score 值分別為43.58%、59.02%、55.67%、50.82%和76.33%，相較于其他4種對比算法，Monte-Carlo 算法的平均F-score 值分別提升了32.75、17.31、20.66 和25.51 個百分點(diǎn)，具有最高的精度（即F-score 指標(biāo)）；而相較于其他算法，Monte-Carlo 算法在Karate和Dolphin 數(shù)據(jù)集上也表現(xiàn)出最高的查全性（即Recall指標(biāo)）。

4.3.2 查詢節(jié)點(diǎn)位置對算法性能的影響

為了直觀驗(yàn)證Monte-Carlo 算法在解決查詢節(jié)點(diǎn)位置敏感問題方面的有效性，以LTE 算法和Monte-Carlo 算法為例，驗(yàn)證查詢節(jié)點(diǎn)分別為core 節(jié)點(diǎn)、boundary 節(jié)點(diǎn)和inter 節(jié)點(diǎn)時算法的執(zhí)行結(jié)果。其中：core 節(jié)點(diǎn)是網(wǎng)絡(luò)中位于社區(qū)核心區(qū)域的節(jié)點(diǎn)；boundary 節(jié)點(diǎn)是網(wǎng)絡(luò)中位于社區(qū)邊緣的節(jié)點(diǎn)，且其度數(shù)較小；inter 節(jié)點(diǎn)是位于多個社區(qū)交界處的節(jié)點(diǎn)。以Karate 數(shù)據(jù)集為例，其真實(shí)結(jié)構(gòu)如圖3 所示。其中灰色節(jié)點(diǎn)和白色節(jié)點(diǎn)分別形成兩個不同的社區(qū)。

當(dāng)查詢節(jié)點(diǎn)位置不同時，LTE 算法與Monte-Carlo 算法的執(zhí)行情況如圖4 所示。其中，圖4（a）為LTE 算法發(fā)現(xiàn)的局部社區(qū)，圖4（b）為Monte-Carlo 算法發(fā)現(xiàn)的局部社區(qū)（灰色節(jié)點(diǎn)為算法的執(zhí)行結(jié)果）。

圖4 不同查詢節(jié)點(diǎn)位置的算法表現(xiàn)Fig.4 Algorithm performance with different query node locations

圖3～4 和實(shí)驗(yàn)結(jié)果表明，無論查詢節(jié)點(diǎn)位于何處，Monte-Carlo 算法都能返回較為完整的局部社區(qū)。特別是當(dāng)查詢節(jié)點(diǎn)為boundary 節(jié)點(diǎn)（12 號節(jié)點(diǎn)）或inter 節(jié)點(diǎn)（29 號節(jié)點(diǎn)）時，Monte-Carlo 算法都可以檢測到真實(shí)局部社區(qū)中幾乎所有的節(jié)點(diǎn)；而對于core 節(jié)點(diǎn)（34 號節(jié)點(diǎn)），Monte-Carlo 算法的性能提升則較為受限。

圖3 Karate數(shù)據(jù)集中的真實(shí)社區(qū)結(jié)構(gòu)Fig.3 Real community structure in Karate dataset

5 結(jié)語

本文提出了一種基于Monte-Carlo 策略迭代求解局部社區(qū)的算法。在社區(qū)擴(kuò)張階段，為每個社區(qū)鄰接候選節(jié)點(diǎn)賦予選擇概率，并據(jù)此概率隨機(jī)選取一個節(jié)點(diǎn)加入局部社區(qū)；當(dāng)社區(qū)質(zhì)量連續(xù)多次迭代未能提升時，為已加入目標(biāo)社區(qū)的每個節(jié)點(diǎn)賦予淘汰概率，并據(jù)此概率隨機(jī)刪除一個節(jié)點(diǎn)；以上過程迭代執(zhí)行，直至社區(qū)規(guī)模連續(xù)多次不變。與傳統(tǒng)方法相比，該方法給予了各候選節(jié)點(diǎn)被選擇的可能性，能有效避免算法陷入局部最優(yōu)而過早收斂的問題，保證了目標(biāo)局部社區(qū)結(jié)構(gòu)的完整性。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，所提算法的性能相較傳統(tǒng)方法有大幅度提升，但相關(guān)參數(shù)的設(shè)定對算法性能的影響還有待進(jìn)一步研究。