子圖匹配中基于啟發(fā)式策略的圖分割算法

繆楊帆

（四川大學計算機學院，成都610065）

0 引言

現(xiàn)實世界中的網(wǎng)絡多為無標度網(wǎng)絡[1]，即在網(wǎng)絡數(shù)據(jù)中，少量的節(jié)點存在大量的鄰居節(jié)點，大量的節(jié)點僅有少量的鄰居節(jié)點，也就是說節(jié)點的度分布[2]符合冪率特性[3]。如科研合作者網(wǎng)絡便是較為典型的無標度網(wǎng)絡，少量的作者會有大量的與之相關聯(lián)的其他作者，而大部分作者僅有少數(shù)的幾個合作者。又如微博關注關系所形成的網(wǎng)絡，少數(shù)人擁有大量的粉絲，如明星、企業(yè)家，等等，而作為普通人基本上只有少量的關注者。正是現(xiàn)實生活中的這種現(xiàn)象形成了符合冪率特性的網(wǎng)絡，也就形成了團或者社區(qū)[4]。

現(xiàn)實生活中大多數(shù)人的活動范圍都有一定的限定，這種限定并非人為創(chuàng)造的，而是自然而然形成的。正是基于這種現(xiàn)象，本文假定用戶在網(wǎng)絡數(shù)據(jù)圖中所做的查詢基本上會在社區(qū)范圍內(nèi)。也就是說，將網(wǎng)絡抽象為圖結構，用戶所查詢的子圖大多數(shù)時候會在某些特定的區(qū)域范圍內(nèi)。

一個社區(qū)一般都會存在一個或者多個度較大的節(jié)點。本文提出的基于啟發(fā)式策略的圖分割[5]算法正是基于此，通過從一個度較大的節(jié)點開始，基于節(jié)點之間的相似性度量，不斷地試圖去激活鄰居節(jié)點，然后再由鄰居節(jié)點去激活其自身的鄰居節(jié)點，直到完成分區(qū)。后續(xù)的子圖匹配[6]操作將在各個分區(qū)之內(nèi)同時進行，可以極大的提高子圖匹配的效率。

1 節(jié)點相似性度量

1.1 節(jié)點相似性

定義1.1（結構性等價）對于一個給定的網(wǎng)絡圖G=(V ，E )，對于任意的 vk∈V ，滿足 vi≠vk且 vj≠vk，如果e(vi，vk)∈E ，當且僅當 e(vj，vk)∈E ，則稱 vi與 vj是結構性等價的。

圖1 結構性等價

如圖1所示，節(jié)點1和節(jié)點3是結構性等價的，因為節(jié)點1和節(jié)點2、節(jié)點4相鄰，而節(jié)點3同樣和節(jié)點2、節(jié)點4相鄰，因此稱節(jié)點1和節(jié)點3為結構性等價。同樣，在圖1中節(jié)點5和節(jié)點6也是結構性等價的。

然而在現(xiàn)實世界的應用中，因為結構性等價太多嚴格，因此一些相對松散的等價定義被提出，如自同構等價和規(guī)則性等價[7]等，不過由于這些定義沒有相應的擴展方法，因此本文采用了一些簡化的相似性度量方法。

1.2 節(jié)點相似性度量

節(jié)點相似性度量方法主要包括Jaccard[8]相似性度量和Cosine[9]相似性度量方法。

對于給定的網(wǎng)絡圖，對于圖中的節(jié)點vi和vj，其相似性定義如下：

（1）Jaccard定義

在上面兩個等式中，其中Ni表示節(jié)點vi的鄰域，Nj表示節(jié)點vj的鄰域，|*|表示元素的個數(shù)。其相似性度量值在0-1之間。

但是，根據(jù)如上定義，存在兩個相鄰節(jié)點之間相似性為0的情況。例如在圖1中，N7={8 ，9，5，6} ，N9={7}，而N7∩N9=?，雖然從結構性等價角度講合理，但是兩個節(jié)點相連接，相似性的可能同樣存在。一般的修正方法是在計算Nv時，將節(jié)點v算在內(nèi)，即N7={7 ，8，9，5，6} ，N9={7 ，9} 。

