竺俊超,王朝坤

(清華大學(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)頁(yè)為節(jié)點(diǎn)、以網(wǎng)頁(yè)間的鏈接為邊組成的萬(wàn)維網(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ù)測(cè)[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(zhǎng)的客觀需求.例如,在實(shí)際應(yīng)用中經(jīng)常會(huì)遇到這樣一些問(wèn)題:如何準(zhǔn)確地找到一個(gè)社區(qū),使它不僅包含某些給定節(jié)點(diǎn),同時(shí)不包含另一些給定節(jié)點(diǎn)?如何智能地找到一個(gè)社區(qū),至少要包含給定的5個(gè)節(jié)點(diǎn)中的任意3個(gè)?本文將這類包含對(duì)節(jié)點(diǎn)條件約束的社區(qū)搜索問(wèn)題統(tǒng)稱為條件社區(qū)搜索問(wèn)題(conditional community search,簡(jiǎn)稱CCS).據(jù)我們所知,目前國(guó)內(nèi)外尚未見(jiàn)針對(duì)CCS問(wèn)題的公開(kāi)報(bào)道.

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

圖1展示了上述社交場(chǎng)景中的部分網(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來(lái)計(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也很難通過(guò)其好友加入到該社區(qū)內(nèi).因此對(duì)于例1,A和B可以邀請(qǐng)?zhí)摼€圈中的成員組建討論小組.此外,在視頻網(wǎng)站為用戶提供社區(qū)推薦、購(gòu)物網(wǎng)站為用戶提供相關(guān)商品推薦等場(chǎng)景下,也會(huì)遇到用戶不希望特定的人物或商品出現(xiàn)在推薦列表中的需求.

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

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

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

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

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

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

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

(2) 提出條件社區(qū)搜索的通用框架,并對(duì)其中的單項(xiàng)條件社區(qū)搜索步驟給出“社區(qū)搜索+過(guò)濾”的方法和基于標(biāo)簽傳播給點(diǎn)加權(quán)的方法(weighting by label propagation,簡(jiǎn)稱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ū)搜索問(wèn)題的形式化定義、解決該問(wèn)題的通用框架和搜索條件的簡(jiǎn)化策略.第 3節(jié)提出對(duì)于單項(xiàng)條件社區(qū)搜索的解決方法.第 4節(jié)報(bào)告并分析實(shí)驗(yàn)結(jié)果,包括對(duì)搜索條件簡(jiǎn)化的有效性驗(yàn)證以及“社區(qū)搜索+過(guò)濾”方法和 WLP方法在時(shí)間開(kāi)銷和社區(qū)結(jié)果質(zhì)量上的比較.第5節(jié)總結(jié)全文.

1 相關(guān)工作

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

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

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

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

標(biāo)簽傳播方法通常為網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)賦予初始標(biāo)簽,接著模擬信息傳播過(guò)程為每個(gè)節(jié)點(diǎn)更新標(biāo)簽,最后通過(guò)標(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ū).目前常見(jiàn)的社區(qū)搜索算法主要基于k-clique[9],k-core[10,11]和k-truss[12,13]等特定結(jié)構(gòu).例如,Cui等人提出了尋找包含一個(gè)給定節(jié)點(diǎn)的k-core社區(qū)的問(wèn)題(CST)和對(duì)應(yīng)算法[11].該算法從給定節(jié)點(diǎn)向外擴(kuò)展得到結(jié)果社區(qū).Huang等人提出了基于k-truss的社區(qū)定義,并設(shè)計(jì)了TCP-index來(lái)尋找包含某個(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ì)了對(duì)應(yīng)索引結(jié)構(gòu) CL-tree[16];Huang等人在k-truss結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)了一個(gè)打分函數(shù)來(lái)度量給定節(jié)點(diǎn)屬性在社區(qū)內(nèi)的流行程度,并提出Attribute Truss社區(qū)定義[17].

2 條件社區(qū)搜索

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

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

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

2.1.1 搜索條件的表示形式

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

定義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í)取真值,對(duì)應(yīng)包含節(jié)點(diǎn)A和B但不包含節(jié)點(diǎn)C的社區(qū).例2中的搜索條件可表示為(A∨B)∧(C∨D).該布爾表達(dá)式在變量A或B為真,且C或D為真時(shí)取真值,對(duì)應(yīng)包含A,B中某一人和C,D中某一人的社區(qū).

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

