江順亮，唐祎玲，葛 蕓，徐少平，葉發(fā)茂

?

基于層序遍歷的頂點(diǎn)不變量及其圖不變量

江順亮，唐祎玲，葛 蕓，徐少平，葉發(fā)茂

(南昌大學(xué)信息工程學(xué)院，江西 南昌 330031)

為了尋找更好性能的圖不變量，利用層序遍歷過程中的頂點(diǎn)數(shù)據(jù)經(jīng)加權(quán)累加定義了15種頂點(diǎn)不變量，每一種頂點(diǎn)不變量排序后可以組成一種圖不變量。層序遍歷時(shí)將頂點(diǎn)度數(shù)分為同層度數(shù)、向前度數(shù)和向后度數(shù)，其中同層度數(shù)和向后度數(shù)包含回路數(shù)信息。依據(jù)對(duì)頂點(diǎn)的細(xì)分能力，挑選出3種頂點(diǎn)不變量，組成圖不變量，其不同組合對(duì)于各種非同構(gòu)連通圖具有較好的區(qū)分性能，不僅對(duì)圖頂點(diǎn)數(shù)N≤8的非同構(gòu)圖全部可以區(qū)分，而且將N=9的不可區(qū)分圖數(shù)量從文獻(xiàn)[9]的989種降到40種，且其簡并度將趨近2，隨機(jī)測試表明這些圖不變量具有很好的區(qū)分度。

圖同構(gòu)；頂點(diǎn)不變量；圖不變量；不可區(qū)分圖；簡并度

圖同構(gòu)問題是計(jì)算機(jī)科學(xué)中的重大復(fù)雜性理論問題，從目前來看，其既不屬于NPC復(fù)雜度也不屬于多項(xiàng)式復(fù)雜度，因此是一個(gè)有待解決的科學(xué)問題，而且還與化學(xué)、模式識(shí)別、社交網(wǎng)絡(luò)等很多研究領(lǐng)域相關(guān)[1]。圖同構(gòu)方面專家BABAI[2]最近宣稱發(fā)現(xiàn)了一個(gè)擬多項(xiàng)式的圖同構(gòu)算法，雖然剛開始有學(xué)者指出其中一個(gè)錯(cuò)誤，經(jīng)過修正，BABAI在其個(gè)人網(wǎng)頁堅(jiān)持其結(jié)論的正確性，引起學(xué)術(shù)界的廣泛關(guān)注。但是，由于理論的復(fù)雜性，有學(xué)者質(zhì)疑這種算法的實(shí)際價(jià)值，認(rèn)為要進(jìn)行實(shí)際應(yīng)用還有段距離[1]。

圖的定義：:<,>，其中為頂點(diǎn)集合，為邊集合，其是笛卡爾集合×的子集。圖同構(gòu)的定義：對(duì)于2個(gè)圖1:<1,1>和2:<2,2>，存在雙射函數(shù):1→2，滿足對(duì)于任意的<,>∈1當(dāng)且僅當(dāng)<(),()>∈2，則1和2同構(gòu)。本文只研究簡單連通無向圖，其中包括二部圖和平面圖等常見的圖形。下面的圖沒有特指都是簡單連通無向圖，并定義=||為圖的頂點(diǎn)數(shù)量。

國際上，獲得廣泛認(rèn)可的圖同構(gòu)方法是Nauty[3]，其幾乎成了圖同構(gòu)規(guī)范標(biāo)記法的工業(yè)標(biāo)準(zhǔn)[4]。Nauty迭代地細(xì)分頂點(diǎn)，隨著頂點(diǎn)細(xì)分越來越小，其會(huì)自動(dòng)創(chuàng)建規(guī)范標(biāo)記[3]。使用圖頂點(diǎn)不變量是頂點(diǎn)細(xì)分的重要手段[3,5]，目的是減少圖同構(gòu)算法的搜索空間[3,5-6]。頂點(diǎn)不變量可以組合成圖不變量，圖不變量對(duì)低階非同構(gòu)圖的區(qū)分情況可以反映頂點(diǎn)不變量的性能，例如用圖不變量能得到多少種低階非同構(gòu)圖[7-8]，有的方法只是進(jìn)行幾種低階非同構(gòu)圖的簡單比對(duì)分析[5]，有的則是對(duì)不可區(qū)分低階非同構(gòu)圖進(jìn)行計(jì)數(shù)[9]。只針對(duì)低階非同構(gòu)圖進(jìn)行分析是有道理的，因?yàn)锽ABAI等[10]的早期研究表明很多簡單的圖不變量對(duì)高階非同構(gòu)圖的測試準(zhǔn)確率非常高。文獻(xiàn)[9]比較了22種圖不變量對(duì)于頂點(diǎn)數(shù)量＜10的非同構(gòu)圖的區(qū)分情況，并把2種或3種圖不變量組合成一個(gè)新的圖不變量，最好的結(jié)果是=9時(shí)，不可區(qū)分非同構(gòu)圖有989種，占總數(shù)的0.38%。

