竺俊超,王朝坤

(清華大學(xué) 軟件學(xué)院,北京 100084)

由大量節(jié)點(diǎn)和節(jié)點(diǎn)間的連接關(guān)系形成的網(wǎng)絡(luò)結(jié)構(gòu)廣泛存在于計(jì)算機(jī)科學(xué)、生物學(xué)和社會(huì)學(xué)[1,2]等領(lǐng)域,例如以網(wǎng)頁為節(jié)點(diǎn)、以網(wǎng)頁間的鏈接為邊組成的萬維網(wǎng)[3]和以人為節(jié)點(diǎn)、以人際間關(guān)系為邊建立的社會(huì)網(wǎng)[1,2]等.在網(wǎng)絡(luò)相關(guān)研究工作中,社區(qū)(community)的概念持續(xù)受到人們的關(guān)注.一般而言,社區(qū)是指內(nèi)部節(jié)點(diǎn)間聯(lián)系較內(nèi)部與外部節(jié)點(diǎn)間聯(lián)系更為緊密的子網(wǎng)絡(luò).發(fā)現(xiàn)網(wǎng)絡(luò)中的各種社區(qū)結(jié)構(gòu)有助于進(jìn)行好友推薦、犯罪團(tuán)伙識(shí)別以及蛋白質(zhì)功能預(yù)測[4-6],同時(shí)能夠有效支持網(wǎng)絡(luò)中傳播熱點(diǎn)選擇[7]和介數(shù)中心度更新[8].

社區(qū)搜索(community search)是指給定一個(gè)或多個(gè)節(jié)點(diǎn),尋找包含它們的社區(qū)[9-14].與社區(qū)發(fā)現(xiàn)(community detection)相比,它更關(guān)注局部的網(wǎng)絡(luò)結(jié)構(gòu),能夠返回更加個(gè)性化的社區(qū)結(jié)果.

現(xiàn)有的社區(qū)搜索方法包括僅與網(wǎng)絡(luò)拓?fù)溆嘘P(guān)的社區(qū)搜索和與節(jié)點(diǎn)屬性有關(guān)的社區(qū)搜索:前者旨在尋找包含給定節(jié)點(diǎn)集且滿足k-clique[9],k-core[10,11]或k-truss[12,13]等特定拓?fù)浣Y(jié)構(gòu)的社區(qū);后者在尋找包含給定節(jié)點(diǎn)集的社區(qū)時(shí)綜合考慮了拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性[15-17],返回的結(jié)果社區(qū)不僅要滿足特定拓?fù)浣Y(jié)構(gòu),還要使內(nèi)部節(jié)點(diǎn)的屬性盡可能相近.

然而,已有的社區(qū)搜索研究成果尚不能滿足人們?nèi)找嬖鲩L的客觀需求.例如,在實(shí)際應(yīng)用中經(jīng)常會(huì)遇到這樣一些問題:如何準(zhǔn)確地找到一個(gè)社區(qū),使它不僅包含某些給定節(jié)點(diǎn),同時(shí)不包含另一些給定節(jié)點(diǎn)?如何智能地找到一個(gè)社區(qū),至少要包含給定的5個(gè)節(jié)點(diǎn)中的任意3個(gè)?本文將這類包含對節(jié)點(diǎn)條件約束的社區(qū)搜索問題統(tǒng)稱為條件社區(qū)搜索問題(conditional community search,簡稱CCS).據(jù)我們所知,目前國內(nèi)外尚未見針對CCS問題的公開報(bào)道.

例1(社交場景):用戶A和B擬共同組建一個(gè)學(xué)習(xí)討論小組,組內(nèi)成員盡可能互相認(rèn)識(shí)以便討論,且不希望保險(xiǎn)推銷員C參與.則A和B可以邀請哪些人加入該小組?

圖1展示了上述社交場景中的部分網(wǎng)絡(luò)結(jié)構(gòu),其中,節(jié)點(diǎn)代表人物,邊代表好友關(guān)系.若以A和B作為社區(qū)必須包含的節(jié)點(diǎn),則依據(jù)以 2-core為基礎(chǔ)的社區(qū)搜索方法得到的結(jié)果社區(qū)如實(shí)線圈所示.這是因?yàn)樵撋鐓^(qū)中每位用戶在本社區(qū)內(nèi)都有至少兩位好友并且該社區(qū)僅有兩條從內(nèi)部連向外部的邊,具有內(nèi)部節(jié)點(diǎn)間聯(lián)系較內(nèi)部與外部節(jié)點(diǎn)間聯(lián)系更加緊密的性質(zhì).但是該社區(qū)顯然不滿足節(jié)點(diǎn)C不參與的要求.如果應(yīng)用CCS來計(jì)算,即找到一個(gè)包含A和B,同時(shí)不包含C的社區(qū),那么結(jié)果社區(qū)如虛線圈所示.這是因?yàn)樵撋鐓^(qū)內(nèi)每位用戶都有至少兩位好友,同時(shí)節(jié)點(diǎn)C不出現(xiàn)在此社區(qū)中.進(jìn)一步而言,C也很難通過其好友加入到該社區(qū)內(nèi).因此對于例1,A和B可以邀請?zhí)摼€圈中的成員組建討論小組.此外,在視頻網(wǎng)站為用戶提供社區(qū)推薦、購物網(wǎng)站為用戶提供相關(guān)商品推薦等場景下,也會(huì)遇到用戶不希望特定的人物或商品出現(xiàn)在推薦列表中的需求.

Fig.1 An example for conditional community search圖1 條件社區(qū)搜索的示例

例2(商業(yè)場景):某公司發(fā)生了商業(yè)機(jī)密泄露事件,內(nèi)部能夠接觸該機(jī)密的有A,B兩人,而競爭對手公司中取得此機(jī)密的是C,D兩人.該公司希望對A和B展開調(diào)查,找出A或B中至少一人可能與C或D存在的聯(lián)系.通過郵件、電話等聯(lián)系方式建立了社會(huì)關(guān)系網(wǎng)絡(luò)后,可以通過尋找至少包含A,B中一人、C,D中一人的社區(qū)來獲得相關(guān)信息.

例 2中的場景對于結(jié)果社區(qū)提出了一類典型需求,即至少包含給定節(jié)點(diǎn)中的任意一個(gè).顯然,傳統(tǒng)社區(qū)搜索方法缺乏對該需求的有效支持;借助CCS,可以將上述需求通過布爾表達(dá)式的形式清晰地予以表示.

上述實(shí)例表明,現(xiàn)有的社區(qū)搜索方法難以有效解決迫切的客觀需求.為此,本文提出并研究條件社區(qū)搜索問題,給出條件社區(qū)搜索的通用框架,嘗試對社交網(wǎng)絡(luò)進(jìn)行智能分析,在復(fù)雜的搜索條件下,為用戶提供更好的結(jié)果社區(qū).

事實(shí)上,傳統(tǒng)的社區(qū)搜索問題可以看做是條件社區(qū)搜索問題的特例,其中,搜索條件退化為社區(qū)中需要包含全部給定節(jié)點(diǎn).需要注意的是:本文關(guān)注如何在復(fù)雜條件下進(jìn)行社區(qū)搜索來獲得更加符合實(shí)際需求的結(jié)果社區(qū),而未涉及新社區(qū)結(jié)構(gòu)的設(shè)計(jì),即現(xiàn)有的社區(qū)結(jié)構(gòu)都可以應(yīng)用到條件社區(qū)搜索中來.

本文的主要貢獻(xiàn)包括:

(1) 提出條件社區(qū)搜索這一新問題,并給出其形式化定義;

(2) 提出條件社區(qū)搜索的通用框架,并對其中的單項(xiàng)條件社區(qū)搜索步驟給出“社區(qū)搜索+過濾”的方法和基于標(biāo)簽傳播給點(diǎn)加權(quán)的方法(weighting by label propagation,簡稱WLP);

(3) 在真實(shí)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果驗(yàn)證了所提方法的正確性和有效性.

本文第 1節(jié)介紹相關(guān)工作,包括社區(qū)發(fā)現(xiàn)和社區(qū)搜索的一般方法.第 2節(jié)給出條件社區(qū)搜索問題的形式化定義、解決該問題的通用框架和搜索條件的簡化策略.第 3節(jié)提出對于單項(xiàng)條件社區(qū)搜索的解決方法.第 4節(jié)報(bào)告并分析實(shí)驗(yàn)結(jié)果,包括對搜索條件簡化的有效性驗(yàn)證以及“社區(qū)搜索+過濾”方法和 WLP方法在時(shí)間開銷和社區(qū)結(jié)果質(zhì)量上的比較.第5節(jié)總結(jié)全文.

1 相關(guān)工作

本節(jié)介紹社區(qū)發(fā)現(xiàn)和社區(qū)搜索的概念,并簡要回顧解決這兩類問題的方法.

1.1 社區(qū)發(fā)現(xiàn)

社區(qū)發(fā)現(xiàn),亦稱為全局社區(qū)發(fā)現(xiàn)(global community detection),指找出給定網(wǎng)絡(luò)圖中的所有社區(qū).社區(qū)這一概念尚沒有統(tǒng)一的形式化定義,目前研究工作中的社區(qū)定義一般依據(jù)特定拓?fù)浣Y(jié)構(gòu)或者描述子圖緊密程度的度量指標(biāo)給出.社區(qū)發(fā)現(xiàn)的常用方法主要包括劃分、聚類、標(biāo)簽傳播等[18].

