羅碧彤 孫晶 李源 李欣蔚

（北方工業(yè)大學(xué)信息學(xué)院 北京市 100144）

1 引言

由于圖形數(shù)據(jù)在不同應(yīng)用中的普遍存在，圖形分析已經(jīng)引起了研究界和行業(yè)界的廣泛關(guān)注。圖分析中的一個主要問題是給定一個圖，識別圖中的內(nèi)聚子圖，如k核，k型桁架，派系，n-派系和n-族。其中，k核能在線性時間復(fù)雜度內(nèi)計算，被定義為無向圖G的極大子圖，使子圖中的所有頂點的度至少為k。社區(qū)搜索在社會網(wǎng)絡(luò)分析中具有重要意義，對于圖中給定頂點，目標(biāo)是找到該頂點所屬的最佳社區(qū)。直觀地說，對于給定頂點的最佳社區(qū)應(yīng)該在頂點附近。Cui等人提出了一種局部搜索策略，即在一個頂點附近進行搜索，以尋找該頂點的最佳社區(qū)。大多數(shù)現(xiàn)實生活中的復(fù)雜網(wǎng)絡(luò)，包括互聯(lián)網(wǎng)、社交網(wǎng)絡(luò)和生物神經(jīng)網(wǎng)絡(luò)，都包含了社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)可以被劃分為組，其中連接緊密，組與組之間的連接是稀疏的。在真實的網(wǎng)絡(luò)中尋找社區(qū)是一項重要的分析任務(wù)，因為社區(qū)結(jié)構(gòu)充滿意義，它們與網(wǎng)絡(luò)的功能高度相關(guān)。由于社區(qū)結(jié)構(gòu)的重要性，社區(qū)搜索的問題，即尋找頂點最可能的社區(qū)，對許多現(xiàn)實生活網(wǎng)絡(luò)和應(yīng)用十分重要。在信息時代，圖的規(guī)模變得巨大，圖模型所代表的數(shù)據(jù)中的價值也越來越重要。因此，在大規(guī)模圖中尋找核數(shù)最大的包含查詢點的極大連通子圖是一個重要且有意義的問題。在探索核數(shù)最大的包含查詢點的極大連通子圖的過程中，從查詢點開始向外擴展，其中判斷擴展的頂點是否具有提升當(dāng)前k核的能力是擴展階段的主要問題。在本文中，提出了Order算法即廣度優(yōu)先搜索，與遍歷頂點相連個數(shù)和與未遍歷頂點相連個數(shù)將需要擴展的頂點進行排序，通過Elevate-K算法即core上界和mcd上界判斷需要擴展的頂點是否具有提升當(dāng)前k核的能力，減少了尋找時間，提高了算法的效率。由于在探索最大k核子圖的過程中，圖是動態(tài)的，其中頂點/邊將隨著判斷是否具有提升當(dāng)前k核的能力被動態(tài)地插入/刪除。因此，降低圖不時動態(tài)更新時計算k核的計算成本是更新階段的主要問題。Lin等人提出了分層核心維護，但本文問題只需要核數(shù)最大即可。Zhang等人提出了一種新的基于順序的方法，在頂點的更新 圖之間保持順序，稱為k階。然而，現(xiàn)有的問題中提出了使用局部搜索策略尋找包含查詢點的k核，忽略了核數(shù)和規(guī)模最大的問題。針對上述問題，首先通過廣度優(yōu)先搜索和最大發(fā)生率，將需要探索的鄰接點進行排序。然后，基于核數(shù)core和最大核心度maximum-core degree（mcd），提出了通過core上界和mcd上界判斷頂點是否具有提升當(dāng)前核數(shù)的能力。對于規(guī)模最大的問題可以理解為什么時候停止搜索的問題，本文提出通過比較已經(jīng)遍歷頂點的鄰接點是否屬于被刪除的頂點這一特性來判斷是否圖規(guī)模達到最大值，是否可以停止搜索，若條件成立，則當(dāng)前社區(qū)是最好的，停止搜索。為了找到核數(shù)最大的包含查詢點的極大連通子圖：

（1）本文提出了一種全局搜索算法，通過與查詢點的度比較，逐步刪除度小于查詢點度的頂點，稱為Global Search-Max K Core(GS-MKC)。

（2）為了提高效率，進一步提出了一種具有擴展-精簡思想的局部搜索算法，稱為Local Search-Max K Core(LSMKC)。

2 基本概念及相關(guān)定義

本節(jié)主要介紹一些基本概念及其符號表達，闡述了k核的相關(guān)定義，并對要解決的主要問題給出具體定義。

2.1 基本概念

