樓昀愷，王朝坤

清華大學(xué) 軟件學(xué)院，北京 100084

1 引言

隨著圖在社交網(wǎng)絡(luò)等領(lǐng)域的廣泛應(yīng)用，如何在圖上高效地實現(xiàn)介數(shù)中心度查詢[1]、連通分量查詢[2]等常用查詢成為學(xué)術(shù)界和工業(yè)界的研究熱點。其中子圖匹配作為圖上的一種基礎(chǔ)而重要的查詢方式，以其方便、直觀的特點成為一個備受關(guān)注的研究問題。子圖匹配問題的定義[3]如下：給定網(wǎng)絡(luò)圖G=(V,E)和模式圖P=(Vp,Ep)，找到G中所有與P同構(gòu)[4]的子圖。通過子圖匹配的查詢方式，用戶可以直觀地從圖中獲取想要的信息。

目前常見的子圖匹配算法，如VF2[5]、R-Join[6]等，存在如下不足：一方面，這些子圖匹配算法的運行效率依然不高；另一方面，雖然研究者提出了不少針對特定子圖匹配算法的改進(jìn)策略，但很少有對多種子圖匹配算法均通用且有效的優(yōu)化方法。本文嘗試解決這兩方面的不足。

作為圖的一種重要屬性，社區(qū)結(jié)構(gòu)反映了圖中結(jié)點間聯(lián)系的緊密程度[7]。同一社區(qū)內(nèi)結(jié)點間聯(lián)系比較緊密，而不同社區(qū)的結(jié)點間的聯(lián)系則比較松散。自社區(qū)的概念被提出以來[7]，涌現(xiàn)出各種各樣的社區(qū)發(fā)現(xiàn)算法[7-17]，并已廣泛應(yīng)用于蛋白質(zhì)功能預(yù)測[18]、商品推薦[19]、反恐[20]等諸多方面。本文嘗試基于社區(qū)結(jié)構(gòu)對子圖匹配過程進(jìn)行優(yōu)化，其基本想法在于社區(qū)結(jié)構(gòu)本質(zhì)上將結(jié)點按照邊的密集程度進(jìn)行了劃分，通過利用兩端點屬于不同社區(qū)的邊的數(shù)量較少的特點，能夠?qū)ψ訄D匹配算法進(jìn)行高效剪枝，進(jìn)而加快子圖匹配的速度。

同時，模式圖中包含了大量的信息，而這部分信息在現(xiàn)有的子圖匹配算法中很少被用到。例如以四完全圖作為模式圖P在網(wǎng)絡(luò)圖G上進(jìn)行子圖匹配時，根據(jù)四完全圖的性質(zhì)，每當(dāng)在G中得到P的1個匹配結(jié)果（包括G中的4個結(jié)點）時，通過交換這4個結(jié)點即可直接得到另外的23種正確匹配結(jié)果，在后續(xù)匹配過程中不必再進(jìn)行相應(yīng)計算，減少了匹配過程中的計算量。據(jù)此，考慮通過分析模式圖的結(jié)構(gòu)特征來減少子圖匹配的計算量，從而降低時間開銷，優(yōu)化匹配過程。

結(jié)合上述兩種優(yōu)化策略，本文提出一種基于社區(qū)結(jié)構(gòu)的子圖匹配算法優(yōu)化方法，對子圖匹配算法進(jìn)行上述兩方面的優(yōu)化。

本文的主要貢獻(xiàn)包括：

（1）提出了子圖匹配中全等點、對稱點和匹配等價的概念。在子圖匹配算法中通過分析模式圖的結(jié)構(gòu)，從中找出全等點對和對稱點對，計算得到匹配等價的模式圖子圖，并基于此減少子圖匹配過程的計算量，加快匹配速度。

（2）提出了一種基于社區(qū)結(jié)構(gòu)的子圖匹配算法優(yōu)化方法（community structure based subgraph matching optimization method，CSO），結(jié)合模式圖信息和社區(qū)信息對子圖匹配算法進(jìn)行加速。CSO方法將子圖匹配流程劃分為社區(qū)內(nèi)子圖匹配和社區(qū)間子圖匹配兩個過程。對于社區(qū)內(nèi)子圖匹配，通過并行化減少時間開銷；對于社區(qū)間子圖匹配，依據(jù)模式圖分析的結(jié)果減少計算量，并在匹配的過程中結(jié)合不同社區(qū)的結(jié)點間的邊數(shù)信息進(jìn)行剪枝，達(dá)到加速匹配的目的。

（3）以VF2[5]算法為例，使用CSO方法對它進(jìn)行優(yōu)化得到AVF2（advanced_VF2）算法。在真實數(shù)據(jù)集和合成數(shù)據(jù)集上對AVF2算法與VF2算法的效率進(jìn)行了比較，并進(jìn)行了可擴(kuò)展性實驗和參數(shù)敏感性分析。實驗結(jié)果表明，CSO方法能有效加快子圖匹配算法的速度，同時具有較好的可擴(kuò)展性。

本文其余部分組織如下：第2章介紹子圖匹配和社區(qū)發(fā)現(xiàn)領(lǐng)域的相關(guān)工作；第3章給出若干基本概念；第4章提出全等點對、對稱點對的查找算法以及模式圖中匹配等價的子圖的查找算法，并進(jìn)行理論分析；第5章提出CSO方法并給出示例；第6章給出并分析實驗結(jié)果；第7章總結(jié)全文。

2 相關(guān)工作

2.1 子圖匹配算法

子圖匹配是圖上常見且實用的一種查詢，它的優(yōu)點在于用戶可以通過構(gòu)造模式圖的方式方便地在圖上進(jìn)行查詢。子圖匹配問題是NP完全問題[5]，因此如何在實際的圖數(shù)據(jù)庫中高效地進(jìn)行子圖匹配已經(jīng)成為一個重要問題。

現(xiàn)有的子圖匹配算法可以按是否使用索引進(jìn)行分類。子圖匹配的經(jīng)典算法，如Ullmann[21]和VF2[5]算法，不使用索引結(jié)構(gòu)。Ullmann算法借助矩陣變換的思想進(jìn)行子圖匹配，最優(yōu)情況下時間復(fù)雜度為Θ(N3)，最差情況下時間復(fù)雜度為Θ(N！N2)；VF2算法通過在深度優(yōu)先的搜索過程中進(jìn)行高效剪枝方法實現(xiàn)子圖匹配，最優(yōu)情況下時間復(fù)雜度為Θ(N2)，最差情況下時間復(fù)雜度為Θ(N！N)。這類不基于索引的方法的時間復(fù)雜度是超線性的，因此在較大規(guī)模的數(shù)據(jù)集上的時間開銷很大。

與上述方法相比，基于索引的方法能減少子圖匹配的時間開銷，其中常見的幾種方法包括R-Join算法[6]、GraphQL[22]算法、基于 SPath 索引的方法[23]、TurboISO算法[24]等。R-Join算法[6]構(gòu)造了基于聚合的R-Join索引；GraphQL[22]對圖中每個結(jié)點，為到它距離小于等于r的結(jié)點構(gòu)成的子圖建立索引；Zhao等[23]提出了SPath索引的概念，對每個結(jié)點v，將和v之間距離小于等于給定值k的結(jié)點的標(biāo)簽編碼為一個簽名，隨后對v與它的簽名間建立索引。在網(wǎng)絡(luò)圖上構(gòu)造索引的方法存在索引占用空間較大的問題，并且對數(shù)據(jù)量較大的圖而言，構(gòu)造索引也有較大的時間開銷。TurboISO[24]算法解析模式圖中具有等價關(guān)系的結(jié)點生成鄰域等價類樹（NECtree），使用樹中信息指導(dǎo)匹配過程中的剪枝。Bi等[25]通過推遲笛卡爾積的計算和引入緊湊路徑索引的數(shù)據(jù)結(jié)構(gòu)的方式優(yōu)化TurboISO[24]算法。TurboISO算法對模式圖進(jìn)行了解析，但解析仍不完全，且未充分利用得到的信息，仍有較大的提升空間。

2.2 社區(qū)發(fā)現(xiàn)

社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的重要屬性之一，受到學(xué)術(shù)界和工業(yè)界廣泛關(guān)注。社區(qū)結(jié)構(gòu)是由網(wǎng)絡(luò)中聯(lián)系緊密的若干結(jié)點構(gòu)成的。社區(qū)內(nèi)的結(jié)點滿足與本社區(qū)中其他結(jié)點聯(lián)系緊密，與其他社區(qū)的結(jié)點聯(lián)系松散的特點。

社區(qū)的概念最早是由Girvan和Newman[7]提出的，他們認(rèn)為社區(qū)結(jié)構(gòu)與小世界屬性、冪律分布和傳遞性一樣，也是網(wǎng)絡(luò)圖的重要屬性。自此之后，出現(xiàn)了多種社區(qū)發(fā)現(xiàn)算法，包括基于最優(yōu)化模塊度的方法、基于標(biāo)簽傳播的算法、矩陣分塊方法[8]、圖嵌入方法[9]等。

基于最優(yōu)化模塊度的方法是一種常見的社區(qū)發(fā)現(xiàn)方法。Newman和Girvan[10]在2003年首先提出使用模塊度（modularity）來評估網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。Newman[11]在2004年提出了在G-N算法[7]基礎(chǔ)上以最優(yōu)化模塊度為目標(biāo)進(jìn)行社區(qū)發(fā)現(xiàn)的貪心算法。同年，Clauset和Newman[12]再次對此方法進(jìn)行改進(jìn)，提出了CNM方法，進(jìn)一步提升了社區(qū)發(fā)現(xiàn)的效率。Blondel等[13]于2008年提出的Louvain算法是一種層次化的貪心的基于最優(yōu)化模塊度的算法，它通過社區(qū)間的合并自下而上地進(jìn)行社區(qū)發(fā)現(xiàn)，將時間復(fù)雜度減小為O(nlbn)。

另一種常見的策略是通過標(biāo)簽傳遞方法進(jìn)行社區(qū)發(fā)現(xiàn)。Raghavan等[14]于2007年提出使用標(biāo)簽傳遞算法LPA（label propagation algorithm）來進(jìn)行社區(qū)發(fā)現(xiàn)。該算法首先給每個結(jié)點設(shè)置不同的標(biāo)簽，隨后在異步更新的每步中將當(dāng)前結(jié)點的鄰居結(jié)點中出現(xiàn)次數(shù)最多的標(biāo)簽設(shè)置為當(dāng)前結(jié)點的標(biāo)簽，通過多次迭代進(jìn)行標(biāo)簽的傳遞，最終將有相同標(biāo)簽的結(jié)點劃分進(jìn)相同社區(qū)中。2008年Leung等[15]在LPA的基礎(chǔ)上增加了標(biāo)簽跳變衰減和結(jié)點的標(biāo)簽偏好的概念，提出了新的社區(qū)發(fā)現(xiàn)算法HANP（hop attenuation and node preference)。

目前社區(qū)發(fā)現(xiàn)仍是一個重要的研究問題，近幾年來出現(xiàn)了許多重要的研究成果。例如，Wang等[16]提出了一種社區(qū)發(fā)現(xiàn)方法的通用框架來對社區(qū)發(fā)現(xiàn)方法進(jìn)行深入分析與準(zhǔn)確評估；為了高效處理大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)，喬少杰等[17]提出了基于Spark的并行的社區(qū)發(fā)現(xiàn)算法DBCS（discovering big community on Spark）；Fortunato等[26]對圖上的社區(qū)發(fā)現(xiàn)方法進(jìn)行了分類和總結(jié)。

3 基本概念

給定一個復(fù)雜網(wǎng)絡(luò)圖G=(V,E,C)，V是結(jié)點集合，E是邊集合，C是G上的社區(qū)列表，有C={c1,c2,…,ck}，其中，ci是G上的社區(qū)i中包含的所有結(jié)點構(gòu)成的結(jié)點集合在G上對應(yīng)的導(dǎo)出子圖。G上的社區(qū)信息可以由數(shù)據(jù)集本身提供，也可以在G上使用社區(qū)發(fā)現(xiàn)算法（例如LPA）計算得到。與網(wǎng)絡(luò)圖類似，用戶給定的模式圖用P=(Vp,Ep)表示，Vp是P中的結(jié)點集合，Ep是P中的邊集合。子圖匹配的過程即是在G中找到所有與P同構(gòu)的G的子圖。

