何潔月 沈 斌

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,南京210096)(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室,南京210096)

基于路徑信息比較的圖同構(gòu)新算法

何潔月1,2沈 斌1

(1東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,南京210096)(2東南大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)和信息集成教育部重點(diǎn)實(shí)驗(yàn)室,南京210096)

為了在多項(xiàng)式時(shí)間內(nèi)解決圖同構(gòu)問題,首先證明了2個同構(gòu)圖相等長度的路徑信息必相同是圖同構(gòu)判定更為嚴(yán)格的必要條件.然后,根據(jù)此條件,提出了一種基于路徑信息比較的圖同構(gòu)PIC算法.該算法依次比較各長度的路徑信息,對鄰接矩陣進(jìn)行調(diào)整,從而實(shí)現(xiàn)了2個圖的快速同構(gòu)判定.為了減少路徑信息的計(jì)算時(shí)間，引入Hash函數(shù)對PIC算法進(jìn)行改進(jìn)，從而得到了HPIC算法.實(shí)驗(yàn)結(jié)果表明,所提的2種算法均能夠正確判定1×104對不同類型、不同大小的隨機(jī)圖是否同構(gòu),并且圖同構(gòu)判定的時(shí)間復(fù)雜度明顯降低.HPIC算法的運(yùn)行速度快于PIC算法；這2種算法在時(shí)間性能方面均優(yōu)于CS算法,略劣于Nauty算法;但對于規(guī)則2維網(wǎng)孔圖,Nauty算法失效,所提的2種算法則仍能快速進(jìn)行圖同構(gòu)判定.

圖同構(gòu);冪階比較;大規(guī)模圖;路徑信息比較

圖的同構(gòu)判定問題是圖論學(xué)科中的基本問題之一,在模式識別、電路分析、分子結(jié)構(gòu)和生物信息學(xué)[1-3]等領(lǐng)域有著廣泛的應(yīng)用.圖同構(gòu)問題既未被歸入 NPC 問題,也未被歸入P問題[4].目前,學(xué)者們已提出了一些有效的圖同構(gòu)判定算法,然而,針對特定類型圖進(jìn)行判定時(shí)這些算法通常會失效.圖同構(gòu)算法大致可以分為3類:① 基于模型的判定算法.文獻(xiàn)[5]提出了一種基于神經(jīng)網(wǎng)絡(luò)的圖同構(gòu)判定算法,并通過簡化能量函數(shù)建立相應(yīng)的數(shù)學(xué)模型,是一種能夠模擬局部功能的超大規(guī)模并行計(jì)算方法.② 基于搜索的算法.Ullmann算法利用預(yù)測方程減少了搜索的空間[6];Nauty算法先將圖表示為某種規(guī)范形式,然后判斷是否同構(gòu)[7].③ 根據(jù)圖的特征信息(如圖的出入度序列、回路數(shù)、樹數(shù)、連通片數(shù)等)提出的算法,如度序列法、電路模擬比較法[8]等.然而,這些算法均具有各自的局限性.例如,基于神經(jīng)網(wǎng)絡(luò)的圖同構(gòu)算法在每次判定時(shí)都需要在能量函數(shù)的步長上進(jìn)行探索,易于陷入局部最優(yōu)值,影響算法的效率.文獻(xiàn)[9]發(fā)現(xiàn)Nauty算法是綜合效率最高的算法,但在網(wǎng)孔圖的情況下完全失效.文獻(xiàn)[10]對電路模擬比較法進(jìn)行了改進(jìn),在大節(jié)點(diǎn)下獲得了較好的效率,但當(dāng)圖中出現(xiàn)孤立點(diǎn)時(shí)失效,且對于對稱性強(qiáng)的圖效率不高.

根據(jù)圖的局部或全局特征信息來判斷圖同構(gòu)性的條件強(qiáng)度較弱,不同構(gòu)的2個圖也可能會出現(xiàn)完全相同的特征信息[11].本文首先證明了2個同構(gòu)圖相等距離的路徑信息必相同是圖同構(gòu)判定中更為嚴(yán)格的必要條件.基于此,提出了一種由局部到全局的路徑信息比對法(PIC)算法,然后利用Hash函數(shù)對獲取路徑信息過程進(jìn)行改進(jìn),得到路徑信息比對(HPIC)算法.

1 算法描述

1.1 基本概念

圖同構(gòu)是指2個圖的拓?fù)浣Y(jié)構(gòu)完全相同,即頂點(diǎn)到頂點(diǎn)、邊到邊之間存在著一一對應(yīng)的關(guān)系.

