史艷翠，王嫄，趙青，張賢坤

（天津科技大學計算機科學與信息工程學院，天津 300457）

1 引言

社區的定義為網絡中所有節點集合的一個子集，該子集內節點之間的連接相對于與子集外其他節點之間更緊密[1]。社區發現則是在一個圖或者社會網絡中找出相關節點集合的過程，這項工作在一些文獻中也稱為圖聚集或局部圖劃分等[2-3]。社區發現可以為用戶需求獲取、輿情監測等研究提供理論依據，具有重要學術研究意義和實用價值。

社區發現方法可分為全局優化和局部優化這兩類。與全局優化相比，局部優化不需要整個網絡的信息，主要基于局部網絡結構信息發現局部或整個網絡的社區。因此，局部優化更適用于大規模社交網絡的社區發現。李建華等[1]根據不同的局部優化策略，將現有的局部優化社區發現方法大致分為局部擴展優化、派系過濾、標簽傳播以及局部邊聚類優化四類。其中，基于局部擴展優化的社區發現方法的思想是根據定義的局部度量，從給定的初始節點逐步合并近鄰節點，從而進行局部擴展優化，該方法包括2個步驟：種子的選擇和將種子擴展為社區[4]。該方法能有效地揭示局部社區結構、提取有意義的局部聚類信息，并且為在線社區挖掘提供了一個非常有效的途徑。本文通過跟蹤研究，總結現階段該領域的研究成果及存在的問題，并對需要進一步探索或研究的問題進行展望。

2 種子的選擇方法

種子的選擇對基于局部擴展的社區發現方法非常重要。種子既可以是邊也可以是節點，既可以是一組互不連接的獨立節點，也可以是緊密連接的子圖/結構/核。常見的種子選擇方法包括隨機選擇某個不屬于任何社區的節點或邊、根據全局排名、根據局部排名、選擇構成規模不小于k的極大團、選擇k-回路、使用混合方法等方法選擇種子。

2.1 隨機選擇某個不屬于任何社區的節點或邊

Lancichinetti等[5]在提出的局部適應度算法（LFM, local fitness method）中，隨機選擇某個不屬于任何社區的節點作為種子；Huang等[6]在提出的局部緊密度擴展算法（LTE, local tightness expansion）中也采用了同樣的方法選擇種子。Baumes等[7]在提出的迭代掃描（IS, iterative scan）社區發現方法中使用隨機選擇的邊作為種子。

隨機選擇方法的缺點是既沒有考慮節點的權重值又沒有考慮網絡的拓撲結構信息，且由于其隨機性使社區發現的結果與種子質量選擇的好壞有關。但由于該方法簡單、時間復雜度小，因此仍然有很多研究人員使用該方法選擇種子[8-10]。

2.2 根據全局排名選擇種子

根據全局排名選擇種子的方法根據節點權重值在整個網絡中的排名選擇種子。

Baumes等[7]在提出的排名移除（RaRe, rank removal）社區發現方法中采用移除策略選擇種子節點。依次移除網頁排名最高或節點度最大的節點，直到剩下一些在給定規模內且連接較少的結構。這些結構被視為每個簇的核，即初始社區。該方法有如下缺點：1） 由于每次刪除節點后，都需要對剩余節點重新計算網頁排名或節點度，因此效率低；2） 該方法的假設不恰當，因為有時排名在前的節點更適合做種子節點。類似地，龍淵[11]也采用移除策略選擇種子節點，與 RaRe所不同的是，該方法通過刪除影響力最小的節點，找到具有最大影響力的節點作為初始種子集合。由于選擇的初始種子集合中可能包含孤點，直接使用孤點作為種子可能導致發現的社區結果不理想，因此該方法根據給定的規則將孤點擴展為仿團集，將生成的仿團集作為種子。

為了提高種子選擇的效率，Baumes等[12]提出了鏈接聚合方法（LA, link aggregate）。該方法首先按照一定準則（例如，遞減的網頁排名）對節點進行排序，然后按照順序依次執行，如果節點添加后不能改善任何簇的密度，則把它選做種子，并生成一個新簇。與RaRe相比，由于LA只需要對節點排序一次，在選擇種子節點時，效率得到了很大提高。

為了更準確地選擇種子節點，國琳等[13]在提出的OClu-detect算法中計算節點的權重值時，考慮了節點與鄰域節點的平均連接強度以及鄰域節點間的關聯密度的影響。該方法首先根據節點的權重按照降序對節點進行排序，然后選擇節點序列中排名最前，且未標記或其鄰居未全部標記的節點作為種子，并將選為種子的節點從節點序列中刪除；重復上述操作，直到被發現的節點全覆蓋或大部分覆蓋整個網絡。Yang等[14]選擇權重最大的節點（WM，weight maximum）在計算節點權重值時考慮了邊的權重，該方法首先根據節點的權重按照降序對節點進行排序，然后選擇節點序列中排名最前，且未出現在已發現社區中的節點作為種子，直至種子候選集為空。

當網絡規模比較大時，對節點進行排序的時間消耗比較大，因此，一些研究人員選用最大值來降低時間復雜度。例如，陳俊宇等[15]在提出的半監督局部擴展式重疊社區發現辦法（SLEM，scmi-super-vised local expansion method）中利用網絡節點的拓撲特征——度中心性選擇種子。在這種方法中，節點的鄰居數量即為節點的權重值，在未標記的節點中選擇具有最大度中心性的節點作為種子，并為該節點的周圍鄰居設置相同的標簽，然后在未標記的節點中重復上述操作。Whang等[16]提出的spread hubs方法與上述方法類似，選擇節點度最大的未標記節點作為種子。楊貴等[17]在提出的基于加權稠密子圖的重疊聚類算法（OCDW, overlap community detection on weighted networks）中選擇種子節點時，考慮到選擇的種子既要位于網絡的拓撲中心位置且種子之間在網絡結構中應相距較遠，因此，使用節點的加權值作為節點的權重，并選擇權重最大的節點作為種子，在選擇下一個種子時，根據設定的規則降低已成為種子的節點被再次選擇的概率。Cao等[18]在提出的交通社區發現算法（TRACED, transportation community detection）中選擇權重高且大于閾值的邊以及相應的節點作為種子。