下文中提到的社區(qū)，如不作特殊說明指的是社區(qū)中所有結(jié)點在圖上對應(yīng)的導(dǎo)出子圖。

定義1（對稱點）給定模式圖P=(Vp,Ep)，vi,vj∈Vp，若vi與vj的拓?fù)浣Y(jié)構(gòu)對稱，則稱vi與vj互為對稱點。結(jié)點vi與vj拓?fù)浣Y(jié)構(gòu)對稱的定義是：若圖上存在一個非平凡自同構(gòu)，該自同構(gòu)對應(yīng)的雙射g滿足g(vi)=vj，g(vj)=vi，則稱結(jié)點vi與vj拓?fù)浣Y(jié)構(gòu)對稱。

定義2（對稱子圖）給定模式圖P=(Vp,Ep)，令Psub1=(Vp1,Ep1)和Psub2=(Vp2,Ep2)為P的兩個子圖，對于這兩個子圖，若存在表示對稱關(guān)系的雙射f：Vp1→Vp2（簡稱為對稱雙射），對于其中的每個映射f(u)=v，均滿足結(jié)點u與v互為對稱點，則稱Psub1和Psub2互為對稱子圖。稱上述雙射f為Psub1關(guān)于Psub2的對稱雙射。

顯然，若有Psub1關(guān)于Psub2的對稱雙射f，定義雙射g，滿足對于f的每個映射f(u)=v，相應(yīng)地有g(shù)(v)=u，則g為Psub2關(guān)于Psub1的對稱雙射。

為了便于敘述，用h({v1,v2,…,vk})表示對結(jié)點集合{v1,v2,…,vk}中各結(jié)點應(yīng)用映射h后得到的結(jié)果構(gòu)成的新集合，即h({v1,v2,…,vk})={h(v1),h(v2),…,h(vk)}。

定義4（全等點）給定無向模式圖P=(Vp,Ep)，v1,v2∈Vp，用Neigh(v)表示結(jié)點v的鄰居結(jié)點集合。稱v1和v2互為全等點，若滿足：（1）|Neigh(v1)|=|Neigh(v2)|；（2）Neigh(v1)-{v1,v2}=Neigh(v2)-{v1,v2}。對于有向模式圖，用OutNeigh(v)表示結(jié)點v的出鄰居結(jié)點集合，用InNeigh(v)表示v的入鄰居結(jié)點集合，稱v1和v2互為全等點，若滿足：（1）|OutNeigh(v1)|=|OutNeigh(v2)|且OutNeigh(v1)-{v1,v2}=OutNeigh(v2)-{v1,v2}；（2）|InNeigh(v1)|=|InNeigh(v2)|且InNeigh(v1)-{v1,v2}=InNeigh(v2)-{v1,v2} ；（3）v1∈OutNeigh(v2)且v2∈OutNeigh(v1)，或v1和v2間不存在邊。

顯然，全等點關(guān)系是特殊的對稱點關(guān)系。全等點關(guān)系具有傳遞性，所有互為全等點的結(jié)點組成的結(jié)點集合稱為一個全等點組。

定義5（鄰域范圍）給定無向模式圖P=(Vp,Ep)，對于結(jié)點v∈Vp，其鄰域范圍N(v)={t|t=vort∈Neigh(v)}。對于有向模式圖，分別定義出鄰域范圍Nout和入鄰域范圍Nin：Nout(v)={t|t=vort∈OutNeigh(v)}，Nin(v)={t|t=vort∈InNeigh(v)}。

定義6（鄰域范圍規(guī)則）給定無向模式圖P=(Vp,Ep)，Psub1和Psub2是P的兩個子圖，且它們互為對稱子圖，令Psub1關(guān)于Psub2的對稱雙射為f，Psub1關(guān)于Psub2的擴(kuò)展對稱雙射為h。對于Psub1和Psub2，鄰域范圍規(guī)則指的是下述兩條規(guī)則：規(guī)則1，Psub1中的每個結(jié)點p的鄰域N(p)與p在Psub2中的對稱點q=f(p)的鄰域N(q)滿足h(N(p))=N(q)；規(guī)則2，Psub1中的每個結(jié)點p與它在Psub2中的對稱點q=f(p)互為全等點。若Psub1和Psub2滿足上述兩條規(guī)則中的至少一條，則稱Psub1和Psub2滿足鄰域范圍規(guī)則。對于有向模式圖P=(Vp,Ep)，關(guān)于互為對稱子圖的Psub1和Psub2的鄰域范圍規(guī)則為：規(guī)則1，Psub1中的每個結(jié)點p的出鄰域Nout(p)、入鄰域Nin(p)與p在Psub2中的對稱點q=f(p)的出鄰域Nout(q)、入鄰域Nin(q)分別滿足條件h(Nout(p))=Nout(q)與h(Nin(p))=Nin(q)；規(guī)則2，Psub1中的每個結(jié)點p與它在Psub2中的對稱點q=f(p)互為全等點。其中，f是Psub1關(guān)于Psub2的對稱雙射，h是Psub1關(guān)于Psub2的擴(kuò)展對稱雙射。若Psub1和Psub2滿足上述兩條規(guī)則中的至少一條，則稱Psub1和Psub2滿足鄰域范圍規(guī)則。

定義7（匹配等價）給定無向或有向模式圖P=(Vp,Ep)，Psub1和Psub2是P的兩個子圖，且它們互為對稱子圖，記Psub1關(guān)于Psub2的對稱雙射為f，Psub1關(guān)于Psub2的擴(kuò)展對稱映射為h。若Psub1和Psub2滿足鄰域范圍規(guī)則，且Psub1和Psub2同構(gòu)，則稱Psub1和Psub2匹配等價。

定義8（社區(qū)邊界出/入結(jié)點）給定有向網(wǎng)絡(luò)圖G=(V,E,C)，c1,c2∈C是G中兩個不同的社區(qū)。對于c1中的某個結(jié)點vi，若vi到c2中某結(jié)點有一條出邊，則稱vi是c1關(guān)于c2的社區(qū)邊界出結(jié)點。本文用commOutBoundary(c1,c2)表示c1所有關(guān)于社區(qū)c2的社區(qū)邊界出結(jié)點構(gòu)成的集合，集合內(nèi)結(jié)點按照它到社區(qū)c2中結(jié)點的出邊總數(shù)從小到大排序。社區(qū)邊界入結(jié)點與出結(jié)點相似，區(qū)別在于不統(tǒng)計出邊而統(tǒng)計入邊。用commInBoundary(c1,c2)表示c1所有關(guān)于c2的邊界入結(jié)點構(gòu)成的集合。對于無向網(wǎng)絡(luò)圖可將每條無向邊替換為對應(yīng)的兩條方向相反的有向邊，得到社區(qū)邊界結(jié)點集合。

定義9（社區(qū)邊界出/入結(jié)點度數(shù)表）給定網(wǎng)絡(luò)圖G=(V,E,C)，c1,c2∈C是G中的兩個不同社區(qū)。用degreePosOut表示社區(qū)邊界出結(jié)點度數(shù)表，用degreePosIn表示社區(qū)邊界入結(jié)點度數(shù)表。其中，degreePosOut(c1,c2,d)表示c1與c2的邊界出結(jié)點集合commOutBoundary(c1,c2)中第一個到c2中結(jié)點的出邊總數(shù)大于或等于d的結(jié)點的在集合中的位置。社區(qū)邊界入結(jié)點度數(shù)表與出結(jié)點度數(shù)表相似，不再贅述。對于無向網(wǎng)絡(luò)圖可將無向邊替換為對應(yīng)的兩條方向相反的有向邊后計算得到度數(shù)表。

4 模式圖解析算法

模式圖的解析主要分為三步，分別是全等點對的查找、對稱點對的查找以及匹配等價的子圖的查找。本章分別給出這三步的算法并進(jìn)行相關(guān)理論分析。本章中給出的算法均是針對有向圖的，對于無向圖，可以將它轉(zhuǎn)換成對應(yīng)有向圖后應(yīng)用本章的算法進(jìn)行計算。

4.1 全等點對查找算法

定義10（全等點對）給定模式圖P=(Vp,Ep)，vi,vj∈Vp，若vi和vj互為全等點，則稱(vi,vj)為一個全等點對。

根據(jù)全等點的定義（定義4），給出算法1（見附錄）來查找模式圖P中所有的全等點對。

算法1查找P中所有的全等點對，并將結(jié)果存儲在equalNodes中。由于每個結(jié)點與它自己互為全等點，算法第1、2行將P中每個結(jié)點與它自己組成的全等點對存入equalNodes中。隨后根據(jù)全等點的定義對每個結(jié)點在除它自身外的結(jié)點集合中找全等點（第3～8行）構(gòu)成全等點對。算法為每個全等點組定義一個組號，存儲在patternEqualClass中（第10～15行）。這些組號將被用于計算模式圖中互相匹配等價的子圖。

例1如圖1（a）所示，結(jié)點v2和v3有相同的出邊數(shù)和入邊數(shù)，但OutNeigh(v2)={v4}，OutNeigh(v3)={v5}，因此OutNeigh(v2)-{v2,v3}≠OutNeigh(v3)-{v2,v3}，故v2和v3不互為全等點，即(v2,v3)不是全等點對。如圖1（b）所示，結(jié)點v1和v2有相同的出邊數(shù)和入邊數(shù)，OutNeigh(v1)={v2,v3}，OutNeigh(v2)={v1,v3}，滿足OutNeigh(v1)-{v1,v2}=OutNeigh(v2)-{v1,v2}={v3}，InNeigh(v1)-{v1,v2}=InNeigh(v2)-{v1,v2}={v3}，且v1∈OutNeigh(v2)，v2∈OutNeigh(v1)，因此v1和v2互為全等點，(v1,v2)是全等點對。圖1（b）經(jīng)過算法1的處理后得到的返回值為equalNodes={(vi,vj)|1≤i,j≤ 3}，patternEqualClass={v1:0;v2:0;v3:0;}。

Fig.1 Two examples of patterns圖1 兩個模式圖的例子

定理1算法1（getEqualNodes）返回的equalNodes中存儲的是P中所有的全等點對。

鑒于篇幅所限，略去本定理及余下定理的證明過程。

定理2算法1（getEqualNodes）的時間復(fù)雜度為，Np是模式圖P中的結(jié)點數(shù)。

4.2 對稱點對查找算法

定義11（對稱點對）給定模式圖P=(Vp,Ep)，vi,vj∈Vp，若vi和vj互為對稱點，則稱(vi,vj)為一個對稱點對。

因為找到模式圖中所有對稱點對的時間復(fù)雜度是指數(shù)級的，所以本節(jié)給出的查找算法是一個貪心算法，它查找圖中非全等點對的對稱點對。算法2（見附錄）和算法3（見附錄）給出了在模式圖中查找對稱點對的具體方法。其中，算法2查找模式圖中的對稱點對，它調(diào)用算法3遞歸地計算對稱點關(guān)系。

若要判斷模式圖中任意兩個結(jié)點組成的點對(vi,vj)是否是非全等點對的對稱點對，則其需要滿足如下三個必要條件：（1）(vi,vj)不是全等點對（算法3第1、2行）；（2）之前未判斷過(vi,vj)是否是對稱點對（算法3第3、4行）；（3）vi的出度與vj的出度相等且vi的入度與vj的入度相等（算法3第5～7行）。如算法3所示，一旦這個點對不滿足上述三個條件中的任意一個，則退出算法3，否則繼續(xù)執(zhí)行，將vi和vj加入到結(jié)點集合used中。其中，used中存儲的是當(dāng)前正在判斷的若干點對中的結(jié)點。

驗證得到vi和vj滿足上述必要條件后，先對它們的出鄰居進(jìn)行判斷。算法3第9行將vi的不在used中的出鄰居結(jié)點存儲在unusedNeighs1中，即unusedNeighs1中存儲的是vi的出鄰居結(jié)點中不在任何一個當(dāng)前正被判斷的點對中的結(jié)點。第10行將結(jié)點vj的不在used中的出鄰居結(jié)點存儲在unusedNeighs2中。