劃分方法指通過刪除網(wǎng)絡(luò)圖中的一些邊,將原圖自然地分成若干個(gè)連通分量來得到社區(qū)結(jié)果.Kernighan-Lin算法[19]要求最大化社區(qū)內(nèi)節(jié)點(diǎn)連邊數(shù)量與不同社區(qū)間節(jié)點(diǎn)連邊數(shù)量的差值.SCD算法[20]要求刪除不屬于任何三角形的邊.KMF算法[21]則要求刪除兩端點(diǎn)共同鄰居節(jié)點(diǎn)的個(gè)數(shù)少于給定閾值的邊.

聚類方法包括層次聚類、譜聚類、k-means聚類等.層次聚類通過自上而下不斷刪除邊或者自下而上不斷加入點(diǎn)的方式得到網(wǎng)絡(luò)圖的層次結(jié)構(gòu),然后切分該結(jié)構(gòu)來得到社區(qū).典型方法包括 Fast-Newman[22],CNM[23],Radicchi[24],GN[25],MSG-VM[26]和DOC[27]等.譜聚類通過將網(wǎng)絡(luò)表示為特定的拉普拉斯矩陣,基于同一社區(qū)內(nèi)的節(jié)點(diǎn)在矩陣中特征向量近似的思想進(jìn)行聚類[28-30].k-means聚類是常見的聚類方法.在社區(qū)發(fā)現(xiàn)問題中,常用點(diǎn)和點(diǎn)之間的距離[31]、Random Walk[32,33]等方式給出兩點(diǎn)間相似度量,接著采用k-means聚類進(jìn)行社區(qū)發(fā)現(xiàn).近年來還涌現(xiàn)出基于深度學(xué)習(xí)的聚類方法,即學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)的低維向量表示,再通過聚類得到社區(qū),如 CoDDA[34],DeepWalk[35]和 GraRep[36]等.

標(biāo)簽傳播方法通常為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)賦予初始標(biāo)簽,接著模擬信息傳播過程為每個(gè)節(jié)點(diǎn)更新標(biāo)簽,最后通過標(biāo)簽分布確定社區(qū)歸屬.基于標(biāo)簽傳播思想的典型方法包括LPA[37],HANP[38]和SLPA[39]等.

1.2 社區(qū)搜索

社區(qū)搜索也稱局部社區(qū)發(fā)現(xiàn)(local community detection).給定一個(gè)或多個(gè)節(jié)點(diǎn),社區(qū)搜索旨在尋找包含這些節(jié)點(diǎn)的社區(qū).由于關(guān)注局部網(wǎng)絡(luò)結(jié)構(gòu),社區(qū)搜索能夠高效地找到用戶關(guān)心的節(jié)點(diǎn)所在的社區(qū).目前常見的社區(qū)搜索算法主要基于k-clique[9],k-core[10,11]和k-truss[12,13]等特定結(jié)構(gòu).例如,Cui等人提出了尋找包含一個(gè)給定節(jié)點(diǎn)的k-core社區(qū)的問題(CST)和對應(yīng)算法[11].該算法從給定節(jié)點(diǎn)向外擴(kuò)展得到結(jié)果社區(qū).Huang等人提出了基于k-truss的社區(qū)定義,并設(shè)計(jì)了TCP-index來尋找包含某個(gè)給定節(jié)點(diǎn)的社區(qū)[12].

此外還有一類結(jié)合拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性的社區(qū)搜索方法[15-17].例如:Shang等人根據(jù)節(jié)點(diǎn)在拓?fù)浣Y(jié)構(gòu)和屬性上的相似關(guān)系構(gòu)建一個(gè)TA-graph,并在此基礎(chǔ)上提出與節(jié)點(diǎn)屬性相關(guān)的社區(qū)搜索算法AGAR[15];Fang等人在k-core結(jié)構(gòu)基礎(chǔ)上要求社區(qū)內(nèi)節(jié)點(diǎn)共享盡可能多的標(biāo)簽屬性,設(shè)計(jì)了對應(yīng)索引結(jié)構(gòu) CL-tree[16];Huang等人在k-truss結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)了一個(gè)打分函數(shù)來度量給定節(jié)點(diǎn)屬性在社區(qū)內(nèi)的流行程度,并提出Attribute Truss社區(qū)定義[17].

2 條件社區(qū)搜索

條件社區(qū)搜索問題不僅要能夠描述社區(qū)必須包含給定節(jié)點(diǎn)這一基本搜索條件,還要能夠描述兩種新的搜索條件:一是社區(qū)不允許包含給定節(jié)點(diǎn),二是社區(qū)至少要包含若干給定節(jié)點(diǎn)中的一個(gè).本節(jié)首先基于布爾表達(dá)式給出搜索條件的形式化表達(dá),接著提出條件社區(qū)搜索通用框架,最后給出搜索條件的簡化方法.

2.1 搜索條件的形式化表達(dá)

布爾表達(dá)式是由布爾變量和邏輯運(yùn)算符組成的式子.布爾變量的取值為真或假,亦可用1或0來表示.邏輯運(yùn)算符包括與(∧)、或(∨)、非(?)等.在每個(gè)布爾變量的取值確定后,可以判斷整個(gè)布爾表達(dá)式的真假.于是,可以考慮用布爾表達(dá)式表示搜索條件.

2.1.1 搜索條件的表示形式

通常,對于一個(gè)給定社區(qū),一個(gè)節(jié)點(diǎn)是否存在于該社區(qū)中可以表示為一個(gè)布爾變量.若節(jié)點(diǎn)存在于該社區(qū)中,則對應(yīng)布爾變量取值為真;反之為假.本文將指代節(jié)點(diǎn)的布爾變量稱為節(jié)點(diǎn)變量.借助節(jié)點(diǎn)變量和邏輯運(yùn)算符構(gòu)成的布爾表達(dá)式,可以有效表示條件社區(qū)搜索問題中的具體搜索條件.

定義1(基本搜索條件).基本搜索條件規(guī)定為:

(1) 單個(gè)節(jié)點(diǎn)變量X是基本搜索條件;

(2) 如果X和Y是基本搜索條件,那么X∧Y是基本搜索條件;

(3) 當(dāng)且僅當(dāng)有限次地應(yīng)用條件(1)和條件(2)所得到的布爾表達(dá)式稱為基本搜索條件.

定義2(搜索條件).搜索條件規(guī)定為:

(1) 單個(gè)節(jié)點(diǎn)變量X是搜索條件;

(2) 如果X是搜索條件,那么?X是搜索條件;

(3) 如果X和Y是搜索條件,那么X∧Y,X∨Y是搜索條件;

(4) 當(dāng)且僅當(dāng)有限次地應(yīng)用條件(1)～條件(3)所得到的布爾表達(dá)式稱為搜索條件.

本文將滿足定義2但不滿足定義1的布爾表達(dá)式稱為復(fù)雜搜索條件.

例3:例1中的搜索條件可表示為A∧B∧?C.該布爾表達(dá)式在變量A和B為真,且C為假時(shí)取真值,對應(yīng)包含節(jié)點(diǎn)A和B但不包含節(jié)點(diǎn)C的社區(qū).例2中的搜索條件可表示為(A∨B)∧(C∨D).該布爾表達(dá)式在變量A或B為真,且C或D為真時(shí)取真值,對應(yīng)包含A,B中某一人和C,D中某一人的社區(qū).

以上實(shí)例表明,布爾表達(dá)式能夠有效表示搜索條件.同時(shí),也容易根據(jù)社區(qū)中是否包含某個(gè)節(jié)點(diǎn)得到對應(yīng)變量的值,從而驗(yàn)證搜索條件.接下來給出條件社區(qū)搜索問題的形式化定義.

定義3(條件社區(qū)搜索問題CCS).給定連通圖G=(V,E)和節(jié)點(diǎn)集V′?V,尋找至少一個(gè)滿足如下條件的節(jié)點(diǎn)集H:(1)H?V;(2)G[H]是連通的,其中,G[H]表示H的導(dǎo)出子圖;(3)H滿足定義在V′上的搜索條件F;(4)H滿足用戶給定的社區(qū)定義?.

其中,搜索條件F按定義2給出,?可以按用戶需求進(jìn)行指定,例如基于k-core[10,11]或k-truss[12,13]的社區(qū)定義.

事實(shí)上,CCS包含了現(xiàn)有的社區(qū)搜索問題.易知有如下引理.

引理1.社區(qū)搜索問題是條件社區(qū)搜索問題的特例.

這是因?yàn)楫?dāng)搜索條件F為基本搜索條件,即F中僅包含節(jié)點(diǎn)變量和邏輯與(∧)時(shí),可以把F涉及的節(jié)點(diǎn)合成一個(gè)節(jié)點(diǎn)集作為社區(qū)搜索算法的輸入.此時(shí),條件社區(qū)搜索問題就退化成社區(qū)搜索問題.

2.1.2 條件社區(qū)搜索的通用框架