全局排名選擇方法有如下缺點：1） 選擇的種子可能是hub節點，使用這些種子有可能導致得到的社區發現結果比較差；2） 使用該方法選擇的種子的多樣性無法保證。

2.3 根據局部排名選擇種子

根據局部排名選擇種子的方法根據節點權重值在局部網絡中的排名選擇種子。

一些研究人員根據節點的最近鄰信息選擇種子。例如，Chen等[19]選擇具有局部最大度的節點（LMD, local maximum degree）作為種子；Deshpande等[20]使用鏈接預測（LP1, link prediction）方法選擇種子時，選擇具有局部最大相似度的節點作為種子；Hao等[2]選擇具有局部最小傳導性的節點作為種子；而Gleich等[21]則選擇具有局部最小傳導性的鄰域社區（LMC, locally minimal conductance）作為種子；Wang等[22]在提出的局部社區中心算法（LCC,locating community centers）中選擇具有局部最大結構中心度的節點作為結構中心，在計算結構中心度時考慮了節點的密度和節點間的相對距離；Su等[23]在提出的基于隨機游走的算法（RWA, random walksbased algorithm）中使用緊密連接的子圖作為初始社區，首先根據局部最大度選擇K（K表示選擇的種子節點或種子子圖的數量）個初始節點，然后選出給定初始節點的局部最大度節點，則具有局部最大度的節點、給定初始節點以及它們的一個共同鄰居構成3個節點的種子社區。

上述方法僅利用了節點的最近鄰信息。為了更準確地選擇種子，汪濤等[24]在提出的基于核心節點跳轉的局部社區發現算法（LCD-NJ, local community detection based on the core nodes jumping）中首先計算給定節點k跳范圍內所有鄰近節點的中心度，然后選擇中心度大于給定閾值的節點作為種子。常振超等[25]在提出的影響力節點集擴展的局部社團檢測方法（IN-LCD, local community detection based on influential nodes）中選擇給定節點的所有最近鄰和次近鄰為種子候選集，然后使用最近鄰和次近鄰信息計算節點的影響力，并根據節點的影響力對候選種子節點進行降序排序。但是這2種方法主要用于發現包含某個節點的局部社區。在全網社區發現中，可以借鑒上述方法，利用k跳范圍內節點的信息選擇種子節點或計算節點的權重值。

Whang等[16]在提出的graclus centers方法中，通過計算節點和所在簇的距離來確定節點的權重。該方法選擇種子的過程如下。首先使用graclus執行從上到下的層次聚類得到大量的簇，然后計算節點到屬于簇的質心的距離，并選擇距離最小的節點作為種子。該方法可以得到多樣性的節點，且計算復雜度不是太大。

局部排名選擇方法的缺點是有可能無法發現最大的社區，而使用極大團作為初始節點的社區發現方法則可以解決該問題。

2.4 極大團

Lee等[26]在提出的貪婪團擴張算法（GCE,greedy clique expansion）中，選用規模不小于3或4的派系作為初始節點。Shang等[27]則選擇規模不小于4的派系作為初始節點。李婕[28]采用基于派系過濾的算法選擇種子節點，該方法為了使選擇的種子群組具有層次性，從最大的派系直至最小的派系逐級過濾構造種子群組。

極大團選擇方法的優點是可以解決社區發現結果的不穩定性問題，缺點是尋找派系所需的計算量非常大[29]，難點是派系最小規模的確定，即k的值。在設定k值時，存在2個問題：1） k值太大或太小都會導致社區發現的結果不理想；2） 相似的派系會導致完全相同的社區冗余[15]。另外，如果將所有發現的派系作為初始節點，社區發現的計算時間非常大。為了解決該問題，Becker等[30]根據網絡中節點的數量來限制選擇的派系的數量。這種種子選擇方法不適合密度較小的網絡。

2.5 k-回路

肖覓等[31]考慮到隨機選擇某個不屬于任何社區的節點和極大團的缺點，使用k-回路作為初始節點，并根據小世界和六度分割理論，設定3≤k≤6。與極大團相比，k-回路放松了對邊的密度的要求，適用于密度稀疏的網絡。

2.6 混合方法

為了克服單種選擇方法存在的缺點，混合方法通過綜合2種或多種方法選擇種子。Shang等[4]為了避免高的計算復雜度和全局排名方法的缺點，提出了一種新的選擇邊作為種子的方法，信息理論和期望值最大化（ITEM, information theory and expectation and maximization）。。該方法首先使用信譽、強度和特異性（RSS, reputation, strength, specificity）選擇候選種子，其中，RSS是一種局部排名方法；然后使用最大化全局信息增益方法（MGIG, maximizing global information gain）選出最終的種子，MGIG從全局角度在候選集中選擇信息分布最大的節點作為種子。

Wilder等[32]綜合隨機和局部排名這2種方法，提出了一種選擇種子節點的方法，ARISEN。首先，隨機選取T（T＞K）個節點，并使用R步的隨機游走找出每個節點的一個小子圖；然后，根據子圖計算每個節點的權重向量，使用正比于權重向量的概率來選擇種子節點。該方法的時間復雜度只與隨機選取的T個節點和R有關，因此效率得到了提高。而Zhou等[33]綜合隨機和局部排名這 2種方法提出了基于最小集群的局部社區發現方法（NewLCD, local community detection algorithm based on the minimal cluster）。首先，隨機選取K個初始節點；然后，按照以下方法找出包含每個初始節點的最小簇：在給定初始節點的鄰居集合中，找出與給定初始節點有最多共同鄰居的節點，該節點、給定初始節點和它們的共同鄰居構成最小簇，即種子。

