基于鄰居向量的近似子圖匹配

陳 東，王 波，席耀一，唐浩浩

（信息工程大學 信息系統(tǒng)工程學院，河南 鄭州450001）

0 引 言

作為圖數(shù)據(jù)挖掘［1－4］的一個重要研究內(nèi)容，近似子圖匹配在很多領(lǐng)域都有應用，如蛋白質(zhì)交互網(wǎng)絡查詢［5］、犯罪團伙檢測［6］、專家推薦系統(tǒng)等。對于大型網(wǎng)絡的近似子圖匹配有多種相似性度量標準。TALE 算法［7］以邊丟失為度量標準，通過構(gòu)建混合索引結(jié)構(gòu)降低候選節(jié)點的規(guī)模，提高查詢速度，但準確性不高。SA－Index算法［8］要求節(jié)點和邊存在對應關(guān)系，該算法基于結(jié)構(gòu)與節(jié)點標簽對數(shù)據(jù)圖進行劃分，縮小了路徑搜索的空間，再將邊／路徑構(gòu)成圖，運算效率比TALE算法有所提高。也有學者針對一些應用對結(jié)構(gòu)相似性要求低的特點 （如知識網(wǎng)絡的語義相似查詢）提出了新的相似度度量標準，并采用新方法提高運算效率。Ness算法［9］通過查詢圖和數(shù)據(jù)圖相應節(jié)點k－近鄰的標簽相似對候選節(jié)點進行過濾，再驗證過濾后的節(jié)點。NeMa算法［10］考慮節(jié)點的鄰近度，引入鄰居向量的概念，提出了子圖匹配代價度量圖匹配的相似性，采用一種啟發(fā)式推理算法進行子圖匹配，比Ness算法有更高的節(jié)點準確率和召回率。Ness和NeMa算法得到查詢節(jié)點和匹配節(jié)點的對應關(guān)系，以節(jié)點準確率和召回率作為度量標準，但由于沒有充分利用結(jié)構(gòu)信息，忽略了查詢邊和匹配邊的對應關(guān)系。

本文研究以下問題：給定一個大型數(shù)據(jù)圖和一個查詢圖，在數(shù)據(jù)圖中找到和查詢圖相似的子圖。針對NeMa算法運算效率高但沒有考慮邊對應關(guān)系的問題，進行以下改進：①根據(jù)查詢節(jié)點在查詢圖中的重要程度給查詢節(jié)點賦予權(quán)重，并改進匹配代價和迭代推理算法；②通過節(jié)點過濾降低候選節(jié)點的數(shù)量；③改進NeMa算法在節(jié)點匹配優(yōu)化階段起始節(jié)點的選擇；④通過邊匹配得到邊的對應關(guān)系。

基于以上4點改進，本文提出近似子圖匹配算法IMNeMa（important node network match），該 算 法 不 僅 得 到節(jié)點對應關(guān)系，還得到邊對應關(guān)系。算法首先對查詢節(jié)點的匹配節(jié)點進行過濾得到候選節(jié)點，然后改進匹配代價和迭代推理得到匹配節(jié)點集合，最后通過邊匹配得到匹配圖。

1 預備知識

標簽圖：標簽圖是一個節(jié)點有標簽標注的網(wǎng)絡圖，表示為G＝ （V，E，L，f），其中，V 表示圖的節(jié)點集合，E表示圖的邊集合，L 表示節(jié)點的標簽集合，f 是標簽分配函數(shù)V→L，表示節(jié)點到標簽的映射，f（u）∈L表示節(jié)點u∈V的標簽（如社會網(wǎng)絡的標簽可以是人的職業(yè)、興趣等）。

問題描述：給定數(shù)據(jù)圖G＝ （VG，EG，LG，fG），查詢圖Q＝ （VQ，EQ，LQ，fQ），要求找到數(shù)據(jù)圖中滿足式（1）的子圖GT

