譚玉婷 王習(xí)特 白 梅 周虹宇 朱 斌

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116000)

0 引 言

現(xiàn)實(shí)世界中的諸多網(wǎng)絡(luò),如生物網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等,都包含社區(qū)結(jié)構(gòu)。發(fā)現(xiàn)網(wǎng)絡(luò)中的社區(qū)是網(wǎng)絡(luò)科學(xué)中的一個(gè)基本問題,近年來受到研究者們的廣泛關(guān)注[1-5]。網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)數(shù)量通常較多,在許多實(shí)際應(yīng)用領(lǐng)域中,人們往往只對(duì)在網(wǎng)絡(luò)中影響力較大的社區(qū)感興趣[5]。受此啟發(fā),在文獻(xiàn)[5-6,14]中基于k-core的概念提出并研究了網(wǎng)絡(luò)中社區(qū)影響值排名的top-r查詢問題。k-影響社區(qū)是網(wǎng)絡(luò)中聯(lián)系密切(即滿足k-core屬性)、具有較大影響且不存在包含關(guān)系的子網(wǎng)絡(luò)。本文用k-core模型來模擬社區(qū)結(jié)構(gòu)的凝聚性[1,5,11-13,15],因此社區(qū)即為k-core,并且社區(qū)影響值是k-core中所有節(jié)點(diǎn)權(quán)重的最小值。根據(jù)k-core的概念,滿足k-core且影響值較大的社區(qū)可表示為“k-influential Community”,本文中用縮寫k-IC表示。如圖1所示的網(wǎng)絡(luò),其中包含13個(gè)節(jié)點(diǎn){v1,v2,…,v13},每個(gè)節(jié)點(diǎn)的權(quán)重表示其影響值的大小。若取k=3,網(wǎng)絡(luò)中包含兩個(gè)k-IC:{v10,v11,v12,v13}和{v1,v2,v3},其社區(qū)影響值分別為13和12。

圖1 k-影響社區(qū)示例

目前,關(guān)于k-IC查詢問題已經(jīng)取得了大量?jī)?yōu)秀的研究成果,但是現(xiàn)有工作大部分關(guān)注的是結(jié)構(gòu)的凝聚性,而忽略了節(jié)點(diǎn)的屬性[7-9],比如影響力。針對(duì)這些問題,提出了網(wǎng)絡(luò)中k-IC的top-r查詢問題。這一問題在許多領(lǐng)域有重要的應(yīng)用,例如從電商直播平臺(tái)形成的社交網(wǎng)絡(luò)中識(shí)別出由粉絲數(shù)量高的主播形成的k-IC,這些主播的影響力都很大,通過他們的推薦,產(chǎn)品的銷售量會(huì)提高很多。同時(shí),k-IC的非包含屬性能減少節(jié)點(diǎn)間的重復(fù),因此可識(shí)別到更多有影響力的主播。此外,還可用來從生物網(wǎng)絡(luò)中提取骨架結(jié)構(gòu)[7],以及識(shí)別數(shù)據(jù)庫(kù)研究人員協(xié)作網(wǎng)絡(luò)中最具影響力的k-IC來組織研討會(huì)[5]等。

本文主要針對(duì)網(wǎng)絡(luò)中k-IC的top-r查詢問題,提出了一種新型的k-IC查詢算法。目前對(duì)此問題的相關(guān)研究主要有文獻(xiàn)[5-6,14]。其中文獻(xiàn)[5-6]中提出了直接算法和基于索引的算法。直接算法基于給定圖的k-core分解計(jì)算社區(qū),算法中逐步刪除屬性值小的節(jié)點(diǎn),運(yùn)行最大連通組件(MCC)算法發(fā)現(xiàn)下一個(gè)k-IC,然而文中對(duì)于是否具有包含關(guān)系的判斷沒有給出高效的方法。基于索引的算法首先建立索引,然后根據(jù)給定的r和k,提取前r個(gè)位于索引樹的葉子節(jié)點(diǎn)的k-core。雖然基于索引的算法相較于直接算法更有效,但是構(gòu)建索引的時(shí)間消耗大且該索引結(jié)構(gòu)需要的空間與原始圖形的大小基本相同,消耗內(nèi)存也較大。直接算法中最耗時(shí)的是識(shí)別圖中包含最小權(quán)重節(jié)點(diǎn)的連通分量,鑒于此,文獻(xiàn)[14]提出了Forward算法,僅對(duì)最后的k次迭代進(jìn)行連通分量的計(jì)算,但是該算法依然是從權(quán)重較小的節(jié)點(diǎn)開始處理,需要對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行處理最后才能得到結(jié)果。針對(duì)這些問題,本文提出了一種新型的算法,該算法不需要頻繁地計(jì)算圖中的連通分量以及判斷k-core間的包含性,并且從權(quán)重較大的節(jié)點(diǎn)開始處理,只對(duì)網(wǎng)絡(luò)中的部分節(jié)點(diǎn)進(jìn)行處理即可漸進(jìn)且快速求得前r個(gè)k-IC。