定義1[12]對于圖G=〈V,E〉與圖G′=〈V′,E′〉,存在雙射f:V→V′和雙射h:E→E′,使得對于每條邊ek∈E,點(diǎn)vi,vj為ek在圖G中的端點(diǎn),在圖G′中存在且唯一存在一條以f(vi),f(vj)為端點(diǎn)的邊h(ek),則稱這2個圖同構(gòu),記做G≈G′.其中,V,E分別為頂點(diǎn)集合和邊的集合.

定義2 圖可以用鄰接矩陣表示.對于具有n個頂點(diǎn)的圖,其鄰接矩陣D為n×n階矩陣,矩陣中元素可表示為

式中,[vi,vj]表示從點(diǎn)vi指向點(diǎn)vj的邊.

定理1[13]圖G與圖G′的鄰接矩陣經(jīng)過行(列)互換的合同變換后,若鄰接矩陣相同,則G與G′同構(gòu).即若存在非奇異列交換矩陣P1,P2,…,Pm,使得D={P1,P2,…,Pm}D′{Pm,Pm-1,…,P1},則G≈G′.反之也成立.

1.2 基于路徑信息比較的圖同構(gòu)判斷算法

傳統(tǒng)的圖特征信息法僅關(guān)注了局部或全局特征信息,這是比較弱的必要條件,在判斷2個圖是否同構(gòu)時(shí)失效情況較多.為此,考慮1～n-1階的路徑信息,根據(jù)由局部逐步推向整體的比對信息進(jìn)行判定.對于圖G中點(diǎn)A與圖G′中點(diǎn)B,如果其鄰接點(diǎn)信息相同,則稱點(diǎn)A與點(diǎn)B的1階路徑信息相似;如果長度為k的鏈路信息完全相同,則稱點(diǎn)A與點(diǎn)B為k階相似;如果點(diǎn)A與點(diǎn)B的1～n-1階路徑信息均相似,則點(diǎn)A必與點(diǎn)B對應(yīng);若2個圖中所有點(diǎn)一一對應(yīng),則2個圖同構(gòu).

顯然可以推出,若存在非奇異行(列)交換矩陣P1,P2,…,Pm,使得R=R′{Pm,Pm-1,…,P1},則R≈R′.

定理3 如果圖G與圖G′同構(gòu),則Dk≈D′k.

證明 由定理1可知,存在非奇異行變換矩陣P1,P2,…,Pm,使得

D1={P1,P2,…,Pm}D′1{Pm,Pm-1,…,P1}

由定義4可知,D1≈D′1，故Dk=(PD′Q)k,又因?yàn)镻Q={P1,P2,…,Pm}{Pm,Pm-1,…,P1}=I,則Dk=PD′kQ,即可得Dk≈D′k.證畢.

定理3是PIC算法的基礎(chǔ),是2個圖同構(gòu)的更為嚴(yán)格的必要條件.對鄰接矩陣進(jìn)行n-1次比較,若Dk≠D′k,則2個圖不同構(gòu).

定理3為證明2個圖不同構(gòu)提供了必要條件,推論2為鄰接矩陣的調(diào)整提供了依據(jù).每經(jīng)過一次比較,都可以利用必要條件進(jìn)行一次檢驗(yàn),同時(shí)可以根據(jù)頂點(diǎn)的路徑信息對矩陣調(diào)整進(jìn)行一次充分性檢驗(yàn).若經(jīng)過調(diào)整的矩陣相等,則2個圖必同構(gòu).

1.3 PIC算法

PIC算法利用定理3與推論2對2個圖的對應(yīng)點(diǎn)進(jìn)行劃分,縮小了比對范圍,提高了圖同構(gòu)判定的速度.

算法1 PIC算法

輸入: 圖G1=〈V1,E1〉,圖G2=〈V2,E2〉.

輸出: 2個圖同構(gòu)的判定結(jié)果.

//計(jì)算2個圖的鄰接矩陣

A=AP1=GetM(G1),B=BP1=GetM(G2)

//判定2個圖是否同構(gòu)

if (A==B)

return true

end if

//計(jì)算矩陣路徑信息

return false

end if

//根據(jù)路徑信息調(diào)整鄰接矩陣

If (A==B)

return true

end if

APi+1=APiA

BPi+1=BPiB

end for

//枚舉同構(gòu)判定結(jié)果

return enum(A,B)

1.4 算法復(fù)雜度分析及改進(jìn)