張忠正[34]考慮到選擇單個節點作為社區的種子時會存在一些問題，因此，通過綜合全局排名和局部排名選擇核心區域作為種子。首先，根據節點的核心值對全部節點進行降序排序構成優先級列表；其次，選擇優先級列表的第一個節點作為初始的種子節點；再次，從該種子節點的鄰居節點中根據局部排名選擇k-1個節點與其合并構成核心區域；最后，對核心區域進行擴展，如果形成社區，則將社區內的節點從優先級列表刪除，否則，將選擇的種子節點從優先級列表刪除。重復上述操作，直至優先級列表為空。該方法可以有效地避免將橋接點被選擇為種子節點。

表1列出了上述種子選擇方法的時間復雜度。其中，NU=|U|和NE=|E|分別表示網絡中節點和邊的數量；p表示邊的平均鄰居數量；NnU表示社區或節點的鄰域的節點平均個數；NnkU表示給定節點k跳內鄰居節點的個數，k≥2；T表示候選種子節點/初始社區的數量；Nvc=|UC|和Nεc=|EC|分別表示雙連通核中節點和邊的數量，UC和EC分別表示雙連通核中節點和邊的集合，且Nvc≤NU，Nεc≤NE[16]；t表示每次刪除的節點的個數，1≤t≤（max-min），min和max分別為種子節點的數量的下限和上限值[7]；kC表示規定的核心區域的規模[34]。

由表1和上述分析可得以下結論。

1） 時間復雜度。隨機選擇方法的時間復雜度最小?；旌线x擇方法綜合了多種方法的優點，大多數情況下時間復雜度不是太大。全局排名方法需要計算所有節點的權重值，有時還需要計算多次，由于計算復雜度與節點的規模呈正比，當應用在大規模的網絡（例如有上億用戶的微信）時，其計算復雜度會很大?；诰植颗琶姆椒ㄔ谶x擇節點時，只需要與局部節點進行對比，在最好的情況下，其時間復雜度可以降為NnUK。k-回路的時間復雜度與節點和邊的數量成正比，所以在大規模網絡中，其時間復雜度比較大。極大團的時間復雜度最大。

表1 種子選擇方法的時間復雜度的對比

2） 種子的質量。由于其隨機性，使用隨機選擇方法選取的種子節點的質量無法保證。全局排名方法可以選擇出網絡中最有影響力的節點，但這些節點有可能不適合作為種子節點，例如當網絡中最有影響力的節點分布比較集中時，則導致選擇的種子比較集中，從而使社區發現的質量比較差?；诰植颗琶姆椒ǘ鄻有员容^好，選擇的種子節點在網絡中分布比較均勻。極大團和k-回路種選擇方法與網絡的拓撲結構有關，當網絡中疏密度不均勻時，會出現與全局排名類似的問題，選擇的種子多樣性比較差。混合方法由于綜合了多種選擇方法的優點，一般情況下，選擇的種子節點的質量比較好。

3） 適用網絡。綜合時間復雜度和種子的質量，總結出各種種子選擇方法的適用網絡如下。隨機選擇方法對網絡沒有要求，可以應用在任何網絡中。全局排名方法由于其時間復雜度與節點規模呈正比，因此適用于小規模、且權重值較大的節點分布比較均勻的網絡，但對稀疏性沒有要求。局部排名方法可以應用在任何網絡中。k-回路和極大團則適用于密度比較大且k-回路和極大團分布比較均勻的小規模的網絡中。混合方法則根據綜合的方法確定其適用網絡。

3 局部擴展優化方法

本文將局部擴展優化算法分為基于無監督的局部擴展優化方法和基于半監督的局部擴展優化方法兩大類進行介紹。

3.1 基于無監督的局部擴展優化方法

當網絡中無法獲取節點所屬社區的任何標記信息時，可以使用無監督的局部擴展優化方法。最簡單的擴展方法就是直接添加種子的全部鄰域節點到相應的社區[13]，但該方法發現的社區的準確性不高。貪婪擴展是最常用的一種社區擴展方法，它通過最大化或最小化某個給定的函數或者社區的某個特征指標來擴展局部社區，本文給出了常用的幾種貪婪擴展方法。

1） 最大化適應度函數

在 Lancichinetti等[5]提出的 LFM 社區發現方法、Lee等[26]提出的GCE社區發現方法中，通過貪婪地最大化局部適應度函數來實現局部擴展優化。LFM的擴展過程如下：① 計算每個種子邊界節點的適應度，如果計算得到的適應度的最大值為正值，則將該邊界節點添加到相應的社區中；② 計算該社區內每個節點的適應度；③ 如果某節點的適應度為負值，則將該節點從社區中移除；④ 如果發生③，則執行②，否則執行①。張忠正[34]采用了與LFM相同的局部擴展方法，與LFM的區別是，在擴展過程中，如果選擇的種子節點被刪除，則停止擴展。

