標(biāo)簽零模型及子圖分布算法應(yīng)用研究

鄒曉紅,郭景峰,2,賀釋千,2,陳 晶,劉院英

1(燕山大學(xué) 信息科學(xué)與工程學(xué)院,河北 秦皇島 066004)2(河北省虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室,河北 秦皇島 066004)3(河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院,石家莊 050061)

1 引 言

圖是表現(xiàn)力很強(qiáng)的數(shù)據(jù)結(jié)構(gòu),能夠充分表示實(shí)體自身的信息及實(shí)體間的聯(lián)系,因而在生物信息學(xué)、化學(xué)等領(lǐng)域廣泛應(yīng)用.并且隨著對結(jié)構(gòu)化數(shù)據(jù)分析需求的大量增加,通過圖建模進(jìn)行圖挖掘問題已經(jīng)成為一個(gè)非常重要的研究課題.圖分類是圖挖掘的一個(gè)重要研究分支[1],而圖向量化是圖分類的基礎(chǔ),通過對圖提取特征向量化后根據(jù)得到的圖向量可以進(jìn)行圖分類.目前關(guān)于圖分類的研究中能用于提取分類特征的算法有兩類,一類是子圖分布算法,另一類是頻繁子圖挖掘算法.用于圖分類的子圖分布算法的相關(guān)研究最早起源于生物學(xué)與社會網(wǎng)絡(luò)等領(lǐng)域,其目的是檢測圖的非平凡特性用于發(fā)現(xiàn)不同圖之間的異同,在生物學(xué)研究中,通過檢測兩組蛋白質(zhì)交互網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)的不同可以發(fā)現(xiàn)兩者功能上的差異.例如通過把要檢測物質(zhì)的化學(xué)結(jié)構(gòu)和已知的致癌癥物質(zhì)抽象成圖比對,就可以初步判斷要檢測物質(zhì)是否致癌.

國外對用于圖分類的子圖分布算法研究已經(jīng)有很多,一般是基于一定的圖模型,將現(xiàn)實(shí)世界中的網(wǎng)絡(luò)抽象為圖并建模,在構(gòu)建圖模型的基礎(chǔ)上再進(jìn)行算法研究.如文獻(xiàn)[2]中首先定義小誘導(dǎo)子圖為Graphlet,簡稱為Graphlet模型,提出使用Graphlet頻度來測量網(wǎng)絡(luò)局部的拓?fù)浣Y(jié)構(gòu),給出了相對圖頻率距離公式和算法.2008年P(guān)rzulj N與Milenkovic′T對GDD改進(jìn),在文獻(xiàn)[3]中提出了GDV,又稱為圖簽名和圖簽名相似度以及圖簽名距離.GDV是一個(gè)圖向量,存放子圖分布信息,并根據(jù)圖的不同維度給出了相應(yīng)的權(quán)值,用于調(diào)節(jié)因?yàn)榫W(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)導(dǎo)致某些維度的數(shù)據(jù)嚴(yán)重偏高或嚴(yán)重偏低.2015年Ahmed N等人在文獻(xiàn)[4]中提出了PGD算法,拓展Graphlet的定義,根據(jù)改進(jìn)后的Graphlet模型計(jì)算子圖分布,利用補(bǔ)圖對所有子圖進(jìn)行了組合,利用組合數(shù)學(xué)公式減少了部分子圖的計(jì)算.2015年Elenberg E R等人在文獻(xiàn)[5]中提出了3-Profiles,描述有3個(gè)頂點(diǎn)的圖,可用于計(jì)算聚類系數(shù),在社會網(wǎng)絡(luò)里,聚類系數(shù)反映了人們間聯(lián)系的緊密程度.該算法利用馬爾科夫鏈建模并估算3-Profiles分布.國內(nèi)的子圖分布研究相對較少,譚尚旺等人對隨機(jī)完全圖中某些子圖的概率分布進(jìn)行了研究并給出極限定理[6].

隨著圖分類在諸多領(lǐng)域的廣泛應(yīng)用,如何提高分類的準(zhǔn)確性變得尤為重要.但是,根據(jù)Graphlet模型及改進(jìn)的模型計(jì)算的子圖分布只考慮到圖的拓?fù)浣Y(jié)構(gòu)信息,并未考慮圖中頂點(diǎn)和邊標(biāo)簽信息,用于圖分類時(shí),因?yàn)樘崛〉膱D分類特征過少而影響圖分類的準(zhǔn)確性.對此本文加以改進(jìn),首先,借鑒統(tǒng)計(jì)學(xué)的零模型構(gòu)建了n階標(biāo)簽零模型,該模型同時(shí)考慮圖的拓?fù)浣Y(jié)構(gòu)信息和圖中頂點(diǎn)和邊標(biāo)簽信息,增加圖分類的特征,提高圖分類的準(zhǔn)確性.其次,針對直接計(jì)算子圖分布,需要反復(fù)多次進(jìn)行圖同構(gòu)測試,導(dǎo)致時(shí)間復(fù)雜度較高的問題,在n階標(biāo)簽零模型基礎(chǔ)上提出兩個(gè)算法,一個(gè)是用于構(gòu)建圖索引的BGLI算法,另一個(gè)是在BGLI算法基礎(chǔ)上提出的計(jì)算子圖分布ESGS算法,降低時(shí)間復(fù)雜度,提高計(jì)算速度.

2 標(biāo)簽零模型

定義1.標(biāo)簽圖:設(shè)G=(V,E,Σ,L),其中V(G)和E(G)分別為圖G的頂點(diǎn)集和邊集、Σ為標(biāo)簽集,L為標(biāo)簽的映射函數(shù):對于?v∈V(G)記為L(v),對于?(vi,vj)∈E(G)記為L(vi,vj),用于映射頂點(diǎn)和邊的標(biāo)簽.

定義2.圖同構(gòu):圖同構(gòu)是雙射函數(shù)f使得f:V(G)→V(H),若標(biāo)簽圖G和標(biāo)簽圖H同構(gòu),則滿足下列條件:

1)若?v∈V(G),?v′∈V(H)

則v?v′,記為V(G)?V(H).

則(vi,vj)?(vk′,vl′),記為E(G)?E(H).

3)若?v∈V(G),?v′∈V(H)

則L(u)=L(v)

4)若?(vi,vj)∈E(G),?(vk′,vl′)∈E(H)

則L(vi,vj)=L(vk′,vl′)

圖同構(gòu)表明,若標(biāo)簽圖G和標(biāo)簽圖H同構(gòu),則V(G)與V(H)一一對應(yīng)且對應(yīng)頂點(diǎn)的標(biāo)簽相同,E(G)與E(H)一一對應(yīng)且對應(yīng)邊的標(biāo)簽相同.