由圖頂點(diǎn)不變量組成的圖不變量可以應(yīng)用到圖同構(gòu)算法中[6,9,11]，尋找更好、更充分的圖不變量仍是一個(gè)開放的研究問題[11]，而且圖不變量在很多領(lǐng)域是非常重要的[12-15]。有些圖不變量的計(jì)算會(huì)比較復(fù)雜[11,16]，需要針對(duì)一些特殊的圖進(jìn)行測試[11,16]。

本文旨在尋找對(duì)低階非同構(gòu)圖有更好性能、計(jì)算簡單的頂點(diǎn)不變量，為此在層序遍歷的框架下把頂點(diǎn)的度數(shù)分為同層之間的度數(shù)、向前的度數(shù)和向后的度數(shù)，其中同層度數(shù)和向后度數(shù)與頂點(diǎn)的回路數(shù)相關(guān)。相同框架下還可以計(jì)算頂點(diǎn)的最短路徑數(shù)和層寬度，以此定義了15種頂點(diǎn)不變量，然后挑選出3種頂點(diǎn)不變量，頂點(diǎn)不變量排序后組成圖不變量。研究這3種圖不變量及其組合對(duì)低階非同構(gòu)圖的區(qū)分情況，獲得的最好結(jié)果是頂點(diǎn)數(shù)=9時(shí)，不可區(qū)分非同構(gòu)圖降低到40種，僅占總數(shù)的0.015%，=10的不可區(qū)分非同構(gòu)圖有4 603種，占總數(shù)的0.039%。

1 系列頂點(diǎn)不變量

圖頂點(diǎn)不變量主要有頂點(diǎn)的度數(shù)、最短距離、路徑數(shù)目、簡單回路數(shù)目、包含三角形的數(shù)目等[5]，以及由其衍生出來的各種不變量[6-7,9,11]。本文依據(jù)計(jì)算單源最短路徑的層序計(jì)算框架，利用每層的信息以及相鄰層的信息設(shè)計(jì)了一系列頂點(diǎn)不變量。首先，將每個(gè)頂點(diǎn)的度數(shù)d分為3個(gè)部分，即

其中，t為頂點(diǎn)同層之間的連接度數(shù)；f為頂點(diǎn)與下一層的頂點(diǎn)之間的連接度數(shù)；b為頂點(diǎn)與上一層的頂點(diǎn)之間的連接度數(shù)。

計(jì)算一個(gè)頂點(diǎn)的頂點(diǎn)不變量示意圖如圖1所示。如要計(jì)算頂點(diǎn)的頂點(diǎn)不變量，則是從第一個(gè)頂點(diǎn)出發(fā)，依據(jù)連接層序，逐層累加。其中，當(dāng)前擴(kuò)展層為FRONT，連接距離為(第一個(gè)結(jié)點(diǎn)的連接距離為1)，當(dāng)前擴(kuò)展層的頂點(diǎn)數(shù)為1 (可以看成局部寬度)，當(dāng)前擴(kuò)展層的頂點(diǎn)度數(shù)平方之和為1。圖1是FRONT層擴(kuò)展后的結(jié)果，新擴(kuò)展獲得的頂點(diǎn)屬于NEW_FRONT層，頂點(diǎn)數(shù)為2，頂點(diǎn)度數(shù)平方之和為2。每層數(shù)據(jù)累加時(shí)，以各層距離、2、3作為權(quán)。15個(gè)不變量的定義見表1，其中用到的基本變量在圖1中有示例，1、2、1、2、1和2的定義見式(2)~(7)。每個(gè)頂點(diǎn)的頂點(diǎn)不變量計(jì)算過程相同，即

其中，np為起點(diǎn)到頂點(diǎn)的最短路徑數(shù)量。

圖1 計(jì)算頂點(diǎn)A的頂點(diǎn)不變量的示意圖

表1 15種不變量的定義

還有幾種簡單的頂點(diǎn)不變量沒有出現(xiàn)在表1中，比如頂點(diǎn)度數(shù)、最遠(yuǎn)距離=max()、最大寬度=max(1)、重心=∑1。這4種頂點(diǎn)不變量很難體現(xiàn)圖形的整體分布特征，限于篇幅，本文不做討論。

每層頂點(diǎn)度數(shù)平方之和能體現(xiàn)頂點(diǎn)度數(shù)在一層中的分布；同理，最短路徑數(shù)量平方之和也能體現(xiàn)最短路徑數(shù)量在一層中的分布。頂點(diǎn)的1=t(1+t)/2與包含該頂點(diǎn)的回路數(shù)有關(guān)，這些回路必須包括與頂點(diǎn)同層的其他頂點(diǎn)，而且一定有奇數(shù)長度的回路存在。實(shí)際的回路數(shù)可能多于t(1+t)/2，但不可能少于這個(gè)數(shù)據(jù)，示意圖如圖2所示。同理，頂點(diǎn)的2=b(b–1)/2也與包含該頂點(diǎn)的回路數(shù)有關(guān)，但這些回路不包括與頂點(diǎn)同層的其他頂點(diǎn)，因此一定有偶數(shù)長度的回路存在。同理，頂點(diǎn)實(shí)際的回路數(shù)可能多于這個(gè)數(shù)據(jù)，但不可能少于這個(gè)數(shù)據(jù)。