若得到的unusedNeighs1和unusedNeighs2均為空，則認(rèn)為vi和vj的出鄰居滿足要求，可以直接判斷它們的入鄰居。否則使用遞歸的方法嘗試找到IunusedNeighs1（unusedNeighs1在模式圖中對應(yīng)的導(dǎo)出子圖）關(guān)于IunusedNeighs2（unusedNeighs2在模式圖中對應(yīng)的導(dǎo)出子圖）的對稱雙射。若unusedNeighs1和unusedNeighs2中包含的結(jié)點個數(shù)不同，則不可能找到這樣的對稱雙射，因此vi和vj不可能互為對稱點，可以直接設(shè)置symm中對應(yīng)值為False，并從used中刪除vi和vj（第11～14行），表示完成了對點對(vi,vj)的判斷。若unusedNeighs1和unusedNeighs2中包含的結(jié)點個數(shù)相同，則用枚舉的方式嘗試找到一個IunusedNeighs1關(guān)于IunusedNeighs2的對稱雙射（第15～25行）。若無法找到這樣的對稱雙射，說明結(jié)點vi和vj不互為對稱點，故(vi,vj)不是對稱點對，在symm中記錄此關(guān)系，將symm[vi][vj]和symm[vj][vi]設(shè)置為False（算法3第23～25行），并結(jié)束對vi和vj的判斷；若在vi和vj的出鄰居結(jié)點集合在模式圖上的導(dǎo)出子圖間構(gòu)造出了滿足要求的對稱雙射，則可以開始對結(jié)點入鄰居進(jìn)行判斷。對結(jié)點入鄰居的判斷方法與出鄰居類似（第26行）。若入鄰居對應(yīng)的unusedNeighs1和unusedNeighs2為空，或?qū)τ谌豚従诱业搅薎unusedNeighs1關(guān)于IunusedNeighs2的對稱雙射，則表明結(jié)點vi和vj互為對稱點，即(vi,vj)是一個對稱點對，設(shè)置symm[vi][vj]和symm[vj][vi]為True（算法3第27行）。完成判斷后，將vi和vj從used中刪去，表示完成了對于點對(vi,vj)是否是對稱點對的判斷（算法3第28行）。

最終，對于所有symm[vi][vj]為True的情況，將點對 (vi,vj)加入symmetryNodes（算法2第7～10行）。symmetryNodes中存儲的點對即是算法2找到的所有對稱點。

例2如圖1(a)所示，判斷結(jié)點v2和v3組成的點對(v2,v3)是否是對稱點對。此時，由于正在對點對(v3,v4)進(jìn)行判斷，因此used中包含結(jié)點v2與v3。算法3中要求判斷v2對應(yīng)的unusedNeighs1（即{v4}）在圖1（a）上的導(dǎo)出子圖I{v4}與v3對應(yīng)的unusedNeighs2（即{v5}）在圖1（a）上的導(dǎo)出子圖I{v5}間是否存在對稱雙射f。嘗試建立v4與v5間的映射，即先判斷點對(v4,v5)是否是一個對稱點對。此時，得到v1對應(yīng)的unusedNeighs1與v2對應(yīng)的unusedNeighs2相同，都等于{v6}。因此，存在對稱雙射f6:{v6}→{v6}，滿足f(v6)=v6，故出鄰居滿足要求。開始對v4和v5的入鄰居集合進(jìn)行判斷，此時入鄰居集合對應(yīng)的unusedNeighs1和unusedNeighs2均為空，因此，(v4,v5)是一個對稱點對。故找到了I{v4}關(guān)于I{v5}的對稱雙射f:{v4}→{v5}，滿足f(v4)=v5。對于v2和v3的入鄰居采用相同的方法也能找到對稱雙射。因此，(v2,v3)也是對稱點對。

定理3給定模式圖P=(Vp,Ep)，算法2找到的所有對稱點對均是P中非全等點對的對稱點對。

由定理3容易證明本節(jié)給出的對稱點對查找算法（算法2）的正確性。

定理4算法2的時間復(fù)雜度為，Np為輸入中模式圖P中的結(jié)點數(shù)。

4.3 匹配等價的子圖的查找算法

本節(jié)給出在模式圖P=(Vp,Ep)中查找匹配等價的子圖的方法（算法4，見附錄）。由于查找對稱點對的算法（算法2）是一個貪心算法，因此所要查找的與P的一個子圖Psub匹配等價的所有P的子圖，是指在算法2找到的所有對稱點對的基礎(chǔ)下能找到的與Psub匹配等價的P的子圖，可能不完全包含所有滿足此條件的子圖。

具體來說，本方法調(diào)用算法5（見附錄）遍歷P中結(jié)點所有可能的組合方式，對每種組合方式在P中生成對應(yīng)的導(dǎo)出子圖，并找到與每個導(dǎo)出子圖同構(gòu)的其他子圖。同時，算法6（見附錄）對每個導(dǎo)出子圖尋找與它滿足鄰域范圍規(guī)則的子圖。最終，算法4根據(jù)得到的同構(gòu)的子圖和滿足鄰域范圍規(guī)則的子圖找到模式圖中所有匹配等價的子圖。

算法4首先通過調(diào)用算法5遍歷P中結(jié)點的所有組合方式（算法4第2行），對于每種組合方式生成P上對應(yīng)的導(dǎo)出子圖，尋找互相同構(gòu)的導(dǎo)出子圖并將同構(gòu)關(guān)系存儲在isomap中，同時找到互相滿足鄰域范圍規(guī)則的子圖，在matchEq中對每個子圖存儲所有與它滿足鄰域范圍規(guī)則的子圖。隨后通過isomap中存儲的子圖同構(gòu)關(guān)系信息，對matchEq中的每個子圖判斷與它滿足鄰域范圍規(guī)則的子圖是否與它同構(gòu)，將不與它同構(gòu)的子圖刪除（第3～7行）。對每個子圖處理完畢后，matchEq中存儲的即為與P的各子圖匹配等價的所有P的子圖。

算法5可以分為兩部分：（1）遍歷P中結(jié)點的組合方式，生成對應(yīng)導(dǎo)出子圖，并找到與每個導(dǎo)出子圖匹配等價的P的子圖；（2）對于每個導(dǎo)出子圖，找到與它同構(gòu)的模式圖子圖。

關(guān)于第1部分，使用current存儲模式圖結(jié)點當(dāng)前的組合方式，算法第24行向current添加新結(jié)點vpos獲得一種新的組合方式。第25行遞歸調(diào)用算法5自身繼續(xù)尋找新的結(jié)點組合方式，第26行將新加的結(jié)點刪除，進(jìn)行回退。對于每種結(jié)點組合方式current，生成其對應(yīng)的導(dǎo)出子圖Icurrent（算法第2行），第6行調(diào)用算法6找到與Icurrent滿足鄰域范圍規(guī)則的所有子圖，并存儲在matchEq[Icurrent]中。

對應(yīng)第2部分，算法5第7～20行判斷Icurrent是否與之前遍歷到的某個子圖同構(gòu)。對于模式圖P，定義它的子圖Ic的特征字符串為Sc。特征字符串Sc的構(gòu)造方法為在P中找與Ic同構(gòu)的P的子圖，對找到的每個子圖，將子圖中的結(jié)點ID升序排序，以空格為分隔符連接排序后的結(jié)點ID形成字符串，將各字符串分別按字典序排列后得到的最小的字符串即為Ic的特征字符串Sc。由同構(gòu)的性質(zhì)易知，P的兩個子圖同構(gòu)當(dāng)且僅當(dāng)它們具有相同的特征字符串。matchedModel中存儲的是元組(Si,Ii)，其中，Si是所有處理過的子圖的特征字符串，Ii是處理過程中特征字符串為Si的第一個子圖。對于matchedModel中的每一個元組(Si,Ii)，若Icurrent與Ii同構(gòu)，則將Icurrent加入記錄所有特征字符串為Si的子圖的數(shù)組isomorphicList[Si]中（第12行），并在記錄每個子圖的特征字符串的字典isomap中添加對應(yīng)項（第13行）。若matchedModel中的所有元組(Si,Ii)中的Ii均不與Icurrent同構(gòu)，則得到的Icurrent的特征字符串Scurrent不與之前處理過的任何子圖的相同，因此將(Scurrent,Icurrent)插入到matchedModel中（第18行），剩余操作與前面類似。處理完所有可能的子圖后，isomap中記錄了所有子圖的特征字符串。

算法6查找所有與Icurrent滿足鄰域范圍規(guī)則的模式圖子圖。同樣可以將它分為兩個階段：（1）計算得到每個與Icurrent互為對稱子圖的子圖It；(2)判斷Icurrent與It是否滿足鄰域范圍規(guī)則，將與Icurrent滿足鄰域范圍規(guī)則的It存儲到matchEq[Icurrent]中。第一階段主要通過算法6第13～26行實現(xiàn)。算法第13～19行將current中的某結(jié)點替換為它的一個全等點，第20～26行將current中某結(jié)點替換為它的一個非全等點的對稱點，通過對current中每個結(jié)點進(jìn)行如上替換操作，并嘗試每種替換方式，得到所有滿足如下條件的結(jié)點集合t：t在P上的導(dǎo)出子圖It與current在P上的導(dǎo)出子圖Icurrent互為對稱子圖。而上述所有It即為Icurrent的所有對稱子圖。當(dāng)滿足算法第1行的條件時，說明得到了一個滿足條件的結(jié)點集合t，使得It與Icurrent互為對稱子圖。

第二階段對于每個滿足條件的結(jié)點集合t進(jìn)行處理。算法6第2行分別構(gòu)造current和t在P上對應(yīng)的導(dǎo)出子圖Icurrent與It。第3行計算得到Icurrent關(guān)于It的擴(kuò)展對稱映射。第4行判斷hasSymm的值，若為True，說明在由current構(gòu)造出t的過程中使用了非全等點的對稱點關(guān)系進(jìn)行替換，因此Icurrent和It不滿足鄰域范圍規(guī)則中的規(guī)則2，需要判斷Icurrent和It是否滿足鄰域范圍規(guī)則中的規(guī)則1（算法6第5行）；否則，若hasSymm為False，則說明由current構(gòu)造出t的過程中只用了全等點關(guān)系進(jìn)行替換，因此Icurrent各結(jié)點與替換后It中對應(yīng)的結(jié)點互為全等點，即Icurrent與It必滿足鄰域范圍規(guī)則中規(guī)則2的要求，故Icurrent與It滿足鄰域范圍規(guī)則。為了避免重復(fù)存儲，對于使用了非全等點的對稱點進(jìn)行替換的情況，第6行判斷Icurrent與It包含的結(jié)點是否相同：若不同，則只有當(dāng)t中結(jié)點的ID升序排列時，才將It存入matchEq[Icurrent]中（第7、8行）；若相同，可以直接將替換后的結(jié)果存儲入matchEq中。對于只使用了全等點關(guān)系進(jìn)行替換的情況，若t中屬于相同全等點組的結(jié)點的ID均升序排列，則存儲當(dāng)前結(jié)果（第10、11行）。

上述算法得到P中與每個子圖匹配等價的所有子圖，并存儲在matchEq中，用于后續(xù)算法中對社區(qū)間子圖匹配過程進(jìn)行加速。

例3以圖1（a）所示的模式圖為例說明上述過程。記此模式圖為P=(Vp,Ep)，其中Vp={v1,v2,v3,v4,v5,v6}，則算法retrivalNodes依次得到結(jié)點組合方式{v6},{v5},{v5,v6},{v4},{v4,v6},{v4,v5},{v4,v5,v6},{v3},{v3,v6},{v3,v5},{v3,v5,v6},{v3,v4},{v3,v4,v6},…，{v2,v4}，…，{v1,v2,v3,v4,v5,v6}。當(dāng)處理由{v2,v4}對應(yīng)的導(dǎo)出子圖I{v2,v4}時，先調(diào)用函數(shù)getAllMatchNodes找與它互為對稱子圖的P的子圖，并驗證它們是否滿足鄰域范圍規(guī)則。因為v2和v3互為對稱點，v4和v5互為對稱點，所以得到的與I{v2,v4}互為對稱子圖的P的子圖包括I{v2,v4}，I{v2,v5}，I{v3,v4}，I{v3,v5}。通過驗證，得到I{v2,v4}和其中的I{v2,v4}滿足鄰域范圍規(guī)則（規(guī)則2），I{v2,v4}和I{v3,v5}也滿足鄰域范圍規(guī)則（規(guī)則1），因此存儲結(jié)果得到matchEq[I{v2,v4}]={I{v2,v4},I{v3,v5}}。在這之后，還需要計算和存儲同構(gòu)信息。計算得到I{v2,v4}的特征字符串為“12”，因為I{v5,v6}的特征字符串也是“12”，并且它在I{v2,v4}之前被處理過了。因此，matchedModel中已經(jīng)存在元組("12",I{v5,v6})，因此算法5中第11行能找到I{v2,v4}與I{v5,v6}同構(gòu)，故只需將I{v2,v4}加入到isomorphicList["1 2"]中，并存儲isomap[I{v2,v4}]="1 2"即可。完成所有子圖的處理后，有isomorphicList["1 2"]={I{v1,v2},I{v1,v3},I{v2,v4},I{v3,v5},…}。當(dāng)完成retrivalNodes函數(shù)的計算后，對所有滿足鄰域范圍規(guī)則的子圖進(jìn)行同構(gòu)的驗證，如對于matchEq[I{v2,v4}]，由于isomap[I{v2,v4}]=isomap[I{v3,v5}]，因此不用刪除元素，找到的與子圖I{v2,v4}匹配等價的子圖包括I{v2,v4}和I{v3,v5}。