真實網(wǎng)絡由于結(jié)構(gòu)復雜，并且存在噪聲和數(shù)據(jù)丟失，拓撲結(jié)構(gòu)完全相同的子圖有時并不存在，因此需要進行近似子圖匹配。圖的近似匹配有很多種度量標準，其中，p同態(tài)［11］是由Fan等在圖同態(tài)定義基礎(chǔ)上的改進，允許節(jié)點標簽相似以及邊和路徑的對應，更加適合真實網(wǎng)絡。本文圖的相似定義simg（Q，G′）與p 同態(tài)類似，若存在VQ到V′的一個映射關(guān)系g：VQ→V′，且滿足如下2個條件，則認為Q 和G′相似：

其中，g（u）和g（v）表示u 和v 在G′中的對應節(jié)點，p（g（u），g（v））＝｛（g（u），u1），...，（ui，g（v））｝表示g（u）到g（v）的最短路徑。

當對于Q 的每一條邊，G′都有一條邊對應時，simg（Q，G′）＝1。

2 IMNeMa算法

本文將近似子圖匹配分為節(jié)點過濾、節(jié)點匹配和邊匹配3個主要階段。首先通過節(jié)點過濾得到候選節(jié)點集合，其次利用節(jié)點匹配得到匹配節(jié)點的位置，最后在包含匹配節(jié)點的擴展圖中進行邊匹配。

2.1 節(jié)點過濾

僅通過節(jié)點標簽相等得到查詢節(jié)點的候選節(jié)點集合，會造成集合中有大量錯誤匹配的候選節(jié)點，導致節(jié)點匹配階段的運算量增大，因此需要通過節(jié)點過濾對候選節(jié)點集合進行刪減。如果一個匹配圖和查詢圖同構(gòu)，那么對應節(jié)點度則相同，但在本文近似匹配的定義下，由于允許若干個等價查詢節(jié)點 （標簽相同，在查詢圖中的位置也相同）對應一個匹配節(jié)點，一些 “好”候選節(jié)點的度也會小于對應的查詢節(jié)點度，因此通過匹配節(jié)點度大于等于查詢節(jié)點度進行節(jié)點過濾會過濾掉一些 “好”候選節(jié)點。為了解決這個問題，本文引入節(jié)點鄰接標簽度。

定義1 節(jié)點鄰接標簽度：節(jié)點鄰接標簽度是指節(jié)點的鄰接節(jié)點集合中的不同標簽的數(shù)量。LN（v）表示節(jié)點鄰接節(jié)點的標簽集合，那么表示節(jié)點鄰接標簽度。使用節(jié)點鄰接標簽度，將節(jié)點度的比較轉(zhuǎn)化為鄰接節(jié)點集合標簽種類的比較。

如果查詢圖和匹配圖相似度為1，則匹配圖中每個節(jié)點的鄰接標簽度和相應查詢節(jié)點的鄰接標簽度相同，而匹配圖又是數(shù)據(jù)圖的子圖，因此數(shù)據(jù)圖中 “好”候選節(jié)點的節(jié)點標簽度要大于對應查詢節(jié)點的節(jié)點標簽度。考慮到復雜網(wǎng)絡的無標度分布特性［12］，數(shù)據(jù)圖中會有大量節(jié)點度很小的節(jié)點，其節(jié)點鄰接標簽度也很小，采用節(jié)點鄰接標簽度進行過濾，可以將候選節(jié)點集合精簡，盡可能的保留 “好”候選節(jié)點，減少了節(jié)點匹配不必要的計算。

給定數(shù)據(jù)圖G 和查詢圖Q，對G 中節(jié)點進行規(guī)則過濾，得到每個查詢節(jié)點的候選節(jié)點集合M（v）。過濾規(guī)則如下

式 （3）表示u和v 標簽相同。式 （4）表示u的節(jié)點鄰接標簽度大于v 的節(jié)點鄰接標簽度。通過節(jié)點過濾，得到查詢節(jié)點的候選節(jié)點集合M（v）。

2.2 節(jié)點匹配