圖2 頂點(diǎn)i的回路數(shù)與ti(1+ti)/2的關(guān)系示意圖

利用每層的信息(1、1、1、1)和新擴(kuò)展層的信息(2、2、2、2)設(shè)計(jì)表1中的15種不變量，這些頂點(diǎn)不變量可以在一個(gè)層序遍歷過程中一次性計(jì)算出來。并能不同程度地反映圖的整體連接特性。距離、2、3可被認(rèn)為是層的權(quán)，高階權(quán)的不變量能體現(xiàn)圖形整體上下的偏分布特性，頂點(diǎn)越集中在圖形的遠(yuǎn)端，不變量越大。頂點(diǎn)不變量公式中還加入了層的寬度，反映了頂點(diǎn)集中的分布情況，因此頂點(diǎn)越集中在一層，不變量越大。同理，相同層的2個(gè)參數(shù)相乘(如1×1、1×1)可以反映圖形的整體不均勻性，比如層寬為2/2/2的頂點(diǎn)不變量會(huì)小于層寬為1/3/2的頂點(diǎn)不變量。不同層之間的2個(gè)參數(shù)相乘(如1×2、21)可以反映圖形層間變化的平滑性，平滑性越好，不變量越大，這是因?yàn)楹蛿?shù)相同的多個(gè)數(shù)，相鄰兩數(shù)的數(shù)值越相近，其相鄰兩數(shù)的乘積之和越大，如4個(gè)數(shù)(1,1,4,4)的1×1+1×4+4×4大于(1,4,1,4)的1×4+4×1+1×4。

綜上，這些不變量可以體現(xiàn)圖形頂點(diǎn)、頂點(diǎn)度數(shù)、頂點(diǎn)路徑數(shù)、頂點(diǎn)回路數(shù)的上下偏分布特性、整體不均勻性和整體平滑性。但這些特性是從某個(gè)頂點(diǎn)開始層序遍歷圖時(shí)獲得的，所以一個(gè)頂點(diǎn)的頂點(diǎn)不變量無法反映圖的全面特性，所有頂點(diǎn)的頂點(diǎn)不變量組合才能形成反映圖全面特性的圖不變量[5-7]。

頂點(diǎn)不變量的計(jì)算是按層序的擴(kuò)展方法分層計(jì)算。圖的數(shù)據(jù)結(jié)構(gòu)采用鄰接表，頂點(diǎn)分為4類：“HOME”、“FRONT”、“NEW_FRONT”和“UNTOUCHED”，分別表示“已擴(kuò)展頂點(diǎn)”、“當(dāng)前擴(kuò)展頂點(diǎn)”、“新擴(kuò)展頂點(diǎn)”和“未處理頂點(diǎn)”。計(jì)算頂點(diǎn)的頂點(diǎn)不變量的算法偽代碼如下：

輸入：頂點(diǎn)，圖的鄰接表

輸出：頂點(diǎn)的15個(gè)頂點(diǎn)不變量

初始化頂點(diǎn)標(biāo)志位及各計(jì)數(shù)數(shù)組

初始化起點(diǎn)并加入當(dāng)前擴(kuò)展層FRONT

循環(huán)1，直至當(dāng)前擴(kuò)展層FRONT為空

循環(huán)2，從當(dāng)前擴(kuò)展層FRONT取出頂點(diǎn)直至空

循環(huán)3，依次取的鄰接點(diǎn)

如果是“未處理頂點(diǎn)”

進(jìn)入新擴(kuò)展層

更新的路徑數(shù)和向后度數(shù)

更新的向前度數(shù)

如果是“新擴(kuò)展頂點(diǎn)”

更新的路徑數(shù)和向后度數(shù)

更新的向前度數(shù)

如果是“當(dāng)前擴(kuò)展頂點(diǎn)”

更新的同層度數(shù)

轉(zhuǎn)至循環(huán)3

轉(zhuǎn)至循環(huán)2

依據(jù)表1的公式更新15個(gè)頂點(diǎn)不變量

距離加1

新擴(kuò)展層更新為前擴(kuò)展層

轉(zhuǎn)至循環(huán)1

2 頂點(diǎn)不變量的頂點(diǎn)細(xì)分能力比較

一種頂點(diǎn)不變量對(duì)頂點(diǎn)的細(xì)分能力是有限的，因此常常利用多種頂點(diǎn)不變量來細(xì)分頂點(diǎn)[3,6-7,9]。一個(gè)頂點(diǎn)的多種頂點(diǎn)不變量組成一個(gè)矢量，所有頂點(diǎn)的不變量矢量組成矢量的矢量，排序后可以看成圖的不變量。排序后頂點(diǎn)的順序改變了，但一個(gè)頂點(diǎn)的多種不變量的相對(duì)順序沒有改變。