定理5算法4所述匹配等價的子圖的查找算法是正確的。

定理6匹配等價子圖的查找算法（算法4）的時間復(fù)雜度為，其中Np為模式圖P的子圖個數(shù)，θ(Np)為子圖匹配算法在結(jié)點數(shù)為Np時的時間復(fù)雜度，Nsub為由模式圖P的子圖能構(gòu)成的最大的集合的大小，滿足集合中各子圖互不同構(gòu)。

當(dāng)模式圖中結(jié)點較少時，定理6給出的算法4的時間復(fù)雜度近似等于Ο(θ(Np))，即約等于子圖匹配算法的時間復(fù)雜度。

當(dāng)模式圖中結(jié)點較多時，可以通過只對模式圖中部分子圖找與它匹配等價的子圖的方法減少這部分的時間開銷。如只對結(jié)點數(shù)不超過Nd的子圖找與它互相匹配等價的子圖，則此時算法的時間復(fù)雜度為。例如當(dāng)Nd=12時，算法的時間復(fù)雜度就降為Ο(212×(Nsub×θ(Np)+212×122))。

5 子圖匹配算法優(yōu)化方法

本章詳細(xì)介紹基于社區(qū)結(jié)構(gòu)的子圖匹配算法優(yōu)化方法CSO。為了便于描述，將CSO方法中涉及到的子圖匹配算法記作Λ。在使用CSO方法對具體的子圖匹配算法（如VF2[5]算法）進(jìn)行優(yōu)化時，只需將下述各算法中的Λ算法替換為該子圖匹配算法即可。其中，在社區(qū)間子圖匹配的算法說明中具體給出基于社區(qū)結(jié)構(gòu)進(jìn)行剪枝的方法。

5.1 CSO方法概述

CSO方法用于對子圖匹配算法進(jìn)行加速。它將子圖匹配流程劃分為社區(qū)內(nèi)子圖匹配和社區(qū)間子圖匹配兩個過程，在這兩個過程中分別并行地進(jìn)行子圖匹配相關(guān)計算。CSO方法采用了模式圖解析和基于社區(qū)結(jié)構(gòu)的剪枝兩種策略對子圖匹配算法進(jìn)行優(yōu)化，以提升子圖匹配算法的效率。下面先給出本節(jié)用到的幾個概念，然后具體講解CSO方法。

定義12（結(jié)點可重復(fù)的子圖匹配）給定網(wǎng)絡(luò)圖G和模式圖P，若子圖匹配過程中允許P中不同結(jié)點與G中的相同結(jié)點相匹配，則稱該子圖匹配為結(jié)點可重復(fù)的子圖匹配。

定義13（分配方案）給定網(wǎng)絡(luò)圖G=(V,E,C)和模式圖P=(Vp,Ep)，G中各社區(qū)構(gòu)成的集合C={c1,c2,…,ck}。劃分Vp得到由m個結(jié)點集合構(gòu)成的集合w（w={vlist1,vlist2,…,vlistm}，w中各結(jié)點集合間互不相交且vlist1∪vlist2∪…∪vlistm=Vp,m≤k）。稱映射fs:C′→w為P關(guān)于C的一種分配方案，如果滿足：（1）C′?C且|C′|=m；（2）fs是一個雙射。

給定模式圖P關(guān)于G中社區(qū)的一個分配方案fs，若有fs(ci)=vlistj，則稱vlistj中各結(jié)點被分配到社區(qū)ci。

定義14（等價的分配方案）給定網(wǎng)絡(luò)圖G=(V,E,C)和模式圖P=(Vp,Ep)，G中各社區(qū)構(gòu)成的集合C={c1,c2,…,ck}。令fs1:C1→w1和fs2:C2→w2為P關(guān)于C的兩個不同的分配方案，則fs1與fs2是等價的分配方案，若：（1）C1=C2；（2）?ci∈C1，fs1(ci)與fs2(ci)在P上的導(dǎo)出子圖匹配等價。用AFS(fs)表示所有與分配方案fs等價的分配方案（含fs）。

為了便于描述，對于滿足fs(c1)=vlist1,fs(c2)=vlist2,…,fs(ct)=vlistt的分配方案fs，將它簡記為fs={c1:vlist1;c2:vlist2;…;ct:vlistt}。

定義15（等價方案映射）給定網(wǎng)絡(luò)圖G=(V,E,C)和模式圖P=(Vp,Ep)，G中各社區(qū)構(gòu)成的集合C={c1,c2,…,ck}。令fs1:C1→w1和fs2:C2→w2為P關(guān)于C的兩個不同的分配方案，且fs1和fs2等價。定義映射esf:Vp→Vp，稱esf是fs1關(guān)于fs2的等價方案映射，若esf滿足：（1）?ci∈C1，記fs1(ci)在P上的導(dǎo)出子圖關(guān)于fs2(ci)在P上的導(dǎo)出子圖的對稱雙射為f，則?v∈fs1(ci),esf(v)=f(v)；（2）esf是雙射。

例4以圖2（a）為網(wǎng)絡(luò)圖，圖2（b）為模式圖，記紅色社區(qū)為c1，綠色社區(qū)為c2，藍(lán)色社區(qū)為c3，可以得到的分配方案包括：fs1={c1:{va};c2:{vb,vd};c3:{vc}}，fs2={c1:{vd};c2:{vc,va};c3:{vb}}等。fs1和fs2的定義域都是{c1,c2,c3}，且有fs1(c1)={va}，fs1(c2)={vb,vd}，fs1(c3)={vc}，fs2(c1)={vd}，fs2(c2)={vc,va}，fs2(c3)={vb}。記結(jié)點集合{v1,v2,…,vk}在模式圖上對應(yīng)的導(dǎo)出子圖為I{v1,v2,…,vk}。因為圖2（b）上I{va}與I{vd}，I{vb,vd}與I{vc,va}，I{vc}與I{vb}分別匹配等價，所以fs1和fs2是等價的分配方案。fs1關(guān)于fs2的等價方案映射esf滿足esf(va)=vd，esf(vb)=vc，g(vc)=vb，esf(vd)=va。

Fig.2 Diagrams for explainingAdvanced_Λ algorithm圖2 Advanced_Λ算法說明用圖

定義16（同社區(qū)結(jié)點一跳共同鄰居分布表）給定網(wǎng)絡(luò)圖G=(V,E,C)和模式圖P=(Vp,Ep)，c1,c2∈C是G中兩個不同的社區(qū)，vpi,vpj∈Vp。將P中的結(jié)點分配到各社區(qū)后，假設(shè)vpi與vpj被分配到c1。用oomessage(vpi,vpj,c2)表示vpi的出鄰居中被分配到c2的結(jié)點組成的集合與vpj的入鄰居中被分配到c2的結(jié)點組成的集合的交集的大小，用表示和的出鄰居的交集中被分配到c2的結(jié)點的數(shù)量，用表示和的入鄰居的交集中被分配到c2的結(jié)點的數(shù)量。稱oomessage、oimessage和iomessage為同社區(qū)結(jié)點一跳共同鄰居分布表。

例5如圖3模式圖所示，圖中相同顏色的結(jié)點被分配到同一個社區(qū)。用c1表示紅色社區(qū)，c2表示綠色社區(qū)，c3表示藍(lán)色社區(qū)，則oomessage(v1,v5,c2)=1，oimessage(v1,v5,c2)=1，iomessage(v1,v5,c2)=0。

Fig.3 Pattern used by example 5圖3 例5所用模式圖

算法7（見附錄）給出了使用CSO方法優(yōu)化Λ算法后得到的新算法Advanced_Λ。

具體地，算法7第1、2行進(jìn)行預(yù)處理。首先，第1行生成超圖SuperG。以G中的社區(qū)作為超圖中的結(jié)點，若G中兩社區(qū)c1、c2間存在有向邊，則為這兩個社區(qū)在SuperG中對應(yīng)的結(jié)點間也添加一條同向的有向邊；若G中某社區(qū)內(nèi)存在兩個不同的結(jié)點，且它們之間存在有向邊，則為這個社區(qū)在SuperG中對應(yīng)的結(jié)點添加自環(huán)。接著，第2行根據(jù)第4.3節(jié)中給出的算法4（匹配等價的子圖的查找算法），對模式圖P中的每個子圖Psub進(jìn)行處理，得到P中與Psub匹配等價的所有子圖，并將這些子圖存儲在matchEq[Psub]中。

第3、4行進(jìn)行具體的子圖匹配。在Advanced_Λ算法中，子圖匹配過程分為社區(qū)內(nèi)子圖匹配（第3行）和社區(qū)間子圖匹配（第4行）兩部分。

5.2 社區(qū)內(nèi)子圖匹配算法

第5.1節(jié)給出的算法7中，第3行進(jìn)行社區(qū)內(nèi)的子圖匹配。算法8（見附錄）給出了社區(qū)內(nèi)子圖匹配的具體算法。

具體地，算法8依據(jù)網(wǎng)絡(luò)圖G的社區(qū)結(jié)構(gòu)，通過并行計算同時在多個社區(qū)內(nèi)使用Λ算法進(jìn)行子圖匹配，從而提升子圖匹配的效率。

例6以圖2中（a）為網(wǎng)絡(luò)圖，（b）為模式圖進(jìn)行子圖匹配，則通過算法8的計算，在紅色社區(qū)內(nèi)得到的匹配結(jié)果為{va→v1,vb→v2,vc→v4,vd→v3},{va→v1,vb→v4,vc→v2,vd→v3},{va→v3,vb→v4,vc→v2,vd→v1},{va→v3,vb→v2,vc→v4,vd→v1}，在藍(lán)色社區(qū)中無匹配結(jié)果，在綠色社區(qū)中的匹配結(jié)果與紅色社區(qū)中的結(jié)果類似，這里不再列舉。

5.3 社區(qū)間子圖匹配算法

在第5.1節(jié)給出的算法中，第4行進(jìn)行社區(qū)間子圖匹配，其具體算法如算法9（見附錄）所示。

算法9通過在超圖SuperG上用模式圖P進(jìn)行結(jié)點可重復(fù)的子圖匹配，獲得大量的模式圖分配方案superMatch，并將這些分配方案存儲在superMatchList中。每當(dāng)superMatchList中存儲的方案超過閾值batch_size時，調(diào)用算法10（見附錄）對這些分配方案進(jìn)行處理。算法9第2行使用的結(jié)點可重復(fù)的子圖匹配算法可以通過擴(kuò)展Λ算法得到。

例7圖2（c）是圖2（a）對應(yīng)的超圖SuperG，在此超圖上對圖2（b）表示的模式圖進(jìn)行子圖匹配可以得到的分配方案包括（記紅色社區(qū)為c1，綠色社區(qū)為c2，藍(lán)色社區(qū)為c3）{c1:{va};c2:{vb,vd};c3:{vc}}，{c2:{va,vb,vc,vd}}，{c1:{va};c2:{vb,vc,vd}}，{c1:{va};c3:{vb,vc,vd}}等。圖2（d）對應(yīng)的是分配方案{c1:{va};c2:{vb,vd};c3:{vc}}。

算法9中調(diào)用算法10處理分配方案列表superMatchList中的各分配方案。