然而，以上兩種標準的基于相似性度量的方法需要計算每一對節(jié)點之間的相似性，故其時間復雜度為O(n2)。當n較大時，計算相似性的時間將急劇增大，故不適合較大的數(shù)據(jù)圖。因此本文并未采用上述定義，而是重新定義了度量標準。

給定網(wǎng)絡圖結構，假設節(jié)點vi和節(jié)點vj為網(wǎng)絡圖中的兩個節(jié)點，且節(jié)點vi和節(jié)點vj直接相連，假設已知節(jié)點vi屬于分區(qū)Ⅱ，那么節(jié)點vj屬于分區(qū)Ⅱ的概率，也即節(jié)點vi能夠激活節(jié)點vj的概率為：

其中，其中Nij表示節(jié)點vi與節(jié)點vj共同鄰居，之所以加1，主要考慮到節(jié)點vi和節(jié)點vj直接相連的情況，dj表示節(jié)點vj自身的度。

依舊以圖1為例進行說明。N54={4} ，d4=4 ，假設節(jié)點5屬于分區(qū)Ⅱ，那么節(jié)點4同樣屬于分區(qū)Ⅱ的概率，也即節(jié)點5激活節(jié)點4的概率為：

2 圖分割

分割圖時有兩種方法，一種是將分區(qū)之間的邊切割掉，另一種是將分區(qū)之間的邊保留下來。由于在大規(guī)模的子圖匹配過程中需要考慮到內(nèi)存及時間效率的問題，因此本文采用的HSGSA算法是將邊直接切割。分割過程如圖2所示。

圖2 HSGSA分割過程

假定用戶設定的閾值p=0.5，開始時選定的度最大的節(jié)點為4，周圍鄰居節(jié)點集合N4={3 ，5，7，8} ，以節(jié)點5為例，節(jié)點4和節(jié)點5的共同鄰居節(jié)點集合為N45={7} ，d5=3，根據(jù)公式（1）計算得出 p(4 ，5) ≥0.5 ，故節(jié)點5被激活，與節(jié)點4屬于相同的分區(qū)，以同樣的方式計算其他節(jié)點，可知如圖步驟②所示，節(jié)點5，7，8可被激活，而節(jié)點3無法被激活，接著從激活的節(jié)點開始繼續(xù)相同的過程，激活節(jié)點6。接著找度最大的節(jié)點，假定找到節(jié)點3，如圖步驟③所示，然后以上述同樣的方式激活節(jié)點1，2，如圖步驟④所示，并最終形成兩個分區(qū)。

算法過程如下：

算法1：基于啟發(fā)式策略的圖分割算法

輸入：數(shù)據(jù)圖G=（V，E），激活的閾值p

輸出：分割后的數(shù)據(jù)圖

算法：

獲取數(shù)據(jù)圖G中度最大的頂點v_max;

將頂點v_max加入隊列Q，將頂點v_max加入分區(qū)n;

While隊列Q非空then

移出Q隊首元素v;

獲取頂點v的鄰居頂點N_v;

For n_v in N_v

If頂點n_v所屬分區(qū)為空then

If（（|N_nv|+1）/d_v）>=p then

將頂點n_v加入隊列Q，同時將其

加入分區(qū)n;

End if

Else

將頂點n_v和v邊加入新分區(qū)，修改頂

點度;

End if

刪除邊，修改頂點v和n_v的度;

End for

End While

首先從網(wǎng)絡數(shù)據(jù)圖中找到度最大的節(jié)點v，將其加入到分區(qū)中。然后遍歷這個節(jié)點的每一個鄰居節(jié)點，首先判斷該節(jié)點是否已經(jīng)被劃分到某一個分區(qū)內(nèi)，如果沒有，那么接著判斷該鄰居頂點能否被v激活，即根據(jù)公式判斷其概率是否大于用戶給定的值p，大于的話將該鄰居節(jié)點加入節(jié)點v所屬的團內(nèi)，刪除邊，同時修改相關節(jié)點的度，如果鄰居節(jié)點已經(jīng)被劃分到某一個團內(nèi)，則將邊加入社區(qū)，然后刪除邊，修改相關節(jié)點的度，如果概率小于用戶給定的p值，則直接刪除邊即可，如此循環(huán)直到遍歷完所有的鄰居節(jié)點，形成一個分區(qū)。若要形成多個分區(qū)重復上述步驟即可。