生成圖的不變量后，可以對(duì)圖的頂點(diǎn)進(jìn)行劃分。劃分時(shí)，如果某個(gè)頂點(diǎn)的不變量矢量與所有其他頂點(diǎn)的不變量不等，該頂點(diǎn)就單獨(dú)形成一個(gè)子集，也意味其是可以被區(qū)分的頂點(diǎn)，本文將此類頂點(diǎn)稱為“可區(qū)分頂點(diǎn)”。其他頂點(diǎn)就是“不可區(qū)分的頂點(diǎn)”。針對(duì)頂點(diǎn)數(shù)2≤≤9的所有非同構(gòu)圖，統(tǒng)計(jì)所有可區(qū)分頂點(diǎn)的數(shù)量，作為該圖不變量細(xì)分能力的比較依據(jù)，可區(qū)分頂點(diǎn)數(shù)量越多區(qū)分度越好。

2≤≤9的非同構(gòu)圖總共273 192種，總計(jì)2 445 436個(gè)頂點(diǎn)。依據(jù)區(qū)分頂點(diǎn)總數(shù)，按線性比例折算得分，最好為100、最差為0，具體得分見表2。表2中“單個(gè)”指用一種頂點(diǎn)不變量進(jìn)行頂點(diǎn)劃分；“組合2”指某種頂點(diǎn)不變量與另外一種頂點(diǎn)不變量進(jìn)行組合，累加所有組合的區(qū)分頂點(diǎn)數(shù)，然后用這個(gè)累加數(shù)進(jìn)行折算得分；同理，“組合3”指某種頂點(diǎn)不變量與其他兩種頂點(diǎn)不變量組合。三項(xiàng)得分的平均值作為該頂點(diǎn)不變量的細(xì)分能力指標(biāo)，數(shù)值越大越好，但該數(shù)據(jù)不是絕對(duì)指標(biāo)，而是15種頂點(diǎn)不變量之間的相對(duì)指標(biāo)。

依據(jù)表2可將15種不變量分為4組：{1、2、3}、{4、5、6、7}、{8、9、10、11}和{12、13、14、15}。第1組性能明顯不如其他3組，忽略這一組。其他3組各選一種最好的不變量進(jìn)行組合獲得(5、9、12)。用9,12來表示組合(9、12)，5,9,12來表示組合(5、9、12)，以下同。

依據(jù)可區(qū)分頂點(diǎn)數(shù)，可以挑選出最佳的一種不變量組合。從單個(gè)頂點(diǎn)不變量的性能看，12性能最好，獲得1 806 018個(gè)可區(qū)分頂點(diǎn)，占總頂點(diǎn)的73.8%。從“組合2”的詳細(xì)結(jié)果來看，組合9,12最好，獲得1 911 771個(gè)可區(qū)分頂點(diǎn)，占總頂點(diǎn)的78.2%。共有6種“組合3”(4,8,12、4,9,12、5,8,12、5,9,12、6,9,12、7,9,12)獲得最好結(jié)果，總計(jì)1 921 681個(gè)可區(qū)分頂點(diǎn)，占總頂點(diǎn)的78.6%；這個(gè)結(jié)果與15種不變量全部組合的結(jié)果相同。從6種“組合3”中挑選出現(xiàn)頻率最高的不變量進(jìn)行組合，也得到組合5,9,12。兩種挑選方法獲得相同的組合5,9,12。

表2 頂點(diǎn)不變量的細(xì)分能力比較結(jié)果

3 圖不變量對(duì)非同構(gòu)圖的區(qū)分度

令={:<,>}為非同構(gòu)圖的集合，||表示集合的元素個(gè)數(shù)，即非同構(gòu)圖數(shù)量。中的所有非同構(gòu)圖的圖不變量構(gòu)成圖不變量集合，||表示圖不變量的個(gè)數(shù)。如果所有非同構(gòu)圖都獲得不同的圖不變量，則||=||，這樣的圖不變量對(duì)集合具備完全的區(qū)分度；如果存在一些非同構(gòu)圖具有相同的圖不變量，則||＞||；而且兩者差值越大意味對(duì)集合中圖的區(qū)分度越差，因此可以用=||－||表征該不變量的同構(gòu)測試性能，本文取名為不變量欠量IVD (in variant deficiency)。=0意味獲得理想的測試性能，IVD越大性能越差。如果單純用||來表示圖不變量的性能，不如IVD直觀。

也可以采用不可區(qū)分圖數(shù)量NDG (non- distinguishable graphs)來表示圖不變量的性能。一個(gè)圖不變量如果對(duì)應(yīng)幾個(gè)非同構(gòu)圖，這些非同構(gòu)圖就是不可區(qū)分圖，對(duì)應(yīng)的圖不變量就是不可區(qū)分不變量，用NDI(non-distinguishable invariants)來表示不可區(qū)分不變量的數(shù)量。IVD、NDG與NDI三者之間存在關(guān)系為

如果不等式(9)取等式，則包含2種情況：①+1=即=1，這說明所有不可區(qū)分圖共享一個(gè)圖不變量的值；②=2，意味著任何一個(gè)不可區(qū)分圖只與另一個(gè)不可區(qū)分圖配對(duì)共享一個(gè)圖不變量的值。在相同的情況下，第二種情況的圖不變量區(qū)分能力最好，而且當(dāng)較大時(shí)，兩者的區(qū)分能力差別較大。所有其他情況介于這兩者之間，有一個(gè)參數(shù)可以表征這種情況，即簡并度(degeneracy)。

