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

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

（西安科技大學(xué) 計算機科學(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é)點與節(jié)點之間的連邊構(gòu)成，其中節(jié)點代表復(fù)雜系統(tǒng)中不同的個體，邊代表個體間按照某種規(guī)則形成的關(guān)系。網(wǎng)絡(luò)的一個重要屬性是社區(qū)結(jié)構(gòu)［3-4］，Newman 等［5］把社區(qū)定義為網(wǎng)絡(luò)中的若干個內(nèi)部連接緊密的節(jié)點群組，節(jié)點與所在群組內(nèi)的節(jié)點連接緊密，與其他群組的節(jié)點連接稀疏。這些社區(qū)通常表示網(wǎng)絡(luò)內(nèi)個體間有意義的拓撲關(guān)系［6］，實際應(yīng)用中的社區(qū)發(fā)現(xiàn)在個性化推薦、信息傳播等方面具有重要的意義。

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

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

本文的主要工作如下：

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

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

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

1 相關(guān)工作

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

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

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

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

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

2 問題描述

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

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

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

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

3 本文算法

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

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

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

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

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

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

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

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

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

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

具體如算法2 所示。

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

3.2 淘汰輪次i的確定

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

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

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

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

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

具體如算法3 所示。

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

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

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

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

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

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

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

4.1 實驗數(shù)據(jù)集

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

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

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

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

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

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

4.2 對比算法與評價指標

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

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

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

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

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

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

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

4.3 實驗結(jié)果分析

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

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

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

圖2 的實驗結(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 個百分點，具有最高的精度（即F-score 指標）；而相較于其他算法，Monte-Carlo 算法在Karate和Dolphin 數(shù)據(jù)集上也表現(xiàn)出最高的查全性（即Recall指標）。

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

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

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

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

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

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

5 結(jié)語

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