算法10并行地處理存儲了大量分配方案的列表superMatchList（第2行）。superMatch是superMatchList中的一個分配方案，其中存儲的是若干元組(ci,vlisti)。(ci,vlisti)表示結(jié)點集合vlisti中的結(jié)點被分配到社區(qū)ci，用vlisti在P中的導(dǎo)出子圖與社區(qū)ci進(jìn)行子圖匹配。稱可能與模式圖結(jié)點v匹配的網(wǎng)絡(luò)圖結(jié)點為v的候選匹配結(jié)點，這些候選匹配結(jié)點組成的集合稱為v的候選匹配結(jié)點集合。對于vlisti中的任意v，v的初始的候選匹配結(jié)點集合即為ci中包含的所有結(jié)點。

算法10首先獲取離線計算得到的社區(qū)邊界出結(jié)點集合、入結(jié)點集合及相關(guān)度數(shù)表commOutBoundary,commInBoundary，degreePosOut和degreePosIn（第1行），接著對一些無效的分配方案進(jìn)行處理。若所有的模式圖結(jié)點被分配到同一個社區(qū)，則不對該方案進(jìn)行處理（算法第3、4行），這是因為這種情況下進(jìn)行的是社區(qū)內(nèi)子圖匹配，在第5.2節(jié)給出的算法8中已完成這類計算；若分配方案中分配到某個社區(qū)的模式圖結(jié)點數(shù)超過了該社區(qū)中的結(jié)點總數(shù)，則當(dāng)前分配方案不可能成功匹配，可以直接處理下一個分配方案（算法第5～7行）。

CSO方法基于社區(qū)結(jié)構(gòu)共進(jìn)行了兩類剪枝。第一類剪枝的方法由算法10第9～26行給出。對于superMatch中的每個元組(ci,vlisti)，每次從vlisti中取出一個結(jié)點v，對于每個社區(qū)c′(c′≠ci)，用outds[c′]記錄v到被分配到c′的所有模式圖結(jié)點的出邊總數(shù)，用inds[c′]記錄被分配到c′的所有模式圖結(jié)點到v的出邊總數(shù)。算法10第13～22行對于模式圖中的每個結(jié)點v，關(guān)于每個社區(qū)c′（不包括v所在的社區(qū)），計算v對應(yīng)的outds[c′]和inds[c′]。若網(wǎng)絡(luò)圖中某結(jié)點u到社區(qū)c′中結(jié)點的總出邊數(shù)小于outds[c′]，則v不可能與u匹配，由此，依據(jù)commOutBoundary、degreePosOut和outds可以從v的候選匹配結(jié)點集合中刪除所有不可能與v匹配的結(jié)點（第24行）。對于inds也可以進(jìn)行相應(yīng)的剪枝（第26行）。將剪枝后得到的v的候選匹配結(jié)點集合存儲到boundary[v]中。在使用Λ算法進(jìn)行子圖匹配時，對于每個結(jié)點v，可以只嘗試將它與boundary[v]中結(jié)點進(jìn)行匹配，從而減少子圖匹配過程中不必要的計算，提升子圖匹配的效率。

算法10第28～30行處理superMatch得到super-MatchMap。superMatchMap中對模式圖中每個結(jié)點，記錄它被分配到的社區(qū)。第31～34行獲取當(dāng)前分配方案對應(yīng)的標(biāo)志字符串，一個分配方案對應(yīng)的標(biāo)志字符串的計算方法為：將分配方案中包含的結(jié)點按照ID升序排列，依次獲得各結(jié)點被分配到的社區(qū)的編號后，將這些編號用空格連接得到該分配方案對應(yīng)的標(biāo)志字符串。若當(dāng)前分配方案的標(biāo)志字符串在與它等價的分配方案中不是最小的，則結(jié)束當(dāng)前分配方案的處理（第35行），這是為了避免重復(fù)計算。在第34行的處理中計算了所有與當(dāng)前分配方案等價的分配方案，若當(dāng)前分配方案的標(biāo)志字符串是其中最小的，則將當(dāng)前分配方案fs關(guān)于AFS(fs)中每個分配方案的等價方案映射存入newallmaps中（第36行）。

算法10第37行調(diào)用算法11（getTwoHopPattern-Pairs）獲得模式圖的同社區(qū)結(jié)點一跳共同鄰居分布表。該表的作用如下：記結(jié)點t的屬于社區(qū)c的出鄰居結(jié)點組成的集合為OutNeighc(t)，屬于c的入鄰居結(jié)點組成的集合為InNeighc(t)。在進(jìn)行子圖匹配的過程中，若對于被分配到c的模式圖結(jié)點u，要在網(wǎng)絡(luò)圖中找到與它匹配的結(jié)點，而同樣被分配到c的另一個模式圖結(jié)點v已與網(wǎng)絡(luò)圖結(jié)點t匹配，對于嘗試與u匹配的網(wǎng)絡(luò)圖結(jié)點s，若它滿足下述任何一種情況，則u不能與s成功匹配：（1）存在社區(qū)c′≠c,|OutNeighc′(t)∩InNeighc′(s)|＜o(jì)omessage(v,u,c′)；（2）存在社區(qū)c′≠c,|OutNeighc′(t)∩OutNeighc′(s)|＜o(jì)imessage(v,u,c′)；（3）存在社區(qū)c′≠c,|InNeighc′(t)∩InNeighc′(s)|＜iomessage(v,u,c′)。此時可直接將u與其他結(jié)點匹配。算法中通過上述方式使用此分布表對子圖匹配算法進(jìn)行加速。這是CSO方法基于社區(qū)結(jié)構(gòu)進(jìn)行的第二類剪枝。

算法10第38行，對于當(dāng)前分配方案superMatch中的每個元組(ci,vlisti)，使用Λ算法對每個社區(qū)ci與Ivlisti進(jìn)行子圖匹配。其中，使用Λ算法進(jìn)行匹配時，從boundary[v]中選擇結(jié)點嘗試與v進(jìn)行匹配，并且使用上述分布表進(jìn)行加速。將每個社區(qū)ci上的所有匹配結(jié)果存儲在maps[ci]中。算法10第42行調(diào)用算法12（test_subgraph_match）對maps中存儲的各社區(qū)上的子圖匹配結(jié)果進(jìn)行合并和結(jié)構(gòu)驗證得到P與G的子圖匹配結(jié)果，并將這些結(jié)果存入finds中。合并指的是對每個社區(qū)ci，從maps[ci]中取出該社區(qū)上的一種匹配結(jié)果，將取出的所有匹配結(jié)果合并得到P與G的子圖匹配結(jié)果。因為合并可能會導(dǎo)致如下情況：存在vi,vj∈Vp，它們分別被分配到社區(qū)ci和cj，且vi和vj間有邊，但是合并后得到的結(jié)果中，與vi匹配的結(jié)點和與vj匹配的結(jié)點間卻沒有邊。這樣的合并結(jié)果顯然不是P與G的子圖匹配結(jié)果。匹配驗證即是要找到所有出現(xiàn)上述情況的合并結(jié)果，使得這些合并結(jié)果不被加入結(jié)果集finds中。

最后，算法10的第43行將finds中的所有子圖匹配結(jié)果通過newallmaps中存儲的等價方案映射進(jìn)行轉(zhuǎn)換，得到在與當(dāng)前分配方案等價的分配方案下P與G的匹配結(jié)果，一并存儲進(jìn)outs中。

例8在圖2（a）所給的網(wǎng)絡(luò)圖上對圖2（b）所示的模式圖進(jìn)行社區(qū)間子圖匹配，記紅色社區(qū)為c1，綠色社區(qū)為c2，藍(lán)色社區(qū)為c3。執(zhí)行rematch函數(shù)時，得到了大量的分配方案，其中分配方案{c2:{va,vb,vc,vd}}由于將所有結(jié)點分配到了同一個社區(qū)，在之前的社區(qū)內(nèi)子圖匹配過程中已處理完畢，因而不用處理。分配方案{c1:{va};c3:{vb,vc,vd}}由于將3個結(jié)點分配到了藍(lán)色社區(qū)，而藍(lán)色社區(qū)中只有2個結(jié)點，因此不可能有匹配結(jié)果出現(xiàn)，因而不用處理。以分配方案{c1:{va};c2:{vb,vd};c3:{vc}}（圖2（d））為例。先進(jìn)行基于社區(qū)結(jié)構(gòu)的剪枝。在計算boundary的過程中，根據(jù)模式圖的結(jié)構(gòu)，要求與結(jié)點va匹配的網(wǎng)絡(luò)圖結(jié)點在社區(qū)c2和c3中各有至少一個出鄰居結(jié)點，并且與va匹配的網(wǎng)絡(luò)圖結(jié)點屬于社區(qū)c1，因此網(wǎng)絡(luò)圖中滿足此條件的只有結(jié)點v4，因而boundary[va]={v4}，同理可得其余三個模式圖結(jié)點對應(yīng)的boundary為boundary[vb]={v6}，boundary[vc]={v9}，boundary[vd]={v7}。完成剪枝后，后續(xù)在社區(qū)c2上對子圖I{vb,vd}進(jìn)行子圖匹配時，與vb匹配的結(jié)點只從集合{v6}中選取，與vd匹配的結(jié)點只從集合{v7}中選取，因而子圖匹配的過程得到了加速?；谀Ｊ綀D解析的優(yōu)化方面，如分配方案fs1={c1:{va};c2:{vb,vd};c3:{vc}}與分配方案fs2={c1:{vd};c2:{vc,va};c3:{vb}}等價，且fs1的標(biāo)志字符串為“1 2 3 2”，是與它等價的所有分配方案中標(biāo)志字符串最小的，因此當(dāng)處理fs1時，fs1關(guān)于fs2的等價方案映射esf會被存入newallmaps中，其中esf(va)=vd，esf(vb)=vc，esf(vc)=vb，esf(vd)=va。完成了在分配方案fs1下的模式圖與網(wǎng)絡(luò)圖的模式匹配后，{va→v4,vb→v6,vc→v9,vd→v7}是它得到的一個子圖匹配結(jié)果，使用fs1關(guān)于fs2的等價方案映射esf對此匹配結(jié)果進(jìn)行轉(zhuǎn)換得到匹配方式{vd→v4,vc→v6,vb→v9,va→v7}。容易發(fā)現(xiàn)，這種匹配方式是在分配方案fs2下的模式圖與網(wǎng)絡(luò)圖的一個模式匹配結(jié)果。

算法11（見附錄）給出了計算模式圖的同社區(qū)結(jié)點一跳共同鄰居分布表的算法getTwoHopPatternPairs。對于模式圖P中的每個結(jié)點v，記v被分配到的社區(qū)為c，先找到v的出鄰居結(jié)點中所有被分配到的結(jié)點，對于其中的每個結(jié)點n，對它的每個出鄰居結(jié)點n2進(jìn)行判斷，若n2≠v且結(jié)點v和n2被分配到相同社區(qū)（第9行），則將oomessage中存儲的v和n2在c′中的共同鄰居數(shù)加1（算法第10行）。對oimessage和iomessage的處理與此類似，算法11第11～13行計算oimessage，第14～20行計算iomessage。

定理8算法11（getTwoHopPatternPairs）的時間復(fù)雜度為。

算法12（見附錄）給出了對maps中存儲的匹配結(jié)果進(jìn)行合并及結(jié)構(gòu)驗證的算法test_subgraph_match。maps[c]中存儲的是被分配到社區(qū)c的模式圖結(jié)點在模式圖上的導(dǎo)出子圖與c進(jìn)行子圖匹配的結(jié)果，comit是在網(wǎng)絡(luò)圖G=(V,E,C)的社區(qū)集合C上的迭代器，記迭代器當(dāng)前所指社區(qū)為cit（第4行）。算法第5行聲明了用match表示社區(qū)cit上得到的一種子圖匹配結(jié)果。若一個社區(qū)對應(yīng)的迭代器在區(qū)間[C.begin(),comit)中，則稱該社區(qū)為處理過的社區(qū)。從各個處理過的社區(qū)中選出的匹配結(jié)果已成功互相合并，且合并結(jié)果存儲在currentMap中。對于被分配到cit的每個模式圖結(jié)點v（第6行），以及每個被分配到處理過的社區(qū)的模式圖結(jié)點n，若n到v有出邊而與n匹配的結(jié)點currentMap[n]到match中與v匹配的結(jié)點match[v]無出邊，則意味著兩個模式圖結(jié)點間有邊，但與它們匹配的網(wǎng)絡(luò)圖結(jié)點間沒有邊，因此合并的結(jié)果不可能是P與G的子圖匹配結(jié)果，因此當(dāng)前match無法通過結(jié)構(gòu)驗證（第8～10行），直接嘗試合并該社區(qū)上的下一個匹配結(jié)果。對于v到n的出邊的處理方法相同（第11～13行）。若當(dāng)前match與currentMap可以合并，則將當(dāng)前匹配結(jié)果match合并入current-Map中（第14行），隨后開始嘗試合并下一個社區(qū)的匹配結(jié)果（第15、16行），完成合并后回退，將match中的匹配從currentMap中刪除（第18行），準(zhǔn)備開始嘗試合并當(dāng)前社區(qū)的下一個匹配結(jié)果。當(dāng)對于每個被分配了模式圖結(jié)點的社區(qū)，均成功將該社區(qū)上的一個匹配結(jié)果合并入currentMap中時，currentMap中存儲的即是P與G的一個子圖匹配結(jié)果，將合并得到的匹配結(jié)果（currentMap）加入finds中（第1～3行）。