本文算法的最優(yōu)情況是指只需進(jìn)行1次矩陣比較便可判定2個圖是否同構(gòu),此時(shí)算法的時(shí)間復(fù)雜度為O(n2).最壞情況是指經(jīng)過n-1次檢驗(yàn)才能判定2個圖是否同構(gòu).其中,每一次判定都需要利用排序算法對行內(nèi)元素進(jìn)行調(diào)整,以得到每個點(diǎn)的路徑信息,得到n個點(diǎn)的路徑信息時(shí)間復(fù)雜度為O(n2lgn);然后,對整理后的矩陣進(jìn)行初等行變換,時(shí)間復(fù)雜法度為O(n2);在Matlab軟件中,矩陣的乘法函數(shù)復(fù)雜度為O(n2.8).因此,總的時(shí)間復(fù)雜度為(n-1)(O(n2lgn)+O(n2)+O(n2.8))=O(n3.8).實(shí)際上,僅當(dāng)2個圖都是旋轉(zhuǎn)對稱圖且旋轉(zhuǎn)周期大于4時(shí),才需要經(jīng)過n-1次檢驗(yàn)來判定2個圖是否同構(gòu).因此,本文中將算法平均時(shí)間復(fù)雜度取為O(n3).

由于無向圖(或有向圖)鄰接矩陣的元素都為0(或1),因此,可以利用Hash函數(shù)對PIC算法進(jìn)行改進(jìn),從而得到HPIC算法.在HPIC算法中,計(jì)算每個點(diǎn)的路徑信息時(shí),先用Hash函數(shù)對鄰居矩陣中每一行元素出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì);然后,比較2個圖的路徑信息集合是否相等.該算法將得到每個點(diǎn)路徑信息的時(shí)間復(fù)雜度從O(nlgn)降低為O(n),從而減少了程序運(yùn)行時(shí)間.該算法在最優(yōu)情況下的時(shí)間復(fù)雜度為O(n2);在最壞情況下,由于高階鄰接矩陣中元素差異性大,Hash函數(shù)法不再適用,故時(shí)間復(fù)雜度仍為O(n3.8).

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

參照文獻(xiàn)[11],構(gòu)造出同構(gòu)測試圖庫,生成了1×104對同構(gòu)測試樣本.待測圖類型主要包括:隨機(jī)圖(3×103對)、規(guī)則2維網(wǎng)孔圖(1×103對)、非規(guī)則2維網(wǎng)孔圖(3×103對)和固定度數(shù)圖(3×103對).

CS算法[10]是一種適用于大圖比對的圖特征法算法.文獻(xiàn)[9]對Ullmann算法、SD算法、VF算法、VF2算法和Nauty算法進(jìn)行了比較,發(fā)現(xiàn)Nauty算法在平均性能方面優(yōu)于其他4種算法.本文實(shí)驗(yàn)中,使用2.0b版Nauty算法,并在Matlab軟件中實(shí)現(xiàn)了CS算法、PIC算法和HPIC算法.

2.1 隨機(jī)圖

對于給定頂點(diǎn),每2個頂點(diǎn)按照概率p(0≤p≤1)連接而成的圖即為隨機(jī)圖.本實(shí)驗(yàn)中產(chǎn)生了10組(共1 000對)隨機(jī)圖,其中每組圖的頂點(diǎn)數(shù)分別為20,40,60,80,100,200,400,600,800,1 000.對于p=0.05的隨機(jī)圖,利用4種算法判定2個圖是否同構(gòu)所需的平均時(shí)間見圖1.由圖可知,4種算法運(yùn)行速度由快到慢依次排序?yàn)? Nauty算法、HPIC算法、PIC算法、CS算法.當(dāng)圖的頂點(diǎn)數(shù)增加到1 000時(shí),CS算法的運(yùn)行時(shí)間分別約為PIC算法和HPIC算法的8.9和19.3倍.值得注意的是,當(dāng)圖中存在孤立點(diǎn)時(shí),CS算法完全失效,需要通過枚舉法來判定2個圖是否同構(gòu),時(shí)間復(fù)雜度為O(n!).這種情況在隨機(jī)圖中出現(xiàn)的概率隨頂點(diǎn)數(shù)的增加而減少.當(dāng)圖的頂點(diǎn)數(shù)為60時(shí),一個圖中出現(xiàn)孤立點(diǎn)的概率為0.225;當(dāng)頂點(diǎn)數(shù)為100時(shí),此概率為0.007;當(dāng)頂點(diǎn)數(shù)大于100后,隨機(jī)圖中出現(xiàn)孤立點(diǎn)的現(xiàn)象為小概率事件.因此,CS算法適合于頂點(diǎn)數(shù)較多的圖.