節(jié)點匹配的目的是得到匹配節(jié)點在數(shù)據(jù)圖中的位置。NeMa算法能得到節(jié)點的對應關(guān)系，但在數(shù)據(jù)圖標簽稀疏情況下運算時間長、準確率低 （將在實驗部分說明）。真實網(wǎng)絡環(huán)境復雜，有的網(wǎng)絡標簽密度較為稀疏，并且很多應用要求保持匹配節(jié)點的連接關(guān)系［11］，這就造成NeMa算法難以直接應用到節(jié)點匹配。

節(jié)點匹配階段基于NeMa算法進行以下改進：①根據(jù)查詢節(jié)點在查詢圖中的重要程度給查詢節(jié)點賦予權(quán)重，并改進匹配代價和迭代推理算法；②改進NeMa算法在節(jié)點匹配優(yōu)化過程起始節(jié)點的選擇。通過以上兩點改進，提高了節(jié)點匹配的匹配效果和運算效率。

NeMa算法將節(jié)點的h－鄰居節(jié)點向量化，定義了匹配代價，通過匹配代價得到匹配節(jié)點，但是NeMa算法不重視結(jié)構(gòu)在匹配中的作用，無法得到準確的匹配節(jié)點。本文改進并重新定義了匹配代價，改進后的匹配代價能返回更準確的匹配節(jié)點。首先介紹節(jié)點匹配階段用到的定義。

定義2 h－鄰居節(jié)點集合：h－鄰居節(jié)點集合N（v）表示圖中所有與v的距離 （即最短路徑長度）小于或等于h 的節(jié)點構(gòu)成的集合。

定義3 鄰居向量：節(jié)點u 的鄰居向量RG（）u ＝｛＜u′，PG（u ，u′）＞ ｝，其 中，u′ 是u 的h－鄰 居 節(jié) 點，PGu，（ ）u′ 表示u′到u 的鄰近度

式中：d（u，u′）——u′到u的距離（即最短路徑長度），傳播因子0＜α＜1，h＞0表示向量化節(jié)點u的半徑（范圍），由于2個實體間的關(guān)系隨著距離的增加迅速下降，h的取值通常很小，本文取h＝2［10］。接下來利用鄰居向量計算匹配代價。

定義4 單節(jié)點匹配代價：給定一個節(jié)點匹配函數(shù)，查詢節(jié)點v和匹配節(jié)點u＝（v）的單節(jié)點匹配代價F（v，u）為

定義5 節(jié)點權(quán)重：引入節(jié)點權(quán)重w（v）表示節(jié)點在圖中的重要性。本文用節(jié)點度衡量。即節(jié)點的度越大，該節(jié)點越重要。節(jié)點權(quán)重也可以采用其他算法度量，如節(jié)點度、特征向量中心度等。

定義6 全節(jié)點匹配代價：給定一個節(jié)點匹配函數(shù)表示查詢節(jié)點v∈VQ到匹配節(jié)點u∈VG的映射，則全節(jié)點匹配代價定義為

式中：w（v）——節(jié)點權(quán)重，0≤C（）≤1。本文通過使用節(jié)點權(quán)重對單節(jié)點匹配代價加權(quán)，使節(jié)點匹配代價更能反映查詢圖的結(jié)構(gòu)特性。由于在查詢圖中，不同的節(jié)點具有不同的重要性，而重要節(jié)點對圖匹配具有重要意義，即全節(jié)點匹配代價對重要性不同的節(jié)點的匹配代價敏感程度不同，式 （7）中加入了節(jié)點權(quán)重，使全節(jié)點匹配代價對重要節(jié)點的匹配代價更加敏感。這里認為全節(jié)點匹配代價越小，得到的匹配圖與查詢圖越相似。如果匹配圖和查詢圖同構(gòu)，則全節(jié)點匹配代價為0，反之不一定成立。全節(jié)點匹配代價是節(jié)點匹配的度量標準。

2.2.1 IMNeMaInfer算法