例9在圖4所示網(wǎng)絡(luò)圖G=(V,E,C)上對圖2（b）所示模式圖進(jìn)行社區(qū)間子圖匹配，C={c1,c2,c3}，其中c1對應(yīng)紅色社區(qū)，c2對應(yīng)綠色社區(qū)，c3對應(yīng)藍(lán)色社區(qū)。對于圖2（d）所示的分配方案，得到的maps中，有{va→v4}∈maps[c1]，{vb→v5,vd→v7},{vb→v6,vd→v7}∈maps[c2]，{vc→v9}∈maps[c3]。先嘗試合并{va→v4}、{vb→v5,vd→v7}與{vc→v9}。comit首先指向紅色社區(qū)，記錄currentMap[va]=v4。完成紅色社區(qū)的匹配后，comit指向下一個社區(qū)，即綠色社區(qū)。隨后開始處理綠色社區(qū)，判斷能否將{vb→v5,vd→v7}合并進(jìn)currentMap中。首先看能否將結(jié)點vb與結(jié)點v5匹配，此時社區(qū)c1是已處理過的社區(qū)，因此作為c1中的結(jié)點va，由于模式圖中存在一條從va到vb的出邊，因此對于與va匹配的v4，也要求存在一條從v4到v5的出邊，但是G中不存在這樣一條邊，因此無法通過結(jié)構(gòu)驗證，合并失敗。而{va→v4}、{vb→v6,vd→v7}與{vc→v9}則能通過算法12的驗證而成功合并，因此{(lán)va→v4,vb→v6,vd→v7,vc→v9}是一個正確的匹配結(jié)果。

Fig.4 Directed network used by example 9圖4 例9所用有向網(wǎng)絡(luò)圖

定理9算法12（test_subgraph_match）的時間復(fù)雜度為，其中，M是模式圖中結(jié)點經(jīng)過基于社區(qū)剪枝后得到的候選匹配結(jié)點最多的結(jié)點對應(yīng)的候選匹配結(jié)點集合的大小，Np是模式圖中的結(jié)點數(shù)量。

顯然，有M＜Ncmax，其中Ncmax為結(jié)點數(shù)量最多的社區(qū)中包含的結(jié)點個數(shù)。在良好的社區(qū)劃分下，屬于不同社區(qū)的結(jié)點間的邊數(shù)較少，使基于社區(qū)剪枝后各結(jié)點對應(yīng)的候選匹配結(jié)點集合中元素個數(shù)較少，進(jìn)而使得M值較小。

定理10社區(qū)間子圖匹配算法（算法9）的時間復(fù)雜度為，其中θ(n)表示使用的子圖匹配算法在結(jié)點數(shù)為n時的時間復(fù)雜度，NSuperG為超圖中的結(jié)點數(shù)量，ns為對超圖進(jìn)行結(jié)點可重復(fù)的子圖匹配得到的分配方案的總數(shù)，Ncmax為結(jié)點數(shù)量最多的社區(qū)包含的結(jié)點個數(shù)，M是模式圖中結(jié)點經(jīng)過基于社區(qū)剪枝后得到的候選匹配結(jié)點最多的結(jié)點對應(yīng)的候選匹配結(jié)點集合的大小，是由并行化和模式圖解析帶來的時間效率提升，其中r2＞1。

當(dāng)Np較小時，定理10中給出的時間復(fù)雜度近似等于。

定理11Λ算法經(jīng)CSO方法優(yōu)化后得到的新算法Advanced_Λ（算法7）的時間復(fù)雜度為是通過并行化和匹配等價帶來的時間效率的提升，其中r＞1。

CSO方法中采用了模式圖解析與基于社區(qū)結(jié)構(gòu)的剪枝兩種策略對子圖匹配算法進(jìn)行優(yōu)化。

下面具體分析這兩種優(yōu)化策略的優(yōu)化效果的影響因素。模式圖的解析利用匹配等價關(guān)系由計算得到的社區(qū)間子圖匹配結(jié)果推斷出其他一些社區(qū)間子圖匹配結(jié)果，因此，對于給定的網(wǎng)絡(luò)圖和模式圖，社區(qū)間子圖匹配的能得到的結(jié)果越多，應(yīng)用模式圖解析的結(jié)果推斷得到的結(jié)果很可能越多，從而使得模式圖解析的優(yōu)化效果越明顯。另外，根據(jù)模式圖解析的過程容易發(fā)現(xiàn)，模式圖中找到的互相匹配等價的子圖越多，能通過推斷得到的匹配結(jié)果就越多，使得優(yōu)化效果越明顯。對于CSO方法的另一種優(yōu)化策略，即基于社區(qū)結(jié)構(gòu)的剪枝，當(dāng)網(wǎng)絡(luò)圖相同時，模式圖越稠密，模式圖中結(jié)點對應(yīng)的候選匹配結(jié)點就越少，即剪枝效果就越好。該優(yōu)化策略的具體優(yōu)化效果與原子圖匹配算法Λ有關(guān)，例如，當(dāng)模式圖變得稠密時，Λ算法會嘗試的錯誤匹配的數(shù)量變少，使其匹配用時減少。同時，由于模式圖變得稠密，模式圖中各結(jié)點對應(yīng)的候選匹配結(jié)點減少，即剪枝效果變好，使Advanced_Λ算法嘗試了更少的匹配方式，但由于Λ算法嘗試的錯誤匹配的數(shù)量也減少了，因此減少的錯誤匹配的數(shù)量可能增加也可能減少，從而導(dǎo)致基于社區(qū)結(jié)構(gòu)的剪枝的優(yōu)化效果不穩(wěn)定。因此，基于社區(qū)結(jié)構(gòu)的剪枝的剪枝效果更好并不一定意味著其優(yōu)化效果也更好。

對于CSO方法中使用的兩種優(yōu)化策略中模式圖解析利用模式圖上的匹配等價的子圖，不計算可以推斷出的子圖匹配結(jié)果；基于社區(qū)結(jié)構(gòu)的剪枝使用社區(qū)信息減少了子圖匹配過程中錯誤匹配的次數(shù)。對于任意的子圖匹配算法上述兩種策略都能有效減少計算量，從而減少子圖匹配的時間開銷，因此CSO方法對任意子圖匹配算法都是有效的。

上述Advanced_Λ的算法中，模式圖的解析和基于社區(qū)結(jié)構(gòu)的剪枝這兩部分的優(yōu)化算法與Λ算法之間是低耦合的，因此能方便地使用CSO方法對各種子圖匹配算法進(jìn)行優(yōu)化。

5.4 CSO方法正確性證明

首先，可以證明在子圖匹配過程中，對于互相匹配等價的兩個模式圖P1=(Vp1,Ep1)和P2=(Vp2,Ep2)，若P1與網(wǎng)絡(luò)圖G=(V,E,C)進(jìn)行子圖匹配得到了若干匹配結(jié)果，在這些匹配結(jié)果上應(yīng)用P1關(guān)于P2的對稱雙射f，得到的是P2與G的所有子圖匹配結(jié)果。這里的“應(yīng)用P1關(guān)于P2的對稱雙射f”指的是：記P1與G的一個匹配結(jié)果為match，定義match′為一個新的匹配結(jié)果。?match[u]=v，其中u∈Vp1,v∈V，令match′[f(u)]=v，得到的match′即是對匹配match應(yīng)用P1關(guān)于P2的對稱雙射f得到的新的匹配結(jié)果。因此，可以證得模式圖解析的優(yōu)化策略的正確性。

接著，根據(jù)基于社區(qū)結(jié)構(gòu)的剪枝的具體策略容易證明該優(yōu)化策略的正確性。

隨后，證明將子圖匹配流程分為社區(qū)內(nèi)子圖匹配和社區(qū)間子圖匹配兩個過程不會得到錯誤的結(jié)果也不會丟失任意一個正確的結(jié)果。

最后，綜合上述的結(jié)論可以證明CSO方法的正確性。

定理12CSO方法是正確的。

6 實驗

鑒于VF2[5]算法是影響最為廣泛的子圖匹配算法之一[27]，本章用CSO對VF2算法進(jìn)行優(yōu)化。

6.1 實驗準(zhǔn)備

本實驗使用了三個合成數(shù)據(jù)集（Opera_1000、Opera_10000和Opera_100000）與三個真實數(shù)據(jù)集（Email[28]、DBLP_5k[29]和 Friendster_5k[29]）。其中，Email是email-Eu-core的簡稱，該數(shù)據(jù)集是一個歐洲大型研究機(jī)構(gòu)人員的郵件往來數(shù)據(jù)，網(wǎng)絡(luò)中的有向邊表示邊起點對應(yīng)的用戶給邊終點對應(yīng)的用戶發(fā)送了至少一封郵件，相同部門的人對應(yīng)的結(jié)點構(gòu)成一個社區(qū)；DBLP_5k數(shù)據(jù)集中記錄的是計算機(jī)科學(xué)領(lǐng)域研究論文的作者間的關(guān)系，每個結(jié)點代表一個人，若兩人共同完成了至少一篇論文，則為他們對應(yīng)的結(jié)點間添加一條邊，在一種給定出版物上發(fā)表過論文的所有人對應(yīng)的結(jié)點構(gòu)成一個社區(qū)，從中選擇質(zhì)量最高的5 000個社區(qū)構(gòu)成DBLP_5k數(shù)據(jù)集；Friendster_5k數(shù)據(jù)集描述的是人與人之間的好友關(guān)系，每個結(jié)點表示一個人，兩個人互為好友則為他們對應(yīng)的結(jié)點間添加一條邊，將人自發(fā)形成的群組作為社區(qū)，選擇其中質(zhì)量最高的5 000個社區(qū)構(gòu)成Friend-ster_5k數(shù)據(jù)集。

這些數(shù)據(jù)集的統(tǒng)計信息如表1所示。需要注意的是，在具體實驗中，無向圖中的每條邊表示為兩條對應(yīng)的有向邊。于是，表1中無向數(shù)據(jù)集的平均度數(shù)等于表格中數(shù)值的兩倍。

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

實驗中共使用了五種不同的模式圖，分別為三完全圖（圖5（a），簡記為K3）、四完全圖（圖5（b），簡記為K4）、五結(jié)點稀疏圖（圖5（c），簡記為P5sp）、五結(jié)點對稱圖（圖5（d），簡記為P5sy）和四結(jié)點對稱圖（圖5（e），簡記為P4sy）。

Fig.5 Patterns used in experiments圖5 實驗中使用的模式圖

本文實驗所有代碼均為C++，開發(fā)工具是VS 2015，操作系統(tǒng)為Windows 7，CPU Intel Core i5 2.00 GHz，內(nèi)存4GB。優(yōu)化后VF2算法簡記為AVF2（Advanced_VF2），參數(shù)batch_size的值設(shè)置為1 000 000。

6.2 性能對比實驗

本節(jié)在多個數(shù)據(jù)集上對VF2算法與AVF2算法的性能進(jìn)行了測試，并對測試結(jié)果進(jìn)行分析。VF2算法和AVF2算法在不同數(shù)據(jù)集和不同模式圖上的效率對比情況如表2所示。用優(yōu)化率來衡量CSO方法對VF2算法的優(yōu)化效果，優(yōu)化率的計算方法是（原算法用時-優(yōu)化后算法的用時）/原算法用時，優(yōu)化率的上界是1，其值越接近1表示優(yōu)化效果越好。