定義3.n階零模型:n階零模型是與原圖G具有相同統(tǒng)計(jì)量的隨機(jī)圖H.設(shè)統(tǒng)計(jì)量有原圖G的頂點(diǎn)數(shù)N、邊數(shù)M和n個(gè)頂點(diǎn)的聯(lián)合度分布p(d1,d2,…,dn)(n≤N),其中dn為頂點(diǎn)度為n的個(gè)數(shù).要求根據(jù)原圖G生成的圖H滿足如下約束:

1)|V(G)|=|V(H)|=N

2)|E(G)|=|E(H)|=M

3)pG(d1,d2,…,dn)=pH(d1,d2,…,dn)(n≤N)

n階零模型是n階零配置模型的簡稱,n階零模型中的n個(gè)頂點(diǎn)的聯(lián)合度分布表明的是,具有n個(gè)頂點(diǎn)的子圖形成的子圖分布,并且當(dāng)n>1時(shí),要求這n個(gè)頂點(diǎn)所形成的子圖為連通圖,不出現(xiàn)孤立頂點(diǎn).下面舉例說明各階模型:

0階零模型:與原圖G具有相同頂點(diǎn)數(shù)N、邊數(shù)M和頂點(diǎn)的平均度D的隨機(jī)圖,其中平均度D是G中所有頂點(diǎn)的度的平均值D=2M/N.

1.階零模型:與原圖G具有相同頂點(diǎn)數(shù)N、邊數(shù)M、平均度D和度分布為p(d)的隨機(jī)圖,其中度分布p(d)是指原圖G中頂點(diǎn)度頻率分布[7].

2.階零模型:與原圖G具有相同的兩個(gè)頂點(diǎn)聯(lián)合度分布p(di,dj)和1階零模型中的所有約束條件的隨機(jī)圖.其中di是度為i的頂點(diǎn),dj是度為j的頂點(diǎn),p(di,dj)為兩個(gè)頂點(diǎn)聯(lián)合度分布,是指每條邊兩端連接頂點(diǎn)度的聯(lián)合度分布.

3.階零模型:與原圖G具有相同的三個(gè)頂點(diǎn)聯(lián)合度分布p(di,dj,dk)和2階零模型中的所有約束條件的隨機(jī)圖.三個(gè)頂點(diǎn)聯(lián)合度分布考慮到三個(gè)頂點(diǎn)之間的相互連接性,主要有兩種情況,一種是開三角形,另一種是閉三角形,即保證與原圖G具有相同的開三角形和閉三角形分布.

n階零模型如圖1所示,其中左邊的(a)圖為原圖,(b)到(e)圖分別為根據(jù)原圖提取的0到3階模型生成的隨機(jī)圖[8].文獻(xiàn)[8]用實(shí)驗(yàn)驗(yàn)證了根據(jù)原圖G提取統(tǒng)計(jì)量達(dá)到3階零模型時(shí),生成的新圖H已經(jīng)比較好的還原了原圖.當(dāng)階數(shù)n等于原圖G的頂點(diǎn)數(shù)N時(shí),n階零模型的約束最強(qiáng).

圖1 零模型示例Fig.1 Null model example

本文根據(jù)n階零模型提出了n階標(biāo)簽零模型用于計(jì)算子圖分布,同時(shí)考慮圖中頂點(diǎn)和邊標(biāo)簽信息.n階標(biāo)簽零模型的定義如下:

定義4.n階標(biāo)簽零模型:n階標(biāo)簽零模型是與原圖G具有相同統(tǒng)計(jì)量的隨機(jī)圖.設(shè)統(tǒng)計(jì)量有原圖G的頂點(diǎn)數(shù)N、邊數(shù)M和n個(gè)頂點(diǎn)的聯(lián)合標(biāo)簽分布p(L(v1),L(v2)…L(vn)),(n≤N)其中v1,v2…vn∈V(G),L(vn)為vn的標(biāo)簽,以及這n個(gè)頂點(diǎn)間邊上標(biāo)簽形成的聯(lián)合標(biāo)簽分布p(L(e1),L(e2)…

L(em))(m≤M),其中e1e2…em∈E(G),L(em)為em的標(biāo)簽.

要求根據(jù)原圖G生成的圖H滿足如下約束:

1)|V(G)|=|V(H)|=N

2)|E(G)|=|E(H)|=M

3)pG(L(v1),…,L(vn))=pH(L(v1),…,L(vn))

4)pG(L(e1),…,L(em))=pH(L(e1),…,L(em))

其中(n≤N),(m≤M)

下面舉例說明各階模型,如圖2所示,圖中所示為根據(jù)標(biāo)簽零模型對標(biāo)簽圖計(jì)算所形成的聯(lián)合標(biāo)簽分布,即n階標(biāo)簽零模型對應(yīng)的子圖分布.為方便舉例,圖中邊標(biāo)簽已省略.

圖2 標(biāo)簽零模型子圖分布示例Fig.2 Subgraph distribution of label null model example

1.階標(biāo)簽零模型:與原圖G具有相同頂點(diǎn)數(shù)N、邊數(shù)M、頂點(diǎn)標(biāo)簽分布p(L(vi))的隨機(jī)圖.即要求與原圖G具有相同的頂點(diǎn)數(shù)N、邊數(shù)M、頂點(diǎn)標(biāo)簽數(shù)、頂點(diǎn)標(biāo)簽種類數(shù)、每種頂點(diǎn)標(biāo)簽中的標(biāo)簽數(shù)、邊標(biāo)簽數(shù)、邊標(biāo)簽種類數(shù)、每種邊標(biāo)簽中的標(biāo)簽數(shù).

2.階標(biāo)簽零模型:與原圖G具有相同的兩個(gè)頂點(diǎn)聯(lián)合標(biāo)簽分布p(L(vi),L(vj))、這兩個(gè)頂點(diǎn)間的邊標(biāo)簽分布p(L(ei′))和1階標(biāo)簽零模型中的所有約束條件的隨機(jī)圖.其中頂點(diǎn)vi的標(biāo)簽為L(vi),頂點(diǎn)vj的標(biāo)簽為L(vi),p(L(vi),L(vj))為兩個(gè)頂點(diǎn)的聯(lián)合標(biāo)簽分布,是指每條邊兩端連接頂點(diǎn)的聯(lián)合標(biāo)簽分布,p(L(ei′)是這兩個(gè)頂點(diǎn)間邊的標(biāo)簽分布.

3.階標(biāo)簽零模型:與原圖G具有相同的三個(gè)頂點(diǎn)聯(lián)合標(biāo)簽分布p(L(vi),L(vj),L(vk)),這三個(gè)頂點(diǎn)間的三條邊聯(lián)合標(biāo)簽分布p(L(ei′),L(ej′),L(ek′))和2階標(biāo)簽零模型中的所有約束條件的隨機(jī)圖.

根據(jù)n階標(biāo)簽零模型提取圖G中n個(gè)頂點(diǎn)的子圖,該子圖包括了n個(gè)頂點(diǎn)及其互相連接的邊,其中包括頂點(diǎn)和邊的標(biāo)簽,即根據(jù)頂點(diǎn)提取的誘導(dǎo)子圖.因?yàn)楦麟A子圖的種類和每種子圖的個(gè)數(shù)由n階標(biāo)簽零模型唯一確定,所以子圖分布為同一分布是圖同構(gòu)的必要條件.下面給出定理和證明.