條件社區(qū)搜索的通用框架將用戶給定的條件社區(qū)搜索問題分解為若干單項(xiàng)條件社區(qū)搜索(single conditional community search,簡稱 SCCS)分別處理,而后進(jìn)行結(jié)果匯聚.需要注意的是,盡管條件社區(qū)搜索存在一種樸素的解決方法——首先對給定網(wǎng)絡(luò)進(jìn)行全局社區(qū)發(fā)現(xiàn)來得到所有社區(qū),接著判斷每個(gè)社區(qū)是否滿足搜索條件,最后留下滿足搜索條件的社區(qū),但是該方法需要找到全部社區(qū),時(shí)間開銷巨大.

定義4(單項(xiàng)條件社區(qū)搜索SCCS).對于一個(gè)條件社區(qū)搜索問題,如果有且僅有一組節(jié)點(diǎn)變量的取值能滿足它的搜索條件F,則稱其為單項(xiàng)條件社區(qū)搜索.

定理1.任意一個(gè)單項(xiàng)條件社區(qū)搜索的搜索條件等價(jià)于一個(gè)合取式(僅由邏輯與運(yùn)算符連接節(jié)點(diǎn)變量或其否定構(gòu)成的式子).

證明:因?yàn)橹挥幸唤M能滿足搜索條件的節(jié)點(diǎn)變量取值,所以每個(gè)節(jié)點(diǎn)能否存在于社區(qū)中是唯一確定的.于是可以構(gòu)造這樣一個(gè)等價(jià)合取式:先用邏輯非修飾不允許出現(xiàn)在社區(qū)中的節(jié)點(diǎn)變量,而后用邏輯與連接所有節(jié)點(diǎn)變量. □

給定一個(gè)搜索條件,可以先枚舉各節(jié)點(diǎn)變量的可能取值,計(jì)算得到一個(gè)真值表,從而找出所有能滿足搜索條件的節(jié)點(diǎn)變量取值組合.用1和0分別代表節(jié)點(diǎn)是否存在于社區(qū)中,于是,滿足例1中搜索條件的節(jié)點(diǎn)變量組合僅有 1組,即A=1,B=1,C=0,例 2則有 9組.接著,對每一種取值組合嘗試找到對應(yīng)的單項(xiàng)社區(qū)搜索的結(jié)果.最后,將每個(gè)單項(xiàng)社區(qū)搜索的結(jié)果合并,就能得到條件社區(qū)搜索的結(jié)果.

綜上,可以歸納出三階段的條件社區(qū)搜索通用框架.

(1) 枚舉所有滿足條件的節(jié)點(diǎn)變量取值組合;

(2) 將每一個(gè)組合對應(yīng)的合取式作為單項(xiàng)條件社區(qū)搜索的條件輸入并執(zhí)行;(3) 合并所有單項(xiàng)條件社區(qū)搜索的結(jié)果.

2.2 條件社區(qū)搜索問題的復(fù)雜性

條件社區(qū)搜索問題的復(fù)雜性和給定的社區(qū)定義及搜索條件有關(guān).通常情況下,CCS是NP完全的.

由引理1,在基本搜索條件下,CCS退化為社區(qū)搜索問題.許多傳統(tǒng)的社區(qū)搜索問題已被證明是 NP完全的,例如尋找滿足k-core定義的最小社區(qū)的問題(mCST)[11].

此外,若把連通子圖作為社區(qū)定義,則CCS是NP完全的.這是因?yàn)镃CS的結(jié)果能夠在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證,是一個(gè)NP問題;同時(shí),布爾邏輯的可滿足性問題(SAT)可以歸約到CCS上.歸約的方法是以布爾表達(dá)式的所有變量對應(yīng)的節(jié)點(diǎn)構(gòu)造一個(gè)完全圖,將布爾表達(dá)式直接對應(yīng)于搜索條件.此時(shí),CCS每產(chǎn)生一個(gè)結(jié)果就等同于找到一組滿足布爾表達(dá)式的解.

這意味著對于上述幾類CCS問題很難找到快速有效的多項(xiàng)式時(shí)間算法.需要注意的是:并非所有的CCS都是NP完全的,如果能夠在多項(xiàng)式時(shí)間內(nèi)找到所有的社區(qū)結(jié)構(gòu)(如k-truss[12]結(jié)構(gòu)就存在多項(xiàng)式時(shí)間的算法),那么可以利用逐一驗(yàn)證搜索條件的樸素方法解決CCS,盡管這樣做的效率較低.

2.3 搜索條件的簡化

因?yàn)椴紶栠壿嫷目蓾M足性(SAT)問題是一個(gè)NP完全問題,所以很難對第2.1節(jié)提出的條件社區(qū)搜索通用框架的第 1步進(jìn)行優(yōu)化.在實(shí)際應(yīng)用中,考慮到用戶輸入的節(jié)點(diǎn)變量總數(shù)一般不會(huì)很多,采用枚舉形式尋找滿足搜索條件的變量取值是可行的.若用戶輸入的節(jié)點(diǎn)數(shù)量較多,則可以使用求解 SAT的快速算法,例如 DPLL[40],GRASP[41]等.注意到通用框架的第2步對每個(gè)滿足條件的取值組合都要進(jìn)行一次單項(xiàng)條件社區(qū)搜索,于是考慮改進(jìn)這一步驟,在一次搜索中同時(shí)處理多個(gè)變量取值組合,從而減少總搜索次數(shù).

首先,在得到所有滿足搜索條件的變量取值組合后,可寫出與搜索條件等價(jià)的主析取范式[42],即對搜索條件進(jìn)行規(guī)范化.例如,用戶輸入的搜索條件是?A∧(B∨C),滿足該式的變量取值組合是:A=0,B=1,C=1;A=0,B=0,C=1和A=0,B=1,C=0,從而把搜索條件規(guī)范化為(?A∧B∧C)∨(?A∧?B∧C)∨(?A∧B∧?C).主析取范式是合取式的析取,其中每個(gè)合取式包含所有節(jié)點(diǎn)變量,對應(yīng)于一組滿足條件的變量取值,即一次單項(xiàng)條件社區(qū)搜索.

接下來,排除主析取范式形式的搜索條件可能存在的冗余.例如,范式(A∧B)∨(A∧?B)可化簡成A,即變量B存在與否對搜索條件不產(chǎn)生實(shí)際影響.本文用奎因-麥克拉斯基(Quine-McCluskey,簡稱 QM)算法[43]將主析取范式轉(zhuǎn)化為等價(jià)的最簡與或式,從而消除此類冗余,進(jìn)而減少單項(xiàng)條件社區(qū)搜索次數(shù).由于最簡與或式具有最少的合取式個(gè)數(shù),所以根據(jù)最簡與或式進(jìn)行單項(xiàng)條件社區(qū)搜索的次數(shù)是最少的.

最后,在最簡與或式基礎(chǔ)上進(jìn)一步發(fā)現(xiàn)可以通過提取部分合取式的公共變量來提高搜索效率.以搜索條件(A∧B∧C)∨(A∧B∧D)為例,需要對該最簡與或式中的兩個(gè)合取式分別進(jìn)行一次單項(xiàng)條件社區(qū)搜索.容易發(fā)現(xiàn),這兩個(gè)合取式里都出現(xiàn)了變量A和B.若將其提取到外部,則該式變形為(A∧B)∧(C∨D),可看做一個(gè)合取式與一個(gè)析取式的合取.本文將一個(gè)合取式與至多一個(gè)析取式的合取稱為搜索項(xiàng);接下來,可以用合取式A∧B作為輸入進(jìn)行單項(xiàng)條件社區(qū)搜索;最后,用析取式C∨D來對搜索得到的社區(qū)進(jìn)行判別,使得所需單項(xiàng)條件社區(qū)搜索的次數(shù)減1.這種合并公共節(jié)點(diǎn)變量、把多個(gè)單項(xiàng)條件社區(qū)搜索一起進(jìn)行的操作能夠有效地提高整體搜索效率,減少時(shí)間開銷.

為有效提取各合取式中的公共變量,本文采取一種貪心的思想:首先統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)變量在最簡與或式的各合取式中出現(xiàn)的次數(shù),找到出現(xiàn)次數(shù)最多的變量;接著,合并含有該變量的所有合取式;而后,用同樣策略嘗試合并剩余合取式,直至不能合并為止.具體提取過程見算法 1,其中,merge方法用于提取若干個(gè)合取式的公共節(jié)點(diǎn)變量,并合并形成新搜索項(xiàng).

算法1.提取公共變量GetCommon(searches,v_set).

輸入:合取式集合searches,節(jié)點(diǎn)變量集合v_set;

輸出:新的搜索項(xiàng)集合new_searches.

令最簡與或式涉及到的所有變量個(gè)數(shù)為n,搜索項(xiàng)的數(shù)量為x,則算法1進(jìn)行統(tǒng)計(jì)節(jié)點(diǎn)變量出現(xiàn)次數(shù)的時(shí)間復(fù)雜度是O(nx),找到出現(xiàn)次數(shù)最多的公共變量的時(shí)間復(fù)雜度是O(n),合并含有該變量的合取式的時(shí)間復(fù)雜度是O(nx).

結(jié)合簡化搜索條件的策略,改進(jìn)后的條件社區(qū)搜索通用框架包括如下步驟:

1. 枚舉所有滿足條件的節(jié)點(diǎn)變量取值組合,得出與搜索條件等價(jià)的主析取范式;