圖不變量的簡并度是指一個(gè)不變量對(duì)應(yīng)幾個(gè)非同構(gòu)圖，對(duì)應(yīng)2個(gè)非同構(gòu)圖的簡并度為2，對(duì)應(yīng)3個(gè)非同構(gòu)圖的簡并度為3。所有不變量的平均簡并度ad=||/||，1≤ad≤||；不可區(qū)分不變量的平均簡并度ad=/，2≤ad≤。平均簡并度越小說明對(duì)非同構(gòu)圖的劃分越細(xì)、區(qū)分性能越好。當(dāng)已知時(shí)，ad可以表示圖不變量對(duì)所有不可區(qū)分圖的區(qū)分性能。

綜上，可以用或來比較圖不變量的區(qū)分度，或的值越小圖不變量的區(qū)分度越好。同時(shí)參考或ad，越大、ad越小圖不變量對(duì)所有不可區(qū)分圖的區(qū)分度越好。如果只用一個(gè)數(shù)值來表示圖不變量對(duì)非同構(gòu)圖的區(qū)分度，可以采用不可區(qū)分圖的兩兩配對(duì)數(shù)NPR (number of pairs)，其中每對(duì)圖都是不可區(qū)分的。配對(duì)數(shù)NPR占所有兩兩組合數(shù)的比例PPR (proportion of pairs)能較好地反映圖不變量對(duì)非同構(gòu)圖的區(qū)分能力；從集合種任意取兩個(gè)非同構(gòu)圖，PPR就是誤判率，即依據(jù)圖不變量不能區(qū)分這兩個(gè)非同構(gòu)圖的概率。

本文用于測試的圖集是相同頂點(diǎn)數(shù)的非同構(gòu)連通無向圖集，數(shù)據(jù)可以用Nauty2.6[3]中的geng生成，也可以追溯文獻(xiàn)[17]獲得。如果只需要非同構(gòu)圖的數(shù)量，可以在http://staffhome.ecm.uwa.edu. au/~00013890/remote/graphs/index.html獲得。=10、11的非同構(gòu)圖分別有11 716 571種和1 006 700 565種，限于非同構(gòu)圖的巨大數(shù)量，本文只使用了2≤≤11的非同構(gòu)圖集。

4 不變量欠量及其百分比

用4≤≤11的所有非同構(gòu)圖計(jì)算了圖不變量的不變量欠量IVD，其中在計(jì)算=10的組合不變量的數(shù)據(jù)時(shí)是按邊數(shù)分類計(jì)算，計(jì)算結(jié)果見表3。

表3 不同圖不變量計(jì)算獲得的不變量欠量IVD

表3中的指由頂點(diǎn)不變量I排序后組成的圖不變量，的代碼與I的代碼相同。=11的非同構(gòu)圖超過十億(總計(jì)1 006 700 565)。為了計(jì)算效率同時(shí)兼顧計(jì)算機(jī)內(nèi)存，計(jì)算=11的圖不變量集合只能分類計(jì)算，其他數(shù)據(jù)也在這個(gè)基礎(chǔ)上計(jì)算。按邊數(shù)量、4度頂點(diǎn)數(shù)量、5度頂點(diǎn)數(shù)量以及6度頂點(diǎn)數(shù)量將1 006 700 565個(gè)非同構(gòu)圖分成4 331個(gè)類，其中超過300萬個(gè)非同構(gòu)圖的大類要進(jìn)一步分裂成100萬左右的小類，分裂標(biāo)準(zhǔn)是∑(d,d)，其中(,)∈。由于=11的非同構(gòu)圖數(shù)量太大，不變量欠量沒有放入表3中，但不變量欠量百分比/||數(shù)據(jù)如圖3所示。

通過對(duì)比表2和表3的數(shù)據(jù)，可以看出頂點(diǎn)不變量的細(xì)分能力基本決定了其組成的圖不變量對(duì)非同構(gòu)圖的區(qū)分能力。第1組{1、2、3}性能最差，第2組{4、5、6、7} 4個(gè)不變量性能基本一致，第3組{8、9、10、11}除10外其他3個(gè)不變量性能基本一致，第4組{12、13、14、15}的12在所有的圖不變量中對(duì)=9和=10的圖性能最好，其他3個(gè)與相比有明顯差距。因此，可以選出3個(gè)圖不變量5、9和12作為進(jìn)一步組合的基礎(chǔ)，這也印證了通過頂點(diǎn)不變量細(xì)分能力挑選不變量的合理性。

下文的分析討論主要針對(duì)5、9和12及其組合展開。當(dāng)增大時(shí)，非同構(gòu)圖的數(shù)量增加很快，同時(shí)不變量欠量也是成倍增加，因此不變量欠量百分比=/||更能體現(xiàn)圖不變量的性能隨增大的情況，7種圖不變量的不變量欠量百分比變化情況如圖3所示。

圖3 不變量欠量百分比隨N變化的趨勢(shì)(“1”代表Ig 1，“(5,9)”代表Ig 5,9)

