圖的相似性描述與匹配方法的研究及其應(yīng)用.pdf

1、圖的相似性和匹配是一個(gè)重要的研究領(lǐng)域,在數(shù)學(xué)問題,生物和化學(xué)領(lǐng)域,數(shù)據(jù)挖掘,網(wǎng)絡(luò)應(yīng)用等許多方面都有著廣泛的應(yīng)用。萬維網(wǎng)的出現(xiàn)在許多領(lǐng)域催生了大規(guī)模的海量統(tǒng)計(jì)數(shù)據(jù),節(jié)點(diǎn)關(guān)系圖是呈現(xiàn)關(guān)系數(shù)據(jù)結(jié)構(gòu)最直觀的方式,在各種研究和應(yīng)用領(lǐng)域中廣泛的采用,因此大規(guī)模圖作為數(shù)據(jù)的表現(xiàn)方式,具有十分重要的研究意義。
　　圖的搜索匹配算法屬于圖同構(gòu)判定的問題,一般情況下無法在多項(xiàng)式時(shí)間之內(nèi)求解,是一個(gè)NP完全問題,傳統(tǒng)方法的高開銷無法適應(yīng)許多大數(shù)據(jù)量應(yīng)用

2、的需要。而優(yōu)化算法的特殊性也無法應(yīng)用在一般的情況。為了提高圖的搜索和匹配效率,將提出一種建立在一個(gè)迭代計(jì)算圖相似性理論的基礎(chǔ)之上的算法。算法的核心思想是利用相關(guān)點(diǎn)和邊之間的相似度進(jìn)行迭代計(jì)算,然后證明了迭代收斂的規(guī)則并給出了算法的下界,將迭代公式用矩陣形式表示,并且利用矩陣性質(zhì)進(jìn)行簡(jiǎn)化。計(jì)算出圖之間的任意點(diǎn)和邊相似性的完整描述,通過一些簡(jiǎn)化方法提高求解效率,計(jì)算圖之間匹配的相似度。
　　最后將給出一個(gè)計(jì)算機(jī)軟件相似性研究的應(yīng)用實(shí)例