NeMaInfer算法 （NeMa算法的子算法）是一種基于圖模型最大和推理問題的啟發(fā)式迭代推理算法，目的是得到查詢節(jié)點的匹配節(jié)點集合，使子圖匹配代價最小。IMNeMaInfer算法對NeMaInfer算法進行改進，在迭代推理時加入節(jié)點權(quán)重提高收斂速度，并在節(jié)點匹配優(yōu)化時選擇鄰接標簽度大的節(jié)點作為初始節(jié)點。通過節(jié)點過濾得到候選集合M（v）后，先初始化推理代價函數(shù)U0（v，u），迭代計算每個查詢節(jié)點v和其候選集合M（v）中每個候選節(jié)點的推理代價函數(shù)Ui（v，u），然后更新最優(yōu)匹配Oi（v）。每次迭代過程中，記錄最優(yōu)匹配節(jié)點u 的鄰居匹配節(jié)點。當保持不變的最優(yōu)匹配節(jié)點比例達到某個閾值時，迭代終止。最后，通過節(jié)點匹配優(yōu)化選擇理想的起始節(jié)點，再向周圍擴展，獲得節(jié)點匹配集合Φ。算法流程如下：

IMNeMaInfer算法

輸入：數(shù)據(jù)圖G＝ （VG，EG，LG，fG），查詢圖Q＝（VQ，EQ，LQ，fQ），查詢節(jié)點候選集M（v）

輸出：Q 的節(jié)點匹配集合Ф

IMNeMaInfer算法基于推理代價和最優(yōu)匹配提高每次迭代中查詢節(jié)點的匹配質(zhì)量。

定義7 推理代價：在迭代過程中，推理代價定義為

假定i＞0，u＝（v），u′＝（v′）。推理代價是單節(jié)點匹配代價F（v，u）和v的所有h－鄰居節(jié)點v′在上次迭代中推理代價的加權(quán)和，加權(quán)權(quán)重是節(jié)點權(quán)重。在推理過程中加入節(jié)點權(quán)重，這就使推理代價相同而權(quán)重不同的查詢節(jié)點對推理產(chǎn)生不同的作用，使推理過程更快收斂。

定義8 最優(yōu)匹配：每次迭代中，定義每個查詢節(jié)點的最優(yōu)匹配。查詢節(jié)點v的最優(yōu)匹配定義為

由于不能保證節(jié)點匹配算法在一定次數(shù)的迭代后收斂，因此當滿足條件Oi（v）＝Oi－1（v）的節(jié)點比例達到閾值ε時終止迭代。

節(jié)點匹配優(yōu)化：迭代終止時每個查詢節(jié)點的最優(yōu)匹配不一定滿足全節(jié)點匹配代價最小，因此需要對迭代結(jié)果進一步處理。Φ（v）表示查詢節(jié)點v的最大可能匹配節(jié)點 （the most probable match）。在每次迭代過程中，記錄匹配節(jié)點的h－鄰居節(jié)點中匹配部分 （算法第9行）。節(jié)點匹配優(yōu)化過程：首先，選擇鄰接標簽度最大的查詢節(jié)點v 作為起始節(jié)點，v的最大可能匹配節(jié)點

式中：i＝i′表示最終迭代。其次，其他的查詢節(jié)點的最大可能匹配節(jié)點通過擴展得到。比如v 的h－鄰居節(jié)點v′∈N（v）的最大可能匹配Φ（v′）可利用Φ（v）得到

2.2.2 算法優(yōu)化

推理代價Ui（v，u）的計算具有指數(shù)級的時間復雜度。NeMa算法引入子推理代價，使推理代價計算能夠在多項式時間內(nèi)完成。在此需證明IMNeMa算法迭代過程加入節(jié)點權(quán)重后依然成立。

定義9 子推理代價：子推理代價定義如下

式中：η（v）＝［∑v′∈N（v）PQ（v，v′）］－1。定理1 推理代價Ui（v，u）計算式為

證明

通過定理1，計算Ui（v，u）只需計算Vi（v，u，v′），故可以在多項式時間計算完成。

2.2.3 時間復雜度

2.2.4 孤立候選節(jié)點和索引建立

