ITIC:一種高效的k-影響社區top-r查詢算法

譚玉婷 王習特 白 梅 周虹宇 朱 斌

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

0 引 言

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

圖1 k-影響社區示例

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

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

本文設計了一種表狀索引結構對網絡圖進行管理和維護,并提出了有效解決k-IC的top-r查詢的新算法。具體地,本文貢獻總結如下:

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

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

(3) 進行了詳細的性能評價實驗。實驗結果表明本文所提出的k-IC的top-r查詢優化算法ITIC可以有效地處理k-IC的top-r查詢問題。

1 相關工作

本節主要對k-IC查詢的相關研究進行概述。與本文所研究問題最為接近的有文獻[5-6,10,14]。

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

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

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

2 問題描述

本文主要研究如何高效地計算出網絡中的前r個k-IC。為了描述方便,表1中給出了本文的符號定義。然后給出了k-IC及相關內容的形式化定義。

表1 符號表示

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

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

(a) 誘導子圖 (b) 子圖

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

(1)

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

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

(2) 內聚性:H中的每個節點的度數至少為k,即H是一個k-core。

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

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

例1考慮圖3中帶有權重的無向圖G,G由{v1,v2,…,v16}共16個節點組成,括號內的數值為其權重,假設k=2、r=3。根據定義2,由節點集{v10,v11,v12,v13}形成的誘導子圖是2-IC,其社區影響值為13。由節點集{v10,v11,v13}和{v11,v12,v13}形成的誘導子圖均不是2-IC,因為它們的社區屬性值也為13,且包含在由{v10,v11,v12,v13}形成的2-IC中,不滿足最大性約束。由節點集{v9,v10,v11,v12,v13}形成的誘導子圖也不是2-IC,因為其包含2-IC{v10,v11,v12,v13},不滿足非包含性。

圖3 網絡圖G

在許多實際應用中,人們通常對網絡中影響值比其他社區的影響值大且重復性小的k-core感興趣,因此本文的研究目標為:給定無向圖G=(V,E),權重向量W和兩個參數k和r,目標是找到具有最高影響值的前r個k-IC。

3 算法設計

本節首先介紹了W-D索引結構,然后提出了基于該索引的算法ITIC。

3.1 W-D索引結構

W-D索引是一種表狀索引結構。每個節點對應其權重和度數以及一個存放其鄰居節點的數組,節點的度數等于鄰居節點的個數。W-D索引中按照權重由大到小對所有節點進行排序。

如表2所示,根據例1中的圖G建立的W-D索引,以v5為例,v5的權重最大,排在索引的首位,度數為2,其鄰居節點有{v3,v6}。

表2 W-D索引表示例

W-D索引在ITIC算法中可用于確定被取節點的順序,以及是否對被取節點進行處理,同時可以加快節點之間鄰居關系的判斷,提高了k-IC的查詢處理效率。

3.2 ITIC描述

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

3.2.1插入處理

ITIC首先從W-D索引中取點,選取索引中未處理部分的首元素v,若節點v在索引中的度數滿足大于等于k,將v插入相應的桶B[i]中進行處理,否則不處理,繼續進行取點。

桶B[i]。要求每個桶B[i]中的節點滿足條件:任意B[i]中的節點能夠組成一個連通子圖。

對B[i]中的節點保留如下存儲結構:

桶度數(B-deg(v,Hm)),即vj在桶B[i]中的度數,其中:Hm是B[i]中的節點形成的誘導子圖。

定義3DC點。在桶B[i]中與組成k-IC的節點直接相連的節點稱為DC點。

節點標記flag的取值有如下4種:

(1)flag=0,表示節點未經判定的初始狀態;

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

(3)flag=2,表示該節點是DC點;

(4)flag=-1,表示經判定該節點一定不是組成k-IC的節點。

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

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

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

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

算法1ITIC描述

輸入:網絡圖G=(V,E),索引,參數k、r。