本文設(shè)計(jì)了一種表狀索引結(jié)構(gòu)對(duì)網(wǎng)絡(luò)圖進(jìn)行管理和維護(hù),并提出了有效解決k-IC的top-r查詢的新算法。具體地,本文貢獻(xiàn)總結(jié)如下:

(1) 提出了W-D(Weight-Degree)索引結(jié)構(gòu),用于管理各個(gè)節(jié)點(diǎn)的度數(shù)及其具體的鄰居節(jié)點(diǎn),并根據(jù)權(quán)重大小對(duì)節(jié)點(diǎn)進(jìn)行排序。使用該索引可以確定被取節(jié)點(diǎn)的順序,并對(duì)度數(shù)不滿足參數(shù)k的節(jié)點(diǎn)進(jìn)行過濾,同時(shí)可以加快節(jié)點(diǎn)之間鄰居關(guān)系的判斷,提高了k-IC的查詢處理效率。

(2) 提出了k-IC的top-r查詢優(yōu)化算法ITIC。該算法從權(quán)重較大的節(jié)點(diǎn)開始處理,無須處理大多數(shù)權(quán)重較小的節(jié)點(diǎn),并且不需要頻繁地計(jì)算圖中的連通分量;另外,算法漸進(jìn)輸出k-IC,當(dāng)k-IC的數(shù)量滿足用戶的需求時(shí),用戶可以在任何時(shí)間終止算法。

(3) 進(jìn)行了詳細(xì)的性能評(píng)價(jià)實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明本文所提出的k-IC的top-r查詢優(yōu)化算法ITIC可以有效地處理k-IC的top-r查詢問題。

1 相關(guān)工作

本節(jié)主要對(duì)k-IC查詢的相關(guān)研究進(jìn)行概述。與本文所研究問題最為接近的有文獻(xiàn)[5-6,10,14]。

Li等[5-6]將網(wǎng)絡(luò)建模為無向圖G=(V,E),其中G中每個(gè)節(jié)點(diǎn)的權(quán)重表示其影響力。針對(duì)此模型,提出了DFS算法,用于在線搜索影響值較大的前k個(gè)社區(qū),在線搜索算法迭代地應(yīng)用以下三個(gè)子程序:(1) 將當(dāng)前圖形刪減為滿足γ-core的最大子圖;(2) 識(shí)別出最大子圖中包含最小權(quán)重節(jié)點(diǎn)的連通分量,這是下一個(gè)γ-影響社區(qū);(3) 從圖中刪除最小權(quán)重節(jié)點(diǎn)。最后的k個(gè)影響值較大的γ-影響社區(qū)就是結(jié)果。該算法需要多次迭代和多次進(jìn)行復(fù)雜的連通分量計(jì)算,效率較低,并且算法從權(quán)重最小的節(jié)點(diǎn)開始計(jì)算,逐步刪除權(quán)重小的節(jié)點(diǎn),在計(jì)算結(jié)束時(shí)才能得到top-k個(gè)γ-影響社區(qū)。對(duì)于非常大的圖,基于DFS的算法比較低效,所以Li等設(shè)計(jì)了ICP-Index索引結(jié)構(gòu),用于預(yù)先計(jì)算k-core,但是構(gòu)建索引所需的內(nèi)存與原始圖形的大小基本相同,消耗內(nèi)存較大。