2. 利用QM算法把主析取范式轉(zhuǎn)化為最簡與或式;

3. 合并最簡與或式中的公共節(jié)點(diǎn)變量;

4. 對于每一搜索項(xiàng),將其合取式作為單項(xiàng)條件社區(qū)搜索的輸入并執(zhí)行,將其析取式用于結(jié)果判別;

5. 合并各單項(xiàng)條件社區(qū)搜索的結(jié)果.

3 單項(xiàng)條件社區(qū)搜索

為解決SCCS,第3.1節(jié)首先提出“社區(qū)搜索+過濾”的方法,第3.2節(jié)給出基于標(biāo)簽傳播給點(diǎn)加權(quán)的方法.

方便起見,本文稱社區(qū)中必須出現(xiàn)的節(jié)點(diǎn)為必要節(jié)點(diǎn),社區(qū)中不能出現(xiàn)的節(jié)點(diǎn)為禁止節(jié)點(diǎn).由定理1,SCCS僅需考慮合取式形式的搜索條件.因此,可以根據(jù)搜索條件中是否存在邏輯非來把對應(yīng)的節(jié)點(diǎn)集合劃分為一個(gè)必要節(jié)點(diǎn)集和一個(gè)禁止節(jié)點(diǎn)集.本文將以這兩個(gè)集合作為SCCS的輸入.

由定義3可知,CCS需要給定社區(qū)定義?.在相關(guān)研究中,基于k-core的社區(qū)定義是一種比較常見的方式[10,11],于是,本節(jié)基于k-core定義來介紹所提方法.顯然,對其他社區(qū)定義,本文所提方法亦可修改適用.

定義5(k-core社區(qū)).給定圖G=(V,E)和常數(shù)k,節(jié)點(diǎn)集H?V,稱H為k-core社區(qū),當(dāng)且僅當(dāng)H的導(dǎo)出子圖G[H]連通且min{degG[H](v)|v∈H}≥k.

3.1 “社區(qū)搜索+過濾”的方法

針對社區(qū)搜索算法沒有考慮禁止節(jié)點(diǎn)的情況,本節(jié)提出預(yù)先搜索社區(qū)(search-first,簡稱SF)、預(yù)先過濾節(jié)點(diǎn)(filter-first,簡稱FF)和搜索時(shí)篩出(on-the-fly,簡稱OTF)等3種不同策略.這3種策略都采用“社區(qū)搜索+過濾”的形式,即:用必要節(jié)點(diǎn)進(jìn)行社區(qū)搜索,用禁止節(jié)點(diǎn)進(jìn)行過濾.三者的區(qū)別在于,過濾步驟分別安排在社區(qū)搜索之后、之前和過程中.

3.1.1 基于k-core的社區(qū)搜索方法FindCore

為便于說明“社區(qū)搜索+過濾”方法的3種不同策略(SF,FF和OTF),本小節(jié)提出基于k-core的社區(qū)搜索算法FindCore(見算法2),用于3種策略的社區(qū)搜索步驟.

算法2.基于k-core的社區(qū)搜索算法FindCore.

輸入:G=(V,E),v_set,k;

輸出:包含v_set的k-core社區(qū)C.

FindCore算法從輸入節(jié)點(diǎn)集出發(fā),通過從鄰居節(jié)點(diǎn)集中選取合適的節(jié)點(diǎn)進(jìn)行擴(kuò)展,得到k-core社區(qū).首先判別社區(qū)的連通性要求,計(jì)算當(dāng)前節(jié)點(diǎn)集導(dǎo)出子圖的連通分量(算法2第2行),優(yōu)先加入連接最多連通分量的節(jié)點(diǎn)(第17行、第18行和第21行、第22行).其次,增加當(dāng)前節(jié)點(diǎn)集的最小點(diǎn)度數(shù),優(yōu)先加入與當(dāng)前節(jié)點(diǎn)集連接數(shù)最多的節(jié)點(diǎn).若連接數(shù)相同,則優(yōu)先加入度數(shù)最大的節(jié)點(diǎn)(第19行、第20行和第23行、第24行).重復(fù)擴(kuò)展過程,直至當(dāng)前節(jié)點(diǎn)集成為連通的k-core社區(qū).需要注意的是:為保證算法的正確性,在加入點(diǎn)的過程中需檢查新增節(jié)點(diǎn)的度數(shù)(第6行、第7行和第27行),如果新增節(jié)點(diǎn)在原圖中度數(shù)小于k,那么它不可能是k-core社區(qū)的一員.同時(shí),通過循環(huán)終止條件保證了結(jié)果社區(qū)滿足k-core要求(第 9行).此外,設(shè)置了搜索節(jié)點(diǎn)個(gè)數(shù)的上限search_limit(第13行),以便提前終止局部搜索的過程.這一設(shè)置是為了在搜索條件所要求的k-core社區(qū)可能不存在時(shí),防止無謂的節(jié)點(diǎn)遍歷.當(dāng)局部向外擴(kuò)展的方法找不到合適的k-core社區(qū)時(shí),調(diào)用global_search方法(第 34行),即從全局出發(fā)不斷迭代,刪除度數(shù)小于k的節(jié)點(diǎn)的方法來尋找k-core社區(qū).文獻(xiàn)[11]中的引理2保證了這一步驟的正確性.

例4:令圖2為當(dāng)前網(wǎng)絡(luò),取k=2,社區(qū)搜索輸入的節(jié)點(diǎn)集為{A,B,C,D}.算法2首先計(jì)算輸入節(jié)點(diǎn)集導(dǎo)出子圖的兩個(gè)連通分量{A,B}和{C,D}.接著,將鄰居節(jié)點(diǎn){E,F,G}加入候選集.由于點(diǎn)G與兩個(gè)連通分量相連,而E和F各連接一個(gè),于是,點(diǎn)G在第 1次擴(kuò)展時(shí)加入節(jié)點(diǎn)集.然后,點(diǎn)E和F依次加入,從而增加了最小節(jié)點(diǎn)度數(shù).最終,得到了{(lán)A,B,C,D,E,F,G}這一2-core社區(qū).

Fig.2 An example fork-core based community search圖2 社區(qū)搜索的示例

算法2的時(shí)間復(fù)雜度是O(m+n),其中,m為邊數(shù)量,n為節(jié)點(diǎn)數(shù)量.這是因?yàn)樗惴ㄔ谧顗那闆r下可能要遍歷所有節(jié)點(diǎn)和邊.

3.1.2 預(yù)先搜索的策略

本小節(jié)介紹預(yù)先搜索(SF)的策略,其過程分為3步:(1) 用必要節(jié)點(diǎn)進(jìn)行社區(qū)搜索得到社區(qū)結(jié)果;(2) 檢查結(jié)果內(nèi)部是否存在禁止節(jié)點(diǎn),若存在,則刪除其中的禁止節(jié)點(diǎn);(3) 檢查剩余社區(qū)結(jié)果是否還滿足社區(qū)定義,若不滿足,則需調(diào)整剩余社區(qū)結(jié)果.一種通用調(diào)整方式是把必要節(jié)點(diǎn)作為輸入在剩余社區(qū)上再進(jìn)行一次社區(qū)搜索.此外,也可以針對特定社區(qū)定義設(shè)計(jì)調(diào)整方案.

以FindCore算法為例,SF先用該算法得到初始k-core社區(qū),再檢查社區(qū)內(nèi)的禁止節(jié)點(diǎn).如果沒有找到禁止節(jié)點(diǎn),就可以直接將它作為結(jié)果返回.反之則刪除禁止節(jié)點(diǎn),檢查社區(qū)是否還滿足k-core定義:如果不滿足,則可以通過依次刪除社區(qū)內(nèi)度數(shù)最低的節(jié)點(diǎn)來調(diào)整社區(qū)結(jié)構(gòu),嘗試得到k-core社區(qū).

需要注意的是,該策略可能在某些情況下得不到結(jié)果社區(qū).以4-core作為社區(qū)定義,假設(shè)通過預(yù)先搜索得到了一個(gè)4完全圖結(jié)構(gòu)的社區(qū)結(jié)果,如果其中含有3個(gè)禁止節(jié)點(diǎn),那么社區(qū)剩余部分僅有1個(gè)節(jié)點(diǎn),無法再得到合理社區(qū)結(jié)構(gòu).因此,該策略有一定的局限性,在實(shí)驗(yàn)中被視作其他方法的基準(zhǔn).

3.1.3 預(yù)先過濾的策略

本節(jié)介紹預(yù)先過濾(FF)的策略,其過程分為2步:(1) 刪除網(wǎng)絡(luò)圖中所有禁止節(jié)點(diǎn);(2) 用必要節(jié)點(diǎn)集作為輸入,在剩余網(wǎng)絡(luò)圖上進(jìn)行社區(qū)搜索.因?yàn)樵诘?1步過濾了禁止節(jié)點(diǎn),所以保證了第 2步得到的社區(qū)能滿足搜索條件.

FF策略的缺點(diǎn)是可能存在不必要的節(jié)點(diǎn)刪除操作.若禁止節(jié)點(diǎn)原本就遠(yuǎn)離最終的結(jié)果社區(qū),則不需要在社區(qū)搜索的過程中對其進(jìn)行訪問.尤其是當(dāng)網(wǎng)絡(luò)圖規(guī)模較大且禁止節(jié)點(diǎn)較多時(shí),這類不必要的刪除操作就會(huì)影響時(shí)間開銷.原因在于,從圖中刪除一個(gè)節(jié)點(diǎn)會(huì)涉及對節(jié)點(diǎn)自身及鄰接邊的訪問.