與LFM不同，在GCE中，只需要計算邊界節點的適應度，如果計算得到的適應度的最大值為正值，則將該邊界節點添加到相應的社區中；否則，終止操作[26]。楊貴等[17]提出的 OCDW（overlap community detection on weighted networks）基于加權稠密子圖的重疊聚類算法、汪濤等[24]提出的LCD-NJ（local community detection based on the core nodes jumping）基于核心節點跳轉的局部社區發現算法以及常振超等[25]提出的IN-LCD（local community detection based on influential nodes）影響力節點集擴展的局部社團檢測方法采用與 GCE類似的方法實現局部擴展，但這些方法沒有限定擴展的候選節點是鄰域節點。為了減少局部擴展的時間，龍淵[11]對 GCE算法中的局部擴展方法進行了改進，對適應度為負值的節點進行了分析，將不可能加入社區的節點在后續的擴展中刪除。

上述局部擴展方法根據適用的場合不同，適應度函數的定義有所不同。LFM和GCE根據社區的內部度數和外部度數定義適應度函數；IN-LCD和LCD-NJ則根據社區的相似度和社區的適應度來定義節點的適應度函數。上述這些方法只適用于無權網絡。為了適用于加權網絡，OCDW方法在定義社區的適應度函數時，考慮了邊的權重值，并用適應度函數評價社區的稠密程度。李婕等[28]使用加權網絡中基于局部適應度方法的派系過濾（CLFMw,clique percolation based local fitness method for weighted network）構建群組，則在定義適應度函數時考慮了節點的度數和邊的權重，只有當適應度函數的值大于給定的增量閾值時，才將節點加入到相應的社區。

2） 最大化可調密度增益

Huang等人在提出的LTE算法中通過最大化可調密度增益實現局部社區擴展[6]。其擴展過程包括兩步：① 更新過程，更新社區的鄰居集合，并計算鄰居集合中每個節點與社區的相似度；② 添加過程，選擇與社區相似度最大的節點，如果該節點的可調密度增益大于零，則將該節點添加到社區，否則將該節點從鄰居集合移除，并按照結構相似度的降序依次分析其余節點。重復上述過程，直到所有節點加入到相應的社區。

3） 最大化局部相關度

肖覓等[31]提出的回路融合社區發現算法（CM,circuits merging）中通過貪婪地最大化局部相關度來實現局部擴展優化。具體過程如下。① 如果節點（不屬于任何種子）只和一個社區（初始時由種子構成的社區）連接，則將其添加到該社區。② 如果節點與多個社區相連，則計算該節點與每個社區的相關度。③ 如果計算得到的相關度的最大值只有一個，則將其添加到相應的社區；如果計算得到的相關度的最大值有多個，則將節點添加到相應的多個社區。重復上述步驟，直到所有節點都被添加到相應社區。

4） 最大化模塊度

在Shang等[27]提出的重疊社區發現方法中，通過最大化模塊度實現貪婪擴展。如果節點只有一個社區相連，則直接將節點添加到該社區。與CM算法不同，當節點與多個社區相連時，通過臨時添加和最終添加來實現擴展，具體如下：① 臨時添加，計算該節點與每個社區的連接度，如果連接度大于給定的閾值，則將該節點添加到相應的社區，否則，將該節點添加到連接度最大的社區；② 最終添加，遵循模塊度最大化原則，將節點添加到相應社區。Zhou等[33]在提出的 NewLCD方法中同樣采用了最大化模塊度的方法實現局部社區擴展，首先計算初始社區的鄰域節點和相應的模塊度，然后將鄰域節點中具有最大模塊度的節點添加到初級社區，重復上述操作，直至沒有節點能添加到初級社區。Chen等[19]在提出的局部社區發現算法（LCDA,local community detection algorithm）中選擇與種子有最多共同鄰居且能最大化模塊度的鄰域節點進行擴展。Yang等[14]在提出的局部擴展方法中，首先通過計算近似的網頁排名向量來確定支持集，然后根據模塊度最大化和傳導率最小原則（HMSC, high modularity and small conductance）選擇支持集中的節點進行局部擴展。

5） 最大化子圖或簇的密度

Baumes等[12]在提出的LA方法中，通過最大化簇的密度實現局部擴展，將節點添加到能增加社區的密度的社區。Wang等[22]在提出的局部社區擴展算法（LCE, local community expansion）中通過最大化子圖密度實現局部社區擴展。過程如下：以選擇的結構中心作為初始的社區，將能增加社區密度的鄰域節點添加到該社區，刪除社區中具有負增益的節點，重復上述操作直到社區的密度不能改善。

6） 最大化概率

Su等[23]在提出的RWA方法中使用隨機游走策略實現局部社區的擴展。該擴展方法首先基于隨機游走計算未標記節點屬于各個初步社區的概率，然后根據計算得到的概率，將該節點添加到最有可能屬于的社區。重復上述操作，直到所有節點添加到相應社區。

7） 最大化中心度

Nathan等[8]使用個性化的中心度——網頁排序或 Katz中心度（PPKC, personalized PageRank or Katz centrality）進行局部擴展。首先計算給定種子節點的個性化的中心度，然后根據給定局部社區的規模，例如社區大小為NCU，則選擇中心度最大的NCU個節點構成局部社區。

8） 最小化傳導值

傳導值是度量社區質量常用的一種評價指標，傳導值越低，社區質量越好[10]。Whang等[16]提出了一種基于個性化網頁排名的種子擴展方法，該方法通過貪婪地最小化傳導值實現種子擴展。具體步驟為：1） 以給定的某個種子節點及其鄰居作為初始節點；2） 計算個性化網頁排名向量，并根據個性化網頁排名向量對節點進行降序排序；3） 依次計算個性化網頁排名向量排序中每個前綴集合的傳導值，選出具有最小傳導值的前綴集合作為最終的擴展集合。Cao等[18]通過最小化簇的傳導值實現局部社區擴展。局部擴展中，如果節點添加到簇能減小給定簇的傳導值則添加到該簇，同時，如果移除給定簇中某個節點可以減小該簇的傳導值，則從該簇中移除該節點，重復執行上述操作，直到沒有節點可以改變簇的傳導值。