定義10 孤立候選節(jié)點：孤立候選節(jié)點定義為

該式表示u的h－鄰居節(jié)點和v 的任何一個h－鄰居節(jié)點的候選節(jié)點交集為空，這里定義為孤立候選節(jié)點，否則為非孤立候選節(jié)點。孤立候選節(jié)點用來進一步過濾候選集中的節(jié)點。

索引建立：為了快速計算推理代價①在離線索引階段，計算數(shù)據(jù)圖的每個節(jié)點u的鄰居向量RG（）u 、節(jié)點鄰接標簽度和標簽權(quán)重并且存儲成索引文件；②在在線節(jié)點匹配階段，如果u 被選為查詢節(jié)點v 的候選節(jié)點，驗證u 是否是一個孤立候選節(jié)點，如果是，將其從v的候選集中去除。

2.3 邊匹配

在得到匹配節(jié)點后，需要知道節(jié)點之間的連接關(guān)系。SA－Index等算法［8］是先確定最短路徑搜索的方法獲得每條查詢邊的匹配邊，最后通過貪心算法將匹配邊連接成匹配圖。這種直接選定2個節(jié)點進行最短路徑搜索的處理方式，搜索空間大，并且在查詢節(jié)點候選節(jié)點數(shù)多的情況下搜索次數(shù)多。這里通過節(jié)點匹配得到查詢節(jié)點的匹配節(jié)點集合后，利用鄰居向量索引得到匹配節(jié)點集合構(gòu)成的匹配擴展圖，在擴展圖中通過最短路徑算法，返回查詢邊的匹配邊集合，減少了搜索的空間和搜索次數(shù)，降低了時間復雜度。邊匹配EdgeMatch算法描述如下：

EdgeMatch算法

輸入：節(jié)點匹配集合Ф，查詢邊集合EQ

輸出：匹配圖GT

（1）利用鄰居向量索引得到匹配節(jié)點的γ（h）－鄰居節(jié)點，和Ф 共同構(gòu)成匹配擴展圖Ga＝ （Va，Ea，La，fa）

（2）初始化VT＝Ф，ET＝

（3）for each（v，v′）∈EQdo

（4） 在Ga中求path（（v），（v′））

（5）ET＝ET∪path（（v），（v′）），VT＝VT∪S

（6）得到匹配圖GT

算法復雜度 假設(shè)匹配節(jié)點的最大度為d，算法第1行利用鄰居向量索引得到匹配擴展圖Ga的時間復雜度為第4行采用廣度優(yōu)先搜索算法求最短路徑，匹配路徑的數(shù)量為，則搜索算法的時間復雜度為。故EdgeMatch算法時間復雜度為

以上IMNeMa算法是得到相似度最大的匹配圖，很多應用要求得到和查詢圖最相似的k 個圖，此時，需要先將式 （1）修改為返回與節(jié)點v最相似的k 個，然后對這k 個候選節(jié)點進行節(jié)點匹配優(yōu)化得到k 組匹配節(jié)點集合Ф，最后分別進行邊匹配即可。

2.4 算法復雜度比較

將IMNeMa算法和同樣能得到邊對應關(guān)系的近似子圖匹配算法SA－Index做復雜度比較 （已知運算效率SA－Index＞Tale，SA－Index＞G－Ray）［8］。SA－Index 算 法 復 雜 度 為為查詢邊的數(shù)量，mQ是一個查詢節(jié)點候選節(jié)點的最大值，分別為數(shù)據(jù)圖的節(jié)點數(shù)和邊數(shù)，為候選路徑集合的大小。IMNeMa算法主要分為節(jié)點過濾、節(jié)點匹配、邊匹配3個階段，每階段的時間復雜度分別為。由于IM－NeMa算法中節(jié)點過濾和邊匹配運行時間遠小于節(jié)點匹配運行時間，因此IMNeMa算法運行時間主要由節(jié)點匹配階段決定，時間復雜度約為表示數(shù)據(jù)圖中標簽種類，l表示數(shù)據(jù)圖中一個標簽對應的最大節(jié)點數(shù)，dQ表示一個查詢節(jié)點的h－鄰居節(jié)點的最大數(shù)目，比較如下（對于一個邊數(shù)確定的連通圖，；真實網(wǎng)絡中往往小于故a1。所以，IMNeMa算法在運算效率上要優(yōu)于SA－Index算法。