定理1.若圖G與圖H同構(gòu),且要求圖G與圖H的頂點(diǎn)集、邊集和標(biāo)簽集都為有限集或可列集,則根據(jù)n階標(biāo)簽零模型計(jì)算的子圖分布必為同一分布,即兩圖的子圖分布為同一分布是兩圖同構(gòu)的必要條件.

證明:當(dāng)n階標(biāo)簽零模型的階數(shù)等于1時(shí).因?yàn)閳DG與圖H同構(gòu),所以圖G與圖H擁有相同標(biāo)簽的頂點(diǎn)一一對應(yīng),并且標(biāo)簽的種類數(shù)相同,每種子圖擁有相同標(biāo)簽的頂點(diǎn)的個(gè)數(shù)也相同.因此,當(dāng)階數(shù)等于1時(shí),子圖分布退化成標(biāo)簽分布,此時(shí)定理顯然成立.

當(dāng)n階標(biāo)簽零模型的階數(shù)n等于大于1時(shí),用反證法證明,假設(shè)圖G與圖H同構(gòu),對應(yīng)的子圖分布分別為FG和FH,且為不同分布.

(1)

(2)

(3)

……,……

(4)

因?yàn)镸G=MH所以

(5)

(6)

因此可知在圖G與圖H中分別選取n個(gè)頂點(diǎn)的分布分別一一對應(yīng),這些分布聯(lián)合后分別為FG和FH,圖G與圖H的分布FG和FH是同一分布,與假設(shè)矛盾.所以兩圖的子圖分布為同一分布是兩圖同構(gòu)的必要條件,該必要條件證明了n階標(biāo)簽零模型用于圖分類的有效性.

問題1.子圖分布估計(jì)問題:設(shè)圖G有N個(gè)頂點(diǎn),M條邊,L個(gè)標(biāo)簽,SGi是G中的子圖.若SGi在圖G中有Ci個(gè)與其同構(gòu)的子圖,記其頻度為Ci,在G中根據(jù)標(biāo)簽零模型選取具有n個(gè)頂點(diǎn)的子圖SGi,將子圖集合{SGi}作為基本事件集,要求據(jù)此估計(jì)子圖分布.

為描述子圖分布需要引入隨機(jī)變量X,設(shè)X為一隨機(jī)變量

F(x)=P{X=φ(SGi)}=pi

(7)

其中{xi=φ(SGi)|(i=1,2…)},φ(SGi)∈[1,+).pi滿足條件:為隨機(jī)變量X的分布函數(shù),簡稱分布.

其中φ是一個(gè)標(biāo)識函數(shù),用于給每一個(gè)SGi一個(gè)唯一標(biāo)識,用于圖向量化,子圖的編號從1開始到+.根據(jù)標(biāo)簽零模型計(jì)算子圖分布,然后把提取的子圖及其頻度以向量的形式作為圖分類特征進(jìn)行圖分類.因?yàn)榇蠖鄶?shù)分類算法不能直接把子圖作為特征計(jì)算,所以需要給每一個(gè)子圖一個(gè)唯一標(biāo)識進(jìn)行向量化.

為估算子圖分布可以通過采樣估算子圖總體分布,樣本分布近似替代總體分布會有一定的偏差,為此需要知道當(dāng)樣本量一定時(shí),樣本分布提取了總體分布多少信息,即量化樣本信息提取比.

問題2.量化樣本信息提取比問題:假設(shè)窮舉圖G中所有子圖,可得到G圖中所有子圖的總體分布,簡稱總體分布,記為p(x).在圖G中采樣,當(dāng)子圖樣本,簡稱為樣本,量為k時(shí),可得到此k個(gè)子圖的樣本分布,簡稱樣本分布,記為q(x).要求據(jù)此定量分析q(x)在p(x)中提取了多少信息.

對于給定的概率分布可用信息熵進(jìn)行量化,因?yàn)樽訄D分布是概率分布,所以使用信息熵量化子圖分布信息.

定義5.信息提取比例:

r=Hq/Hp

(8)

信息提取比例是指樣本信息占總體信息的比例,簡稱信息提取比,其中Hp為總體分布的熵值,簡稱總體熵值,Hq為樣本分布熵值,簡稱樣本熵值.

樣本熵值可以通過樣本直接計(jì)算,而對于總體熵值,當(dāng)總體分布的信息熵收斂的情況下,可以通過窮舉計(jì)算出總體熵值,但時(shí)間復(fù)雜度是NP,所以可以根據(jù)最大熵原理推斷出總體最大熵分布,推斷出總體的極限熵值,近似替代總體熵值.考慮到實(shí)際需求,在樣本中最容易提取也最具有一般意義的統(tǒng)計(jì)量是均值和方差,所以假設(shè)均值和方差都存在的情況下,根據(jù)最大熵原理和相對熵推斷出總體最大熵分布.子圖分布本身是離散型分布,最大熵原理對離散或連續(xù)型分布都適用,為方便計(jì)算,令每個(gè)子圖映射為一個(gè)數(shù),且要求這些映射數(shù)相互間隔大于1.經(jīng)映射后,xi表示一個(gè)子圖.約束條件,xi在[1,+)區(qū)間內(nèi),總體的參數(shù)均值μ、總體的參數(shù)方差σ2都存在時(shí),總體最大熵分布p(x)就是正態(tài)分布N(μ,σ2).

設(shè):總體最大熵分布的概率密度函數(shù)為p(x),簡寫為p、熵函數(shù)為H(p)、總體的參數(shù)均值、總體的參數(shù)方差σ2、總體的極限熵值Hp.樣本的分布概率密度函數(shù)為q(x),簡寫為q、熵函數(shù)為H(q)、樣本統(tǒng)計(jì)量均值x、樣本統(tǒng)計(jì)量方差s2、樣本的信息熵Hq.

由相對熵公式可知

(9)

(10)

(11)

當(dāng)均值μ和方差σ2都存在時(shí),取p(x)=N(μ,σ2)則

(12)

令底數(shù)為e得

(13)

(14)

由于q(x)的均值方差有如下關(guān)系