給定G(V,E)為頂點集合為V，邊集合為E的無向圖。對于任一子集H?V，由H誘導(dǎo)出的子圖定義為G[H]，其中頂點集合為H，邊集合為(H×H)∩E。deg(v)表示頂點v在圖G中的度，其中G[H]為圖G的子圖，因此deg(v)≤deg(v)。

定義 1（群體良度）：給定G(V,E)，其中集合H?V，由集合H誘導(dǎo)出的子圖G[H]為一個群體。G[H]的群體良度定義為圖的最小度：

δ(G[H])=min{deg(v)|v∈H}

其中δ(·)是不單調(diào)的，因此δ(G[H]∪{v})并不一定小于δ(G[H])。

定義 2（鄰接點）：使用nbr(u,G)表示頂點u∈V(G)的鄰接點，定義為：

nbr(u,G)={v∈V|(u,v)∈E}

定義 3（群體鄰接點）：給定圖G(V,E)，對于集合H?V，G[H]的群體鄰接點定義為集合H中的頂點與集合H外直接相連的頂點的集合：

nbr(G[H])={v|w∈H,v∈V,v?H,(w,v)∈E}

定義 4（k核）：圖G的子圖G表示為k核，定義為：（1）對于?u∈V(G)，deg(u,G)≥k;

G是最大的。若圖G的k核不存在，則G=?。對于一個給定的k，圖G的k核G是唯一的，并且?k≥0，G?G。當(dāng)k=0時，G就是圖G。

定義 5（核數(shù)）：對于每個頂點u∈V(G)，它的核數(shù)core(u,G)定義為：

core(u,G)=max{k|u∈V(G)}

定義 6（core(v,v)）：由核數(shù)定義可知，在圖G中加入點v之后，頂點v的核數(shù)可能保持不變，也可能增加，因此core(v,v)定義為在加入頂點v之前，頂點v的核數(shù)。

定義 7（最大核度maximum-core degree）：頂點u的最大核的度表示為mcd(u)，給定w為頂點u的鄰接點，mcd(u)定義為具有core(w)≥core(u)性質(zhì)的鄰接點的個數(shù)：

mcd(u)=|{w:(u,w)∈E,core(w)≥core(u)}|

定義 8（純核度pure-core degree）：頂點u的純核度表示為pcd(u)，給定w為頂點u的鄰接點,pcd(u)定義為具有core(w)=core(u)并且mcd(w)>core(w)性質(zhì)或者core(w)>core(u)的鄰接點的個數(shù)：

pcd(u)=|{w:(u,w)∈E,core(w)=core(u)∩mcd(w)>core(w) or core(w)>core(u)}|

定義 9（集合定義）：在加入或刪除一個節(jié)點之后，圖中各個頂點的核數(shù)有可能發(fā)生改變，有的頂點核數(shù)增加，有的頂點會確定不在所求圖中。因此，定義集合H包含已經(jīng)遍歷過的頂點，集合N包含需要遍歷的頂點，集合C包含確定不在所求圖中的頂點，集合F記錄最終所求圖的頂點。集合H的初始頂點為查詢頂點v。N=?,C=?,F=?.對于還未遍歷過的頂點核數(shù)設(shè)為無窮大。

2.2 問題定義

基于以上定義，本文給出了在大規(guī)模圖中發(fā)現(xiàn)核數(shù)最大的包含查詢點的極大連通子圖的問題定義。

問題：對于一個圖G(V,E)和一個任意頂點v∈V，發(fā)現(xiàn)集合H?V，其中H具有如下性質(zhì)：

（1）v∈H；

（2）G[H]是一個連接子圖；

（3）δ(G[H])是最大的；

（4）G[H]的頂點數(shù)量最多。

接下來的章節(jié)，本文具體的闡述Max K Core(MKC)的發(fā)現(xiàn)算法。

3 MKC發(fā)現(xiàn)算法

本節(jié)講述大規(guī)模圖中核數(shù)最大的包含查詢點的極大連通子圖發(fā)現(xiàn)問題，給定查詢點v，從中發(fā)現(xiàn)包含查詢點v的最大k核。本節(jié)將從兩方面出發(fā)研究探索這一問題，即全局搜索和局部搜索。全局搜索將查詢圖中每個節(jié)點的度，局部搜索從查詢點v開始逐層向外擴展，添加具有提升當(dāng)前k核能力的頂點，淘汰當(dāng)前不具有提升k核能力的頂點。接下來詳細的介紹兩種發(fā)現(xiàn)算法。

3.1 GS-MKC算法

本小節(jié)的GS-MKC算法，是基于從大規(guī)模圖逐步搜索核數(shù)最大的包含查詢點的極大連通子圖的基礎(chǔ)策略，該算法需要遍歷圖中的所有頂點。

算法1.GS-MKC（G,v）