Chen等[14]改進(jìn)了文獻(xiàn)[5]中的在線搜索算法,提出了Forward和Backward兩種在線算法。Forward算法僅對(duì)最后的k次迭代進(jìn)行連通分量計(jì)算,但依然是從權(quán)重小的節(jié)點(diǎn)開始計(jì)算。Backward算法雖然是從權(quán)重大的節(jié)點(diǎn)開始處理,但是算法中多次調(diào)用updateCores更新節(jié)點(diǎn)的核數(shù),使得算法的時(shí)間復(fù)雜度很高。Bi等[10]對(duì)在線搜索算法進(jìn)行了改進(jìn),提出了局部搜索算法,但是算法通過多次迭代增大的方式確定子圖,計(jì)算成本不低且存在不確定性,并且該算法沒有給出高效的判斷k-core間是否具有包含性的方法。

總之,目前現(xiàn)有的k-IC的top-r查詢算法存在諸多不足,無法保證計(jì)算效率,因此本文就此問題進(jìn)行了研究。

2 問題描述

本文主要研究如何高效地計(jì)算出網(wǎng)絡(luò)中的前r個(gè)k-IC。為了描述方便,表1中給出了本文的符號(hào)定義。然后給出了k-IC及相關(guān)內(nèi)容的形式化定義。

表1 符號(hào)表示

把網(wǎng)絡(luò)建模為無向圖G=(V,E),其中V和E分別表示點(diǎn)集合和邊集合。G中的每個(gè)節(jié)點(diǎn)u都具有權(quán)重wu∈W(例如PageRank或其他用戶定義的屬性),表示u的影響值(或重要性)。在本文中,假設(shè)不同節(jié)點(diǎn)的權(quán)重不同,即wv≠wu,v≠u。

文中的deg(v,G)表示節(jié)點(diǎn)v在圖G中的度數(shù)。設(shè)H=(VH,EH)為G=(V,E)的誘導(dǎo)子圖,即VHV,EH={(u,v)|u,v∈VH,(u,v)∈E}。如從圖1中選取節(jié)點(diǎn)v1、v2、v3、v4,形成的G的誘導(dǎo)子圖如圖2(a)所示,保留了在圖1中與v1、v2、v3、v4有關(guān)的所有邊。若去掉此誘導(dǎo)子圖中的任意邊,如去掉v1、v4之間的邊,形成的圖僅為G的子圖,不再是誘導(dǎo)子圖,如圖2(b)所示。若H是誘導(dǎo)子圖,且其中每個(gè)節(jié)點(diǎn)v∈H的度數(shù)至少為k,即deg(v,H)≥k,則H稱為k-core。若H′是k-core,并且沒有更大的k-core可以包含H′,則H′稱為最大k-core。

(a) 誘導(dǎo)子圖 (b) 子圖

定義1社區(qū)影響值[5]。給定無向圖G=(V,E)和G的誘導(dǎo)子圖H=(VH,EH),H的社區(qū)影響值是H中所有節(jié)點(diǎn)權(quán)重的最小值,記作f(H),即:

(1)

定義2k-影響社區(qū)k-IC。給定無向圖G=(V,E)和整數(shù)k,G的誘導(dǎo)子圖H=(VH,EH)若是一個(gè)k-IC,需要滿足以下屬性:

(1) 連通性:H是連通的子圖。

(2) 內(nèi)聚性:H中的每個(gè)節(jié)點(diǎn)的度數(shù)至少為k,即H是一個(gè)k-core。

(3) 最大性:不存在G的誘導(dǎo)子圖H′滿足:①H′滿足連通性和內(nèi)聚性;②H′包含H;③f(H′)=f(H)。

(4) 非包含性:H不能包含社區(qū)影響值滿足f(H′)>f(H)的H′。