(15)

所以

(16)

當(dāng)p(x)=N(μ,σ2)時(shí),上式取等號.根據(jù)最大熵原理求出總體最大熵分布后,就可以根據(jù)上式計(jì)算其極限熵值.

3 子圖分布算法

3.1 算法主要思想

子圖分布最基本的兩個(gè)步驟是:第一步,對圖進(jìn)行采樣.其中,樣本是圖中的子圖.第二步,對采集的樣本進(jìn)行圖同構(gòu)檢測,并對其計(jì)數(shù).

計(jì)算子圖分布過程中,不進(jìn)行任何優(yōu)化直接計(jì)算,會不可避免反復(fù)多次進(jìn)行圖同構(gòu)測試,導(dǎo)致相對較高時(shí)間復(fù)雜度.設(shè)k為采樣的子圖數(shù),則k個(gè)具有n個(gè)頂點(diǎn)的子圖需計(jì)算k2n!次.所以計(jì)算子圖分布的時(shí)間復(fù)雜度是O(k2n!).因?yàn)橹苯铀阉髯訄D需多次進(jìn)行掃描遍歷,會耗費(fèi)很多時(shí)間,尤其是在分布式的情況下,多機(jī)并發(fā)搜索子圖會極大增加網(wǎng)絡(luò)開銷減慢算法效率.而建立一個(gè)合適的索引實(shí)現(xiàn)對子圖的快速查找,可以避免多機(jī)并發(fā)搜索子圖,并通過每個(gè)索引找到關(guān)于子圖的信息,減少搜索時(shí)間.

為此,本文根據(jù)n階標(biāo)簽零模型提出兩個(gè)算法,一個(gè)是用于構(gòu)建GLI索引的BGLI(Build Graph Location Index)算法,另一個(gè)是在BGLI算法基礎(chǔ)上提出的計(jì)算子圖分布ESGS (Estimate SubGraph on Spark)算法.

3.2 基于圖不變量的圖索引

圖不變量是圖自身的屬性.如果兩個(gè)圖同構(gòu),那么它們不但擁有相同的拓?fù)浣Y(jié)構(gòu)而且也具有相同的圖不變量,反之,該性質(zhì)不成立,即不變量是判定圖同構(gòu)的必要非充分條件.例如一個(gè)圖的頂點(diǎn)數(shù)和邊數(shù)就是兩個(gè)圖不變量,圖中最大頂點(diǎn)度也是圖不變量.對于同構(gòu)的圖其圖不變量都是相同的,而圖不變量相同的圖不一定同構(gòu),所以,圖不變量不能直接用在同構(gòu)子圖的匹配或計(jì)數(shù)上.然而,圖不變量可以用來對非同構(gòu)圖進(jìn)行過濾,縮減搜索空間,間接提高算法效率.

本文提出兩個(gè)函數(shù),圖似然函數(shù)和頂點(diǎn)度映射函數(shù).這兩個(gè)函數(shù)分別利用標(biāo)簽信息和頂點(diǎn)度建立圖不變量.

定義6.圖似然函數(shù)(Graph Likelihood function):

(17)

該函數(shù)是利用子圖中頂點(diǎn)和邊的標(biāo)簽信息建立的圖不變量.其中G為標(biāo)簽圖,SG為G的子圖,pi是G中頂點(diǎn)標(biāo)簽i的頻率,ci是SG中標(biāo)簽i的出現(xiàn)次數(shù),CN為SG中標(biāo)簽總數(shù).其中標(biāo)簽分為頂點(diǎn)標(biāo)簽和邊標(biāo)簽兩種情況.圖似然函數(shù),簡稱GL函數(shù).

定理2.若SG和SG′同構(gòu),則

gl(G,SG)=gl(G,SG′)

(18)

定理可以分別應(yīng)用于頂點(diǎn)標(biāo)簽和邊標(biāo)簽,得到下列等式:

glv(G,SG)=glv(G,SG′)

(19)

gle(G,SG)=gle(G,SG′)

(20)

證明:設(shè)標(biāo)簽圖G有N個(gè)頂點(diǎn),M條邊,SG和SG′是G的子圖.epi是G中邊標(biāo)簽i的頻率,eci和ec′i分別是SG和SG′中邊標(biāo)簽i的出現(xiàn)次數(shù),CLE(SG)為SG邊標(biāo)簽的種類集合,|CLE(SG)|=em,CLE(SG′)為SG′邊標(biāo)簽的種類集合,|CLE(SG′)|=em′,若SG和SG′同構(gòu),則當(dāng)標(biāo)簽為邊標(biāo)簽時(shí):

gle(G,SG)=gle(G,SG′)

(21)

(22)

若SG和SG′同構(gòu),則SG和SG′共同擁有圖G的子邊標(biāo)簽集合{L1,L2,…,Li}=CLE(SG)=CLE(SG′)并且邊標(biāo)簽集合中的標(biāo)簽滿足下列等式

ec1=ec′1,ec2=ec′2,…,eci=ec′i

(23)

兩邊分別乘以各自邊標(biāo)簽Li的頻率的對數(shù)log(epi)得

ec1log(ep1)=ec′1log(ep1)

(24)

ec2log(ep2)=ec′2log (ep2)

(25)

…

ecilog (epi)=ec′ilog (epi)

(26)

因?yàn)閨CLE(SG)|=|CLE(SG′)|所以

gle(G,SG)=gle(G,SG′)

(27)

同理可得

glv(G,SG)=glv(G,SG′)

(28)

因此定理成立.

定義7.圖頂點(diǎn)度映射函數(shù)(graph vertex Degree Map function):

(29)

該函數(shù)是利用子圖中頂點(diǎn)的度信息建立的圖不變量.其中G為標(biāo)簽圖,SG為G的子圖,vi是G中頂點(diǎn),d(vi)是SG中頂點(diǎn)vi的度,f(d(vi))為SG中頂點(diǎn)vi的函數(shù).其中f映射函數(shù)是將具有相同度的頂點(diǎn)映射為同一正整數(shù),比如素?cái)?shù).圖頂點(diǎn)度映射函數(shù),簡稱DM函數(shù).

定理3.若SG和SG′同構(gòu),則

dm(SG)=dm(SG′)

(30)

證明:設(shè)標(biāo)簽圖G有N個(gè)頂點(diǎn),M條邊,其中|V(G)|=N,|E(G)|=M.SG和SG′是G的子圖.d(vi)是SG中頂點(diǎn)vi的度,d(v′i)是SG′中頂點(diǎn)v′i的度,若SG和SG′同構(gòu),則下式相等

dm(SG)=dm(SG′)

(31)