首先計算查詢頂點v的度，逐個將圖中度小于deg(v)的頂點刪除，并將其鄰接點保存在集合中，因為在刪除度小于deg(v)的頂點時，其鄰接點的度也會受到影響而變化，下一步便檢查集合中即鄰接點的度是否在刪除頂點之后度小于deg(v)，若鄰接點為查詢點v的鄰接點則不刪除，因為若刪除查詢點的鄰接點，查詢點的度會變小，如此一直檢查，直到?jīng)]有頂點可刪，得到包含查詢頂點v的圖即為核數(shù)最大的包含查詢點的極大連通子圖。

輸入：圖G(V,E);查詢頂點v；

輸出：核數(shù)最大的包含查詢頂點v的極大連通子圖；

（1）計算查詢頂點v的度；

（2）WHILE deg(v)

（3）刪除頂點v；

（4）判斷頂點v的鄰接點是否小于deg(v)；

（5）得到包含查詢點的最大k核子圖。

3.2 LS-MKC算法

本節(jié)對上一小節(jié)的算法進行改進，上一節(jié)算法雖然簡單，但代價非常昂貴，因為圖中的所有頂點都需要訪問，在此基礎(chǔ)上提出一種優(yōu)化策略下的LS-MKC算法,從查詢點出發(fā)，對需要遍歷的頂點使用Order算法排序，減少發(fā)現(xiàn)時間，提高算法效率，在每次插入頂點之后使用Elevate-K算法將不能幫助提升當(dāng)前核數(shù)的頂點刪除，其中，插入/刪除頂點之后保持k核采用現(xiàn)有算法提出的k階，將每個k核保存在k階之中，頂點在k階之間變化。

算法 2.LS-MKC(G,v)

從查詢點出發(fā)，將其鄰接點按照優(yōu)先級排序插入圖G’中，插入之后重新將頂點分組，再將需要遍歷的頂點插入圖中，直到已遍歷的頂點集合的群體鄰接點小于查詢點v的核數(shù)且都處于刪除集合中，表示群體鄰接點已經(jīng)沒有頂點可以遍歷，則搜索結(jié)束，得到核數(shù)最大的包含查詢點的極大連通子圖。

輸入：圖G(V,E);查詢頂點v；

輸出：核數(shù)最大的包含查詢頂點v的極大連通子圖；

（1）WHILE F=? do；

（2）從集合N中取出下一個遍歷的頂點；

（3）在G'中插入與H集合中頂點有關(guān)的邊；

（4）FOR 集合H中的頂點w IF mcd(w)

（5）將頂點輸入H集合；

（6）將頂點輸出N集合；

（7）N?Order(G,N,v)；

（8）判斷頂點v是否有提升當(dāng)前k核的能力，若無則刪除；

（9）判斷當(dāng)前已經(jīng)遍歷過的頂點是否構(gòu)成核數(shù)最大的包含查詢頂點v的極大連通子圖；

（10）返回 G'。

算法 3. Order(G,N,v)

排序算法是對需要遍歷的頂點集合進行排序，使頂點按照一定的優(yōu)先級先后插入圖G’中。首先使用廣度優(yōu)先搜索排序，在廣度優(yōu)先搜索的基礎(chǔ)上使用功能函數(shù)對頂點進行排序，即按照在將該頂點插入圖G’之后，頂點的度從大到小排序，表示與圖G’連接最緊密的頂點先遍歷，最后按照頂點的未擴展節(jié)點個數(shù)從大到小進行排序，表示與外界連接最緊密的頂點先遍歷，因為這樣的頂點提升當(dāng)前k核和擴大圖規(guī)模的能力更強，由此得到插入順序。

輸入：圖G(V,E)；需要遍歷的頂點集合N；插入的頂點v；輸出：有順序的頂點集合N；

（1）廣度優(yōu)先搜索得到需要遍歷的頂點，得到集合S；

（2）計算集合S中的f值；

（3）計算集合S中的deg值；

（4）對于集合S的頂點排序；

（5）N?N+S；

（6）返回N。

算法 4.Elevate-K(G,v,core(v,v0))

Elevate-K算法通過core值上界和mcd上界，判斷頂點是否具有提升k核的能力。core值上界表示為當(dāng)前頂點的核數(shù)加上頂點未擴展的鄰接點，當(dāng)前頂點的核數(shù)表示現(xiàn)在已經(jīng)確定的核數(shù)，未擴展的鄰接點表示該頂點提升當(dāng)前核數(shù)的可能性，頂點與外界的緊密程度。mcd上界表示當(dāng)前頂點的鄰接點中核數(shù)大于等于該頂點的數(shù)量，同樣表示該頂點提升當(dāng)前核數(shù)的可能性。若core值上界或mcd上界小于查詢點的核數(shù)，則表示該頂點不能為提升當(dāng)前核數(shù)提供幫助，應(yīng)該刪除。