3 實驗結(jié)果及分析

實 驗 環(huán) 境：Pentium （R）Dual－Core E5500＠2.80 GHz，8.00 GB 內(nèi) 存，操 作 系 統(tǒng) 為Ubuntu12.04 LTS 64位，編譯環(huán)境為gcc／g＋＋。實驗使用了Patents，wiki－Talk，Youtube這3個數(shù)據(jù)集。Patents和wiki－Talk數(shù)據(jù)來自Stanford大學大型網(wǎng)絡數(shù)據(jù)集。Patents是美國37 年專利數(shù)據(jù)集，節(jié)點表示專利，邊表示專利之間的引用關(guān)系，標簽是專利的類型；wiki－Talk數(shù)據(jù)集是有向圖，節(jié)點表示維基用戶，邊表示用戶之間的關(guān)系，對數(shù)據(jù)圖進行處理，將有向圖變成無向圖。Youtube社會網(wǎng)絡關(guān)系數(shù)據(jù)集中，節(jié)點代表用戶，邊代表用戶間的關(guān)系。wiki－Talk 和Youtube數(shù)據(jù)集節(jié)點標簽由人工生成，人工生成的虛擬標簽在網(wǎng)絡中均勻分布。處理后的數(shù)據(jù)集的詳細統(tǒng)計信息見表1。

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

3.1 相似度指標的評測實驗及分析

真實網(wǎng)絡標簽密度差異較大，比如知識網(wǎng)絡的節(jié)點標簽密度接近1，而蛋白質(zhì)網(wǎng)絡的標簽密度為10%左右，而論文引用網(wǎng)絡更是達到0.5%左右。因此，首先比較IMNeMa算法、NeMa算法和NeMaexact算法在不同標簽密度下子圖匹配的相似度。NeMa算法是得到查詢圖的匹配節(jié)點集合，而IMNeMa還要求得到匹配邊集合；并且NeMa算法在節(jié)點匹配優(yōu)化時隨機選擇起始節(jié)點，效果較差。為了使實驗結(jié)果更有說服力，本文實驗中提到的NeMa算法都是進行了改進，即節(jié)點匹配優(yōu)化時選擇節(jié)點鄰接標簽度大的節(jié)點作為起始節(jié)點，得到節(jié)點匹配后進行邊匹配。Ne－Maexact算法則對NeMa算法進行四點改進：①加入節(jié)點過濾；②對匹配代價和IMNeMa保持一致；③節(jié)點匹配優(yōu)化時選擇節(jié)點鄰接標簽度大的查詢節(jié)點作為起始節(jié)點；④節(jié)點匹配后進行邊匹配。由于本文要求邊匹配，數(shù)據(jù)圖中可能有多個子圖和查詢圖匹配，因此考慮節(jié)點準確率和召回率［10］不能客觀反映匹配效果。該實驗選擇的評價標準為simg（Q，G′）（詳見式 （2））。對3種算法建立h ＝2的鄰居向量索引；ε＝0.8；k＝1即top－1匹配。數(shù)據(jù)圖選擇wiki－Talk數(shù)據(jù)集，分別通過人工生成不同標簽密度的標簽集合并均勻分配給節(jié)點。查詢圖是數(shù)據(jù)圖隨機產(chǎn)生的子圖，和分別為11，10，每個標簽密度下產(chǎn)生20個查詢圖，對結(jié)果求平均。實驗結(jié)果如圖1所示。