若SG和SG′同構(gòu),則SG中頂點(diǎn)vi,SG′中頂點(diǎn)v′i分別一一對應(yīng),且頂點(diǎn)的度相等,有等式(v1)=d(v′1),d(v2)=d(v′2),d(vi)=d(v′i),令f映射函數(shù)是將具有相同度的頂點(diǎn)映射為同一正整數(shù),比如素?cái)?shù).

f(d(v1))=f(d(v′1))

(32)

f(d(v2))=f(d(v′2))

(33)

…

f(d(vi))=f(d(v′i))

(34)

則

(35)

dm(SG)=dm(SG′)

(36)

但兩圖圖同構(gòu)也有可能度分布不相同,所以DM函數(shù)值是判斷圖同構(gòu)的非充分條件.由上述討論可知DM函數(shù)值是判斷圖同構(gòu)的必要非充分條件,所以是圖不變量.

本文提出了基于GL函數(shù)值和DM函數(shù)值的GLI索引,該索引可以用于分布式條件下.由定理2和定理3可知,GL函數(shù)值和DM函數(shù)值相同是圖同構(gòu)的必要條件,所以用GL函數(shù)值和DM函數(shù)值作為子圖的索引值,對子圖進(jìn)行分組.若有兩個(gè)子圖的GL函數(shù)值和DM函數(shù)值都分別相等,則把這兩個(gè)子圖分到同一組中.因?yàn)閼?yīng)用GL函數(shù)值和DM函數(shù)建立索引的過程類似,因此以GL函數(shù)為例進(jìn)行介紹.GLI索引如圖3所示.在圖3中(a)圖為圖G,(b)圖為根據(jù)其子圖GL函數(shù)值構(gòu)建的索引.

3.3 圖索引算法BGLI

算法1.BGLI

輸入:圖G,SG_list子圖列表

輸出:GLI索引

1 初始化GLI索引,GLI為空字典

2 ForSGiin SG_list:

3 Key=根據(jù)GL函數(shù)和DM函數(shù)計(jì)算SGi的索引值

4 If Key not in GLI:

5 Then初始化SG_Vec子圖向量,放入SG

6 Else SG_Vec =GLI[Key] 找鍵為Key的子圖向量

7 IfSGiin SG_Vec:

8 ThenSGi對應(yīng)的同構(gòu)圖計(jì)數(shù)加1

9 Else 在SG_Vec中初始化SGi

10 Return GLI索引

圖3 圖索引示例Fig.3 Index of graph example

BGLI算法的輸入為圖G,SG_list子圖列表,其中子圖列表是在圖G中通過采樣獲得的樣本.GLI索引是3層的森林結(jié)構(gòu).GLI索引的第一層和第二層形成了鍵值對(key value)字典結(jié)構(gòu),其中,鍵是子圖SGi的GL函數(shù)值和DM函數(shù)值,在BGLI算法第3行計(jì)算;值是具有相同GL函數(shù)值和DM函數(shù)值的子圖向量SG_Vec,在BGLI算法第4～10行計(jì)算.GLI索引的第二層和第三層也是鍵值對字典結(jié)構(gòu),其中,鍵是第二層中子圖向量SG_Vec中的子圖;值是該子圖的計(jì)數(shù)和該子圖鄰接字典,即由哈希列表實(shí)現(xiàn)的鄰接列表.

3.4 子圖分布算法ESGS

計(jì)算子圖分布問題有兩個(gè)技術(shù)難點(diǎn).其一是,當(dāng)數(shù)據(jù)規(guī)模過大時(shí),會導(dǎo)致較高時(shí)間復(fù)雜度,針對小規(guī)模數(shù)據(jù)的算法將難以處理海量數(shù)據(jù).其二是,計(jì)算子圖分布過程中會有大量的子圖數(shù)據(jù)存放在內(nèi)存當(dāng)中,這些中間運(yùn)算結(jié)果數(shù)據(jù)十分龐大.而基于分布式框架Spark的分布式算法能利用集群資源快速處理海量數(shù)據(jù).

ESGS算法是基于Spark的分布式算法,因此ESGS算法的計(jì)算流程也必須符合Spark的MapReduce計(jì)算模型流程,所以ESGS算法分為map過程和reduce過程,下面分別對ESGS算法的map過程和reduce過程詳細(xì)說明.

下面介紹ESGS算法的map過程,該過程主要負(fù)責(zé)將要計(jì)算任務(wù)分發(fā)到集群中每一個(gè)負(fù)責(zé)計(jì)算的worker節(jié)點(diǎn)中,包括對給定k個(gè)n階的子圖采樣,建立延遲采樣列表,根據(jù)BGLI算法對子圖列表中的子圖分類計(jì)數(shù)并構(gòu)建GLI索引.

算法2.ESGS-Fun-Map

輸入:階數(shù)n,圖G,采樣個(gè)數(shù)max_k

輸出:被索引的子圖數(shù)據(jù)GLI_data

1 初始化當(dāng)前采樣數(shù)k,初始化SG_list延遲采樣子圖列表

2 While k

3 初始化當(dāng)前采樣子圖SGi數(shù)的頂點(diǎn)集合vs={}

4 根據(jù)隨機(jī)游走選取頂點(diǎn)并放入vs中

5 根據(jù)頂點(diǎn)集合vs中的頂點(diǎn)提取子圖SGi

6 將SGi放入SG_list延遲采樣子圖列表

7 k++

8 調(diào)用算法 BGLI(G,SG_list)

9 Return GLI_data

算法ESGS-Fun-Map中2到7行是圖采樣過程,該圖采樣過程是基于隨機(jī)游走的.圖采樣過程有兩個(gè)條件,其一,若頂點(diǎn)集合vs為空且vs中的頂點(diǎn)數(shù)小于n,則隨機(jī)選取第一個(gè)頂點(diǎn)v,然后將頂點(diǎn)v放入頂點(diǎn)集合vs.其二,若頂點(diǎn)集合vs非空且vs中的頂點(diǎn)數(shù)小于n,則在鄰居頂點(diǎn)集合nvs中隨機(jī)選取一個(gè)頂點(diǎn),然后將其放入頂點(diǎn)集合vs.根據(jù)上述頂點(diǎn)選取的方法保證了采樣的子圖SGi是連通圖.該過程并不會真正在map過程全部發(fā)生,其第6行是構(gòu)建延遲采樣子圖列表,該延遲采樣子圖列表會記錄采樣的條件和隨后的行為,直至reduce函數(shù)觸發(fā)Spark提交作業(yè)完成.

下面介紹ESGS算法的reduce過程,該過程主要負(fù)責(zé)將集群中每一個(gè)負(fù)責(zé)計(jì)算的worker節(jié)點(diǎn)中數(shù)據(jù)回收與合并.

算法3.ESGS-Fun-Reduce