圖1 隨機(jī)圖中不同算法平均運(yùn)行時(shí)間比較

2.2 規(guī)則2維網(wǎng)孔圖

規(guī)則2維網(wǎng)孔圖是指規(guī)則的有向網(wǎng)格圖.本實(shí)驗(yàn)中產(chǎn)生了10組(共1 000對)隨機(jī)圖,其中每組圖的頂點(diǎn)數(shù)分別為9,16,25,36,64,100,225,400,625,1 024.對于規(guī)則2維網(wǎng)孔圖,利用4種算法判定2個圖是否同構(gòu)所需的平均時(shí)間見圖2.

圖2 規(guī)則2維網(wǎng)孔圖中不同算法平均運(yùn)行時(shí)間比較

由圖2可知,Nauty算法在規(guī)則2維網(wǎng)孔圖中完全失效.在程序運(yùn)行時(shí)間方面,HPIC算法最短,PIC算法與CS算法接近.當(dāng)圖的頂點(diǎn)數(shù)增加到1 024時(shí),CS算法的運(yùn)行時(shí)間分別約為HPIC算法和PIC算法的1.9和1.3倍.

2.3 非規(guī)則2維網(wǎng)孔圖

在規(guī)則2維網(wǎng)孔圖的基礎(chǔ)上添加一些隨機(jī)連接邊,得到非規(guī)則2維網(wǎng)孔圖.本實(shí)驗(yàn)中,在10組規(guī)則網(wǎng)孔圖的基礎(chǔ)上加入0.2N條隨機(jī)邊,得到10組非規(guī)則網(wǎng)孔圖,其中N為圖的頂點(diǎn)數(shù).對于非規(guī)則2維網(wǎng)孔圖,利用4種算法判定2個圖是否同構(gòu)所需的平均時(shí)間見圖3.

圖3 非規(guī)則2維網(wǎng)孔圖中不同算法平均運(yùn)行時(shí)間比較

由圖3可知,4種算法運(yùn)行速度由快到慢依次排序?yàn)? Nauty算法、HPIC算法、PIC算法、CS算法.當(dāng)圖的頂點(diǎn)數(shù)增加到1 000時(shí),CS算法的運(yùn)行時(shí)間分別約為PIC算法和HPIC算法的7.9和10.2倍.

2.4 固定度數(shù)圖

固定度數(shù)圖是指每個頂點(diǎn)出入度之和為定值的圖.本實(shí)驗(yàn)中產(chǎn)生了10組(共1 000對)隨機(jī)圖,其中每組圖的頂點(diǎn)數(shù)分別為20,40,60,80,100,200,400,600,800,1 000.對于定值為3的固定度數(shù)圖,利用4種算法判定2個圖是否同構(gòu)所需的平均時(shí)間見圖4.

圖4 固定度數(shù)圖中不同算法平均運(yùn)行時(shí)間比較

由圖4可知,CS算法的運(yùn)行時(shí)間最長,其次是PIC算法,HPIC算法和Nauty算法接近.當(dāng)圖的頂點(diǎn)數(shù)大于600時(shí),HPIC算法的運(yùn)行速度比Nauty算法快.當(dāng)圖的頂點(diǎn)數(shù)增加到1 000時(shí),CS算法的運(yùn)行時(shí)間分別約為PIC算法和HPIC算法的2.8和7.6倍.

綜上所述,PIC算法和HPIC算法在大部分情況下都能較快地對2個圖進(jìn)行同構(gòu)判定.此外,對于規(guī)則2維網(wǎng)孔圖,Nauty算法已經(jīng)失效,所提2種算法則能夠較快地進(jìn)行同構(gòu)判定.

3 結(jié)語

圖同構(gòu)問題是經(jīng)典的圖論問題,現(xiàn)有的圖同構(gòu)判定算法都具有一定的局限性.本文首先證明了2個同構(gòu)圖相等長度的路徑信息必相同是圖同構(gòu)判定更為嚴(yán)格的必要條件.基于此,提出了PIC算法和HPIC算法,分析了算法的時(shí)間復(fù)雜度.試驗(yàn)結(jié)果表明,PIC算法和HPIC算法均具有較優(yōu)的綜合性能.

References)

[1]Bunke H, Riesen K. Recent advances in graph-based pattern recognition with applications in document analysis [J].PatternRecognition, 2011, 44(5):1057-1067.

[2]Dehmer M, Sivakumar L, Varmuza K. Uniquely discriminating molecular structures using novel eigenvalue-based descriptors [J].CommunicationsinMathematicalandComputerChemistry, 2012, 67(3)： 147-172.

