局部最大核子圖搜索算法研究

羅碧彤 孫晶 李源 李欣蔚

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

1 引言

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

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

（2）為了提高效率，進(jìn)一步提出了一種具有擴(kuò)展-精簡(jiǎn)思想的局部搜索算法，稱為L(zhǎng)ocal Search-Max K Core(LSMKC)。

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

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

2.1 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 問(wèn)題定義

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

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

（1）v∈H；

（2）G[H]是一個(gè)連接子圖；

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

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

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

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

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

3.1 GS-MKC算法

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

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

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

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

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

（1）計(jì)算查詢頂點(diǎn)v的度；

（2）WHILE deg(v)

（3）刪除頂點(diǎn)v；

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

（5）得到包含查詢點(diǎn)的最大k核子圖。

3.2 LS-MKC算法

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

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

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

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

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

（1）WHILE F=? do；

（2）從集合N中取出下一個(gè)遍歷的頂點(diǎn)；

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

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

（5）將頂點(diǎn)輸入H集合；

（6）將頂點(diǎn)輸出N集合；

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

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

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

（10）返回 G'。

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

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

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

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

（2）計(jì)算集合S中的f值；

（3）計(jì)算集合S中的deg值；

（4）對(duì)于集合S的頂點(diǎn)排序；

（5）N?N+S；

（6）返回N。

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

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

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

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

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

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

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

4.1 算法高效性分析

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

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

（1）遍歷頂點(diǎn)個(gè)數(shù)：在算法運(yùn)行過(guò)程中遍歷過(guò)的頂點(diǎn)；

（2）運(yùn)行時(shí)間：本文提出的兩個(gè)算法的運(yùn)行時(shí)間。

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

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

圖2：不同規(guī)模下算法運(yùn)行時(shí)間

4.2 算法有效性分析

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

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

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

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

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