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

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

1 引言

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

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

2 種子的選擇方法

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

2.1 隨機選擇某個不屬于任何社區(qū)的節(jié)點或邊

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

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

2.2 根據(jù)全局排名選擇種子

根據(jù)全局排名選擇種子的方法根據(jù)節(jié)點權重值在整個網(wǎng)絡中的排名選擇種子。

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

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

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

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

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

2.3 根據(jù)局部排名選擇種子

根據(jù)局部排名選擇種子的方法根據(jù)節(jié)點權重值在局部網(wǎng)絡中的排名選擇種子。

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

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

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

局部排名選擇方法的缺點是有可能無法發(fā)現(xiàn)最大的社區(qū)，而使用極大團作為初始節(jié)點的社區(qū)發(fā)現(xiàn)方法則可以解決該問題。

2.4 極大團

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

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

2.5 k-回路

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

2.6 混合方法

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

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

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

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

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

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

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

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

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

3 局部擴展優(yōu)化方法

本文將局部擴展優(yōu)化算法分為基于無監(jiān)督的局部擴展優(yōu)化方法和基于半監(jiān)督的局部擴展優(yōu)化方法兩大類進行介紹。

3.1 基于無監(jiān)督的局部擴展優(yōu)化方法

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

1） 最大化適應度函數(shù)

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

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

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

2） 最大化可調密度增益

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

3） 最大化局部相關度

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

4） 最大化模塊度

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

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

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

6） 最大化概率

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

7） 最大化中心度

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

8） 最小化傳導值

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

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

9） 最大化社區(qū)權重

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

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

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

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

3.2 基于半監(jiān)督的局部擴展優(yōu)化方法

基于半監(jiān)督的局部擴展優(yōu)化方法通過獲取部分節(jié)點先驗知識來指導社區(qū)發(fā)現(xiàn)，從而避免無監(jiān)督方法的盲目性。通常考慮的先驗知識包括以下2種：1） 已知部分節(jié)點的社區(qū)標簽（例如種子節(jié)點）；2） 成對節(jié)點之間的必須連接和不可能連接的約束[35]。

1） 已知部分節(jié)點的社區(qū)標簽

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

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

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

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

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

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

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

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

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

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

4 評價指標

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

4.1 模塊度

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

其中，eii表示社區(qū)Ci的內部邊與網(wǎng)絡中總邊數(shù)的比例，eij表示連接社區(qū)Ci和社區(qū)Cj的邊與網(wǎng)絡中總邊數(shù)的比例，ai表示一端和社區(qū)Ci中節(jié)點相連的邊與網(wǎng)絡中總邊數(shù)的比例，且

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

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

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

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

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

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

4.2 標準互信息

1） NMI

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

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

當評價社區(qū)發(fā)現(xiàn)的質量時，I值越大，則表明社區(qū)發(fā)現(xiàn)的結果越準確，當發(fā)現(xiàn)的社區(qū)劃分與真實社區(qū)一致時，I=1。

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

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

2）F1-measure

F1-measure是正確率和召回率的調和平均值，用于衡量給定社區(qū)發(fā)現(xiàn)結果與真實社區(qū)結構的相似度/相關度，可以度量社區(qū)發(fā)現(xiàn)結果的精度。在不同的文獻中，研究人員給出了不同的命名，例如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）表示社區(qū)發(fā)現(xiàn)的準確率，Recall（Cf,j,Cr,i）表示社區(qū)發(fā)現(xiàn)的召回率，其計算式如式（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）既適用于非重疊社區(qū)也適用于重疊社區(qū)。

3） Jaccard 系數(shù)

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

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

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

5 基于局部擴展的社區(qū)發(fā)現(xiàn)的應用

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

1） 社區(qū)發(fā)現(xiàn)方法共有的應用

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

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

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

③ 在醫(yī)療疾病方面的應用。將社區(qū)發(fā)現(xiàn)應用在患者分類、疾病識別等方面。例如Hoshi等[48]根據(jù)發(fā)現(xiàn)的社區(qū)結構對患者進行分類；Mall等[49]根據(jù)社區(qū)結構對生物網(wǎng)絡中的疾病模塊進行識別；Steve等[50]則將發(fā)現(xiàn)的社區(qū)結構應用在復雜疾病關聯(lián)分析中。

④ 在生物學方面的應用。將社區(qū)發(fā)現(xiàn)應用在神經(jīng)、蛋白質等網(wǎng)絡中。Becker等[30]根據(jù)蛋白質相互作用網(wǎng)絡中的重疊社區(qū)發(fā)現(xiàn)多功能蛋白質；Garcia等[51]將社區(qū)發(fā)現(xiàn)應用在神經(jīng)影像構建的腦圖中。

2） 基于局部擴展的社區(qū)發(fā)現(xiàn)方法特有的應用

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

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

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

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

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

3） 在個性化推薦系統(tǒng)中的應用

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

6 基于局部擴展的社區(qū)發(fā)現(xiàn)的研究難點

基于局部擴展的社區(qū)發(fā)現(xiàn)包括種子的選取和局部擴展兩部分，在這兩部分中遇到的研究難點分別如下。

1） 如何有效地度量節(jié)點的權重值

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

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

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

7 基于局部擴展的社區(qū)發(fā)現(xiàn)的研究展望

目前，對基于局部擴展的社區(qū)發(fā)現(xiàn)已經(jīng)做了大量研究，但仍然有一些需要進一步深入探索或研究的問題。

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

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

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

8 結束語

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