Table 2 Comparison between efficiency of VF2 andAVF2表2 VF2與AVF2效率比較

實驗中VF2算法和AVF2算法在相同數(shù)據(jù)集上對相同模式圖進(jìn)行匹配時得到相同的結(jié)果，證明了CSO方法的正確性。

分析表2所示實驗結(jié)果，對于算法VF2和AVF2能在24 h內(nèi)完成的匹配任務(wù)，AVF2相比VF2用時普遍減少55%以上，其中在DBLP_5k數(shù)據(jù)集下用K3進(jìn)行子圖匹配時優(yōu)化效果最明顯，優(yōu)化率達(dá)到了0.94。另一個優(yōu)化效果明顯的例子是在Email數(shù)據(jù)集上用P5sp進(jìn)行模式匹配，VF2在此任務(wù)上的用時為21.5 h，而AVF2算法只用了1.6 h。

這些測試結(jié)果均表明，AVF2算法相比VF2算法時間開銷大大減小，證明了CSO方法的有效性。

通過分析表2中三個數(shù)據(jù)集上的實現(xiàn)結(jié)果，可以發(fā)現(xiàn)與合成數(shù)據(jù)集上的優(yōu)化效果相比，在真實數(shù)據(jù)集上的優(yōu)化率提高了0.2以上。這是因為相比合成數(shù)據(jù)集，真實數(shù)據(jù)集對應(yīng)的網(wǎng)絡(luò)圖稀疏得多，所以屬于不同社區(qū)的結(jié)點之間的邊更少，CSO方法中基于社區(qū)結(jié)構(gòu)的剪枝效果更明顯，因此子圖匹配算法性能提升更大。生產(chǎn)生活中使用的網(wǎng)絡(luò)圖通常較為稀疏，這意味著本文的CSO方法在現(xiàn)實應(yīng)用中能產(chǎn)生很好的效果，具有重要的現(xiàn)實意義。

在DBLP_5k數(shù)據(jù)集上使用模式圖P5sp和P5sy進(jìn)行實驗時，VF2算法和AVF2算法在24 h內(nèi)均無法完成匹配，這是因為AVF2算法是用CSO方法對VF2算法進(jìn)行優(yōu)化得到的，在AVF2中使用VF2進(jìn)行社區(qū)內(nèi)子圖匹配。隨著數(shù)據(jù)規(guī)模的增大和模式圖的復(fù)雜化，VF2的時間開銷大幅增加，使得AVF2算法的耗時隨之增加。

上述實驗證明了CSO方法的有效性，值得探究的一點是CSO方法中使用的兩種策略各自有怎樣的優(yōu)化效果。下面結(jié)合具體實驗比較基于社區(qū)結(jié)構(gòu)進(jìn)行剪枝和解析模式圖兩種策略對子圖匹配算法的優(yōu)化效果。從算法AVF2中將基于社區(qū)結(jié)構(gòu)進(jìn)行剪枝的相關(guān)優(yōu)化刪掉得到新的算法NC_AVF2，從算法AVF2中將模式圖解析相關(guān)的優(yōu)化刪掉得到新的算法NP_AVF2。在Email和Opera_1000兩個數(shù)據(jù)集上以模式圖K3、K4和P4sy為例進(jìn)行子圖匹配，測試上述兩種算法的用時，并將測試結(jié)果與AVF2算法進(jìn)行比較。

由表3可以發(fā)現(xiàn)，在兩個數(shù)據(jù)集上，NC_AVF2和NP_AVF2相比算法AVF2用時均有所增加，其中在Email數(shù)據(jù)集上刪去任意一種優(yōu)化策略均會導(dǎo)致用時增加40%以上，這表明CSO方法中使用的兩個優(yōu)化策略都是有效的。

Table 3 Comparison ofAVF2,NC_AVF2 and NP_AVF2 algorithm表3 AVF2算法、NC_AVF2算法和NP_AVF2算法比較

在Email數(shù)據(jù)集上，模式圖解析的優(yōu)化效果均達(dá)到40%以上，而在Opera_1000數(shù)據(jù)集上其優(yōu)化效果卻不明顯，其原因在于，根據(jù)第5.3節(jié)中的分析，模式圖解析的優(yōu)化效果受社區(qū)間子圖匹配結(jié)果數(shù)量的影響，而在Opera_1000數(shù)據(jù)集上的社區(qū)間子圖匹配結(jié)果的數(shù)量遠(yuǎn)少于Email數(shù)據(jù)集，因此導(dǎo)致Opera_1000數(shù)據(jù)集上模式圖解析的優(yōu)化效果不明顯。以模式圖K4為例，在Email數(shù)據(jù)集上，共有1 498 656個社區(qū)間子圖匹配結(jié)果，占總匹配結(jié)果數(shù)的82.3%，而在Opera_1000數(shù)據(jù)集上，僅有2 184個社區(qū)間子圖匹配結(jié)果，占總匹配結(jié)果數(shù)量的0.02%，這就導(dǎo)致在Opera_1000數(shù)據(jù)集上模式圖解析優(yōu)化效果遠(yuǎn)不如Email數(shù)據(jù)集。

值得注意的是，模式圖K4與P4sy上的實驗結(jié)果驗證了第5.3節(jié)中關(guān)于基于社區(qū)結(jié)構(gòu)的剪枝的優(yōu)化效果與模式圖稠密程度的關(guān)系的分析。雖然K4比P4sy更稠密，使得在網(wǎng)絡(luò)圖相同的情況下，P4sy中的各結(jié)點對應(yīng)更多的候選匹配結(jié)點，即基于社區(qū)結(jié)構(gòu)的剪枝的剪枝效果更差，嘗試了更多的匹配方式，但在模式圖為P4sy時VF2算法嘗試的錯誤的匹配方式也增加了，且增加的幅度更大，這使得基于社區(qū)結(jié)構(gòu)的剪枝在模式圖為P4sy時比模式圖為K4時有更明顯的優(yōu)化效果。這驗證了第5.3節(jié)中分析得到的基于社區(qū)結(jié)構(gòu)的剪枝的剪枝效果更好并不代表其優(yōu)化效果也更好的結(jié)論。

6.3 可擴(kuò)展性分析

CSO方法的可擴(kuò)展性體現(xiàn)在其優(yōu)化效果隨數(shù)據(jù)集規(guī)模增大的變化情況。在本實驗中，CSO方法的可擴(kuò)展性具體表現(xiàn)為隨著數(shù)據(jù)集規(guī)模的擴(kuò)大，AVF2算法相對VF2算法的優(yōu)化率的變化情況。以模式圖K3為例，在不同規(guī)模的數(shù)據(jù)集下的子圖匹配用時如表4所示。

Table 4 Results of scalability tests表4 可擴(kuò)展性測試結(jié)果

根據(jù)實驗結(jié)果可以看出，隨著網(wǎng)絡(luò)圖規(guī)模的不斷擴(kuò)大，優(yōu)化率逐漸提升，在Friendster數(shù)據(jù)集下，優(yōu)化率接近1。這意味著隨著網(wǎng)絡(luò)圖數(shù)據(jù)量的增大，CSO方法的優(yōu)化效果越來越明顯。因此，CSO方法具有很好的可擴(kuò)展性。

6.4 參數(shù)敏感性分析

本節(jié)分析CSO方法的參數(shù)敏感性。在CSO方法中，batch_size是一個重要的參數(shù)，其用途是：當(dāng)superMatchList中存儲了batch_size個分配方案時，調(diào)用算法10（rematch）批量地處理這些分配方案。本實驗中，CSO方法的參數(shù)敏感性體現(xiàn)在AVF2算法的子圖匹配用時隨batch_size的變化情況。

以在Email數(shù)據(jù)集上用模式圖K4進(jìn)行子圖匹配為例測試CSO方法的參數(shù)敏感性。在Email數(shù)據(jù)集上使用AVF2算法進(jìn)行子圖匹配時，共能獲得790 593種分配方案。在1到790 593的范圍內(nèi)選擇若干值作為batch_size的取值進(jìn)行實驗，得到表5中的實驗結(jié)果。

Table 5 Execution time of AVF2 with different values of batch_size表5 不同batch_size取值時AVF2算法用時

從表5可以看出，隨著batch_size從小到大接近實際的分配方案數(shù)，子圖匹配的用時逐漸減少，這表明當(dāng)batch_size小于實際分配方案數(shù)時，更大的batch_size能通過減少rematch執(zhí)行次數(shù)減少算法用時。另一方面，隨著batch_size的增大，AVF2算法用時減少的幅度不斷減小，當(dāng)batch_size值接近實際分配方案數(shù)時，AVF2算法的用時基本不再隨著batch_size的變化而變化。

需要注意的是，更大的batch_size值就意味著要在存儲待處理分配方案的列表superMatchList中存儲更多的待處理分配方案，因此會帶來更大的內(nèi)存開銷。在選擇參數(shù)batch_size的值時，需要權(quán)衡用時和內(nèi)存開銷，合理選擇batch_size的值。

7 結(jié)束語

本文提出了一種基于社區(qū)結(jié)構(gòu)的子圖匹配算法優(yōu)化方法CSO。CSO方法通過將子圖匹配流程劃分為社區(qū)內(nèi)子圖匹配和社區(qū)間子圖匹配兩個過程實現(xiàn)了匹配過程的并行化；通過解析模式圖中的匹配等價的子圖減少了子圖匹配過程中的計算量；通過依據(jù)社區(qū)結(jié)構(gòu)進(jìn)行剪枝減少了匹配過程中錯誤匹配發(fā)生的次數(shù)。使用上述策略，CSO方法能大大提升子圖匹配算法的計算速度。實驗結(jié)果表明CSO方法具有高效性和很好的可擴(kuò)展性。未來將嘗試通過并行化方法同時進(jìn)行社區(qū)內(nèi)子圖匹配和社區(qū)間子圖匹配，進(jìn)一步提升子圖匹配算法的運行速度。

附錄：

算法1模式圖中全等點對的查找算法getEqualNodes

輸入：P=(Vp,Ep)。

輸出：equalNodes,patternEqualClass。

1.for each nodev∈Vp

2.將(v,v)插入equalNodes中

3.for each nodevi∈Vp

4.for each nodevj∈Vp-{vk|k≤i}

5.ifSize(OutNeigh(vi))≠

Size(OutNeigh(vj))or Size(InNeigh(vi))≠

Size(InNeigh(vj))

6.continue

7.ifOutNeigh(vi)-{vi,vj} ==OutNeigh(vj)-{vi,vj} andInNeigh(vi)-{vi,vj}==InNeigh(vj)-{vi,vj}andvi和vj間存在雙向邊或不存在邊

8.將(vi,vj)、(vj,vi)插入equalNodes中

9.classNumber=0

10.for each nodev∈Vp

11.ifpatternEqualClass[v]≠NULL

12.continue

13.classNumber=classNumber+1

14.for each noden∈equalNodes[v]

15.patternEqualClass[node]=classNumber

16.returnequalNodes,patternEqualClass

算法2模式圖中對稱點對的查找算法getSymmetryNodes

輸入：P=(Vp,Ep),symm。

輸出：symmetryNodes。

1.for each nodevi∈Vp

2.for each nodevj∈Vp-{vk|k≤i}

3.if(vi,vj)∈equalNodes

4.continue

5.set＜int＞used//定義存儲使用過的結(jié)點的集合used

6.symmetryTest(P,vi,vj,symm,used)

7.for each nodevi∈Vp

8.for each nodevj∈Vp

9.ifsymm[vi][vj]==True

10.將(vi,vj)插入symmetryNodes中

11.returnsymmetryNodes

算法3遞歸查找對稱點對的算法symmetryTest

輸入：P=(Vp,Ep),vi,vj,symm,used。

輸出：isSymmetry。

1.if(vi,vj)∈equalNodes

2.returnTrue

3.ifsymm[vi][vj]≠NULL

4.returnsymm[vi][vj]

5.ifSize(OutNeigh(vi))≠Size(OutNeigh(vj))orSize(InNeigh(vi))≠Size(InNeigh(vj))

6.設(shè)置symm[vi][vj],symm[vj][vi]為False

7.returnFalse

8.將vi、vj插入used中

9.unusedNeighs1=OutNeigh(vi)-used

10.unusedNeighs2=OutNeigh(vj)-used