但該擴展方法對社區的內部連通性不是很敏感，在最壞的情況下，具有低傳導值集合的內部可能是斷開的。

9） 最大化社區權重

在Baumes等[7]提出的RaRe方法中，通過改善社區權重來實現局部擴展。在RaRe方法中，只分析在種子選擇階段刪除的節點，因此只涉及添加操作。將刪除節點添加到能改善權重值的社區，否則添加到與之相連的社區。重復上述操作，直到所有刪除的節點都被添加到相應社區中。

在Baumes等[7]提出的IS方法中，同樣是通過改善社區權重來實現。與RaRe方法不同，IS方法是針對所有節點進行分析，或添加或刪除。具體過程為：① 將種子看作初級社區并計算社區的權重值；② 對所有節點進行分析生成新社區，如果節點屬于給定的社區，則從社區中移除，否則將該節點添加到給定社區；③ 計算新產生社區的權重值，如果新產生社區的權重值大于原有社區的權重值，則用新產生的社區代替原有社區，否則原有社區保持不變；④ 重復上述操作，直到所有社區的權重值不再改變。實驗結果證明，使用該方法獲得的社區結果優于使用RaRe方法得到的結果。另外，該方法還可以改善使用其他方法得到的簇，使之成為最優的局部最優簇，例如，將RaRe方法得到的結果作為IS的輸入。

為了減少 IS算法中局部擴展的運行時間，Baumes等[12]提出了改進的迭代掃描方法（IS2, improved iterative scan）。在IS方法中進行局部擴展時，每次迭代是對所有節點進行分析，而在IS2方法中，只分析了給定社區內的節點以及該社區的鄰域節點，但該方法引入了尋找給定社區鄰域節點的時間。當社會網絡比較稀疏時，由于分析節點減少的時間大于尋找給定社區鄰域節點所花費的時間，因此，IS2方法優于IS方法；當給定的社會網絡密度比較大時，由于分析節點減少的時間小于尋找給定社區鄰域節點所花費的時間，因此，IS方法優于IS2方法。綜上，當社會網絡比較稀疏時，應該采用IS2方法中的局部擴展方法，當社會網絡的密度比較大時，應該采用IS方法中的局部擴展方法。

在上述方法中，每個種子在擴展時是獨立進行的，因此某個節點可能被劃分到多個社區，所以上述算法可用于重疊社區的發現。

3.2 基于半監督的局部擴展優化方法

基于半監督的局部擴展優化方法通過獲取部分節點先驗知識來指導社區發現，從而避免無監督方法的盲目性。通?？紤]的先驗知識包括以下2種：1） 已知部分節點的社區標簽（例如種子節點）；2） 成對節點之間的必須連接和不可能連接的約束[35]。

1） 已知部分節點的社區標簽

Shang等[4]提出的擴展方法是利用半監督學習技術將邊劃分到不同的社區中。在該擴展方法中，將種子標注相應的社區標簽，并作為訓練集。另外，考慮到在訓練中每個社區只有一個樣本，因此在實施擴展算法前，對訓練集進行了擴展，將種子鄰居節點之間的邊標注上和種子相同的社區標簽并添加到訓練集中。擴展過程利用期望和最大化算法將邊分類到社區中，包括2個步驟：① 期望步驟，首先利用拓撲信息確定某條邊是否為給定社區的潛在邊，在確定某條邊為給定社區的潛在邊后根據主題信息計算其屬于給定社區的后驗概率，并將其添加到具有最大后驗概率的社區；② 最大化步驟，基于所有標注的邊來評估期望步驟中的未知參數。

2） 成對節點之間的必須連接和不可能連接的約束

陳俊宇等[15]提出的SLEM。該方法考慮到事先準確知道某個節點屬于哪個社區是不現實的，因此通過判斷一對節點是否屬于同一個社區作為約束信息來指導社區發現的執行。SLEM算法的局部擴展采用貪心策略將初始節點擴展為局部社區，通過對比與合并，得到最終的社區發現結果。

表2列出了上述局部社區擴展方法的時間復雜度。其中，Ci∈C表示生成的某個社區，C為生成的社區的集合；NCU表示生成的社區內節點的平均個數；NnE表示社區或節點的鄰域的邊的平均數；NlE表示給定節點所在的確定規模的局部社區內邊的數量；β是給定的參數，b∈[1,■logNE■]，KZ表示支持集的規模[14]；m表示EM算法的迭代次數[4]。

由表2和上述分析可知，貪婪擴展方法有多種特征指標，但擴展策略主要分為4類，具體如下。

① 以未標記的節點為中心添加節點。這種擴展方法首先找出與未標記節點連接的種子，然后根據貪婪規則與相應的種子合并[7,12,17,24-25,27-28,31]。大多數情況下這種擴展方法的時間復雜度與網絡中的邊成正比，因此，更適用于密度小的網絡。

② 以種子為中心添加節點。這種擴展方法首先找出種子的鄰域，然后根據貪婪規則選擇某個鄰域節點與種子合并[6,11,19,26,33]。大多數情況下這種擴展方法的時間復雜度只與網絡中的節點和鄰域的平均規模有關，因此，它更適用于密度較小的網絡。由于NUNnU=2NE，且通常K≥2，因此，與第一類擴展策略相比，在密度大的網絡中，該類擴展方法的時間復雜度更小。

表2 局部擴展方法的時間復雜度對比

③ 以種子為中心添加或刪除節點。這種擴展方法不僅根據貪婪規則選擇某個鄰域節點與種子合并，同時還根據貪婪規則刪除已標記的節點[5,15,18,22,34]。這種擴展方法的精確度優于前兩類方法，但增加了刪除已標記節點的時間復雜度，因此，它適用于對社區發現結果要求高且密度小的網絡。