定義3(條件社區(qū)搜索問(wèn)題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ū)搜索問(wèn)題.易知有如下引理.

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

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

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

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

定義4(單項(xiàng)條件社區(qū)搜索SCCS).對(duì)于一個(gè)條件社區(qū)搜索問(wèn)題,如果有且僅有一組節(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組.接著,對(duì)每一種取值組合嘗試找到對(duì)應(yīng)的單項(xiàng)社區(qū)搜索的結(jié)果.最后,將每個(gè)單項(xiàng)社區(qū)搜索的結(jié)果合并,就能得到條件社區(qū)搜索的結(jié)果.

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

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

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

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

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

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

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

這意味著對(duì)于上述幾類CCS問(wèn)題很難找到快速有效的多項(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 搜索條件的簡(jiǎn)化

因?yàn)椴紶栠壿嫷目蓾M足性(SAT)問(wèn)題是一個(gè)NP完全問(wèn)題,所以很難對(duì)第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步對(duì)每個(gè)滿足條件的取值組合都要進(jìn)行一次單項(xiàng)條件社區(qū)搜索,于是考慮改進(jìn)這一步驟,在一次搜索中同時(shí)處理多個(gè)變量取值組合,從而減少總搜索次數(shù).

首先,在得到所有滿足搜索條件的變量取值組合后,可寫(xiě)出與搜索條件等價(jià)的主析取范式[42],即對(duì)搜索條件進(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)變量,對(duì)應(yīng)于一組滿足條件的變量取值,即一次單項(xiàng)條件社區(qū)搜索.

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

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

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

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

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

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

令最簡(jiǎn)與或式涉及到的所有變量個(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é)合簡(jiǎn)化搜索條件的策略,改進(jìn)后的條件社區(qū)搜索通用框架包括如下步驟:

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

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

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

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

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

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

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

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

由定義3可知,CCS需要給定社區(qū)定義?.在相關(guān)研究中,基于k-core的社區(qū)定義是一種比較常見(jiàn)的方式[10,11],于是,本節(jié)基于k-core定義來(lái)介紹所提方法.顯然,對(duì)其他社區(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ū)搜索+過(guò)濾”的方法

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

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

為便于說(shuō)明“社區(qū)搜索+過(guò)濾”方法的3種不同策略(SF,FF和OTF),本小節(jié)提出基于k-core的社區(qū)搜索算法FindCore(見(jiàn)算法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ā),通過(guò)從鄰居節(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ò)展過(guò)程,直至當(dāng)前節(jié)點(diǎn)集成為連通的k-core社區(qū).需要注意的是:為保證算法的正確性,在加入點(diǎn)的過(guò)程中需檢查新增節(jié)點(diǎn)的度數(shù)(第6行、第7行和第27行),如果新增節(jié)點(diǎn)在原圖中度數(shù)小于k,那么它不可能是k-core社區(qū)的一員.同時(shí),通過(guò)循環(huán)終止條件保證了結(jié)果社區(qū)滿足k-core要求(第 9行).此外,設(shè)置了搜索節(jié)點(diǎn)個(gè)數(shù)的上限search_limit(第13行),以便提前終止局部搜索的過(guò)程.這一設(shè)置是為了在搜索條件所要求的k-core社區(qū)可能不存在時(shí),防止無(wú)謂的節(jié)點(diǎn)遍歷.當(dāng)局部向外擴(kuò)展的方法找不到合適的k-core社區(qū)時(shí),調(diào)用global_search方法(第 34行),即從全局出發(fā)不斷迭代,刪除度數(shù)小于k的節(jié)點(diǎn)的方法來(lái)尋找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)的策略,其過(guò)程分為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ū)搜索.此外,也可以針對(duì)特定社區(qū)定義設(shè)計(jì)調(diào)整方案.

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

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

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

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

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

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