3.1.4 搜索時(shí)篩出的策略

本節(jié)介紹搜索時(shí)篩出(OTF)的策略,即:在社區(qū)搜索過程中避開禁止節(jié)點(diǎn),不再需要對結(jié)果進(jìn)行檢查,直接得到符合搜索條件的社區(qū).

以FindCore算法為例,用in_set和out_set分別表示必要節(jié)點(diǎn)集和禁止節(jié)點(diǎn)集,算法3給出了應(yīng)用OTF策略的FindCore算法偽碼.它在算法2的基礎(chǔ)上僅修改了第1行、第20行和第34行.其中,第1行避免了將禁止節(jié)點(diǎn)加入候選集,第20行消除了禁止節(jié)點(diǎn)的度數(shù)貢獻(xiàn),第34行的global_search′方法在迭代刪除度數(shù)小于等于k的節(jié)點(diǎn)前先刪除了禁止節(jié)點(diǎn).于是,算法3保證了得到的k-core社區(qū)能滿足搜索條件.

算法3.基于OTF策略的FindCore算法.

輸入:G=(V,E),in_set,out_set,k;

輸出:社區(qū)C(in_set?C,out_set∩C=?).

與前兩種策略相比,OTF策略修改了社區(qū)搜索算法,以便在搜索過程中檢查禁止節(jié)點(diǎn).該策略在保證得到正確結(jié)果的同時(shí)還排除了冗余的刪除操作,因此相比而言更為高效.此外,基于FF策略和OTF策略使用FindCore算法得到的社區(qū)結(jié)果相同,易證得如下定理:

定理2.使用FindCore算法,通過FF策略和OTF策略所得單項(xiàng)條件社區(qū)搜索的結(jié)果是相同的.

證明:假定給出合理的單項(xiàng)搜索條件,即,從條件中得出的必要節(jié)點(diǎn)集和禁止節(jié)點(diǎn)集不相交.首先,在候選集節(jié)點(diǎn)提取過程中,FF策略下禁止節(jié)點(diǎn)被預(yù)先刪除而不會(huì)進(jìn)入候選集,而在 OTF策略下,禁止節(jié)點(diǎn)會(huì)在候選集擴(kuò)展時(shí)被過濾掉,因此兩種策略下的候選集相同.其次,在從候選集選取優(yōu)先加入的節(jié)點(diǎn)的過程中,FF策略里點(diǎn)的度數(shù)是刪除禁止節(jié)點(diǎn)后計(jì)算的,這一度數(shù)與OTF策略下統(tǒng)計(jì)的不在禁止節(jié)點(diǎn)集中的鄰居節(jié)點(diǎn)個(gè)數(shù)是相等的,因此兩種策略下,每次候選集中選出的最優(yōu)節(jié)點(diǎn)是一樣的.綜上,這兩種策略得到的社區(qū)結(jié)果是相同的. □

3.2 基于標(biāo)簽傳播思想給點(diǎn)加權(quán)的方法

例5:如圖3所示,一個(gè)示例網(wǎng)絡(luò)中的節(jié)點(diǎn)代表個(gè)體,邊表示好友關(guān)系.假定個(gè)體A擬建立一個(gè)不包含B的討論小組,于是對應(yīng)的CCS為尋找滿足搜索條件A∧?B的社區(qū),即A為必要節(jié)點(diǎn)、B為禁止節(jié)點(diǎn).若以3-core作為社區(qū)結(jié)構(gòu),則通過“社區(qū)搜索+過濾”的方法(FF策略)得到的一個(gè)社區(qū)結(jié)果為虛線包圍的子網(wǎng)絡(luò).因?yàn)樵撋鐓^(qū)中的B1～B3和B都是好友關(guān)系,所以B有可能通過其中的某個(gè)/些好友了解該討論小組的情況,而這是A所不希望的.

Fig.3 Result of community+search method (FF)圖3 FF策略下“社區(qū)搜索+過濾”方法的結(jié)果

例5表明,“社區(qū)搜索+過濾”的方法得到的社區(qū)雖然能夠滿足社區(qū)定義和搜索條件,但是難以體現(xiàn)出社區(qū)中的節(jié)點(diǎn)應(yīng)盡量遠(yuǎn)離禁止節(jié)點(diǎn),同時(shí)盡量靠近必要節(jié)點(diǎn)的潛在需求.簡便起見,文中以傾向性指代節(jié)點(diǎn)相對于必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的接近程度.一個(gè)節(jié)點(diǎn)離禁止節(jié)點(diǎn)越遠(yuǎn)、離必要節(jié)點(diǎn)越近,則該節(jié)點(diǎn)的傾向性越大.本節(jié)提出了基于標(biāo)簽傳播給點(diǎn)加權(quán)的方法(WLP),用節(jié)點(diǎn)的權(quán)重來表示節(jié)點(diǎn)的傾向性.

3.2.1 基于標(biāo)簽傳播的加權(quán)過程

利用標(biāo)簽傳播進(jìn)行社區(qū)發(fā)現(xiàn)的方法包括以下步驟:首先為每個(gè)節(jié)點(diǎn)賦予唯一的初始標(biāo)簽,接著逐輪迭代,把每個(gè)節(jié)點(diǎn)的標(biāo)簽迭代更新為其鄰居節(jié)點(diǎn)中出現(xiàn)次數(shù)最多的那一個(gè).經(jīng)過數(shù)輪迭代后,最終把標(biāo)簽相同的節(jié)點(diǎn)歸入同一社區(qū).

基于上述思想,本節(jié)提出一種為節(jié)點(diǎn)加權(quán)的方法.初始時(shí),先將節(jié)點(diǎn)權(quán)重設(shè)置如下:

接著對節(jié)點(diǎn)的權(quán)重進(jìn)行迭代更新,但保持必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的權(quán)重固定不變.一個(gè)節(jié)點(diǎn)的新權(quán)重決定于其所有鄰居節(jié)點(diǎn)的上一輪權(quán)重.為了使得新權(quán)重落在[-1,1]區(qū)間內(nèi),以如下方式更新權(quán)重:

其中,N(v)表示節(jié)點(diǎn)v的鄰居節(jié)點(diǎn),Wi(v)表示節(jié)點(diǎn)v的第i輪權(quán)重.在第1輪迭代中,必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的一跳鄰居被賦予新權(quán)重.此時(shí),與較多必要節(jié)點(diǎn)相連的節(jié)點(diǎn)權(quán)重變大,和較多禁止節(jié)點(diǎn)相連的節(jié)點(diǎn)權(quán)重變小,體現(xiàn)出各自的傾向性大小.在第γ輪迭代中,這種傾向性會(huì)傳遞給必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的γ跳鄰居.

接下來,通過給定閾值λ排除權(quán)重小于λ的節(jié)點(diǎn),這樣可以去除那些不宜出現(xiàn)在社區(qū)中的傾向性較小的節(jié)點(diǎn).經(jīng)過閾值篩選后的節(jié)點(diǎn)所形成的導(dǎo)出子圖可能不滿足任何的社區(qū)定義,為此,在最后需要調(diào)整該子圖的結(jié)構(gòu),例如通過FindCore算法在該子圖里尋找k-core社區(qū).綜上,WLP方法分為如下3個(gè)步驟.

(1) 按標(biāo)簽傳播的方式為各個(gè)節(jié)點(diǎn)賦予權(quán)重;

(2) 以給定閾值篩選出權(quán)重較大的節(jié)點(diǎn);

(3) 在篩出節(jié)點(diǎn)集的導(dǎo)出子圖上進(jìn)行社區(qū)搜索.

相對于“社區(qū)搜索+過濾”方法,WLP方法強(qiáng)調(diào)了條件中必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)對周圍節(jié)點(diǎn)的影響,排除了那些與禁止節(jié)點(diǎn)過近的節(jié)點(diǎn),保留了與必要節(jié)點(diǎn)更接近即傾向性更大的節(jié)點(diǎn).

WLP方法如算法4所示,其中,第2行～第15行是權(quán)重賦值過程,第16行～第19行是篩選過程,最后一行調(diào)用FindCore在導(dǎo)出子圖上進(jìn)行社區(qū)搜索.需要注意的是,最后一行也可以用任意的社區(qū)搜索算法進(jìn)行替換.

因?yàn)樵跈?quán)重賦值時(shí)把禁止節(jié)點(diǎn)權(quán)重固定為-1,所以取λ>-1就可以保證篩選出的節(jié)點(diǎn)集不包含禁止節(jié)點(diǎn),從而滿足搜索條件,保證了WLP方法的正確性.

算法4.WLP方法.

輸入:G=(V,E),in_set,out_set,k,λ,γ//λ表示權(quán)重的閾值,γ表示迭代次數(shù);

輸出:社區(qū)C(in_set?C,out_set∩C=?).

