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

（天津科技大學(xué)計(jì)算機(jī)科學(xué)與信息工程學(xué)院，天津 300457）

1 引言

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

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

2 種子的選擇方法

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

2.1 隨機(jī)選擇某個(gè)不屬于任何社區(qū)的節(jié)點(diǎn)或邊

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 極大團(tuán)

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

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

2.5 k-回路

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

2.6 混合方法

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

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

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

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

由表1和上述分析可得以下結(jié)論。

1） 時(shí)間復(fù)雜度。隨機(jī)選擇方法的時(shí)間復(fù)雜度最小。混合選擇方法綜合了多種方法的優(yōu)點(diǎn)，大多數(shù)情況下時(shí)間復(fù)雜度不是太大。全局排名方法需要計(jì)算所有節(jié)點(diǎn)的權(quán)重值，有時(shí)還需要計(jì)算多次，由于計(jì)算復(fù)雜度與節(jié)點(diǎn)的規(guī)模呈正比，當(dāng)應(yīng)用在大規(guī)模的網(wǎng)絡(luò)（例如有上億用戶的微信）時(shí)，其計(jì)算復(fù)雜度會(huì)很大。基于局部排名的方法在選擇節(jié)點(diǎn)時(shí)，只需要與局部節(jié)點(diǎn)進(jìn)行對(duì)比，在最好的情況下，其時(shí)間復(fù)雜度可以降為NnUK。k-回路的時(shí)間復(fù)雜度與節(jié)點(diǎn)和邊的數(shù)量成正比，所以在大規(guī)模網(wǎng)絡(luò)中，其時(shí)間復(fù)雜度比較大。極大團(tuán)的時(shí)間復(fù)雜度最大。

表1 種子選擇方法的時(shí)間復(fù)雜度的對(duì)比

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

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

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

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

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

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

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

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

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

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

2） 最大化可調(diào)密度增益

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

3） 最大化局部相關(guān)度

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

4） 最大化模塊度

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

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

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

6） 最大化概率

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

7） 最大化中心度

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

8） 最小化傳導(dǎo)值

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

但該擴(kuò)展方法對(duì)社區(qū)的內(nèi)部連通性不是很敏感，在最壞的情況下，具有低傳導(dǎo)值集合的內(nèi)部可能是斷開(kāi)的。

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

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

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

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

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

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

基于半監(jiān)督的局部擴(kuò)展優(yōu)化方法通過(guò)獲取部分節(jié)點(diǎn)先驗(yàn)知識(shí)來(lái)指導(dǎo)社區(qū)發(fā)現(xiàn)，從而避免無(wú)監(jiān)督方法的盲目性。通?？紤]的先驗(yàn)知識(shí)包括以下2種：1） 已知部分節(jié)點(diǎn)的社區(qū)標(biāo)簽（例如種子節(jié)點(diǎn)）；2） 成對(duì)節(jié)點(diǎn)之間的必須連接和不可能連接的約束[35]。

1） 已知部分節(jié)點(diǎn)的社區(qū)標(biāo)簽

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

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

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

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

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

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

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

表2 局部擴(kuò)展方法的時(shí)間復(fù)雜度對(duì)比

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

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

4 評(píng)價(jià)指標(biāo)

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

4.1 模塊度

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

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

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

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

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

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

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

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

4.2 標(biāo)準(zhǔn)互信息

1） NMI

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

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

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

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

其中，X和Y分別表示Cr和Cf相關(guān)的隨機(jī)變量，H（X|Y）表示X對(duì)Y的條件熵。

2）F1-measure

F1-measure是正確率和召回率的調(diào)和平均值，用于衡量給定社區(qū)發(fā)現(xiàn)結(jié)果與真實(shí)社區(qū)結(jié)構(gòu)的相似度/相關(guān)度，可以度量社區(qū)發(fā)現(xiàn)結(jié)果的精度。在不同的文獻(xiàn)中，研究人員給出了不同的命名，例如F-measure[3,23]、成對(duì)F-measure[35]、F1-measure[16]、F-score[33]、F1score[2,18,41]，在本文中，將該評(píng)價(jià)指標(biāo)命名為F1-measure。計(jì)算式如式（7）和式（8）所示。

其中，precision（Cf,j,Cr,i）表示社區(qū)發(fā)現(xiàn)的準(zhǔn)確率，Recall（Cf,j,Cr,i）表示社區(qū)發(fā)現(xiàn)的召回率，其計(jì)算式如式（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的思想相同，也是通過(guò)計(jì)算社區(qū)發(fā)現(xiàn)結(jié)果與真實(shí)社會(huì)結(jié)構(gòu)的相似程度來(lái)評(píng)價(jià)社區(qū)發(fā)現(xiàn)結(jié)果的質(zhì)量，其定義如式（13）和式（14）所示[9]。

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

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

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

大部分基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)方法的研究重點(diǎn)是如何更準(zhǔn)確地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)，而對(duì)其具體的應(yīng)用介紹的較少。基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)方法不僅可以發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)，有些方法還可以發(fā)現(xiàn)網(wǎng)絡(luò)中全局或局部最有影響力的用戶，例如基于全局排名的種子選擇方法可以發(fā)現(xiàn)網(wǎng)絡(luò)中最有影響力的用戶，而基于局部排名的種子選擇方法可以發(fā)現(xiàn)網(wǎng)絡(luò)中局部最有影響力的用戶。鑒于此，本文對(duì)基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)的具體應(yīng)用總結(jié)如下。

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

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

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

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

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

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

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

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

① 在微信/QQ平臺(tái)上廣告推薦中的應(yīng)用

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

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

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

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

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

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

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

1） 如何有效地度量節(jié)點(diǎn)的權(quán)重值

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

2） 如何選擇貪婪擴(kuò)展算法

貪婪擴(kuò)展算法通過(guò)最大化或最小化某個(gè)指標(biāo)實(shí)現(xiàn)社區(qū)的擴(kuò)展。本文中總結(jié)了現(xiàn)有的一些貪婪擴(kuò)展指標(biāo)，這些指標(biāo)從不同的角度來(lái)度量發(fā)現(xiàn)的社區(qū)。選擇的度量指標(biāo)不同，則最終發(fā)現(xiàn)的社區(qū)也會(huì)不同。因此，如何選擇合適的度量指標(biāo)，使發(fā)現(xiàn)的社區(qū)的準(zhǔn)確性最好也是基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)的難點(diǎn)之一。

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

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

1） 基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)方法在移動(dòng)社會(huì)網(wǎng)絡(luò)中的應(yīng)用。精確度和運(yùn)行時(shí)間是基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)方法追求的2個(gè)重要目標(biāo)，然而這2個(gè)指標(biāo)常常互相制約，提高精確度需要復(fù)雜的時(shí)間復(fù)雜度，而快速的運(yùn)行時(shí)間則可能通過(guò)犧牲精確度來(lái)實(shí)現(xiàn)。隨著智能終端和移動(dòng)網(wǎng)絡(luò)的完善，用戶可以隨時(shí)隨地獲取信息，因此對(duì)社區(qū)發(fā)現(xiàn)的實(shí)時(shí)性和精確度提出了更高的要求。為了適應(yīng)移動(dòng)環(huán)境，在今后的研究中，需要提出既能改進(jìn)社區(qū)發(fā)現(xiàn)的精確度又能降低運(yùn)行時(shí)間的基于局部擴(kuò)展的社區(qū)發(fā)現(xiàn)方法。

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

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

8 結(jié)束語(yǔ)

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