11.ifSize(unusedNeighs1)≠Size(unusedNeighs2)

12.設(shè)置symm[vi][vj],symm[vj][vi]為False

13.從used中刪除vi和vj

14.returnFalse

15.for eachnode1∈unusedNeighs1

16.find=False

17.for eachnode2∈unusedNeighs2

18.ifsymmetryTest(G,node1,node2,symm,used)==True

19.find=True

20.從unusedNeighs2中刪除node2

21.break

22.if find==False

23.設(shè)置symm[vi][vj],symm[vj][vi]為False

24.從used中刪除vi和vj

25.returnFalse

26.仿照9～25行對結(jié)點的入鄰居進(jìn)行處理

27.設(shè)置symm[vi][vj],symm[vj][vi]為True

28.從used中刪除vi和vj

29.returnTrue

算法4匹配等價的子圖的查找算法handleMatchPattern

輸入：P=(Vp,Ep),isomorphicList,isomap,matchedModel,matchEq。

輸出：matchEq。

1.vector＜int＞current//聲明了存儲模式圖子圖包含的結(jié)點的向量current

2.matchEq=retrivalNodes(current,0,isomorphicList,isomap,matchedModel,P,False,matchEq)

3.for each(I,listI)∈matchEq

4.SI=isomap[I]

5.for eachIt∈listI

6.ifisomap[It]≠SI

7.從matchEq[I]中刪除It

8.returnmatchEq

算法5遍歷模式圖結(jié)點能構(gòu)成的所有子圖并構(gòu)造匹配等價的子圖之間的映射的算法retrivalNodes

輸入：current,pos,isomorphicList,isomap,matchedModel,P=(Vp,Ep),added,matchEq。

輸出：matchEq。

1.ifadded==True

2.構(gòu)造由current對應(yīng)的模式圖P的導(dǎo)出子圖Icurrent

3.if Size(current)≥1

4.set＜int＞record//聲明存儲使用過的結(jié)點的集合record

5.vector＜int＞t//聲明存儲current通過對稱點替換和全等點替換得到的新結(jié)點列表t

6.matchEq=getAllMatchNodes(P,current,0,t,record,False,matchEq)

7.succeed=False

8.for(Si,Ii)∈matchedModel

9.ifSize(Icurrent)≠Size(Ii)

10.continue

11.ifIcurrent與Ii同構(gòu)

12.將Icurrent加到isomorphicList[Si]末尾

13.isomap[Icurrent]=Si

14.succeed=True

15.break

16.ifsucceed==False

17.計算Icurrent的特征字符串Scurrent

18.將(Scurrent,Icurrent)插入matchedModel

19.將Icurrent加到isomorphicList[Scurrent]末尾

20.isomap[Icurrent]=Scurrent

21.ifpos≥Size(V)

22.returnmatchEq

23.matchEq=retrivalNodes(current,pos+1,isomorphicList,isoMap,matchedModel,P,False,matchEq)

24.將vpos加到current末尾

25.matchEq=retrivalNodes(current,pos+1,isomorphicList,

isomap,matchedModel,P,True,matchEq)

26.彈出current最后一項

27.returnmatchEq

算法6計算所有與輸入的圖滿足鄰域范圍條件的圖的算法getAllMatchNodes

輸入：P=(Vp,Ep),current,pos,t,record,hasSymm,matchEq。

輸出：matchEq。

1.ifpos≥Size(current)

2.分別構(gòu)造current和t在P上對應(yīng)的導(dǎo)出子圖Icurrent與It

3.用f表示Icurrent得到It過程中進(jìn)行的所有替換，每個f(u)=v表示將Icurrent中的結(jié)點u替換成了v，對于未被替換的結(jié)點n，令f(n)=n。f即是Icurrent關(guān)于It的擴(kuò)展對稱映射

4.ifhasSymm==True

5.若Icurrent與It不滿足鄰域范圍規(guī)則，returnmatchEq

6.ifIcurrent與It包含的結(jié)點相同

7.if is_sorted(t)

8.將It插入matchEq[Icurrent]中 //It是t在P上對應(yīng)的導(dǎo)出子圖

9.else 將It插入matchEq[Icurrent]中

10.else若t中屬于相同全等點組的結(jié)點的ID均升序排列

11.將It插入matchEq[Icurrent]中

12.returnmatchEq

13.for each(current[pos],n)∈equalNodes

14.ifnnot inrecord

15.將n加到t的末尾

16.將n插入record中

17.matchEq=getAllMatchNodes(G,current,pos+1,t,record,hasSymm,matchEq)

18.彈出t的最后一項

19.從record中刪除n

20.for each(current[pos],n)∈symmetryNodes

21.ifnnot inrecord

22.將n加到t的末尾

23.將n插入record中

24.matchEq=getAllMatchNodes(G,current,pos+1,t,

record,True,matchEq)

25.彈出t的最后一項

26.從record中刪除n

27.returnmatchEq

算法7使用CSO方法優(yōu)化L后得到的新算法Advanced_L。

輸入：G=(V,E,C),P=(Vp,Ep),batch_size。

輸出：子圖匹配的結(jié)果。

1.根據(jù)G生成超圖SuperG

2.找出P中所有互相匹配等價的子圖，存儲在matchEq中

3.ins←intraCommPatternMatch(G,P) //社區(qū)內(nèi)子圖匹配

4.outs←interCommPatternMatch(G,P,SuperG,batch_size,matchEq)//社區(qū)間子圖匹配

5.returnins+outs

算法8并行的社區(qū)內(nèi)子圖匹配算法intraCommPattern-Match

輸入：G=(V,E,C)，P=(Vp,Ep)。

輸出：ins。

1.parallel for ea ch communitycomminG

2.在社區(qū)comm中使用Λ算法對P進(jìn)行子圖匹配，將結(jié)果存儲到ins中

3.returnins

算法9社區(qū)間子圖匹配算法interCommPatternMatch

輸入：G=(V,E,C),P=(Vp,Ep),SuperG,batch_size,matchEq。

輸出：outs。

1.superMatchList=[]//聲明存儲分配方案的列表superMatchList

2.在超圖SuperG上用模式圖P進(jìn)行結(jié)點可重復(fù)的子圖匹配，將得到的分配方案superMatch插入superMatchList中，每當(dāng)superMatchList內(nèi)分配方案個數(shù)超過batch_size，執(zhí)行算法第3行

3.rematch(G,P,SuperG,superMatchList,outs,matchEq)

4.若尚未完成結(jié)點可重復(fù)的子圖匹配，清空superMatch-List并執(zhí)行算法第2行

5.returnouts

算法10對算法9中得到的模式圖分配方案列表super-MatchList進(jìn)行處理的算法rematch

輸入：G=(V,E,C),P=(Vp,Ep),SuperG,superMatchList,outs,matchEq。

輸出：outs。

1.獲取離線計算得到的commOutBoundary,commInBoundary,degreePosOut,degreePosIn

2.parallel for eachsuperMatch∈superMatchList

3.ifSize(superMatch)==1

4.continue

5.for each(c,vlist)∈superMatch

6.ifSize(c)＜Size(vlist)

7.continue

8.unordered_map＜int,vector＜int＞＞boundary//聲 明記錄能與模式圖中結(jié)點匹配的網(wǎng)絡(luò)圖G中的結(jié)點列表的字典boundary

9.for each(c,vlist)∈superMatch

10.for each nodev∈vlist

11.unordered_map＜int,int＞outds,inds//聲 明記錄模式圖中結(jié)點v與被分配到各社區(qū)的所有模式圖結(jié)點間的出邊總數(shù)和入邊總數(shù)的字典

12.hasOut,hasIn=False

13.for each(c′,vlist′)∈superMatch

14.ifc==c′

15.continue

16.forv′∈vlist′

17.ifhasedge(v,v′)

18.outds[c′]++

19.hasOut=True

20.ifhasedge(v′,v)

21.inds[c′]++

22.hasIn=True

23.ifhasOut==True

24.根據(jù)commOutBoundary、degreePosOut及outds縮小v的候選匹配結(jié)點集合，若候選集合為空，直接執(zhí)行第一行

25.ifhasIn==True

26.根據(jù)commInBoundary、degreePosIn及inds縮小v的候選匹配結(jié)點集合，若候選集合為空，直接執(zhí)行第一行

27.map＜int,int＞superMatchMap//聲明記錄模式圖中每個結(jié)點被分配到哪個社區(qū)的字典superMatchMap

28.for each(c,vlist)∈superMatch

29.for each nodev∈vlist

30.superMatchMap[v]=c

31.mystr=""

32.Sort(Vp)

33.for ea ch nodev∈Vp

34.mystr+=to_string(superMatchMap[v])+""

35.使用matchEq找到與當(dāng)前分配方案等價的分配方案，并比較它們的標(biāo)志字符串，若mystr不是所有標(biāo)志字符串中最小的，則結(jié)束匹配并執(zhí)行第一行

36.將當(dāng)前關(guān)于與它等價的分配方案的等價方案映射存儲到newallmaps中

37.oomessage,oimessage,iomessage=getTwoHopPatternPairs(P,superMatchMap)

38.根據(jù)分配方案，對被分配了模式圖結(jié)點的社區(qū)與被分配的結(jié)點集合對應(yīng)的模式圖導(dǎo)出子圖使用Λ算法進(jìn)行子圖匹配，其中，模式圖中各結(jié)點能與G中哪些結(jié)點匹配由boundary給定。匹配中使用同社區(qū)結(jié)點一跳共同鄰居分布表進(jìn)行剪枝。若匹配失敗，則不再處理當(dāng)前分配方案，并執(zhí)行第一行，否則將各社區(qū)c上的匹配結(jié)果存儲到maps[c]中

39.currentMap={} //聲明用于記錄已完成結(jié)構(gòu)驗證的匹配的字典

40.finds={} //聲明用于存儲完成合并和結(jié)構(gòu)驗證得到的模式圖P在網(wǎng)絡(luò)圖G上的匹配結(jié)果

41.comit=C.begin() //C是G對應(yīng)的社區(qū)集合，聲明commit為C上的迭代器

42.test_subgraph_match(G,P,superMatch,maps,comit,currentMap,finds)

43.對newallmaps中存儲的每種映射，將finds中的所有匹配結(jié)果通過映射得到新的匹配結(jié)果，并將得到的匹配結(jié)果存儲到outs中

44.returnouts

算法11模式圖的同社區(qū)結(jié)點一跳共同鄰居分布表的計算算法getTwoHopPattern Pairs

輸入：P=(Vp,Ep)，superMatchMap。

輸出：oomessage,oimessage,iomessage。

1.for each nodev∈Vp

2.cv←superMatchMap[v]

3.for each noden∈OutNeigh(v)

4.cn←superMatchMap[n]

5.ifcv==cn

6.continue

7.for each noden2∈OutNeigh(n)

8.cn2←superMatchMap[n2]

9.ifv≠n2且cv==cn2

10.oomessage[v][n2][cn]++

11.for each noden2∈InNeigh(n)

12.ifv≠n2且cv==cn2

13.oimessage[v][n2][cn]++

14.for each noden∈InNeigh(v)

15.cn←superMatchMap[n]

16.ifcv==cn

17.continue

18.forn2∈OutNeigh(n)

19.Ifv≠n2且cv==cn2

20.iomessage[v][n2][cn]++

21.returnoomessage,oimessage,iomessage

算法12對maps中存儲的匹配結(jié)果進(jìn)行合并及結(jié)構(gòu)驗證的算法test_subgraph_match

輸入：G=(V,E,C),P=(Vp,Ep),superMatch,maps,comit,currentMap,finds。

輸出：finds。

1.ifcomit==C.end()

2.將currentMap加到finds末尾

3.returnfinds

4.cit←C[comit]

5.for eachmatch∈maps[cit]

6.for each nodev∈superMatch[cit]

7.對被分配到處理過的社區(qū)的各結(jié)點n，記與它匹配的結(jié)點vn=currentMap[n]。

8.ifP.hasedge(n,v)

9.if！G.hasedge(vn,match[v])

10.執(zhí)行第5行

11.ifP.hasedge(v,n)

12.if！G.hasedge(match[v],vn)

13.執(zhí)行第5行

14.將match中的匹配加入currentMap中

15.comit++

16.test_subgraph_match(G,C,P,superMatch,maps,comit,currentMap,finds)

17.comit--

18.將match中的匹配從currentMap中刪除

19.returnfinds