例6:圖4和圖5展示了通過WLP方法解決圖3中CCS的過程.在第1輪迭代后,各個(gè)點(diǎn)的權(quán)重更新為其鄰居點(diǎn)的權(quán)重均值,得到了圖4.重復(fù)迭代,最后得到圖5.設(shè)定閾值為0,可將節(jié)點(diǎn)A,A1,A2和A3預(yù)先選出;接著,在這4個(gè)節(jié)點(diǎn)的導(dǎo)出子圖上應(yīng)用FindCore算法.可以發(fā)現(xiàn),虛線圈出部分已經(jīng)是一個(gè)2-core社區(qū).相比于圖3,它規(guī)模更小,結(jié)構(gòu)更緊湊,并且社區(qū)內(nèi)部的成員更靠近節(jié)點(diǎn)A,遠(yuǎn)離節(jié)點(diǎn)B.

Fig.4 Result of the first propagation圖4 第1輪加權(quán)結(jié)果

Fig.5 Result of conditional community search (WLP)圖5 通過WLP進(jìn)行條件社區(qū)搜索的結(jié)果

3.2.2 WLP方法的復(fù)雜度分析

令網(wǎng)絡(luò)圖中邊數(shù)為m,節(jié)點(diǎn)數(shù)為n,迭代次數(shù)為γ,則通過標(biāo)簽傳播來給點(diǎn)加權(quán)的過程的時(shí)間復(fù)雜度是O(n)+O(γm),其中,初始賦權(quán)重標(biāo)簽的復(fù)雜度O(n).鑒于每一輪迭代的計(jì)算過程需要訪問每個(gè)節(jié)點(diǎn)的所有鄰居,于是,其時(shí)間復(fù)雜度為O(m).在實(shí)際計(jì)算中,可以僅維護(hù)權(quán)重不為 0的節(jié)點(diǎn)數(shù)組,隨著迭代,再不斷添加而不必將所有點(diǎn)賦予初始值.這樣做可以將上述過程的復(fù)雜度降到O(γm).

4 實(shí)驗(yàn)與分析

本節(jié)首先介紹實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集,通過實(shí)驗(yàn)展示利用簡化的搜索條件進(jìn)行條件社區(qū)搜索的有效性,最后比較不同條件社區(qū)搜索方法的時(shí)間開銷和結(jié)果社區(qū)質(zhì)量.

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

本文實(shí)驗(yàn)所用機(jī)器的CPU是Intel Xeon E5-2650 2.0GHZ,內(nèi)存大小256GB,操作系統(tǒng)為Windows Server 2008 R2.用Python-3.6.1實(shí)現(xiàn)了3種策略下(FF,OTF,SF)的“社區(qū)搜索+過濾”方法和WLP方法.

本文實(shí)驗(yàn)采用的真實(shí)數(shù)據(jù)集有Football,DBLP,Amazon和Youtube,其中,Football數(shù)據(jù)集來自Khorasgani[44],其余數(shù)據(jù)集來自Stanford Large Network Dataset Collection(http://snap.stanford.edu/data/),具體統(tǒng)計(jì)信息見表1,均帶有真實(shí)的社區(qū)分布.表1最后一列的top5000社區(qū)是指數(shù)據(jù)集提供的前5 000個(gè)質(zhì)量最高的社區(qū)(評判標(biāo)準(zhǔn)因數(shù)據(jù)集而異,如conductance,modularity等,詳見文獻(xiàn)[45]).我們統(tǒng)計(jì)發(fā)現(xiàn),DBLP,Amazon和Youtube這3個(gè)數(shù)據(jù)集的top5000社區(qū)中都有95%以上的社區(qū)規(guī)模在50個(gè)節(jié)點(diǎn)以下.因此在后續(xù)實(shí)驗(yàn)中,FindCore算法的搜索上限search_limit設(shè)置為50,以便提前終止局部搜索過程,提高算法效率.

Table 1 Datasets表1 數(shù)據(jù)集

為了研究簡化搜索條件的方法在不同規(guī)模網(wǎng)絡(luò)圖上的效果,本文還采用人工網(wǎng)絡(luò)生成工具 Lancichinetti-Fortunato-Radicchi(LFR)[46]來合成不同規(guī)模的網(wǎng)絡(luò)圖.具體地,合成網(wǎng)絡(luò)圖中節(jié)點(diǎn)數(shù)量n的變化范圍是 104～105.LFR工具的其他參數(shù)設(shè)置如下:節(jié)點(diǎn)平均度數(shù)d為5,節(jié)點(diǎn)最大度數(shù)dmax為50,最小社區(qū)規(guī)模cmin為20,最大社區(qū)規(guī)模cmax為100,拓?fù)浣Y(jié)構(gòu)混合參數(shù)u為0.1.

4.2 社區(qū)結(jié)果的評價(jià)指標(biāo)

通過參考現(xiàn)有社區(qū)發(fā)現(xiàn)和社區(qū)搜索的評價(jià)標(biāo)準(zhǔn),本文選取F1-measure和Ql(局部模塊度)來評估結(jié)果社區(qū)的質(zhì)量,其中,F1-measure衡量了結(jié)果社區(qū)的正確性,Ql評估了結(jié)果社區(qū)內(nèi)部的緊密程度.

F1-measure是準(zhǔn)確率和召回率的調(diào)和平均值,用于衡量計(jì)算得到的結(jié)果社區(qū)與真實(shí)社區(qū)的接近程度,其計(jì)算公式為

其中,C代表計(jì)算出的結(jié)果社區(qū),C′是真實(shí)社區(qū).F1-measure的值越接近1,則計(jì)算結(jié)果越精確.需要注意的是,數(shù)據(jù)集提供的真實(shí)社區(qū)的獲取方式不盡相同.例如:Football數(shù)據(jù)集是依據(jù)球員的好友關(guān)系構(gòu)建的網(wǎng)絡(luò),同一個(gè)俱樂部成員標(biāo)定為同一社區(qū);DBLP是依據(jù)論文作者的協(xié)作關(guān)系構(gòu)建的網(wǎng)絡(luò),同一個(gè)小組的成員標(biāo)定為同一社區(qū).

依據(jù)數(shù)據(jù)集給出的真實(shí)社區(qū),一種很自然的假定是:當(dāng)單項(xiàng)條件社區(qū)搜索中的必要節(jié)點(diǎn)都來自同一真實(shí)社區(qū),而禁止節(jié)點(diǎn)都在該社區(qū)外時(shí),數(shù)據(jù)集提供的真實(shí)社區(qū)就是對應(yīng)單項(xiàng)條件社區(qū)搜索的真實(shí)社區(qū).在其他情況下,例如必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)都來自數(shù)據(jù)集提供的某個(gè)真實(shí)社區(qū)時(shí),本文提出的“社區(qū)搜索+過濾”方法以及WLP方法仍有返回結(jié)果的可能.該結(jié)果往往預(yù)示著數(shù)據(jù)集提供的真實(shí)社區(qū)中存在著可以細(xì)分的子社區(qū)結(jié)構(gòu),但此時(shí)的真實(shí)社區(qū)無法預(yù)知.因此,在這種情形下就無法使用F1-measure進(jìn)行正確性度量,而只關(guān)心所得社區(qū)的緊密性和社區(qū)內(nèi)成員相對必要節(jié)點(diǎn)的遠(yuǎn)近,即,從合理性的角度去度量社區(qū)結(jié)果好壞.

局部模塊度(local modularity)指一個(gè)子圖內(nèi)部所有的邊數(shù)與原圖中所有涉及到該子圖中節(jié)點(diǎn)的邊數(shù)量的比值[47],即:

其中,kin表示社區(qū)內(nèi)部的邊數(shù),kout表示社區(qū)內(nèi)部和外部連接的邊數(shù).Ql越大,表明社區(qū)緊密性越好.

除此之外,為了評估社區(qū)內(nèi)節(jié)點(diǎn)與必要節(jié)點(diǎn)的接近程度,本文設(shè)計(jì)了相對最短路徑比這一新指標(biāo),即社區(qū)內(nèi)節(jié)點(diǎn)分別與必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的平均最短路徑距離之比(average shortest pathdistance ratio,簡稱ASD-ratio):

其中,in_set和out_set分別表示必要節(jié)點(diǎn)集和禁止節(jié)點(diǎn)集,dist(vi,vj)表示vi和vj之間的最短路徑距離,C表示社區(qū)結(jié)果.ASD-ratio越小,意味著社區(qū)內(nèi)成員與必要節(jié)點(diǎn)越近,與禁止節(jié)點(diǎn)越遠(yuǎn).

4.3 搜索條件簡化的有效性

第2.3節(jié)給出了簡化搜索條件以減少單項(xiàng)條件社區(qū)搜索次數(shù)的方法.本節(jié)將對此進(jìn)行實(shí)驗(yàn)驗(yàn)證.