輸入:被索引的子圖數(shù)據(jù)GLI_src和 GLI_dec

輸出:合并后的被索引的子圖數(shù)據(jù)GLI_dec

1 For Key in GLI_src:

2 If Key not in GLI_dec:

3 Then在GLI_dec加入新數(shù)據(jù),其鍵為Key

4 value為GLI_src 對應(yīng)的SG_Vec

5 Else 合并GLI_src與GLI_dec具有相同Key的

6 SG_Vec,由相近頻率子圖開始圖同構(gòu)測試,

7 直到對全部子圖測試完畢.

8 If未找到同構(gòu)子圖 Then 插入 GLI_dec

其中偽代碼第5到7行是優(yōu)化的關(guān)鍵,該過程是數(shù)據(jù)回收合并階段,集群中每一個(gè)負(fù)責(zé)計(jì)算的worker節(jié)點(diǎn),都采集了相同數(shù)量的子圖樣本并依照索引對子圖進(jìn)行了分組,同一組的子圖都具有相同的GL函數(shù)值和DM函數(shù)值,在同一組的子圖已經(jīng)無法按照上述函數(shù)值進(jìn)行區(qū)分,必須進(jìn)行圖同構(gòu)測試.為提高計(jì)算速度,提出了依子圖頻度搜索及合并子圖的策略.該策略過程先依頻率對子圖排序,然后測試頻率相近的子圖,再測試頻率差異大的子圖,直到測試完畢.

該策略假設(shè)對獨(dú)立同分布的兩組樣本,當(dāng)采樣足夠大時(shí),同構(gòu)的子圖在這兩組樣本中的頻率應(yīng)相近或相同.設(shè)有兩個(gè)負(fù)責(zé)計(jì)算的worker節(jié)點(diǎn),都采集k個(gè)樣本,返回兩組子圖記為SG_Vec1與SG_Vec2,令每一個(gè)子圖的頻率為隨機(jī)變量,則由大數(shù)定律可知隨樣本量增大頻率會逼近其概率,則在SG_Vec1中任意取一個(gè)子圖sg1,其頻率為sg1f,若在SG_Vec2中有與sg1同構(gòu)的子圖sg2,則當(dāng)樣本量足夠大時(shí),sg2的頻率sg2f應(yīng)與sg1f相近或相同.根據(jù)上述討論可知,在上述情況下合并子圖時(shí),應(yīng)先測試頻率相近的子圖,進(jìn)而避免無效的圖同構(gòu)測試.

3.5 算法性能分析

BGLI與ESGS算法需要計(jì)算分以下幾個(gè)部分(1)計(jì)算圖G的各個(gè)標(biāo)簽頻率,設(shè)N=|V(G)|,其中N為圖G的頂點(diǎn)個(gè)數(shù),則需要計(jì)算N次.(2)根據(jù)GL函數(shù)和DM函數(shù)對k個(gè)子圖計(jì)算檢索,需要2k次.(3)設(shè)k為子圖個(gè)數(shù),c為索引類別個(gè)數(shù),λ為同一索引檢索到的子圖個(gè)數(shù),則k=cλ,則k個(gè)子圖需要計(jì)算kλ2n!次.則計(jì)算量總計(jì)為N+2kn+kλ2n!,其中N+2kn遠(yuǎn)遠(yuǎn)小于kλ2n!,所以ESGS算法的時(shí)間復(fù)雜度是O(kλ2n!).其中根據(jù)實(shí)驗(yàn)觀察發(fā)現(xiàn),當(dāng)無標(biāo)度網(wǎng)絡(luò)中的頂點(diǎn)標(biāo)簽分布服從參數(shù)為1.1的泊松分布時(shí),λ一般小于5.

4 實(shí)驗(yàn)分析

實(shí)驗(yàn)在一臺基本配置為:CPU AMD Athlon(tm)II X4 605e Processor、內(nèi)存4G、64G硬盤的PC上進(jìn)行、操作系統(tǒng)Fedora 23、Python 3.4.3 、Spark-2.0.2-bin-hadoop2.7、Java 1.8.0_60.為了驗(yàn)證(1)n階標(biāo)簽零模型用于圖分類的有效性.(2)根據(jù)n階標(biāo)簽零模型計(jì)算信息提取比可以間接確定合適的樣本數(shù)量減少冗余計(jì)算.(3)基于n階標(biāo)簽零模型的ESGS算法提取的子圖向量化后作為分類特征進(jìn)行圖分類的正確率.分別進(jìn)行三組實(shí)驗(yàn).

4.1 實(shí)驗(yàn)1.卡方檢驗(yàn)實(shí)驗(yàn)

卡方檢驗(yàn)實(shí)驗(yàn)要驗(yàn)證的是:

1)根據(jù)標(biāo)簽零模型計(jì)算的子圖分布可以判斷圖不同構(gòu).

2)對比標(biāo)簽零模型與Graphlet模型在判斷圖不同構(gòu)方面的差異顯著性水平.

用于卡方檢驗(yàn)的數(shù)據(jù),是由文獻(xiàn)[9]的模擬數(shù)據(jù)生成器生成的兩個(gè)圖,這兩個(gè)圖都是無標(biāo)度網(wǎng)絡(luò),其中模擬數(shù)據(jù)生成器的參數(shù)設(shè)置為:頂點(diǎn)數(shù)n為1000、隨機(jī)添加新邊數(shù)m為2、添加新邊后形成的三角形概率p分別為0.1和0.5.模擬數(shù)據(jù)生成器生成的圖并無標(biāo)簽,所以使用泊松分布生成標(biāo)簽,其中泊松分布的參數(shù)為1.1.

圖4 卡方檢驗(yàn)對比Fig.4 Comparison of chi2 testing

卡方檢驗(yàn)對比的實(shí)驗(yàn)結(jié)果如圖4,圖中Graphlet曲線是根據(jù)Graphlet模型計(jì)算的子圖分布進(jìn)行的卡方檢驗(yàn)值的曲線,ESGS曲線是根據(jù)標(biāo)簽零模型計(jì)算的子圖分布進(jìn)行的卡方檢驗(yàn)值的曲線.橫坐標(biāo)為樣本量,縱坐標(biāo)為顯著水平,顯著水平代表的是兩分布為同一分布的概率,接近1表示相同,接近0表示不相同.待檢測的數(shù)據(jù)是兩個(gè)不同構(gòu)的圖,通過各自的子圖分布檢驗(yàn)兩個(gè)圖不同構(gòu).

由圖4可知,隨著樣本量增加,Graphlet和ESGS顯著水平波動(dòng)性下降,其中ESGS顯著水平下降更快,當(dāng)樣本量增加到50至100時(shí),ESGS顯著水平已經(jīng)迅速下降到0.05左右,并且較為穩(wěn)定,而Graphlet還在劇烈波動(dòng).當(dāng)超過100后ESGS基本穩(wěn)定在0左右.