本節(jié)介紹搜索時(shí)篩出(OTF)的策略,即:在社區(qū)搜索過(guò)程中避開(kāi)禁止節(jié)點(diǎn),不再需要對(duì)結(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ū)搜索算法,以便在搜索過(guò)程中檢查禁止節(jié)點(diǎn).該策略在保證得到正確結(jié)果的同時(shí)還排除了冗余的刪除操作,因此相比而言更為高效.此外,基于FF策略和OTF策略使用FindCore算法得到的社區(qū)結(jié)果相同,易證得如下定理:

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

證明:假定給出合理的單項(xiàng)搜索條件,即,從條件中得出的必要節(jié)點(diǎn)集和禁止節(jié)點(diǎn)集不相交.首先,在候選集節(jié)點(diǎn)提取過(guò)程中,FF策略下禁止節(jié)點(diǎn)被預(yù)先刪除而不會(huì)進(jìn)入候選集,而在 OTF策略下,禁止節(jié)點(diǎn)會(huì)在候選集擴(kuò)展時(shí)被過(guò)濾掉,因此兩種策略下的候選集相同.其次,在從候選集選取優(yōu)先加入的節(jié)點(diǎn)的過(guò)程中,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的討論小組,于是對(duì)應(yīng)的CCS為尋找滿足搜索條件A∧?B的社區(qū),即A為必要節(jié)點(diǎn)、B為禁止節(jié)點(diǎn).若以3-core作為社區(qū)結(jié)構(gòu),則通過(guò)“社區(qū)搜索+過(guò)濾”的方法(FF策略)得到的一個(gè)社區(qū)結(jié)果為虛線包圍的子網(wǎng)絡(luò).因?yàn)樵撋鐓^(qū)中的B1～B3和B都是好友關(guān)系,所以B有可能通過(guò)其中的某個(gè)/些好友了解該討論小組的情況,而這是A所不希望的.

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

例5表明,“社區(qū)搜索+過(guò)濾”的方法得到的社區(qū)雖然能夠滿足社區(qū)定義和搜索條件,但是難以體現(xiàn)出社區(qū)中的節(jié)點(diǎn)應(yīng)盡量遠(yuǎn)離禁止節(jié)點(diǎn),同時(shí)盡量靠近必要節(jié)點(diǎn)的潛在需求.簡(jiǎn)便起見(jiàn),文中以傾向性指代節(jié)點(diǎn)相對(duì)于必要節(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)重來(lái)表示節(jié)點(diǎn)的傾向性.

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

利用標(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)過(guò)數(shù)輪迭代后,最終把標(biāo)簽相同的節(jié)點(diǎn)歸入同一社區(qū).

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

接著對(duì)節(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)的γ跳鄰居.

接下來(lái),通過(guò)給定閾值λ排除權(quán)重小于λ的節(jié)點(diǎn),這樣可以去除那些不宜出現(xiàn)在社區(qū)中的傾向性較小的節(jié)點(diǎn).經(jīng)過(guò)閾值篩選后的節(jié)點(diǎn)所形成的導(dǎo)出子圖可能不滿足任何的社區(qū)定義,為此,在最后需要調(diào)整該子圖的結(jié)構(gòu),例如通過(guò)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ū)搜索.

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