根據(jù)第 2節(jié)提出的條件社區(qū)搜索通用框架,無論搜索條件是否經(jīng)過簡化,該框架都需要先枚舉所有滿足原始搜索條件的變量組合,簡化搜索條件的有效性在之后的步驟才體現(xiàn)出來.因此在本節(jié)實(shí)驗(yàn)中,搜索條件被設(shè)計(jì)為主析取范式的形式,相當(dāng)于省去枚舉變量取值過程的開銷.該主析取范式包含q個(gè)搜索項(xiàng),每個(gè)搜索項(xiàng)包含相同的v個(gè)節(jié)點(diǎn)變量.這v個(gè)節(jié)點(diǎn)變量按照均勻分布從網(wǎng)絡(luò)圖中隨機(jī)選取.此外,對每個(gè)搜索項(xiàng),按照均勻分布隨機(jī)為部分節(jié)點(diǎn)變量添加了邏輯非運(yùn)算符,表示禁止這部分節(jié)點(diǎn)出現(xiàn)在社區(qū)中.例如,(A∧B∧?C)∨(A∧?B∧C)表示一個(gè)包含2個(gè)搜索項(xiàng)、3個(gè)節(jié)點(diǎn)變量A,B和C的主析取范式形式的搜索條件.因?yàn)閷θ我庑问降乃阉鳁l件總能得出與其等價(jià)的主析取范式[40],范式中搜索項(xiàng)的個(gè)數(shù)和節(jié)點(diǎn)變量的個(gè)數(shù)允許任意指定,并且節(jié)點(diǎn)變量是隨機(jī)選取的,所以上述搜索條件設(shè)計(jì)可以表達(dá)任意的搜索條件,其完備性得以保證.

本節(jié)以O(shè)TF方法為例來驗(yàn)證搜索條件簡化的優(yōu)勢,其他3種方法的效果類似.公平起見,簡化前后的條件社區(qū)搜索方法中的單項(xiàng)條件社區(qū)搜索步驟都應(yīng)用了 FindCore算法.為保證實(shí)驗(yàn)結(jié)果的普遍性,在不同的節(jié)點(diǎn)變量個(gè)數(shù)v和不同搜索項(xiàng)個(gè)數(shù)q下進(jìn)行了多次對比.對固定的一組v和q,重復(fù)10次實(shí)驗(yàn),取時(shí)間開銷的均值.FindCore算法中的k值從2～10的范圍內(nèi)逐一嘗試,保留使社區(qū)規(guī)模最大的k值.

圖6展示了簡化前后條件社區(qū)搜索方法的時(shí)間開銷隨搜索項(xiàng)個(gè)數(shù)v的變化情況,其中,簡化后條件社區(qū)搜索方法的時(shí)間開銷包含了化簡過程自身的時(shí)間開銷.如圖6(b)～圖6(d)所示:簡化前的條件社區(qū)搜索方法的時(shí)間開銷基本上和搜索項(xiàng)個(gè)數(shù)成正比,簡化后的條件社區(qū)搜索方法在時(shí)間開銷上具有明顯優(yōu)勢.例如:針對DBLP數(shù)據(jù)集,當(dāng)節(jié)點(diǎn)個(gè)數(shù)為5、搜索項(xiàng)個(gè)數(shù)為14時(shí),簡化前的時(shí)間開銷是簡化后時(shí)間開銷的5倍以上.這是因?yàn)楣潭ü?jié)點(diǎn)數(shù)量后,搜索項(xiàng)越多,越容易引發(fā)搜索項(xiàng)冗余現(xiàn)象,也越容易出現(xiàn)公共搜索變量.于是,當(dāng)冗余的搜索項(xiàng)數(shù)量增多時(shí),簡化后的條件社區(qū)搜索方法的提高效果更為明顯.

圖7展示了簡化前后條件社區(qū)搜索方法的時(shí)間開銷隨節(jié)點(diǎn)變量個(gè)數(shù)q的變化情況,其中,簡化后條件社區(qū)搜索方法的時(shí)間開銷包含了化簡過程自身的時(shí)間開銷.如圖7(b)～圖7(d)所示:從時(shí)間開銷隨節(jié)點(diǎn)個(gè)數(shù)的變化趨勢上看,節(jié)點(diǎn)個(gè)數(shù)增加并不會(huì)影響簡化后的條件社區(qū)搜索方法的優(yōu)勢.例如在圖7(b)中,節(jié)點(diǎn)個(gè)數(shù)從4增加到6,簡化后時(shí)間開銷穩(wěn)定地為簡化前時(shí)間開銷的1/4.

需要注意的是,圖6(a)和圖7(a)中存在簡化后條件社區(qū)搜索方法的時(shí)間開銷更高的情形(不過整體時(shí)間開銷均在0.3s內(nèi)).這是因?yàn)?一方面,圖6(a)和圖7(a)對應(yīng)的Football數(shù)據(jù)集規(guī)模較小,于是運(yùn)行社區(qū)搜索算法的開銷較小;另一方面,社區(qū)搜索條件的化簡過程也需要一定開銷,條件越復(fù)雜,則化簡過程自身需要越多的時(shí)間.因此,當(dāng)條件較復(fù)雜(比如搜索項(xiàng)數(shù)量大于 8)時(shí),化簡過程的時(shí)間開銷占到較大比重,從而使簡化后的社區(qū)搜索方法耗時(shí)更多.

Fig.6 Time costs of conditional community search with different query numbers (# node variablev=5)圖6 不同搜索項(xiàng)個(gè)數(shù)下條件社區(qū)搜索方法的時(shí)間開銷(節(jié)點(diǎn)變量個(gè)數(shù)v=5)

Fig.7 Time costs of conditional community search with different node numbers (# queriesq=10)圖7 不同節(jié)點(diǎn)個(gè)數(shù)下條件社區(qū)搜索方法的時(shí)間開銷(簡化前搜索項(xiàng)個(gè)數(shù)q=10)

為了分析最簡與或式化簡程度與條件社區(qū)搜索方法的關(guān)系,給出冗余項(xiàng)數(shù)目的概念并展示冗余項(xiàng)數(shù)目對簡化后條件社區(qū)搜索方法時(shí)間開銷的影響.具體地,冗余項(xiàng)數(shù)目定義為化簡為最簡與或式前后減少的搜索項(xiàng)個(gè)數(shù).圖8展示了DBLP等3個(gè)數(shù)據(jù)集簡化后條件社區(qū)搜索方法的時(shí)間開銷隨冗余項(xiàng)數(shù)目的變化情況,其中,節(jié)點(diǎn)變量個(gè)數(shù)v為8,簡化前搜索項(xiàng)個(gè)數(shù)q為8.顯然,隨冗余項(xiàng)數(shù)目的增加,時(shí)間開銷進(jìn)一步得到縮減.需要說明的是,因?yàn)镕ootball數(shù)據(jù)集上的整體時(shí)間開銷較小,所以沒有進(jìn)行展示.

Fig.8 Effect of redundant items on the time cost圖8 冗余項(xiàng)數(shù)目對時(shí)間開銷的影響

圖9對比了不同網(wǎng)絡(luò)圖規(guī)模下條件社區(qū)搜索方法的時(shí)間開銷,其中,網(wǎng)絡(luò)圖的規(guī)模由圖中的節(jié)點(diǎn)數(shù)量表示.對不同節(jié)點(diǎn)變量個(gè)數(shù)v和搜索項(xiàng)個(gè)數(shù)q,簡化前后條件社區(qū)搜索方法的時(shí)間開銷都隨網(wǎng)絡(luò)圖規(guī)模的增大而增加,并且簡化后的條件社區(qū)搜索方法一直保持明顯優(yōu)勢.實(shí)際上,社區(qū)規(guī)模大小只影響每次單項(xiàng)條件社區(qū)搜索的時(shí)間開銷而不影響對搜索條件的化簡過程,因此,化簡過程在大規(guī)模網(wǎng)絡(luò)圖上依然適用.

Fig.9 Time costs of conditional community search with different graph size圖9 不同網(wǎng)絡(luò)圖規(guī)模下條件社區(qū)搜索的時(shí)間開銷

4.4 單項(xiàng)條件社區(qū)搜索方法的對比實(shí)驗(yàn)

第 3節(jié)提出了單項(xiàng)條件社區(qū)搜索方法,即“社區(qū)搜索+過濾”的方法(使用 3種不同策略的方法分別記為FF,OTF和 SF)和基于標(biāo)簽傳播給點(diǎn)加權(quán)的方法(記為 WLP).本節(jié)將從時(shí)間開銷和社區(qū)結(jié)果質(zhì)量角度對上述方法進(jìn)行實(shí)驗(yàn).

由定義4可知,單項(xiàng)條件社區(qū)搜索的輸入條件只有一種可滿足的取值組合,因此可以通過隨機(jī)指定必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的個(gè)數(shù)來構(gòu)造搜索條件.鑒于用戶輸入的節(jié)點(diǎn)總數(shù)通常較小,實(shí)驗(yàn)中設(shè)計(jì)了 5種類型的單項(xiàng)社區(qū)搜索條件(見表2),對應(yīng)不同的必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)個(gè)數(shù).例如,編號(hào)i對應(yīng)形如A∧B∧?C的搜索條件,包含2個(gè)必要節(jié)點(diǎn)和 1個(gè)禁止節(jié)點(diǎn).在執(zhí)行具體搜索實(shí)驗(yàn)時(shí),節(jié)點(diǎn)變量替換為具體的節(jié)點(diǎn)編號(hào),且每一種搜索條件對應(yīng)100組不同的具體節(jié)點(diǎn)編號(hào).不同方法中,每類搜索條件的時(shí)間開銷、F1-measure、Ql以及ASD-ratio都是相關(guān)的100組實(shí)驗(yàn)的均值.

為公平起見,所有社區(qū)搜索算法均采用FindCore算法.對不同節(jié)點(diǎn)變量,k值在2～10的范圍內(nèi)嘗試,留下使社區(qū)規(guī)模最大的一個(gè).