例1考慮圖3中帶有權(quán)重的無向圖G,G由{v1,v2,…,v16}共16個(gè)節(jié)點(diǎn)組成,括號(hào)內(nèi)的數(shù)值為其權(quán)重,假設(shè)k=2、r=3。根據(jù)定義2,由節(jié)點(diǎn)集{v10,v11,v12,v13}形成的誘導(dǎo)子圖是2-IC,其社區(qū)影響值為13。由節(jié)點(diǎn)集{v10,v11,v13}和{v11,v12,v13}形成的誘導(dǎo)子圖均不是2-IC,因?yàn)樗鼈兊纳鐓^(qū)屬性值也為13,且包含在由{v10,v11,v12,v13}形成的2-IC中,不滿足最大性約束。由節(jié)點(diǎn)集{v9,v10,v11,v12,v13}形成的誘導(dǎo)子圖也不是2-IC,因?yàn)槠浒?-IC{v10,v11,v12,v13},不滿足非包含性。

圖3 網(wǎng)絡(luò)圖G

在許多實(shí)際應(yīng)用中,人們通常對(duì)網(wǎng)絡(luò)中影響值比其他社區(qū)的影響值大且重復(fù)性小的k-core感興趣,因此本文的研究目標(biāo)為:給定無向圖G=(V,E),權(quán)重向量W和兩個(gè)參數(shù)k和r,目標(biāo)是找到具有最高影響值的前r個(gè)k-IC。

3 算法設(shè)計(jì)

本節(jié)首先介紹了W-D索引結(jié)構(gòu),然后提出了基于該索引的算法ITIC。

3.1 W-D索引結(jié)構(gòu)

W-D索引是一種表狀索引結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)其權(quán)重和度數(shù)以及一個(gè)存放其鄰居節(jié)點(diǎn)的數(shù)組,節(jié)點(diǎn)的度數(shù)等于鄰居節(jié)點(diǎn)的個(gè)數(shù)。W-D索引中按照權(quán)重由大到小對(duì)所有節(jié)點(diǎn)進(jìn)行排序。

如表2所示,根據(jù)例1中的圖G建立的W-D索引,以v5為例,v5的權(quán)重最大,排在索引的首位,度數(shù)為2,其鄰居節(jié)點(diǎn)有{v3,v6}。

表2 W-D索引表示例

W-D索引在ITIC算法中可用于確定被取節(jié)點(diǎn)的順序,以及是否對(duì)被取節(jié)點(diǎn)進(jìn)行處理,同時(shí)可以加快節(jié)點(diǎn)之間鄰居關(guān)系的判斷,提高了k-IC的查詢處理效率。

3.2 ITIC描述

ITIC主要處理過程如下:(1) 插入桶;(2) k-IC判定。

3.2.1插入處理

ITIC首先從W-D索引中取點(diǎn),選取索引中未處理部分的首元素v,若節(jié)點(diǎn)v在索引中的度數(shù)滿足大于等于k,將v插入相應(yīng)的桶B[i]中進(jìn)行處理,否則不處理,繼續(xù)進(jìn)行取點(diǎn)。

桶B[i]。要求每個(gè)桶B[i]中的節(jié)點(diǎn)滿足條件:任意B[i]中的節(jié)點(diǎn)能夠組成一個(gè)連通子圖。

對(duì)B[i]中的節(jié)點(diǎn)保留如下存儲(chǔ)結(jié)構(gòu):

桶度數(shù)(B-deg(v,Hm)),即vj在桶B[i]中的度數(shù),其中:Hm是B[i]中的節(jié)點(diǎn)形成的誘導(dǎo)子圖。

定義3DC點(diǎn)。在桶B[i]中與組成k-IC的節(jié)點(diǎn)直接相連的節(jié)點(diǎn)稱為DC點(diǎn)。

節(jié)點(diǎn)標(biāo)記flag的取值有如下4種:

(1)flag=0,表示節(jié)點(diǎn)未經(jīng)判定的初始狀態(tài);

(2)flag=1,表示該節(jié)點(diǎn)是組成k-IC的節(jié)點(diǎn);

(3)flag=2,表示該節(jié)點(diǎn)是DC點(diǎn);

(4)flag=-1,表示經(jīng)判定該節(jié)點(diǎn)一定不是組成k-IC的節(jié)點(diǎn)。