輸入：圖G(V,E)；插入頂點v；插入頂點v之前v的核數(shù)core(v,v)；

輸出：頂點v是否具有提升查詢點核數(shù)的能力；

4 實驗結(jié)果與分析

為了有效的評估提出的算法，本實驗用真實的數(shù)據(jù)集進行評估，數(shù)據(jù)集的詳細統(tǒng)計信息匯總在表1中，其中|V|表示頂點個數(shù)、|E|表示時序邊數(shù)。

表1：統(tǒng)計數(shù)據(jù)集

4.1 算法高效性分析

本節(jié)分析LS-MKC算法和GS-MKC算法的高效性。

由于不同的圖規(guī)模對算法的高效性有影響，本節(jié)將進行不同規(guī)模圖下算法性能的對比試驗，選用遍歷頂點個數(shù)和運行時間兩個指標(biāo)對算法的高效性進行評價，兩個指標(biāo)的具體概念如下：

（1）遍歷頂點個數(shù)：在算法運行過程中遍歷過的頂點；

（2）運行時間：本文提出的兩個算法的運行時間。

從圖1可以看出，通過調(diào)整圖的規(guī)模可以改變發(fā)現(xiàn)包含查詢點的最大核子圖訪問節(jié)點的數(shù)量。對于GS-MKC算法，由于需要圖中全部頂點與查詢點的度相比較，因此，GS-MKC算法訪問的節(jié)點數(shù)量為整張圖的節(jié)點數(shù)量，而對于LS-MKC算法，只需要從查詢點開始遍歷部分頂點，通過上界判斷頂點是否需要刪除，是否需要停止遍歷搜索。從圖1中可以看出，LS-MKC算法查找包含查詢點的最大核子圖訪問節(jié)點的數(shù)量遠小于GS-MKC算法。從圖2可以看出，通過調(diào)整圖的規(guī)模，查找包含查詢點的最大核子圖的算法運行時間也隨之變化，從圖中可以看出，對于規(guī)模較小的圖LSMKC算法的運行時間比GS-MKC算法長。這是因為，對于規(guī)模較小的圖，GS-MKC算法可以以較短的時間遍歷整張圖，并且算法只需要計算每個頂點的度即可，而LS-MKC算法會從查詢點開始，通過計算mcd,pcd,核數(shù),鄰接點來判斷是否插入/刪除頂點和是否停止搜索，由此發(fā)現(xiàn)最大核子圖，因此運行時間長于GS-MKC算法。但是，當(dāng)圖規(guī)模較大時，GS-MKC算法會因為需要遍歷整張圖使得運行時間變長，而LS-MKC算法只需要遍歷部分頂點，雖然同樣需要計算中間值，但是對比GS-MKC算法，運行時間更小。

圖1：不同規(guī)模下算法發(fā)現(xiàn)遍歷頂點數(shù)量

圖2：不同規(guī)模下算法運行時間

4.2 算法有效性分析

本節(jié)使用包含查詢點的極大連通子圖的核數(shù)來測試我們提出的算法發(fā)現(xiàn)MKC子圖的有效性。

圖3給出了通過改變圖的規(guī)模，對于某個查詢點使用LS-MKC算法和GS-MKC算法發(fā)現(xiàn)的包含查詢點的極大連通子圖的核數(shù)。從實驗結(jié)果可以清楚地看出，對于同一規(guī)模圖的同一查詢點，使用LS-MKC算法和GS-MKC算法，得到的極大連通子圖的核數(shù)相同，可以得出LS-MKC算法和GS-MKC算法的有效性?？傊?，從總的實驗結(jié)果可以看出，LS-MKC算法優(yōu)于GS-MKC算法。

圖3：不同規(guī)模下算法發(fā)現(xiàn)極大連通子圖的核數(shù)

5 結(jié)束語

本文旨在發(fā)現(xiàn)在大規(guī)模圖中核數(shù)最大的包含查詢頂點的極大連通子圖。提出了基于全局搜索的GS-MKC算法，該算法需要遍歷圖中的所有頂點，雖然思想簡單，但是代價昂貴。因此為了更早地發(fā)現(xiàn)核數(shù)最大的包含查詢頂點的極大連通子圖，本文結(jié)合頂點的核數(shù)core和最大核心度mcd判斷頂點是否具備提升當(dāng)前核數(shù)的能力，決定頂點是否被刪除以及是否需要停止搜索，提出了基于局部搜索的LS-MKC算法。最后，本文在三個大型真實數(shù)據(jù)集上進行了大量的實驗，以證明提出的算法的高效性和有效性。