Table 2 Design of search conditions表2 搜索條件設(shè)計(jì)

圖10展示了當(dāng)搜索條件為iii,WLP方法中的閾值λ在[0,0.4]范圍內(nèi)取值時(shí)所得社區(qū)F1-measure的變化情況.當(dāng)λ超過0.2時(shí),在DBLP上難以找到合適社區(qū),而在Football上社區(qū)準(zhǔn)確性下降.需要說明的是,在兩個(gè)數(shù)據(jù)集上,-1<λ<0時(shí)F1-measure的值與λ=0時(shí)F1-measure的值相等;當(dāng)λ>0.4時(shí),得到的F1-measure的值均為0,所以在圖中沒有顯示上述范圍內(nèi)的變化情況.考慮到取較大閾值可減小社區(qū)搜索范圍,因此在后續(xù)實(shí)驗(yàn)中,統(tǒng)一將閾值λ設(shè)置為0.2.

Fig.10 F1-measure with different thresholds of WLP method圖10 不同閾值下WLP方法得到的F1-measure

根據(jù)第3.2.1節(jié)中WLP方法的具體過程,第γ輪迭代中相對于必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的傾向性會(huì)傳遞給必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的γ跳鄰居.此外,考慮到六度分離的原則,當(dāng)?shù)?6次時(shí),網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)已經(jīng)得到了能反映出傾向性的權(quán)重.因此,實(shí)驗(yàn)中的迭代次數(shù)γ被設(shè)置為6.

圖11對比了4種不同方法的時(shí)間開銷.圖11(a)和圖11(b)分別是在Football和DBLP數(shù)據(jù)集上取得的實(shí)驗(yàn)結(jié)果,橫坐標(biāo)編號(hào)對應(yīng)搜索條件.

Fig.11 Time costsof different singleconditionalcommunity search methods圖11 不同單項(xiàng)條件社區(qū)搜索方法的時(shí)間開銷對比

因?yàn)閃LP方法需要進(jìn)行節(jié)點(diǎn)權(quán)重的計(jì)算,且該計(jì)算涉及圖中所有邊,較為費(fèi)時(shí),所以其時(shí)間開銷最大.“社區(qū)搜索+過濾”方法的3種策略FF,OTF和SF的時(shí)間開銷相近,其中,OTF策略相對稍好.這是因?yàn)镕F策略存在部分冗余刪除,SF策略需要進(jìn)一步調(diào)整社區(qū)結(jié)構(gòu),而 OTF策略在搜索過程中過濾掉禁止節(jié)點(diǎn),從而避免了另兩種策略在效率上的不足.

圖12展示了4種不同方法在Football和DBLP數(shù)據(jù)集上所得社區(qū)結(jié)果的F1-measure.在每次單項(xiàng)條件社區(qū)搜索的具體實(shí)驗(yàn)中,要求其搜索條件中的必要節(jié)點(diǎn)來自同一實(shí)際社區(qū),同時(shí)禁止節(jié)點(diǎn)來自該社區(qū)外.這樣就可以根據(jù)數(shù)據(jù)集附帶的真實(shí)社區(qū)結(jié)果計(jì)算F1-measure.從圖12(a)和圖12(b)可以看出:無論是Football還是DBLP數(shù)據(jù)集,3種不同策略下“社區(qū)搜索+過濾”方法得到的F1-measure都基本相同.這表明給定符合真實(shí)社區(qū)分布的搜索條件,這3種策略都能找到相同準(zhǔn)確程度的社區(qū)結(jié)果.WLP方法得到的社區(qū)搜索結(jié)果在多數(shù)搜索條件下有更好的準(zhǔn)確性,在少數(shù)條件下準(zhǔn)確性不如其他方法,如圖12(a)的 ii和圖12(b)的 i,iii和iv,但是相對差異并不明顯.這是由于WLP方法的結(jié)果受到禁止節(jié)點(diǎn)的影響,從而產(chǎn)生波動(dòng).例如:當(dāng)禁止節(jié)點(diǎn)離真實(shí)社區(qū)較近時(shí),WLP方法一般會(huì)得到比真實(shí)社區(qū)更小的社區(qū).這是因?yàn)樵谡鎸?shí)社區(qū)內(nèi)部,有部分與禁止節(jié)點(diǎn)相連的節(jié)點(diǎn)會(huì)被閾值過濾排除在外.這實(shí)際上是為使社區(qū)內(nèi)成員與必要節(jié)點(diǎn)更接近而付出的必要開銷.

Fig.12 F1-measure of different singleconditional community search methods圖12 不同單項(xiàng)條件社區(qū)搜索方法的F1-measure對比

圖13對比了通過不同方法所得結(jié)果社區(qū)的局部模塊度Ql,其中,圖13(b)的搜索條件中,禁止節(jié)點(diǎn)和必要節(jié)點(diǎn)來自同一社區(qū),即搜索條件和數(shù)據(jù)集提供的真實(shí)結(jié)果有沖突,而圖13(a)則不存在這樣的沖突.在有沖突的情形下,容易發(fā)現(xiàn):在“社區(qū)搜索+過濾”方法的3種不同策略中,SF所得結(jié)果對應(yīng)的Ql較低,而FF和OTF的Ql相對較高.這是因?yàn)閳D中顯示的Ql為多次實(shí)驗(yàn)的均值,在搜索條件存在沖突的情形下,SF在調(diào)整社區(qū)結(jié)構(gòu)時(shí)可能無法得到社區(qū)結(jié)果,此時(shí)的Ql被記為0,從而導(dǎo)致SF的平均Ql降低.在搜索條件不存在沖突時(shí),這3種策略所得社區(qū)結(jié)果具有相同緊密程度.通過 WLP方法得到的社區(qū),在緊密程度上由于受禁止節(jié)點(diǎn)的影響存在較大波動(dòng).此外,圖12和圖13的結(jié)果也能驗(yàn)證定理2,即,應(yīng)用FF策略和OTF策略的FindCore算法得到的結(jié)果是相同的.

Fig.13 Qlof singleconditional community search methods圖13 不同單項(xiàng)條件社區(qū)搜索方法的Ql對比

圖14展示了不同方法所得結(jié)果社區(qū)的ASD-ratio.顯然,WLP方法在兩個(gè)數(shù)據(jù)集和不同的搜索條件下都具有最小的 ASD-ratio.這表明 WLP方法能夠充分考慮必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的影響,得到社區(qū)成員與必要節(jié)點(diǎn)更接近的社區(qū).

Fig.14 ASD-ratio of different singleconditional community search methods圖14 不同單項(xiàng)條件社區(qū)搜索方法的ASD-ratio對比

上述實(shí)驗(yàn)結(jié)果表明:采用FF和OTF策略的“社區(qū)搜索+過濾”方法可以有效處理CCS,使用OTF策略則可略微提升效率.WLP方法盡管需要更多的時(shí)間開銷,所得社區(qū)在準(zhǔn)確性和緊密程度上存在波動(dòng),但是其結(jié)果能夠體現(xiàn)出社區(qū)內(nèi)成員對于必要節(jié)點(diǎn)的傾向性,排除與禁止節(jié)點(diǎn)相近的節(jié)點(diǎn),使社區(qū)內(nèi)成員與必要節(jié)點(diǎn)更接近,且在ASD-ratio上最優(yōu),具有較高的應(yīng)用價(jià)值.

5 結(jié)束語

條件社區(qū)搜索問題是在傳統(tǒng)的社區(qū)搜索問題基礎(chǔ)上,結(jié)合實(shí)際需求提出的新問題,它包含了現(xiàn)有社區(qū)搜索問題,并且考慮了特定節(jié)點(diǎn)能否存在于社區(qū)中等復(fù)雜條件約束.

本文給出了 CCS的形式化定義,并使用布爾表達(dá)式表示搜索條件.在此基礎(chǔ)上,本文提出了解決 CCS的通用框架,將CCS分解為多個(gè)SCCS來處理,并通過簡化搜索條件對通用框架進(jìn)行了優(yōu)化.對于SCCS,本文提出了“社區(qū)搜索+過濾”的方法(包括FF,OTF和SF這3種策略)和基于標(biāo)簽傳播給點(diǎn)加權(quán)的WLP方法.通過在4個(gè)真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn),比較了這些方法的時(shí)間開銷和社區(qū)結(jié)果.實(shí)驗(yàn)結(jié)果表明,使用OTF策略的“社區(qū)搜索+過濾”方法在時(shí)間開銷和社區(qū)結(jié)果上具有優(yōu)勢.如果考慮用戶在使用條件社區(qū)搜索時(shí)讓社區(qū)成員遠(yuǎn)離禁止節(jié)點(diǎn)的需求,那么 WLP方法能夠充分考慮必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的影響,找到社區(qū)內(nèi)成員與必要節(jié)點(diǎn)更接近的社區(qū)結(jié)果.

條件社區(qū)搜索的研究尚處在探索階段,后續(xù)會(huì)考慮向CCS中引入更多類型的社區(qū)定義.對于SCCS,希望找到一種新的社區(qū)搜索算法,使得社區(qū)結(jié)構(gòu)在準(zhǔn)確性和緊密程度上達(dá)到最優(yōu)的同時(shí)也能考慮必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的影響.