④ 以未標記的節點為中心添加或刪除節點。對于網絡中的任意節點，首先判斷該節點是否屬于給定社區，如果屬于給定社區且刪除該節點能改善社區的特性則刪除該節點，如果不屬于給定社區且添加該節點能改善社區的特性則添加該節點[7,12]，這種擴展方法的時間復雜度只與節點的數量有關。在密度大的網絡中，這種擴展方法優于第三類擴展策略。

4 評價指標

評價社區發現結果最常用的指標是模塊度[1,3,29,31,36-41]。除了模塊度，目前使用的評價指標還有標準互信息、F1-measure/F1-score、Jaccard系數、時間復雜度等。這些評價指標從不同的角度對社區發現結果進行評價。

4.1 模塊度

模塊度，即Q函數。模塊度可以度量社區連接的緊密度以及社區的穩定性。模塊度的基本思想是將劃分社區后的網絡與不存在社區結構的零模型進行比較。由于該評價指標只需社區發現的結果和不存在社區結構的零模型信息，因此當實驗數據集中沒有給出真實的社會結構信息時，可以使用該評價指標。Newman等[37]給出的計算式如式（1）所示。

其中，eii表示社區Ci的內部邊與網絡中總邊數的比例，eij表示連接社區Ci和社區Cj的邊與網絡中總邊數的比例，ai表示一端和社區Ci中節點相連的邊與網絡中總邊數的比例，且

李建華等[1]為了便于實際計算，則將eii定義為社區Ci的內部邊的數量，ai定義為一端與社區i中節點相連的邊的數量。當評價社區發現結果的質量時，Q值越大越好。

然而，Q函數不適用于加權網絡，為了適應加權網絡，徐建民等[36]提出了擴展的模塊度函數Qw，其定義如式（2）所示。其中，W表示網絡中所有邊的權重之和，Wi表示社區Ci的內部邊的權重之和，Tc表示與社區Ci中的所有節點相鄰的邊的權重之和。

由于Q函數不能評價重疊社區的發現結果，因此，研究人員對Q函數進行了修改以評價重疊社區的發現結果[3,22,27]，如式（3）所示。

其中，A表示社會化網絡的鄰接矩陣，Avu∈A表示鄰接矩陣中的元素，當節點v和節點u之間存在邊時，Avu=1，否則，Avu=0；NE=|E|表示網絡中邊的數量；kv表示節點v的度數；表示節點v是否屬于社區Ci，如果節點v屬于社區Ci，則否則

然而，在重疊社區中，一個節點可能屬于多個社區，因此，為了更準確地度量重疊社區的質量，對QO函數進行了擴展[15,31]，如式（4）所示。

其中，αCi,v表示節點v屬于社區Ci的程度，其計算方法有多種。例如，肖覓等[31]根據節點在給定社區內連接邊數的比例來計算其對社區的隸屬度，即表示節點v與社區Ci連邊的數量，當節點只屬于一個社區時，陳俊宇等[15]引入了每個節點屬于社區的數量，即表示節點v屬于的社區的數量，當節點只屬于一個社區時，

4.2 標準互信息

1） NMI

標準互信息度量（NMI, normalized mutual information）用于衡量社區發現結果與真實社區結構的相似度，可以度量社區發現結果的穩定性和精度[42-43]。因此，當實驗數據集中包含真實的社區結構（例如，LFR（lancichinetti fortunato radicchi）基準測試網絡）時，可以使用 NMI評價指標，具體定義如式（5）所示[1,22-23]。

其中，Cr表示真實的社區結構；Cf表示使用社區發現方法發現的社區結構；Nr表示真實社區的數目；Nf表示發現的社區數目；M為Nr×Nf的混合矩陣，其元素Mij表示真實社區與發現社區所對應的2個社區間共同的節點數量，當真實的社區結構和發現的社區結構完全相同時，M為對稱矩陣，且當i≠j，Mij=0，當i=j，Mij的值即為社區Cr,i包含的節點的數量；Mi.表示矩陣M中第i行元素的總和，即社區Cr,i包含的節點的數量；M.j表示矩陣M中第j列元素的總和，即社區Cf,j包含的節點的數量。

當評價社區發現的質量時，I值越大，則表明社區發現的結果越準確，當發現的社區劃分與真實社區一致時，I=1。

但是，式（5）不能評價重疊社區的發現結果。在重疊社區中，一個節點可能屬于多個社區，為了度量重疊社區的發現結果，Lancichinetti等[5,15]對式（5）進行了擴展，如式（6）所示。

其中，X和Y分別表示Cr和Cf相關的隨機變量，H（X|Y）表示X對Y的條件熵。

2）F1-measure

F1-measure是正確率和召回率的調和平均值，用于衡量給定社區發現結果與真實社區結構的相似度/相關度，可以度量社區發現結果的精度。在不同的文獻中，研究人員給出了不同的命名，例如F-measure[3,23]、成對F-measure[35]、F1-measure[16]、F-score[33]、F1score[2,18,41]，在本文中，將該評價指標命名為F1-measure。計算式如式（7）和式（8）所示。

其中，precision（Cf,j,Cr,i）表示社區發現的準確率，Recall（Cf,j,Cr,i）表示社區發現的召回率，其計算式如式（9）和式（10）所示。

precision =Cr

∑

,i∈ Cr

Cmf,j

a

∈Cxfprecision（Cf,j,Cr,i）

（11）

Nr

recall =C∑

r,i∈ Cr

Cmf,j∈

aCxfrecall（Cf,j,Cr,i）

（12）

Nr

式（7）、式（11）和式（12）既適用于非重疊社區也適用于重疊社區。