從圖1可以看出，當標簽密度大于10%時，3 個算法都有較好的性能，但隨著標簽密度的下降，3 個算法的性能也隨之下降，而IMNeMa算法下降趨勢緩慢。這說明IMNeMa算法的適用范圍更廣，匹配結(jié)果更準確。原因有兩點：①節(jié)點過濾將不滿足要求的節(jié)點從候選集合中去除，減少了對匹配過程的干擾；②IMNeMa算法在迭代過程中加入了節(jié)點權(quán)重，對查詢圖的不同節(jié)點在迭代中的作用起到了很好的區(qū)分作用，避免了匹配較多錯誤的節(jié)點，從而更好的保持了匹配圖的結(jié)構(gòu)。

圖1 不同標簽密度下的相似度

通過實驗發(fā)現(xiàn)，3 種算法對于星形結(jié)構(gòu)匹配都具有很好的效果，相似度維持在0.95以上，但對線性結(jié)構(gòu)匹配效果波動較大，以標簽密度為0.01%的數(shù)據(jù)集為例，線性結(jié)構(gòu)進行子圖匹配的相似度最低達到了0.5。這是因為本文采用的是啟發(fā)式算法，節(jié)點匹配優(yōu)化的起始節(jié)點的匹配是否準確對實驗結(jié)果產(chǎn)生很大影響，如果選擇了錯誤的起始節(jié)點，匹配相似度就會比較低。而起始節(jié)點匹配是否理想是由所選節(jié)點的特征決定的。鄰接標簽度大的節(jié)點特征多，找到正確起始節(jié)點的概率大。所以星形結(jié)構(gòu)要比線性結(jié)構(gòu)匹配效果好，這也是節(jié)點匹配優(yōu)化時選擇鄰接標簽度大大的節(jié)點作為起始節(jié)點的原因。社會網(wǎng)絡中存在連接緊密且直徑較小的核心結(jié)構(gòu)，并且規(guī)模中等的社區(qū)主要呈現(xiàn)星形結(jié)構(gòu)［12］，說明IMNeMa 算法能應用到社會網(wǎng)絡的子圖匹配。

從圖2可以看出，隨著噪聲的增加，子圖匹配相似度在下降，但是不同數(shù)據(jù)集下的下降速度不同。這是由查詢圖的選擇和數(shù)據(jù)集的結(jié)構(gòu)和標簽的差異導致。該算法在噪聲率較高的情況下仍有較好的表現(xiàn)，這說明該算法有很好的容錯性。

3.2 運算效率指標的評測實驗及分析

圖2 不同噪聲率的相似度

比較IMNeMa算法、NeMa算法、NeMaexact算法的在3種不同情況給下的運算效率。3個算法情況及參數(shù)設(shè)定同上，查詢圖生成方法同上。在wiki－Talk數(shù)據(jù)集中考察不同標簽密度情況下的運算時間，查詢圖大小同上，實驗結(jié)果如圖3所示；在Youtube數(shù)據(jù)集中考察不同算法不同數(shù)據(jù)圖節(jié)點數(shù)時的子圖匹配時間，查詢圖大小同上。實驗結(jié)果如圖4所示；在Patents數(shù)據(jù)集中考察不同數(shù)量查詢節(jié)點和查詢邊的情況下的子圖匹配時間，查詢節(jié)點和查詢邊的數(shù)量關(guān)系滿足實驗結(jié)果如圖5所示。

圖3 不同標簽密度下IMNeMa的運算效率 （WIKI－talk）

圖4 不同節(jié)點數(shù)量下的運算效率 （Youtube）

圖5 不同查詢圖大小的運算效率 （patents）

從圖3、圖4和圖5可以看出，隨著標簽密度的下降或數(shù)據(jù)集規(guī)模的增大或查詢圖的增大，IMNeMa算法和Ne－Ma算法查詢時間都在增加，這是由于查詢節(jié)點候選集變大，造成初始化式 （8）的計算量和迭代次數(shù)的增加。相比NeMa算法，IMNeMa算法通過節(jié)點過濾降低候選集，迭代過程中引入節(jié)點權(quán)重使迭代收斂更快，因此運算效率更高。Patents數(shù)據(jù)集下運算時間長，這是因為標簽密度低，造成候選節(jié)點集合大，迭代推理計算量增大。

