使用社區(qū)結(jié)構(gòu)信息的子圖匹配算法優(yōu)化方法*

樓昀愷，王朝坤

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

1 引言

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

2.1 子圖匹配算法

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

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

與上述方法相比，基于索引的方法能減少子圖匹配的時(shí)間開銷，其中常見的幾種方法包括R-Join算法[6]、GraphQL[22]算法、基于 SPath 索引的方法[23]、TurboISO算法[24]等。R-Join算法[6]構(gòu)造了基于聚合的R-Join索引；GraphQL[22]對(duì)圖中每個(gè)結(jié)點(diǎn)，為到它距離小于等于r的結(jié)點(diǎn)構(gòu)成的子圖建立索引；Zhao等[23]提出了SPath索引的概念，對(duì)每個(gè)結(jié)點(diǎn)v，將和v之間距離小于等于給定值k的結(jié)點(diǎn)的標(biāo)簽編碼為一個(gè)簽名，隨后對(duì)v與它的簽名間建立索引。在網(wǎng)絡(luò)圖上構(gòu)造索引的方法存在索引占用空間較大的問(wèn)題，并且對(duì)數(shù)據(jù)量較大的圖而言，構(gòu)造索引也有較大的時(shí)間開銷。TurboISO[24]算法解析模式圖中具有等價(jià)關(guān)系的結(jié)點(diǎn)生成鄰域等價(jià)類樹（NECtree），使用樹中信息指導(dǎo)匹配過(guò)程中的剪枝。Bi等[25]通過(guò)推遲笛卡爾積的計(jì)算和引入緊湊路徑索引的數(shù)據(jù)結(jié)構(gòu)的方式優(yōu)化TurboISO[24]算法。TurboISO算法對(duì)模式圖進(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é)點(diǎn)構(gòu)成的。社區(qū)內(nèi)的結(jié)點(diǎn)滿足與本社區(qū)中其他結(jié)點(diǎn)聯(lián)系緊密，與其他社區(qū)的結(jié)點(diǎn)聯(lián)系松散的特點(diǎ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）來(lái)評(píng)估網(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]再次對(duì)此方法進(jìn)行改進(jìn)，提出了CNM方法，進(jìn)一步提升了社區(qū)發(fā)現(xiàn)的效率。Blondel等[13]于2008年提出的Louvain算法是一種層次化的貪心的基于最優(yōu)化模塊度的算法，它通過(guò)社區(qū)間的合并自下而上地進(jìn)行社區(qū)發(fā)現(xiàn)，將時(shí)間復(fù)雜度減小為O(nlbn)。

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

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

3 基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

4 模式圖解析算法

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

4.1 全等點(diǎn)對(duì)查找算法

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

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

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

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

Fig.1 Two examples of patterns圖1 兩個(gè)模式圖的例子

定理1算法1（getEqualNodes）返回的equalNodes中存儲(chǔ)的是P中所有的全等點(diǎn)對(duì)。

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

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

4.2 對(duì)稱點(diǎn)對(duì)查找算法

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

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

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

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

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

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

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

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

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

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

4.3 匹配等價(jià)的子圖的查找算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 CSO方法概述

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

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

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

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

定義14（等價(jià)的分配方案）給定網(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的兩個(gè)不同的分配方案，則fs1與fs2是等價(jià)的分配方案，若：（1）C1=C2；（2）?ci∈C1，fs1(ci)與fs2(ci)在P上的導(dǎo)出子圖匹配等價(jià)。用AFS(fs)表示所有與分配方案fs等價(jià)的分配方案（含fs）。

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

定義15（等價(jià)方案映射）給定網(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的兩個(gè)不同的分配方案，且fs1和fs2等價(jià)。定義映射esf:Vp→Vp，稱esf是fs1關(guān)于fs2的等價(jià)方案映射，若esf滿足：（1）?ci∈C1，記fs1(ci)在P上的導(dǎo)出子圖關(guān)于fs2(ci)在P上的導(dǎo)出子圖的對(duì)稱雙射為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é)點(diǎn)集合{v1,v2,…,vk}在模式圖上對(duì)應(yīng)的導(dǎo)出子圖為I{v1,v2,…,vk}。因?yàn)閳D2（b）上I{va}與I{vd}，I{vb,vd}與I{vc,va}，I{vc}與I{vb}分別匹配等價(jià)，所以fs1和fs2是等價(jià)的分配方案。fs1關(guān)于fs2的等價(jià)方案映射esf滿足esf(va)=vd，esf(vb)=vc，g(vc)=vb，esf(vd)=va。

Fig.2 Diagrams for explainingAdvanced_Λ algorithm圖2 Advanced_Λ算法說(shuō)明用圖

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

例5如圖3模式圖所示，圖中相同顏色的結(jié)點(diǎn)被分配到同一個(gè)社區(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é)點(diǎn)，若G中兩社區(qū)c1、c2間存在有向邊，則為這兩個(gè)社區(qū)在SuperG中對(duì)應(yīng)的結(jié)點(diǎn)間也添加一條同向的有向邊；若G中某社區(qū)內(nèi)存在兩個(gè)不同的結(jié)點(diǎn)，且它們之間存在有向邊，則為這個(gè)社區(qū)在SuperG中對(duì)應(yīng)的結(jié)點(diǎn)添加自環(huán)。接著，第2行根據(jù)第4.3節(jié)中給出的算法4（匹配等價(jià)的子圖的查找算法），對(duì)模式圖P中的每個(gè)子圖Psub進(jìn)行處理，得到P中與Psub匹配等價(jià)的所有子圖，并將這些子圖存儲(chǔ)在matchEq[Psub]中。

第3、4行進(jìn)行具體的子圖匹配。在Advanced_Λ算法中，子圖匹配過(guò)程分為社區(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)，通過(guò)并行計(jì)算同時(shí)在多個(gè)社區(qū)內(nèi)使用Λ算法進(jìn)行子圖匹配，從而提升子圖匹配的效率。

例6以圖2中（a）為網(wǎng)絡(luò)圖，（b）為模式圖進(jìn)行子圖匹配，則通過(guò)算法8的計(jì)算，在紅色社區(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ū)中無(wú)匹配結(jié)果，在綠色社區(qū)中的匹配結(jié)果與紅色社區(qū)中的結(jié)果類似，這里不再列舉。

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

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

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

例7圖2（c）是圖2（a）對(duì)應(yīng)的超圖SuperG，在此超圖上對(duì)圖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）對(duì)應(yīng)的是分配方案{c1:{va};c2:{vb,vd};c3:{vc}}。

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

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

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

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

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

算法10第37行調(diào)用算法11（getTwoHopPattern-Pairs）獲得模式圖的同社區(qū)結(jié)點(diǎn)一跳共同鄰居分布表。該表的作用如下：記結(jié)點(diǎn)t的屬于社區(qū)c的出鄰居結(jié)點(diǎn)組成的集合為OutNeighc(t)，屬于c的入鄰居結(jié)點(diǎn)組成的集合為InNeighc(t)。在進(jìn)行子圖匹配的過(guò)程中，若對(duì)于被分配到c的模式圖結(jié)點(diǎn)u，要在網(wǎng)絡(luò)圖中找到與它匹配的結(jié)點(diǎn)，而同樣被分配到c的另一個(gè)模式圖結(jié)點(diǎn)v已與網(wǎng)絡(luò)圖結(jié)點(diǎn)t匹配，對(duì)于嘗試與u匹配的網(wǎng)絡(luò)圖結(jié)點(diǎn)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′)。此時(shí)可直接將u與其他結(jié)點(diǎn)匹配。算法中通過(guò)上述方式使用此分布表對(duì)子圖匹配算法進(jìn)行加速。這是CSO方法基于社區(qū)結(jié)構(gòu)進(jìn)行的第二類剪枝。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.4 CSO方法正確性證明

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

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

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

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