輸出:top-rk-IC。

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

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

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

4.Else

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

//標記flag,臨時集合b

6.For (每個B[m])

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

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

9.flag(v)=2;

//DC點標記flag=2

10.把B[m]中的所有節點移加到b中;

11.刪除B[m];

12.v加入b中,更新b中節點的桶度數并

將所有節點移到新桶B[n];

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

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

3.2.2k-IC判定處理

當桶B[n]中插入節點v后,若達到判定條件,需要對B[n]進行k-IC判定。本節主要介紹k-IC判定策略。

定理1DC點一定不是組成k-IC的節點,包含DC點的k-core一定不是k-IC。

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

證畢。

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

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

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

證畢。

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

根據定理1和定理2,如果節點v是DC點,只需對v進行插入操作即可,然后返回取下一個節點。

引理1當B[n]中有多于k個flag=0的節點滿足deg(u,Hn)≥k時,B[n]中可能存在k-IC。

定理3只有當v不是DC點同時滿足deg(v,Hn)≥k,并且B[n]滿足引理1時,可對B[n]進行k-IC判定。

證明:根據定理1和引理1易得證。

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

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

輸入:桶B[n],參數k。

輸出:包含v的k-IC。

1.Tm=?;R=?;

//臨時集合Tm,返回結果集R

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

3.求Tm中每個節點u的臨時度數degTm(u,HTm);

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

5.R←只由flag=0的節點組成的最大連通分量;

6.Else

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

8.If (Tm中degTm(u,HTm)≥k的節點個數>k)

9.R←只由flag=0的節點組成的最大連通分量;

10.Else return false;

11.If (R≠?)

12.為R中的每個節點設置flag=1;

13.將Tm中flag=0的節點設置標記flag=-1;

14.returnR;

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

例3仍以例1中的圖G為例,k=2、r=3。當節點v13插入桶B[4]時,B[4]滿足定理3,如圖5所示,對B[4]進行2-IC判定。將B[4]中滿足桶度數B-deg(

圖5 k-IC判定示例

u,Hn)≥2的節點v10、v11、v12、v13加入臨時集合Tm,并求它們在Tm中的臨時度數degTm(u,HTm),在此例中B-deg(u,Hn)=degTm(u,HTm),各節點均滿足≥2,因此{v10,v11,v12,v13}是一個2-IC。

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

4 實驗與結果分析

在本節中,使用C++語言實現了文中提出的ITIC。環境配置為Intel Xeon W-2104 3.19 GHz CPU,32 GB內存,Windows 10操作系統。

本節將ITIC與之前效果較好的NC算法[4]和LocalSearch算法[10]進行性能分析比較。本文使用了兩個真實網絡數據集Wiki和Arabic驗證算法性能。節點的權重為其PageRank值。表3總結了數據集的統計數據。在表3中,n和m分別表示網絡中節點和邊的數量,dmax和kmax分別表示網絡的最大度數和最大核數。

表3 實驗參數

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

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

圖7描述了Wiki和Arabic兩個數據集下,參數r對算法的影響。此處設置參數k=15不變,參數r的取值范圍為{5,10,20,50,100}。可以看出,兩個數據集都表現為整體處理時間ITIC優于NC算法和LocalSearch算法。其中當參數r不是特別大時,ITIC優勢明顯,因為ITIC為漸進輸出,只需要處理部分權重較大的節點就能求得top-r的結果,使得ITIC效率更高。

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

圖8所示為當r=15時算法在不同k下的內存占用大小比較,其中k的取值范圍為{5,10,15,20,25}。可以看出,對于Wiki和Arabic兩個網絡,ITIC消耗的內存比NC算法和LocalSearch算法都少,因為ITIC根據參數k進行了過濾,k越大,過濾掉的節點越多,并且ITIC不需要頻繁計算圖中的連通分量,使得ITIC消耗的內存更小。

(a) Wiki

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

5 結 語

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