插入處理的具體過程如下:(1) 取到度數(shù)大于等于k的節(jié)點(diǎn)v后,遍歷現(xiàn)有桶B[m],只要B[m]中存在節(jié)點(diǎn)u與v是鄰居,就將此B[m]中的節(jié)點(diǎn)全部移加到臨時(shí)桶b中,并刪除當(dāng)前B[m];(2) 遍歷完成后,將v加到b中,更新b中節(jié)點(diǎn)的桶度數(shù)并移加全部節(jié)點(diǎn)到新桶B[n](v所在的桶記作B[n])。

例2依然以例1中的圖G為例,當(dāng)取到節(jié)點(diǎn)v11時(shí),現(xiàn)有桶僅B[2]中有其鄰居節(jié)點(diǎn)v10,因此v11插入后的桶如圖4(a)所示。當(dāng)取到節(jié)點(diǎn)v9時(shí)桶的分布如圖4(b)所示,桶中的{v10,v11,v12,v13}是一個(gè)2-IC,因此v9是DC點(diǎn)。

(a) 取到v11時(shí)的桶(b) 取到v9時(shí)的桶

算法1給出了ITIC的偽代碼描述。

算法1ITIC描述

輸入:網(wǎng)絡(luò)圖G=(V,E),索引,參數(shù)k、r。

輸出:top-rk-IC。