[3]He J Y, Wang C Y, Qiu K P, et al. An novel frequent probability pattern mining algorithm based on circuit simulation method in uncertain biological networks[J].BMCSystemsBiology, 2014, 8(S3): S6.

[4]Torán J. On the hardness of graph isomorphism [J].SIAMJournalonComputing, 2004, 33(5): 1093-1108.

[5]許進(jìn),張軍英,保錚.基于Hopfield網(wǎng)絡(luò)的圖的同構(gòu)算法 [J].電子科學(xué)學(xué)刊, 1996, 18(S1): 116-121. Xu Jin, Zhang Junying, Bao Zheng. Graph isomorphism algorithm based on the Hopfield network[J].ChinaJournalofElectronics, 1996, 18(S1): 116-121. (in Chinese)

[6]Ullmann J R. An algorithm for subgraph isomorphism [J].JournaloftheAssociationforComputingMachinery, 1976, 23(1): 31-42.

[7]McKay B D, Piperno A. Practical graph isomorphism, Ⅱ [J].JournalofSymbolicComputation, 2014, 60: 94-112.

[8]Shang H L, Li F, Tang X D, et al.A new algorithm for isomorphism determination of undirected graphs-circuit simulation method [J].CircuitsSystemsandSignalProcessing, 2011, 30(5): 1115-1130.

[9]Foggia P, Sansone C, Vento M. A performance comparison of five algorithms for graph isomorphism [C]//Proceedingsofthe3rdIAPRTC-15WorkshoponGraph-basedRepresentationsinPatternRecognition. Napoli, Italy, 2001: 188-199.

[10]趙愉, 李鋒, 商慧亮. 同構(gòu)圖判定: 改進(jìn)的電路模擬法[J]. 信息與電子工程, 2011, 9(4): 478-482. Zhao Yu, Li Feng, Shang Huiliang. Improved circuit simulation method for testing isomorphism [J].ChinaInformationandElectronicEngineering, 2011, 9(4): 478-482.(in Chinese)

[11]Gori M, Maggini M, Sarti L. Exact and approximate graph matching using random walks [J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2005, 27(7): 1100-1111.

[12]Bondy J A, Murty U S R.Graphtheorywithapplications[M]. London: Macmillan, 1976: 4-7.

[13]謝科, 饒懷章. 圖同構(gòu)的充要條件[J]. 西南民族大學(xué)學(xué)報(bào):自然科學(xué)版, 2011,37(5): 703-705. Xie Ke, Rao Huaizhang. Necessary and sufficient condition of graph isomorphism [J].ChinaJournalofSouthwestUniversityforNationalities:NaturalScienceEdition, 2011, 37(5): 703-705. (in Chinese)

Novel graph isomorphism algorithm based on path information comparison

He Jieyue1,2Shen Bin1

(1School of Computer Science and Engineering, Southeast University,Nanjing 210096, China)(2Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 210096, China)

To solve the graph isomorphism problem in polynomial time, it is proved that the fact that the path information with same length of two isomorphism graphs must be the same is a more rigorous prerequisite for judging whether two graphs are isomorphism. Then, according to this prerequisite, the PIC (path information comparison) algorithm based on graph isomorphism comparison is proposed. In this algorithm, the path information with different lengths of two graphs is compared successively. The adjacent matrixes are adjusted based on the vertex path information in the comparing process and quick isomorphism of the two graphs is realized. By introducing the Hash function to improve the PIC algorithm, the HPIC (hash path information comparison) algorithm is proposed to reduce the computation time of the path information. The experiment results demonstrate that the two proposed algorithms can correctly judge whether the 1×104pairs of figures with different types and sizes are isomorphism graphs, and the time complexity is obviouly reduced. The HPIC algorithm is faster than the PIC algorithm. Furthermore, these two algorithms are faster than the CS(circuit simulation) algorithm, but slightly slower than the Nauty algorithm. However, as for the regular two-dimensional meshes, the Nauty algorithm is invalid while the two proposed algorithms can still solve the graph isomorphism problem quickly.

graph isomorphism; matrix power comparison; large graph; path information comparison

10.3969/j.issn.1001-0505.2015.02.007

2014-11-08. 作者簡介: 何潔月(1964—),女,博士,教授,Jieyuehe@seu.edu.cn.

江蘇省自然科學(xué)基金資助項(xiàng)目(BK2012742).

何潔月，沈斌.基于路徑信息比較的圖同構(gòu)新算法[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2015,45(2):236-240.

10.3969/j.issn.1001-0505.2015.02.007

TP301

A

1001-0505(2015)02-0236-05