卡方檢驗(yàn)實(shí)驗(yàn)結(jié)果分析:造成顯著水平劇烈波動(dòng)的原因分兩方面,一方面,當(dāng)樣本量小于50時(shí),根據(jù)隨機(jī)采樣得到的子圖數(shù)量和種類差異都比較大,導(dǎo)致子圖分布收斂性不好,以至于Graphlet和ESGS顯著水平劇烈波動(dòng).另一方面,當(dāng)樣本量大于50時(shí),因?yàn)镚raphlet模型只考慮圖的拓?fù)湫畔⒉豢紤]頂點(diǎn)和邊的標(biāo)簽信息,提取出用于區(qū)分圖的特征較少,導(dǎo)致顯著水平劇烈波動(dòng).而ESGS不僅考慮圖的拓?fù)湫畔⑦€考慮頂點(diǎn)和邊的標(biāo)簽信息,提取出用于區(qū)分圖的特征相對較多,相對較多特征使得子圖分布檢驗(yàn)更容易判斷出兩圖是不同構(gòu)的,結(jié)果表現(xiàn)在ESGS顯著水平波動(dòng)較小.

在當(dāng)前的試驗(yàn)條件下,上述實(shí)驗(yàn)結(jié)果表明:(1)根據(jù)標(biāo)簽零模型計(jì)算的子圖分布能夠判斷圖不同構(gòu).(2)ESGS的顯著水平下降更快且相對穩(wěn)定,說明用標(biāo)簽零模型比Graphlet模型在判斷圖不同構(gòu)方面的差異顯著性水平上更好.

4.2 實(shí)驗(yàn)2.信息提取比實(shí)驗(yàn)

信息提取比實(shí)驗(yàn)要驗(yàn)證的是:(1)子圖總體分布信息熵的上限是存在的,其上限是正態(tài)分布的熵值.(2)計(jì)算信息提取比可間接確定樣本量,避免樣本量過多造成冗余計(jì)算.

圖5 熵曲線和信息提取比Fig.5 Entropy curve and information extraction ratio

用于信息提取比實(shí)驗(yàn)的數(shù)據(jù)和上文的卡方檢驗(yàn)實(shí)驗(yàn)數(shù)據(jù)相同.信息提取比實(shí)驗(yàn)結(jié)果如圖5,在圖5中的(a)到(d)圖為從數(shù)據(jù)中分別對3到6階各自采樣的子圖樣本的熵曲線圖.其中,橫坐標(biāo)為采樣數(shù)量,單位為子圖個(gè)數(shù),縱坐標(biāo)為熵值,底數(shù)為e,單位為奈特nat;圖中Hpe、Hpn、Hq分別為指數(shù)分布熵曲線、正態(tài)分布熵曲線、樣本分布熵曲線,其中指數(shù)分布、正態(tài)分布的參數(shù)都是通過樣本統(tǒng)計(jì)量均值、方差和參數(shù)上下界估算的.圖5中的(e)到(h)圖為從數(shù)據(jù)中分別對3到6階各自采樣的子圖樣本的信息提取比曲線圖,其中橫坐標(biāo)為采樣數(shù)量,縱坐標(biāo)為信息提取比r,Hper為以指數(shù)分布為上限的信息提取比熵曲線,Hpnr為以正態(tài)分布為上限的信息提取比熵曲線.

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

1)可以觀察到給定均值和方差的情況下,隨階數(shù)增大,樣本熵曲線與正態(tài)分布熵曲線接近速度最快,而且相對于樣本熵與指數(shù)分布的熵偏離更小,正態(tài)分布的熵值是樣本分布的熵值上界.隨階數(shù)增高,信息提取比熵曲線逐漸穩(wěn)定,以正態(tài)分布為上限的信息提取比高于以指數(shù)分布為上限的信息提取比,這進(jìn)一步證明了正態(tài)分布的熵值比指數(shù)分布的熵值更接近樣本分布的熵值,所以正態(tài)分布的熵值可以近似替代總體分布的極限熵.樣本分布的熵值與正態(tài)分布的熵值接近速度最快,但依舊有發(fā)散趨勢,說明正態(tài)分布并非總體分布.

2)結(jié)合信息提取比實(shí)驗(yàn)和上文的卡方檢驗(yàn)實(shí)驗(yàn)結(jié)果分析,可發(fā)現(xiàn)當(dāng)樣本量為50以下時(shí)信息熵增長最快,此時(shí)顯著水平劇烈波動(dòng),當(dāng)樣本量為50到200時(shí),信息熵增長趨于平緩,信息提取比處于90%到98%之間,此時(shí)顯著水平也趨于0.顯著水平接近0表明兩圖不同構(gòu).

在當(dāng)前的試驗(yàn)條件下,通過本實(shí)驗(yàn)可以得出結(jié)論:

1)從熵極限角度看,正態(tài)分布的熵是總體分布的上限,但總體分布并非正態(tài)分布.因此可以使用正態(tài)分布的熵近似替代總體分布的極限熵計(jì)算信息提取比.

2)通過對信息提取比計(jì)算可以間接確定樣本的數(shù)量,避免樣本量過多造成冗余計(jì)算.

4.3 實(shí)驗(yàn)3.分類實(shí)驗(yàn)

本實(shí)驗(yàn)驗(yàn)證在不同數(shù)據(jù)集下,基于n階標(biāo)簽零模型的ESGS算法提取的子圖向量化后作為分類特征進(jìn)行圖分類的正確率.

本實(shí)驗(yàn)使用的數(shù)據(jù)集是由美國國家癌癥研究院(NCI)公開的兩組基準(zhǔn)數(shù)據(jù),包括NCI1數(shù)據(jù)集和NCI109數(shù)據(jù)集,NCI提供的兩組基準(zhǔn)數(shù)據(jù)來自于抗腫瘤活性預(yù)測任務(wù).這兩組基準(zhǔn)數(shù)據(jù)分別代表兩組可能致癌物的數(shù)據(jù)集,致肺癌物質(zhì)和致卵巢癌物質(zhì).每一種物質(zhì)表示為一個(gè)圖,若癌癥檢測為陽性則為1,否則為0.如圖6和圖7所示,圖中橫坐標(biāo)為分類使用的方法,縱坐標(biāo)為正確率.