隨著增大，只有12的不變量欠量百分比越來越小，而且明顯比159和組合數(shù)值小，已經(jīng)接近千分之一。組合9,12與組合5,9,12的數(shù)據(jù)非常接近，沒有在圖3中畫出。組合5,12和組合5,9,12的PIVD雖然比12的PIVD小，但其是在增大的，而且從下逼近12的PIVD。產(chǎn)生這樣的原因是與5、、12各自的特點(diǎn)有關(guān)。

圖不變量5的計(jì)算不包含圖的路徑數(shù)、回路數(shù)的信息，因此只適合對(duì)類似樹的圖進(jìn)行非同構(gòu)檢測，實(shí)際上其在對(duì)大量非同構(gòu)樹的檢測中表現(xiàn)很好。

圖不變量9利用頂點(diǎn)的路徑數(shù)和最短距離進(jìn)行計(jì)算，因此對(duì)于回路數(shù)不多的圖有較好的性能；而對(duì)于樹，圖不變量9退化為二階矩(也可以看成旋轉(zhuǎn)慣量)，對(duì)于非同構(gòu)樹也具有較高性能，但對(duì)于>15的非同構(gòu)樹存在低比例的不可區(qū)分樹。

圖不變量12是利用回路數(shù)進(jìn)行計(jì)算的，但對(duì)于只存在偶數(shù)長度回路的圖(包括沒有回路的樹)計(jì)算的12皆為零，原理可參考圖2。圖不變量12對(duì)于存在奇數(shù)長度回路的圖能進(jìn)行高準(zhǔn)確率的非同構(gòu)測試，針對(duì)=10的非同構(gòu)圖的計(jì)算表明：是適合邊數(shù)較多的稠密非同構(gòu)圖的同構(gòu)測試的，而且pivd隨邊數(shù)的增多在減少。圖4顯示了各種圖不變量在=10及不同邊數(shù)||情況下的不變量欠量百分比。

由于圖4的數(shù)據(jù)是用對(duì)數(shù)坐標(biāo)顯示，結(jié)果為0的數(shù)據(jù)沒有在圖中畫出，因此有些曲線兩端的數(shù)據(jù)空白。9,12的數(shù)據(jù)與5,9,1的數(shù)據(jù)非常接近，也沒有在圖4中畫出。從圖4中可以看出5、9、12各自的特點(diǎn)。5的加入可以有效地降低稀疏圖的不變量欠量，12可以維持稠密圖的低不變量欠量，9的加入可以進(jìn)一步降低非稠密圖的不變量欠量。所以，這3個(gè)不變量的組合5,9,12對(duì)于各種非同構(gòu)圖具有較好的性能。

圖4 不變量欠量百分比隨邊數(shù)|E|變化的趨勢(shì)(N=10) (“1”代表Ig 1，“(5,9)”代表Ig 5,9)

5 不可區(qū)分圖數(shù)量NDG及簡并度

文獻(xiàn)[9]列舉了22種已有的圖不變量對(duì)頂點(diǎn)數(shù)∈[5,9]的所有非同構(gòu)圖的NDG，并利用這些圖不變量進(jìn)行組合，共有20種不同的組合及NDG。本文結(jié)果與文獻(xiàn)[9]中最好結(jié)果的比較見表4，沒有列在表4中的其他20個(gè)引用結(jié)果[9]的平均值(=5,6,···,9)分別為9、61、547、8 364和21 534，其最優(yōu)值分別為2、23、96、1 701和43 133。

表4 不同圖不變量計(jì)算獲得的不可區(qū)分圖數(shù)量NDG

從單個(gè)不變量的結(jié)果看，9的結(jié)果優(yōu)于文獻(xiàn)[9]中引用的22種結(jié)果中的最好結(jié)果，12的≥9結(jié)果優(yōu)于22種結(jié)果中的最好結(jié)果，而且=10時(shí)12的結(jié)果優(yōu)于9的結(jié)果，只有9的27%。從組合不變量的結(jié)果看，與12的所有組合結(jié)果優(yōu)于文獻(xiàn)[9]的組合結(jié)果，不僅對(duì)≤8的非同構(gòu)圖都能區(qū)分，而且降低了=9的NDG的量級(jí)(從989降為40)。

簡并度可以進(jìn)一步對(duì)不可區(qū)分圖的性能進(jìn)行分析，這個(gè)值越小說明對(duì)這些圖的劃分越細(xì)、區(qū)分性能越好。不可區(qū)分不變量的平均簡并度ad的數(shù)據(jù)見表5。9、12及包含各種組合不變量的簡并度都處于較小的水平，而且隨著的增大簡并度幾乎沒有增大，其中12的簡并度有明顯下降的趨勢(shì)，5,129,12和5,9,12的簡并度已經(jīng)非常接近最優(yōu)值2?？梢灶A(yù)計(jì)，其將趨近2。這意味著這些圖不變量的絕大部分不可區(qū)分圖是兩兩不可區(qū)分的；當(dāng)非同構(gòu)數(shù)量非常巨大時(shí)，尋找一個(gè)不可區(qū)分圖的另外一個(gè)不可區(qū)分圖就變得很困難，這與文獻(xiàn)[10]的結(jié)論相吻合。5的簡并度隨著的增大似乎在線性增加，考慮到非同構(gòu)圖數(shù)量超指數(shù)增加，5在較大時(shí)應(yīng)該具有一定的區(qū)分度；同時(shí)，1的簡并度隨著的增大在指數(shù)增加，其在較大時(shí)應(yīng)該性能較差。