3.1 實驗數(shù)據(jù)

實驗數(shù)據(jù)主要來自科研合作者網(wǎng)絡數(shù)據(jù)（DBLP）。因本文提出的算法的適用條件為符合冪率分布的網(wǎng)絡數(shù)據(jù)圖，故首先從DBLP數(shù)據(jù)集中抽取出五個數(shù)據(jù)圖，如表 1 所示，在對 G1，G2，G3，G4，G5 的度分布進行驗證之后確定所抽取的數(shù)據(jù)圖其度分布均符合冪率特性。

3.2 實驗分析

3 實驗及結果分析

首先在DBLP數(shù)據(jù)集中取G1數(shù)據(jù)圖，將其分成兩個分區(qū)。圖3是隨著p值變化，分割出來的分區(qū)占原來數(shù)據(jù)圖的比例，以及HSGSA算法中邊的丟失率。從圖3中可以看出，當p的取值逐漸增大時，新形成的分區(qū)規(guī)模逐漸減小，而邊的丟失率也在減少。但是，當p值較大時會形成大量的小分區(qū)，而這對圖匹配有重大的影響，既不能形成大量的小分區(qū)，又不能造成大量的邊丟失。故p的取值既不能太大也不能太小。如果要形成多個分區(qū)p的值應當設置的偏大，而本文提出的分割算法旨在能夠快速分割，又能自由控制分區(qū)的個數(shù)，因此p的值設置在0.2-0.4之間比較好。

表1 數(shù)據(jù)圖

圖3 數(shù)據(jù)圖G1中p值變化帶來的影響

在以下實驗過程中設定p的值均為0.3，分成兩個分區(qū)。從算法的描述部分可知，本文設計的基于啟發(fā)式策略的圖分割算法對切割的邊不作保存，雖然會造成一些邊的缺失，但是所需要的內(nèi)存空間就相對較小，在大規(guī)模的圖處理過程中可以減少設備的內(nèi)存消耗。與此同時，分割的時間也會隨著數(shù)據(jù)圖規(guī)模的增加而呈現(xiàn)線性增長，分割時間也隨分區(qū)個數(shù)的增加而逐漸增加，如圖4所示。

圖4中的④是將數(shù)據(jù)圖分割成兩個分區(qū)后，結果匹配的展示，藍色表示的為隨機生成的23個查詢子圖，紅色表示的為HSGSA算法形成的兩個分區(qū)匹配出的結果數(shù)，從結果中可以看出雖然匹配效果并沒有完全正確，但實驗中的查詢子圖是通過隨機算法生成的，而本文設計的算法則是在假定用戶查詢不是隨機的，而是在分區(qū)范圍內(nèi)的，故在符合假設的條件下準確率會提高。這也說明了本文提出的先將大規(guī)模數(shù)據(jù)圖分割成幾個部分，同時進行匹配的合理性。

圖4 實驗結果

4 結語

基于現(xiàn)實網(wǎng)絡基本上符合冪律分布的特性，在假定用戶的大多查詢模式處于社區(qū)范圍內(nèi)的情況下，本文提出了基于啟發(fā)式策略的圖分割算法，一方面確保能夠對大規(guī)模數(shù)據(jù)圖按指定的分區(qū)數(shù)進行分割，同時又能夠使其分割時間隨數(shù)據(jù)圖的規(guī)模成線性增長。而且從實驗結果中可以發(fā)現(xiàn)，在對圖進行分割時去掉分區(qū)之間的邊依然能夠取得較好的匹配效果，而對于內(nèi)存空間和時間的消耗卻不多。