圖分類的實(shí)驗(yàn)結(jié)果如圖6和圖7,在圖6和圖7中Graphlet代表的是根據(jù)Graphlet模型提取特征后應(yīng)用于各分類算法的實(shí)驗(yàn)結(jié)果.圖中PGD代表的是根據(jù)PGD算法提取特征后,應(yīng)用于各分類算法的實(shí)驗(yàn)結(jié)果.圖中ESGS代表的是ESGS算法根據(jù)標(biāo)簽零模型提取特征后,應(yīng)用于各分類算法的實(shí)驗(yàn)結(jié)果.圖中ESGS_gl代表的是ESGS算法近似計(jì)算版,其中提取特征為圖似然函數(shù)值分布,應(yīng)用于各分類算法的實(shí)驗(yàn)結(jié)果.圖6和圖7中分類方法分別為,基于伯努利模型的貝葉斯分類算法bernoulliNB,基于多項(xiàng)式模型的貝葉斯分類算法MultinomialNB,支持向量機(jī)分類算法clf_svm.其中clf_svm_ch2代表的是數(shù)據(jù)經(jīng)過卡方校驗(yàn)的方法進(jìn)行特征選取后,進(jìn)行支持向量機(jī)分類算法計(jì)算.

實(shí)驗(yàn)結(jié)果分析:由圖6和圖7可知,Graphlet模型的正確率最低,隨子圖頂點(diǎn)個(gè)數(shù)增加,正確率有所提升.PGD算法的正確率有所提高,而應(yīng)用標(biāo)簽零模型計(jì)算的ESGS算法正確率最高.即使是當(dāng)ESGS算法僅計(jì)算了圖似然函數(shù)值分布,對應(yīng)的分類正確率也比PGD算法的要好.

圖6 NCI1數(shù)據(jù)分類對比Fig.6 NCI1 data classification and comparison

其中支持向量機(jī)的正確率提高最為顯著,這是由于支持向量機(jī)在處理線性不可分?jǐn)?shù)據(jù)的方法決定的.支持向量機(jī)會通過核函數(shù)將輸入的低維空間數(shù)據(jù)映射到高維特征空間中,然后在其中構(gòu)造出最優(yōu)分離超平面,把低維空間中不好分的非線性數(shù)據(jù)分開.顯然當(dāng)對同一組數(shù)組,提取的分類特征越多,就越容易形成高維空間,從實(shí)驗(yàn)結(jié)果看,在這樣的高維空間更容易對數(shù)據(jù)分類.

圖7 NCI109數(shù)據(jù)分類對比Fig.7 NCI109 data classification and comparison

Graphlet模型提取的分類特征最少,所以正確率最低.PGD算法的正確率有所提高,這是因?yàn)镻GD算法提取的分類特征包含了Graphlet模型中所不包含的非連通子圖.ESGS_gl代表了當(dāng)ESGS算法僅計(jì)算圖似然函數(shù)值分布時(shí),忽略了部分結(jié)構(gòu)信息,導(dǎo)致分類特征減少,正確率稍低.ESGS算法提取的分類特征雖然是連通子圖,但包含了子圖中頂點(diǎn)的標(biāo)簽信息,其分類特征最多,所以正確率最高.

4.4 實(shí)驗(yàn)總結(jié)

首先,用實(shí)驗(yàn)驗(yàn)證了n階標(biāo)簽零模型用于圖分類的有效性.其次,通過實(shí)驗(yàn)的結(jié)果驗(yàn)證了子圖總體分布信息極限熵值的上限是正態(tài)分布的熵值,計(jì)算信息提取比可以間接確定樣本的數(shù)量,避免樣本量過多造成冗余計(jì)算.最后,在NCI1數(shù)據(jù)集和NCI109數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了,基于n階標(biāo)簽零模型的ESGS算法提取的子圖向量化后作為分類特征可以提高圖分類的準(zhǔn)確性.

5 總結(jié)和展望

為提高子圖分布算法用于圖分類的準(zhǔn)確性,本文構(gòu)建了n階標(biāo)簽零模型,該模型同時(shí)考慮圖的拓?fù)浣Y(jié)構(gòu)信息和圖的標(biāo)簽信息,增加了圖分類的特征.證明和驗(yàn)證了n階標(biāo)簽零模型用于圖分類的有效性.借鑒信息熵,對子圖分布進(jìn)行了量化分析.針對計(jì)算子圖分布時(shí)需要反復(fù)多次進(jìn)行圖同構(gòu)測試的問題,本文提出了索引算法BGLI和子圖分布算法ESGS并在spark上實(shí)現(xiàn),降低了時(shí)間復(fù)雜度.通過實(shí)驗(yàn)驗(yàn)證了,基于n階標(biāo)簽零模型的ESGS算法提取的子圖作為分類特征可以提高圖分類的準(zhǔn)確性.

本文在計(jì)算子圖分布時(shí),計(jì)算的是全部子圖的分布,覆蓋面雖然全面,但計(jì)算量大.因?yàn)樵趫D分類時(shí),不同類別的圖,可能具有共同的子圖,而這部分子圖作為共有特征,分類意義不大.所以下一步的工作是,整合子圖分布到圖分類算法中,進(jìn)一步提高圖分類的準(zhǔn)確性,減少計(jì)算量.

：

[1] Lam W W M,Chan K C C.A graph mining algorithm for classifying chemical compounds [C].IEEE International Conference on Bioinformatics and Biomedicine,2008:321-324.

[2] Przulj N,Corneil D I.Modeling interactome scale-free or geometric [J].Bioinformatics,2004,20(18):3508-3515.

[4] Ahmed N K,Neville J,Rossi R A,et al.Efficient graphlet counting for large networks [C].IEEE International Conference on Data Mining,2015:1-10.

[5] Elenberg E R,Shanmugam K,Borokhovich M,et al.Beyond triangles:a distributed framework for estimating 3-profiles of large graphs [C].Proceedings of the 21thACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2015:229-238.

[6] Tan Shan-wang,Huang Guo-xun.The limit theorem of probability distribution for some subgraphs in random complete graphs [J].Journal of Guangxi University Natural Science Edition,1991,16(3):12-18.

[7] Newman M,Guo Shi-ze,Chen Zhe.Networks:an introduction [M].Beijing:Oxford University Press,Inc,2014.

[8] Mahadevan P,Krioukov D,Fall K,et al.Systematic topology analysis and generation using degree correlations [C].ACM Special Interest Group on Data Communication Computer Communication Review,2006,36(4):135-146.

[9] Holme P,Kim B J.Growing scale-free networks with tunable clustering [J].Physical Review E,2002,65(2):026107.

附中文參考文獻(xiàn)：

[6] 譚尚旺,黃國勛.隨機(jī)完全圖中某些子圖的概率分布極限定理 [J].廣西大學(xué)學(xué)報(bào)自然科學(xué)版,1991,16(3):12-18.

[7] 馬克·紐曼,郭世澤,陳 哲.網(wǎng)絡(luò)科學(xué)引論 [M].北京：電子工業(yè)出版社,2014.