圖6 Top－k近似匹配運算效率 （patents）

3.3 基于IMNeMa算法的Top－k近似匹配實驗

考察IMNeMa top－k 近似匹配在不同k 值下的運算效率。實驗數(shù)據(jù)選擇Patents數(shù)據(jù)集，查詢圖的節(jié)點數(shù)為5，邊數(shù)為4。實驗結(jié)果如圖6所示。從圖中可以看出：在返回top－k近似匹配結(jié)果時，IMNeMa算法節(jié)點匹配階段的運算時間基本保持平穩(wěn)，這是因為該算法主要是初始化和迭代推理計算復雜，節(jié)點匹配優(yōu)化部分和邊匹配耗時相對較小。

4 結(jié)束語

本文基于鄰居向量提出了IMNeMa算法應用于近似子圖匹配，可以得到數(shù)據(jù)圖中和查詢圖最相似的k 個匹配圖。實驗證明，該算法在標簽較稀疏和噪聲存在的情況下都有較高的匹配效果。由于采用先節(jié)點匹配后邊匹配的思路，邊匹配的耗時被大大降低，在百萬節(jié)點的數(shù)據(jù)圖中也保持較高的相似度和較高的運算效率。節(jié)點匹配優(yōu)化時的起始節(jié)點選擇不佳會造成節(jié)點匹配的效果降低，標簽稀疏圖中的候選集合數(shù)量大，分別對匹配效果和運算效率造成影響，有待進一步解決。

［1］Han Jiawei.Mining heterogeneous information networks by exploring the power of links ［C］／／Discovery Science.Berlin：Springer Berlin Heidelberg，2009：13－30.

［2］Zou L，Mo J，Chen L，et al.gStore：Answering SPARQL queries via subgraph matching ［J］.Proceedings of the VLDB Endowment，2011，4 （8）：482－493.

［3］Han L，F(xiàn)inin T，Joshi A.GoRelations：An intuitive query system for DBpedia ［M］.The Semantic Web.Berlin：Springer Berlin Heidelberg，2012：334－341.

［4］Sambhoos K，Nagi R，Sudit M，et al.Enhancements to high level data fusion using graph matching and state space search［J］.Information Fusion，2010，11 （4）：351－364.

［5］Zaslavskiy M，Bach F，Vert JP.Global alignment of proteinprotein interaction networks by graph matching methods ［J］.Bioinformatics，2009，25 （12）：1259－1267.

［6］Chau P.Catching bad guys with graph mining ［J］.XRDS：Crossroads，The ACM Magazine for Students，2011，17 （3）：16－18.

［7］Tian Y，Patel JM.Tale：A tool for approximate large graph matching ［C］／／IEEE 24th International Conference on Data Engineering.IEEE，2008：963－972.

［8］Zhu L，Keong Ng W，Cheng J.Structure and attribute index for approximate graph matching in large graphs［J］.Information Systems，2011，36 （6）：958－972.

［9］Khan A，Li N，Yan X，et al.Neighborhood based fast graph search in large networks［C］／／Proceedings of the ACM SIGMOD International Conference on Management of Data.ACM，2011：901－912.

［10］Khan A，Wu Y，Aggarwal CC，et al.NeMa：fast graph search with label similarity ［C］／／Proceedings of the 39th International Conference on Very Large Data Bases.VLDB Endowment，2013：181－192.

［11］Fan W，Li J，Ma S，et al.Graph homomorphism revisited for graph matching ［J］.Proceedings of the VLDB Endowment，2010，3 （1－2）：1161－1172.

［12］DOU Binglin，LI Shusong，ZHANG Shiyong.Social network analysis based on structure ［J］.Journal of Computers，2012，35 （4）：741－753 （in Chinese）. ［竇炳琳，李澍淞，張世永.基于結(jié)構(gòu)的社會網(wǎng)絡分析 ［J］.計算機學報，2012，35 （4）：741－753.］