1.While(索引不為空&&|S|

2.取索引中未處理部分的首元素v;

3.If (v在度-鄰索引中的度數(shù)

4.Else

5.flag(v)=0;b=?;

//標(biāo)記flag,臨時(shí)集合b

6.For (每個(gè)B[m])

7.If(B[m]中存在節(jié)點(diǎn)u與v是鄰居)

8.If (flag(u)==1&&flag(v)==0)

9.flag(v)=2;

//DC點(diǎn)標(biāo)記flag=2

10.把B[m]中的所有節(jié)點(diǎn)移加到b中;

11.刪除B[m];

12.v加入b中,更新b中節(jié)點(diǎn)的桶度數(shù)并

將所有節(jié)點(diǎn)移到新桶B[n];

13.If (B[n]中節(jié)點(diǎn)滿足定理3)

14.S←S∪JudK-IC(B[n],k);

3.2.2k-IC判定處理

當(dāng)桶B[n]中插入節(jié)點(diǎn)v后,若達(dá)到判定條件,需要對(duì)B[n]進(jìn)行k-IC判定。本節(jié)主要介紹k-IC判定策略。

定理1DC點(diǎn)一定不是組成k-IC的節(jié)點(diǎn),包含DC點(diǎn)的k-core一定不是k-IC。

證明:根據(jù)DC點(diǎn)的定義,DC點(diǎn)直接與組成k-ICH的節(jié)點(diǎn)相連,并且易知DC點(diǎn)的影響值比H的社區(qū)屬性值小。根據(jù)定義2,包含此DC點(diǎn)的k-core若滿足最大性,需要包含H,因此不滿足非包含性,此k-core一定不是k-IC。定理1得證。

證畢。

圖3中G的誘導(dǎo)子圖{v9,v10,v11,v12,v13}和{v1,v2,v3,v4}中分別包含DC點(diǎn)v9和v3,二者均不是2-IC。

定理2任意包含組成已得k-IC的節(jié)點(diǎn)(即flag=1的節(jié)點(diǎn))的k-core一定不是新的k-IC。

證明:根據(jù)定義2的最大性,k-IC的子圖一定不是新的k-IC;又根據(jù)定理1,無論k-IC還是k-IC的子圖,加上DC點(diǎn)后組成的新的最大k-core都一定不是新的k-IC。定理2得證。

證畢。

根據(jù)定理2,包含k-IC中所有flag=1的節(jié)點(diǎn)的k-core和包含部分flag=1節(jié)點(diǎn)的k-core均不是新的k-IC,如圖3中G的誘導(dǎo)子圖{v9,v10,v11,v13}和{v1,v2,v3,v5,v6}均不是新的2-IC。

根據(jù)定理1和定理2,如果節(jié)點(diǎn)v是DC點(diǎn),只需對(duì)v進(jìn)行插入操作即可,然后返回取下一個(gè)節(jié)點(diǎn)。

引理1當(dāng)B[n]中有多于k個(gè)flag=0的節(jié)點(diǎn)滿足deg(u,Hn)≥k時(shí),B[n]中可能存在k-IC。

定理3只有當(dāng)v不是DC點(diǎn)同時(shí)滿足deg(v,Hn)≥k,并且B[n]滿足引理1時(shí),可對(duì)B[n]進(jìn)行k-IC判定。

證明:根據(jù)定理1和引理1易得證。

滿足定理3時(shí),對(duì)B[n]進(jìn)行k-IC判定,算法2給出了k-IC判定算法的偽代碼描述。

算法2JudK-IC(B[n],k)

輸入:桶B[n],參數(shù)k。

輸出:包含v的k-IC。

1.Tm=?;R=?;

//臨時(shí)集合Tm,返回結(jié)果集R

2.把B[n]中B-deg(u,Hn)≥k的節(jié)點(diǎn)u加入Tm;

3.求Tm中每個(gè)節(jié)點(diǎn)u的臨時(shí)度數(shù)degTm(u,HTm);

4.If (Tm中全部節(jié)點(diǎn)均滿足degTm(u,HTm)≥k)

5.R←只由flag=0的節(jié)點(diǎn)組成的最大連通分量;

6.Else

7.遞歸刪除Tm中degTm(u,HTm)

8.If (Tm中degTm(u,HTm)≥k的節(jié)點(diǎn)個(gè)數(shù)>k)

9.R←只由flag=0的節(jié)點(diǎn)組成的最大連通分量;

10.Else return false;

11.If (R≠?)

12.為R中的每個(gè)節(jié)點(diǎn)設(shè)置flag=1;

13.將Tm中flag=0的節(jié)點(diǎn)設(shè)置標(biāo)記flag=-1;

14.returnR;

k-IC判定的具體過程如下:(1) 把B[n]中桶度數(shù)B-deg(u,Hn)≥k的節(jié)點(diǎn)u加入臨時(shí)集合Tm,并求Tm中每個(gè)節(jié)點(diǎn)u的臨時(shí)度數(shù)degTm(u,HTm)。(2) 如果Tm中全部節(jié)點(diǎn)均滿足degTm(u,HTm)≥k,則返回這些節(jié)點(diǎn)中只由flag=0的節(jié)點(diǎn)組成的最大連通分量;否則,遞歸刪除Tm中degTm(u,HTm)

例3仍以例1中的圖G為例,k=2、r=3。當(dāng)節(jié)點(diǎn)v13插入桶B[4]時(shí),B[4]滿足定理3,如圖5所示,對(duì)B[4]進(jìn)行2-IC判定。將B[4]中滿足桶度數(shù)B-deg(

圖5 k-IC判定示例

u,Hn)≥2的節(jié)點(diǎn)v10、v11、v12、v13加入臨時(shí)集合Tm,并求它們?cè)赥m中的臨時(shí)度數(shù)degTm(u,HTm),在此例中B-deg(u,Hn)=degTm(u,HTm),各節(jié)點(diǎn)均滿足≥2,因此{(lán)v10,v11,v12,v13}是一個(gè)2-IC。

當(dāng)取到節(jié)點(diǎn)v2時(shí),從桶中共輸出3個(gè)2-IC,分別為H1={v10,v11,v12,v13},H2={v14,v15,v16},H3={v1,v2,v4},社區(qū)屬性值分別為f(H1)=13,f(H2)=9,f(H3)=8。至此已滿足參數(shù)r=3,求得top-3 2-IC,算法結(jié)束。

4 實(shí)驗(yàn)與結(jié)果分析

在本節(jié)中,使用C++語(yǔ)言實(shí)現(xiàn)了文中提出的ITIC。環(huán)境配置為Intel Xeon W-2104 3.19 GHz CPU,32 GB內(nèi)存,Windows 10操作系統(tǒng)。

本節(jié)將ITIC與之前效果較好的NC算法[4]和LocalSearch算法[10]進(jìn)行性能分析比較。本文使用了兩個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集Wiki和Arabic驗(yàn)證算法性能。節(jié)點(diǎn)的權(quán)重為其PageRank值。表3總結(jié)了數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)。在表3中,n和m分別表示網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)量,dmax和kmax分別表示網(wǎng)絡(luò)的最大度數(shù)和最大核數(shù)。