WLP方法如算法4所示,其中,第2行～第15行是權(quán)重賦值過(guò)程,第16行～第19行是篩選過(guò)程,最后一行調(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展示了通過(guò)WLP方法解決圖3中CCS的過(guò)程.在第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 通過(guò)WLP進(jìn)行條件社區(qū)搜索的結(jié)果

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

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

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

本節(jié)首先介紹實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集,通過(guò)實(shí)驗(yàn)展示利用簡(jiǎn)化的搜索條件進(jìn)行條件社區(qū)搜索的有效性,最后比較不同條件社區(qū)搜索方法的時(shí)間開(kāi)銷和結(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ū)搜索+過(guò)濾”方法和WLP方法.

本文實(shí)驗(yàn)采用的真實(shí)數(shù)據(jù)集有Football,DBLP,Amazon和Youtube,其中,Football數(shù)據(jù)集來(lái)自Khorasgani[44],其余數(shù)據(jù)集來(lái)自Stanford Large Network Dataset Collection(http://snap.stanford.edu/data/),具體統(tǒng)計(jì)信息見(jiàn)表1,均帶有真實(shí)的社區(qū)分布.表1最后一列的top5000社區(qū)是指數(shù)據(jù)集提供的前5 000個(gè)質(zhì)量最高的社區(qū)(評(píng)判標(biāo)準(zhǔn)因數(shù)據(jù)集而異,如conductance,modularity等,詳見(jiàn)文獻(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,以便提前終止局部搜索過(guò)程,提高算法效率.

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

為了研究簡(jiǎn)化搜索條件的方法在不同規(guī)模網(wǎng)絡(luò)圖上的效果,本文還采用人工網(wǎng)絡(luò)生成工具 Lancichinetti-Fortunato-Radicchi(LFR)[46]來(lái)合成不同規(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é)果的評(píng)價(jià)指標(biāo)

通過(guò)參考現(xiàn)有社區(qū)發(fā)現(xiàn)和社區(qū)搜索的評(píng)價(jià)標(biāo)準(zhǔn),本文選取F1-measure和Ql(局部模塊度)來(lái)評(píng)估結(jié)果社區(qū)的質(zhì)量,其中,F1-measure衡量了結(jié)果社區(qū)的正確性,Ql評(píng)估了結(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è)俱樂(lè)部成員標(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)都來(lái)自同一真實(shí)社區(qū),而禁止節(jié)點(diǎn)都在該社區(qū)外時(shí),數(shù)據(jù)集提供的真實(shí)社區(qū)就是對(duì)應(yīng)單項(xiàng)條件社區(qū)搜索的真實(shí)社區(qū).在其他情況下,例如必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)都來(lái)自數(shù)據(jù)集提供的某個(gè)真實(shí)社區(qū)時(shí),本文提出的“社區(qū)搜索+過(guò)濾”方法以及WLP方法仍有返回結(jié)果的可能.該結(jié)果往往預(yù)示著數(shù)據(jù)集提供的真實(shí)社區(qū)中存在著可以細(xì)分的子社區(qū)結(jié)構(gòu),但此時(shí)的真實(shí)社區(qū)無(wú)法預(yù)知.因此,在這種情形下就無(wú)法使用F1-measure進(jìn)行正確性度量,而只關(guān)心所得社區(qū)的緊密性和社區(qū)內(nèi)成員相對(duì)必要節(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ū)緊密性越好.

除此之外,為了評(píng)估社區(qū)內(nèi)節(jié)點(diǎn)與必要節(jié)點(diǎn)的接近程度,本文設(shè)計(jì)了相對(duì)最短路徑比這一新指標(biāo),即社區(qū)內(nèi)節(jié)點(diǎn)分別與必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的平均最短路徑距離之比(average shortest pathdistance ratio,簡(jiǎn)稱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 搜索條件簡(jiǎn)化的有效性

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

根據(jù)第 2節(jié)提出的條件社區(qū)搜索通用框架,無(wú)論搜索條件是否經(jīng)過(guò)簡(jiǎn)化,該框架都需要先枚舉所有滿足原始搜索條件的變量組合,簡(jiǎn)化搜索條件的有效性在之后的步驟才體現(xiàn)出來(lái).因此在本節(jié)實(shí)驗(yàn)中,搜索條件被設(shè)計(jì)為主析取范式的形式,相當(dāng)于省去枚舉變量取值過(guò)程的開(kāi)銷.該主析取范式包含q個(gè)搜索項(xiàng),每個(gè)搜索項(xiàng)包含相同的v個(gè)節(jié)點(diǎn)變量.這v個(gè)節(jié)點(diǎn)變量按照均勻分布從網(wǎng)絡(luò)圖中隨機(jī)選取.此外,對(duì)每個(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)閷?duì)任意形式的搜索條件總能得出與其等價(jià)的主析取范式[40],范式中搜索項(xiàng)的個(gè)數(shù)和節(jié)點(diǎn)變量的個(gè)數(shù)允許任意指定,并且節(jié)點(diǎn)變量是隨機(jī)選取的,所以上述搜索條件設(shè)計(jì)可以表達(dá)任意的搜索條件,其完備性得以保證.

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

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

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

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

Fig.6 Time costs of conditional community search with different query numbers (# node variablev=5)圖6 不同搜索項(xiàng)個(gè)數(shù)下條件社區(qū)搜索方法的時(shí)間開(kāi)銷(節(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í)間開(kāi)銷(簡(jiǎn)化前搜索項(xiàng)個(gè)數(shù)q=10)

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

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

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

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

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

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

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

為公平起見(jiàn),所有社區(qū)搜索算法均采用FindCore算法.對(duì)不同節(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)λ超過(guò)0.2時(shí),在DBLP上難以找到合適社區(qū),而在Football上社區(qū)準(zhǔn)確性下降.需要說(shuō)明的是,在兩個(gè)數(shù)據(jù)集上,-1<λ<0時(shí)F1-measure的值與λ=0時(shí)F1-measure的值相等;當(dāng)λ>0.4時(shí),得到的F1-measure的值均為0,所以在圖中沒(méi)有顯示上述范圍內(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方法的具體過(guò)程,第γ輪迭代中相對(duì)于必要節(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對(duì)比了4種不同方法的時(shí)間開(kāi)銷.圖11(a)和圖11(b)分別是在Football和DBLP數(shù)據(jù)集上取得的實(shí)驗(yàn)結(jié)果,橫坐標(biāo)編號(hào)對(duì)應(yīng)搜索條件.

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

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

圖12展示了4種不同方法在Football和DBLP數(shù)據(jù)集上所得社區(qū)結(jié)果的F1-measure.在每次單項(xiàng)條件社區(qū)搜索的具體實(shí)驗(yàn)中,要求其搜索條件中的必要節(jié)點(diǎn)來(lái)自同一實(shí)際社區(qū),同時(shí)禁止節(jié)點(diǎn)來(lái)自該社區(qū)外.這樣就可以根據(jù)數(shù)據(jù)集附帶的真實(shí)社區(qū)結(jié)果計(jì)算F1-measure.從圖12(a)和圖12(b)可以看出:無(wú)論是Football還是DBLP數(shù)據(jù)集,3種不同策略下“社區(qū)搜索+過(guò)濾”方法得到的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,但是相對(duì)差異并不明顯.這是由于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ì)被閾值過(guò)濾排除在外.這實(shí)際上是為使社區(qū)內(nèi)成員與必要節(jié)點(diǎn)更接近而付出的必要開(kāi)銷.

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

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

圖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對(duì)比

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

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

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

本文給出了 CCS的形式化定義,并使用布爾表達(dá)式表示搜索條件.在此基礎(chǔ)上,本文提出了解決 CCS的通用框架,將CCS分解為多個(gè)SCCS來(lái)處理,并通過(guò)簡(jiǎn)化搜索條件對(duì)通用框架進(jìn)行了優(yōu)化.對(duì)于SCCS,本文提出了“社區(qū)搜索+過(guò)濾”的方法(包括FF,OTF和SF這3種策略)和基于標(biāo)簽傳播給點(diǎn)加權(quán)的WLP方法.通過(guò)在4個(gè)真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn),比較了這些方法的時(shí)間開(kāi)銷和社區(qū)結(jié)果.實(shí)驗(yàn)結(jié)果表明,使用OTF策略的“社區(qū)搜索+過(guò)濾”方法在時(shí)間開(kāi)銷和社區(qū)結(jié)果上具有優(yōu)勢(shì).如果考慮用戶在使用條件社區(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ū)定義.對(duì)于SCCS,希望找到一種新的社區(qū)搜索算法,使得社區(qū)結(jié)構(gòu)在準(zhǔn)確性和緊密程度上達(dá)到最優(yōu)的同時(shí)也能考慮必要節(jié)點(diǎn)和禁止節(jié)點(diǎn)的影響.