表5 不可區(qū)分不變量的簡并度

6 誤判率及隨機(jī)測試

誤判率是依據(jù)圖不變量不能區(qū)分兩個(gè)非同構(gòu)圖的概率，其可以采用不可區(qū)分圖的兩兩配對(duì)數(shù)NPR占所有兩兩組合數(shù)的比例來表示。圖5顯示了=7~10的；當(dāng)=0時(shí)，=0，圖5中沒有顯示這樣的數(shù)據(jù)。除1外，隨的增大呈指數(shù)級(jí)下降，當(dāng)=10時(shí)，已經(jīng)不足百萬分之一。可以預(yù)計(jì)當(dāng)較大時(shí)，很多圖不變量(如5、9、12及其組合)的誤判率會(huì)非常低，這確實(shí)是圖同構(gòu)的特點(diǎn)，文獻(xiàn)[11]引用了圖同構(gòu)方面專家BABAI和大數(shù)學(xué)家ERD?S的結(jié)論：只有一部分特殊的圖使圖同構(gòu)問題變得非常困難，而且找出這樣的圖例也是非困難的。本文認(rèn)為原因可能是絕大部分不可區(qū)分的圖是成對(duì)、成三或非常小圖群的形式出現(xiàn)，而非同構(gòu)圖的數(shù)量是驚人的，比如=13、||=40的非同構(gòu)圖有4 409 911 747 398種。因此即使是百萬級(jí)的非同構(gòu)圖集，出現(xiàn)一對(duì)或幾對(duì)不可區(qū)分的非同構(gòu)圖的概率也比較低。

圖5 配對(duì)數(shù)NPR占比PPR隨N變化的趨勢(shì)(“1”代表Ig 1，“(5,9)”代表Ig 5,9)

為了檢驗(yàn)5、9、12及其組合在較大時(shí)的誤判率，分別生成了=11、12、13、14、15的不同邊數(shù)的各10組1 000 000個(gè)圖的圖集。圖集是用Nauty2.6中的genrang生成，然后用shortg消去了其中同構(gòu)的圖。這些圖集平均有998 629個(gè)圖，最少的也有989 936個(gè)圖。=11~15的各組圖集對(duì)應(yīng)邊數(shù)分別為23~32、28~37、34~43、40~49和40~49。每組圖集計(jì)算得到的累加的結(jié)果見表6。依據(jù)=11的總數(shù)可以判斷不同圖不變量的性能，性能從低到高的排列為1＜5＜9＜5,9＜12＜5,12＜9,12≈5,9,12，而且除9,12與5,9,12之外，數(shù)據(jù)的區(qū)分很明顯。其實(shí)9,12與5,9,12的各項(xiàng)數(shù)據(jù)(不變量欠量、不可區(qū)分圖數(shù)、簡并度、不可區(qū)分圖的配對(duì)數(shù))都非常接近。

表6 10組圖集的不可區(qū)分圖的配對(duì)數(shù)NPR總數(shù)

由于＞11的累加數(shù)據(jù)出現(xiàn)不少0，其無法區(qū)分對(duì)應(yīng)的不變量性能，因此要有效地比較圖不變量的性能，建議對(duì)低階非同構(gòu)圖進(jìn)行計(jì)算，到目前為止，還沒有發(fā)現(xiàn)可以完全區(qū)分=9的所有非同構(gòu)圖的圖不變量。

7 結(jié) 論

本文依據(jù)頂點(diǎn)的層序遍歷信息，把頂點(diǎn)的度數(shù)分為同層之間的度數(shù)、向前的度數(shù)和向后的度數(shù)，結(jié)合頂點(diǎn)的最短路徑數(shù)和每層的寬度定義了15種頂點(diǎn)不變量。通過比較頂點(diǎn)不變量的細(xì)分能力，挑選出3種頂點(diǎn)不變量進(jìn)行組合，獲得了相應(yīng)的圖不變量5、9和12。對(duì)這些圖不變量及其組合進(jìn)行了較為詳細(xì)的分析，結(jié)果表明組合5,9,12對(duì)于各種非同構(gòu)圖具有較好的性能，不僅對(duì)≤8的非同構(gòu)圖都能區(qū)分，而且把=9的不可區(qū)分圖數(shù)量降到40，對(duì)=10和11的非同構(gòu)圖的計(jì)算表明其簡并度將趨近2，因此絕大部分不可區(qū)分圖是兩兩成對(duì)不可區(qū)分。

計(jì)算表明5、9和12的各種組合對(duì)于≥13的非同構(gòu)圖，即使是百萬級(jí)的非同構(gòu)圖集，出現(xiàn)一對(duì)或幾對(duì)不可區(qū)分非同構(gòu)圖的概率也非常低。因此要有效地比較圖不變量的性能，建議對(duì)低階非同構(gòu)圖進(jìn)行計(jì)算。尋找對(duì)于=9、10、11的所有非同構(gòu)圖具有更高性能的圖不變量是一個(gè)值得研究的方向。