3） Jaccard 系數

Jaccard系數與NMI的思想相同，也是通過計算社區發現結果與真實社會結構的相似程度來評價社區發現結果的質量，其定義如式（13）和式（14）所示[9]。

當評價社區發現結果的質量時，Jaccard值越大，則表明社區發現的結果越準確。當發現的社區和真實的社區完全相同時，J=1；當發現的社區和真實的社區完全不同時，J=0。式（13）既適用于非重疊社區也適用于重疊社區。

除模塊度外，上述評價指標都需要數據集中包含真實的社區結構信息。然而，在爬取的網絡數據中，例如Twitter、微博、微信、Facebook、大眾點評、豆瓣等網絡，不包含真實的社區結構。因此，在實際應用時，只能使用不需要真實社區結構的模塊度進行評價。但是，在評價社區發現結果時，需要從多角度進行評價，例如精度、社區發現的穩定性、社區發現的可擴展性等。因此，需要尋求或設計更多可用的評價指標，從多方面評價真實網絡的社區發現結果。

5 基于局部擴展的社區發現的應用

大部分基于局部擴展的社區發現方法的研究重點是如何更準確地發現社區結構，而對其具體的應用介紹的較少?；诰植繑U展的社區發現方法不僅可以發現網絡中的社區結構，有些方法還可以發現網絡中全局或局部最有影響力的用戶，例如基于全局排名的種子選擇方法可以發現網絡中最有影響力的用戶，而基于局部排名的種子選擇方法可以發現網絡中局部最有影響力的用戶。鑒于此，本文對基于局部擴展的社區發現的具體應用總結如下。

1） 社區發現方法共有的應用

這部分應用主要是將發現的社區結構應用到相應的領域，它的應用重點是發現的社區結構，而不是社區發現技術，因此，可以是基于局部擴展技術發現的社區結構，也可以是基于其他技術發現的社區結構。主要應用領域包括商業、公共安全、醫療疾病、生物學等領域[38]。

① 在商業方面的應用。社區一般是由偏好或社會背景相同/相似的用戶組成的群體，因此社區發現可以應用到推薦系統中，尤其是基于協同過濾的推薦系統[44]。例如，在電子商務網站上挖掘用戶需求，推薦滿足用戶個性化需求的產品（如電影、音樂、美食等），可以提高用戶的購物體驗，從而提高銷售額。肖覓等[31]考慮到用戶需求會受家人、朋友的影響，因此對基于移動用戶行為的回路融合社區發現進行了研究；劉宇等[45]將發現的重疊社區結構作為用戶群組，并根據用戶對群組的隸屬關系完成推薦任務；李婕等[28]通過分析用戶的通話記錄，建立用戶間聯系緊密度模型，并使用局部擴張原理和派系過濾算法進行用戶群組構造以對用戶資源進行了解，從而使移動運營商更好地拓展新業務。

② 在公共安全方面的應用。將社區發現應用在輿情監測、偵破案件等領域中。Bouchard等[46]對在線犯罪網絡的社區發現及共犯進行了研究；丁晟春等[47]將社區結構應用在微博熱點主題識別中，以實現輿情監控。

③ 在醫療疾病方面的應用。將社區發現應用在患者分類、疾病識別等方面。例如Hoshi等[48]根據發現的社區結構對患者進行分類；Mall等[49]根據社區結構對生物網絡中的疾病模塊進行識別；Steve等[50]則將發現的社區結構應用在復雜疾病關聯分析中。

④ 在生物學方面的應用。將社區發現應用在神經、蛋白質等網絡中。Becker等[30]根據蛋白質相互作用網絡中的重疊社區發現多功能蛋白質；Garcia等[51]將社區發現應用在神經影像構建的腦圖中。

2） 基于局部擴展的社區發現方法特有的應用

這部分應用是基于局部擴展的社區發現所特有的應用。基于局部擴展的社區發現只需要局部的拓撲結構信息即可實現，且方法簡單。它可以在對實時性要強，且能獲取其他信息較少的稀疏網絡中有較好的應用。另外，由于局部擴展方法的特點，它在種子選取階段有可能發現全局或局部最有影響力的用戶。因此，與其他社區發現方法相比，它具有一些特有的應用。

① 在微信/QQ平臺上廣告推薦中的應用

在微信/QQ平臺上，用戶的聯系人可能是家人、朋友，也可能是陌生人，所以，由微信用戶構成的社會網絡比較稀疏；另外，微信/QQ平臺上廣告上線時間短，因此獲取的標簽信息比較少，且對社區發現方法的計算復雜度有更高的要求。因此基于標簽傳播、派系過濾、邊聚類優化的社區發現方法都不適合微信/QQ平臺上廣告的推廣。因此，吳哲[52]將基于局部擴展的社區發現方法應用在微信廣告推薦中。

② 在病毒式營銷、產品推廣、企業輿情推廣中的應用

在線網絡為市場營銷提供了新的機遇，對于廣告投放者、產品供應商來說，希望找到網絡中k個影響力最大的用戶作為種子節點，并通過口口相傳的方法（病毒式營銷）讓更多用戶獲取信息或了解產品，從而獲取最大的利益。Wilder等[32]綜合隨機和局部排名選取最有影響力的種子節點，以實現影響力最大化，從而促進信息的快速傳播。本文中介紹的基于全局排名的種子選擇方法（例如，基于節點度的排名）可以找到網絡中最有影響力的用戶，從而使信息在網絡中最大化傳播[53]。除了使用基于全局排名的種子選擇方法外，也可以使用本文在局部擴展方法中介紹的貪婪算法，選擇具有最大影響力范圍增益的節點作為種子節點[54-56]。例如，李國良等[54]使用貪婪算法為多網絡選擇種子節點，并應用在病毒式營銷中；馬茜等[55]考慮到在產品推廣過程中有些種子節點無法激活，因此使用貪婪算法發現種子節點的替代節點；為了使信息在社交網絡上更好地傳播，Tong等[56]使用貪婪自適應種子選擇策略選擇最有影響力的用戶。