定理12CSO方法是正確的。

6 實(shí)驗(yàn)

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

6.1 實(shí)驗(yàn)準(zhǔn)備

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

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

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

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

Fig.5 Patterns used in experiments圖5 實(shí)驗(yàn)中使用的模式圖

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

6.2 性能對(duì)比實(shí)驗(yàn)

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

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

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

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

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

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

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

上述實(shí)驗(yàn)證明了CSO方法的有效性，值得探究的一點(diǎn)是CSO方法中使用的兩種策略各自有怎樣的優(yōu)化效果。下面結(jié)合具體實(shí)驗(yàn)比較基于社區(qū)結(jié)構(gòu)進(jìn)行剪枝和解析模式圖兩種策略對(duì)子圖匹配算法的優(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兩個(gè)數(shù)據(jù)集上以模式圖K3、K4和P4sy為例進(jìn)行子圖匹配，測(cè)試上述兩種算法的用時(shí)，并將測(cè)試結(jié)果與AVF2算法進(jìn)行比較。

由表3可以發(fā)現(xiàn)，在兩個(gè)數(shù)據(jù)集上，NC_AVF2和NP_AVF2相比算法AVF2用時(shí)均有所增加，其中在Email數(shù)據(jù)集上刪去任意一種優(yōu)化策略均會(huì)導(dǎo)致用時(shí)增加40%以上，這表明CSO方法中使用的兩個(gè)優(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個(gè)社區(qū)間子圖匹配結(jié)果，占總匹配結(jié)果數(shù)的82.3%，而在Opera_1000數(shù)據(jù)集上，僅有2 184個(gè)社區(qū)間子圖匹配結(jié)果，占總匹配結(jié)果數(shù)量的0.02%，這就導(dǎo)致在Opera_1000數(shù)據(jù)集上模式圖解析優(yōu)化效果遠(yuǎn)不如Email數(shù)據(jù)集。

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

6.3 可擴(kuò)展性分析

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

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

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

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

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

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

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

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

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

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

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

附錄：

算法1模式圖中全等點(diǎn)對(duì)的查找算法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模式圖中對(duì)稱點(diǎn)對(duì)的查找算法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//定義存儲(chǔ)使用過(guò)的結(jié)點(diǎn)的集合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遞歸查找對(duì)稱點(diǎn)對(duì)的算法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行對(duì)結(jié)點(diǎn)的入鄰居進(jìn)行處理

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

28.從used中刪除vi和vj

29.returnTrue

算法4匹配等價(jià)的子圖的查找算法handleMatchPattern

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

輸出：matchEq。

1.vector＜int＞current//聲明了存儲(chǔ)模式圖子圖包含的結(jié)點(diǎn)的向量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é)點(diǎn)能構(gòu)成的所有子圖并構(gòu)造匹配等價(jià)的子圖之間的映射的算法retrivalNodes

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

輸出：matchEq。

1.ifadded==True

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

3.if Size(current)≥1

4.set＜int＞record//聲明存儲(chǔ)使用過(guò)的結(jié)點(diǎn)的集合record

5.vector＜int＞t//聲明存儲(chǔ)current通過(guò)對(duì)稱點(diǎn)替換和全等點(diǎn)替換得到的新結(jié)點(diǎn)列表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.計(jì)算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最后一項(xiàng)

27.returnmatchEq

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

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

輸出：matchEq。

1.ifpos≥Size(current)

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

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

4.ifhasSymm==True

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

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

7.if is_sorted(t)

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

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

10.else若t中屬于相同全等點(diǎn)組的結(jié)點(diǎn)的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的最后一項(xiàng)

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的最后一項(xiàng)

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中所有互相匹配等價(jià)的子圖，存儲(chǔ)在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中使用Λ算法對(duì)P進(jìn)行子圖匹配，將結(jié)果存儲(chǔ)到ins中

3.returnins

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

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

輸出：outs。

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

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

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

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

5.returnouts

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

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

輸出：outs。

1.獲取離線計(jì)算得到的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é)點(diǎn)匹配的網(wǎng)絡(luò)圖G中的結(jié)點(diǎn)列表的字典boundary

9.for each(c,vlist)∈superMatch

10.for each nodev∈vlist

11.unordered_map＜int,int＞outds,inds//聲 明記錄模式圖中結(jié)點(diǎn)v與被分配到各社區(qū)的所有模式圖結(jié)點(diǎn)間的出邊總數(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é)點(diǎn)集合，若候選集合為空，直接執(zhí)行第一行

25.ifhasIn==True

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

27.map＜int,int＞superMatchMap//聲明記錄模式圖中每個(gè)結(jié)點(diǎn)被分配到哪個(gè)社區(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)前分配方案等價(jià)的分配方案，并比較它們的標(biāo)志字符串，若mystr不是所有標(biāo)志字符串中最小的，則結(jié)束匹配并執(zhí)行第一行

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

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

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

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

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

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

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

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

44.returnouts

算法11模式圖的同社區(qū)結(jié)點(diǎn)一跳共同鄰居分布表的計(jì)算算法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對(duì)maps中存儲(chǔ)的匹配結(jié)果進(jìn)行合并及結(jié)構(gòu)驗(yàn)證的算法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.對(duì)被分配到處理過(guò)的社區(qū)的各結(jié)點(diǎn)n，記與它匹配的結(jié)點(diǎn)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