[1] SAVAGE N. Graph matching in theory and practice [J]. Communications of the ACM, 2016, 59(7): 12-14.

[2] BABAI L. Graph Isomorphism in quasi-polynomial time [EP/OL]. [2017-01-10]. http: //arxiv.org/abs/1512. 03547.

[3] MCKAY B D, PIPERNO A. Practical graph isomorphism, II [J]. Journal of Symbolic Computation, 2014, 60(1): 94-112.

[4] HAO J Q, GONG Y Z, WANG Y W, et al. Using k-Mix-Neighborhood subdigraphs to compute canonical labelings of digraphs [J]. Entropy, 2017, 19(2): 79-128.

[5] 侯愛民. 哈密頓環(huán)與圖同構(gòu)問題的理論研究及算法設(shè)計(jì)[D]. 廣州: 華南理工大學(xué), 2013.

[6] 鄒瀟湘, 戴瓊. 圖同構(gòu)中的一類頂點(diǎn)細(xì)分方法[J]. 軟件學(xué)報(bào), 2007, 18(2): 213-219.

[7] PIEC S M, MALARZ K, KULAKOWSKI K, et al. How to count trees [J]. International Journal of Modern Physics C, 2005, 16(10): 1527-1534.

[8] 呼加璐. 基于特征壓縮方法的圖同構(gòu)算法及其在網(wǎng)絡(luò)模體發(fā)現(xiàn)中的應(yīng)用[D]. 西安: 西安電子科技大學(xué), 2010.

[9] DEHMER M, GRABNER M, MOWSHOWITZ A, et al. An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants [J]. Advances in Computational Mathematics, 2013, 39(2): 311-325.

[10] BABAI L, ERD?S P, SELKOW S M. Random graph isomorphism [J]. Siam Journal on Computing, 1980, 9(3): 628-635.

[11] GAMKRELIDZE A, VARAMASHVILI L, HOTZ G. New invariants for the graph isomorphism problem [J]. Journal of Mathematical Sciences, 2016, 218(6): 754-781.

[12] ALEKSANDAR I, YU G H, FENG L H. On the eccentric distance sum of graphs [J]. Journal of Mathematical Analysis & Applications, 2011, 381(2): 590-600.

[13] ORSINI F, FRASCONI P, RAEDT L D. Graph invariant kernels [C]//International Conference on Artificial Intelligence. New York: ACM Press, 2015: 3756-3762.

[14] HAUG N S, WAGNER S G, WANG H. Greedy trees, caterpillars, and Wiener-type graph invariants [J]. Match Communications in Mathematical and in Computer Chemistry, 2012, 68(1): 273-292.

[15] TRAN N T, MOHAN S, XU Z, et al. Current innovations and future challenges of network motif detection [J]. Briefings in Bioinformatics, 2015, 16(3): 497-525.

[16] MELO V A D, BOAVENTURANETTO P O, BAHIENSE L, et al. QAPV: a polynomial invariant for graph isomorphism testing [J]. Pesquisa Operacional, 2013, 33(2): 163-184.

[17] BRINKMANN G, COOLSAET K, GOEDGEBEUR J, et al. House of graphs: a database of interesting graphs[J]. Discrete Applied Mathematics, 2013, 161(1-2): 311-314.

Vertex Invariants Based on Level-Order Traversal and Their Graph Invariants

JIANG Shunliang, TANG Yiling, GE Yun, XU Shaoping, YE Famao

(Information Engineering School, Nanchang University, Nanchang Jiangxi 330031, China)

In order to find graph invariants with higher performance, fifteen kinds of vertex invariants are defined by weighted accumulation with the help of vertex data in the process of level-order traversal. Every kind of vertex invariants are able to compose a graph invariant after being sorted. The vertex degree is divided into the internal degree, the forward degree, and the backward degree during the traversal, while the internal degree and the backward degree include the number of loops. Three kinds of vertex invariants are selected based on the refining performance, and then the graph invariants are generated. The combination of three kinds of graph invariants performs well in distinguishing a variety of non-isomorphic connected graphs. Not only all the non-isomorphic graphs with the number of vertexes≤8 are distinguishable, but also the number of undistinguishable graphs with=9 is reduced from 989 of literature [9] down to 40, with the degeneracies of these graph invariants approaching 2. Random tests shows that these graph invariants have good performances in differentiation.

graph isomorphism; vertex invariants; graph invariants; indistinguishable graphs; degeneracy

TP 301.6

10.11996/JG.j.2095-302X.2018030424

A

2095-302X(2018)03-0424-08

2017-01-14；

2017-05-11

國家自然科學(xué)基金項(xiàng)目(61662044)

江順亮(1965-)，男，江西豐城人，教授，博士，博士生導(dǎo)師。主要研究方向?yàn)樗惴ㄔO(shè)計(jì)、計(jì)算機(jī)仿真、人工智能。E-mail：jiangshunliang@ncu.edu.cn