表3 實(shí)驗(yàn)參數(shù)

圖6描述了Wiki和Arabic兩個(gè)數(shù)據(jù)集下,參數(shù)k對(duì)算法的影響。此處設(shè)置參數(shù)r=15不變,參數(shù)k的取值范圍為{5,10,20,50}。可以看出,隨著參數(shù)k的增大,NC算法的處理時(shí)間逐漸減少,ITIC和LocalSearch算法的處理時(shí)間逐漸增加,但兩個(gè)數(shù)據(jù)集整體處理效率都表現(xiàn)為ITIC優(yōu)于NC算法和LocalSearch算法。NC算法是從權(quán)重小的節(jié)點(diǎn)開始處理,需要處理完所有節(jié)點(diǎn)之后才能得到結(jié)果;LocalSearch算法需要先估算局部搜索圖的大小,遍歷局部圖中的所有節(jié)點(diǎn)找到全部keys,然后才能得到結(jié)果;而ITIC是從權(quán)重大的節(jié)點(diǎn)開始處理,處理權(quán)重較大的部分節(jié)點(diǎn)就能得到結(jié)果,不需要提前估算局部圖的大小,并且不需要頻繁計(jì)算圖中的連通分量,使得ITIC效率更高。

圖6 參數(shù)k對(duì)算法的影響(r=15)

圖7描述了Wiki和Arabic兩個(gè)數(shù)據(jù)集下,參數(shù)r對(duì)算法的影響。此處設(shè)置參數(shù)k=15不變,參數(shù)r的取值范圍為{5,10,20,50,100}?？梢钥闯?兩個(gè)數(shù)據(jù)集都表現(xiàn)為整體處理時(shí)間ITIC優(yōu)于NC算法和LocalSearch算法。其中當(dāng)參數(shù)r不是特別大時(shí),ITIC優(yōu)勢(shì)明顯,因?yàn)镮TIC為漸進(jìn)輸出,只需要處理部分權(quán)重較大的節(jié)點(diǎn)就能求得top-r的結(jié)果,使得ITIC效率更高。

圖7 參數(shù)r對(duì)算法的影響(k=15)

圖8所示為當(dāng)r=15時(shí)算法在不同k下的內(nèi)存占用大小比較,其中k的取值范圍為{5,10,15,20,25}。可以看出,對(duì)于Wiki和Arabic兩個(gè)網(wǎng)絡(luò),ITIC消耗的內(nèi)存比NC算法和LocalSearch算法都少,因?yàn)镮TIC根據(jù)參數(shù)k進(jìn)行了過濾,k越大,過濾掉的節(jié)點(diǎn)越多,并且ITIC不需要頻繁計(jì)算圖中的連通分量,使得ITIC消耗的內(nèi)存更小。

(a) Wiki

通過上述多種不同的實(shí)驗(yàn)測(cè)試,驗(yàn)證了本文提出的ITIC的有效性,無論是變化參數(shù)k還是參數(shù)r,ITIC在處理時(shí)間和內(nèi)存占用方面都優(yōu)于現(xiàn)有算法,可以滿足人們的日常需求。

5 結(jié) 語(yǔ)

本文研究了網(wǎng)絡(luò)中k-IC的top-r查詢問題。首先,提出了用W-D索引來管理網(wǎng)絡(luò),該索引結(jié)構(gòu)可以確定被取節(jié)點(diǎn)的順序,且對(duì)不滿足條件的節(jié)點(diǎn)進(jìn)行過濾,同時(shí)可以加快對(duì)節(jié)點(diǎn)之間鄰居關(guān)系的判斷,提高了k-IC的查詢處理效率。然后,提出了k-IC的top-r查詢優(yōu)化算法:ITIC。該算法從權(quán)重較大的節(jié)點(diǎn)開始處理,一般情況下,只需處理部分節(jié)點(diǎn)即可求得結(jié)果,并且不需要頻繁地計(jì)算圖中的連通分量;另外,ITIC漸進(jìn)輸出k-IC,當(dāng)k-IC的數(shù)量滿足用戶的需求時(shí),用戶可以在任意時(shí)間終止算法。最后,通過實(shí)驗(yàn)驗(yàn)證了ITIC的有效性。