3） 在個性化推薦系統中的應用

在社區發現共有的應用中，當把社區結構應用到個性化推薦系統時，認為目標用戶與同一社區的用戶的偏好相似度比與其他社區的用戶的偏好相似度高，但是無法區分社區內不同用戶對目標用戶的影響。而在基于局部擴展的社區發現方法中，可以發現社區中的種子節點，因此，可以利用種子節點改善推薦性能。例如，Interdonato等[57]將基于多層局部擴展優化的社區發現應用在個性化興趣點推薦中。首先，選擇受歡迎的地方作為種子興趣點；然后根據4個數據集尋找種子節點周圍的興趣點以及興趣點之間的距離；最后，當用戶輸入需求信息后，系統會以種子節點為中心，推薦滿足用戶需求的興趣點。

6 基于局部擴展的社區發現的研究難點

基于局部擴展的社區發現包括種子的選取和局部擴展兩部分，在這兩部分中遇到的研究難點分別如下。

1） 如何有效地度量節點的權重值

全局排名、局部排名以及混合方法涉及節點的權重值，即用戶的影響力?，F有的方法是通過節點的中心度、網頁排名等來度量節點的權重值。這些方法過于簡單，有時不能準確地度量節點的權重。因此，為了準確選擇種子，需要綜合多種信息度量節點的權重值。另外，種子節點的選擇還應該考慮具體的應用。例如，在大眾點評網中，假設用戶A為新用戶，關注了100個用戶，但沒有評價過任何商家；用戶B為注冊已有3年的用戶，關注了80個用戶，評價了200家餐廳；用戶C為注冊已有3年的用戶，關注了80個用戶，評價了200家電影院。如果根據節點的中心度進行種子的選擇，則節點A會被選為種子，顯然是不合理的；綜合多種信息來度量節點的權重值但不考慮具體的應用，則節點B和C會被選為種子；綜合多種信息來度量節點的權重值且應用在餐廳推薦系統中，則節點B會被選為種子；綜合多種信息來度量節點的權重值且應用在電影院推薦系統中，則節點C會被選為種子。綜上可知，度量權重值的方法、應用不同，選擇的種子則有可能不同，而種子的選擇直接影響社區發現的結果。因此，如何有效度量節點的權重值是基于局部擴展的社區發現的難點之一。

2） 如何選擇貪婪擴展算法

貪婪擴展算法通過最大化或最小化某個指標實現社區的擴展。本文中總結了現有的一些貪婪擴展指標，這些指標從不同的角度來度量發現的社區。選擇的度量指標不同，則最終發現的社區也會不同。因此，如何選擇合適的度量指標，使發現的社區的準確性最好也是基于局部擴展的社區發現的難點之一。

7 基于局部擴展的社區發現的研究展望

目前，對基于局部擴展的社區發現已經做了大量研究，但仍然有一些需要進一步深入探索或研究的問題。

1） 基于局部擴展的社區發現方法在移動社會網絡中的應用。精確度和運行時間是基于局部擴展的社區發現方法追求的2個重要目標，然而這2個指標常?；ハ嘀萍s，提高精確度需要復雜的時間復雜度，而快速的運行時間則可能通過犧牲精確度來實現。隨著智能終端和移動網絡的完善，用戶可以隨時隨地獲取信息，因此對社區發現的實時性和精確度提出了更高的要求。為了適應移動環境，在今后的研究中，需要提出既能改進社區發現的精確度又能降低運行時間的基于局部擴展的社區發現方法。

2） 社區的初步劃分。真實的社會網絡中，用戶數量較多，為了降低基于局部擴展的社區發現方法的時間復雜度，可以使用一些合理的規則，對整個網絡進行初步劃分，然后在得到的子圖中使用基于局部擴展的社區發現方法。不同的網站有其獨有的特點，在實際應用中可以根據網站的特點設定相應的規則。例如，在大眾點評網站上，用戶數量已達千萬，如果直接在整個網絡上使用基于局部擴展的社區發現方法，則時間復雜度會非常大?？紤]到大眾點評網的特點（例如用戶在天津，那么他/她只會關注天津的餐廳、電影院等商家，且受天津用戶的影響較大），首先根據用戶注冊的位置信息將整個網絡劃分為多個子圖，然后在各個子圖上進行基于局部擴展的社區發現，則可以降低時間復雜度。因此，如何設計合理的規則，對社會網絡進行初步劃分是一個有意義的研究問題。

3） 上下文信息的引入。目前，在基于局部優化的社區發現方法中，很少考慮用戶的上下文信息，而僅僅根據用戶的行為信息完成社區發現。上下文信息的引入可以更準確地度量用戶在社會網絡中的影響力以及用戶間的影響力[58]。由于種子的選擇與節點的影響力相關（如全局排名、局部排名），且社區構建和部分局部擴展方法與用戶間影響力相關，因此，上下文信息的引入可以改善基于局部擴展的社區發現的準確性。如何合理地將上下文引入到基于局部擴展的社區發現是一個值得探索的問題。

8 結束語

隨著社交網絡、電子購物網站等的興起，社區發現得到了更廣泛的關注和研究。本文對基于局部擴展的社區發現方法的研究進展和趨勢進行歸納、總結和預測，并介紹給相關研究人員，希望能為此領域及其相關研究領域（例如用戶需求獲取、個性化推薦、群推薦、輿情監測等）提供理論依據。