圖數(shù)據(jù)中屬性差異緊密子圖查詢.pdf

1、近年來，圖數(shù)據(jù)挖掘技術(shù)已經(jīng)成為了一個備受關(guān)注的研究領(lǐng)域，由于現(xiàn)實世界中很多事物都能夠自然地使用圖模型來描述，該技術(shù)廣泛地應(yīng)用于社會網(wǎng)絡(luò)、計算機網(wǎng)絡(luò)、計算生物學、web應(yīng)用等領(lǐng)域。緊密子圖是具有特殊結(jié)構(gòu)與性質(zhì)的子圖，因緊密子圖的諸多性質(zhì)，緊密子圖能夠幫助理解各種類型關(guān)系網(wǎng)絡(luò)的結(jié)構(gòu)特征。因此，緊密子圖成為圖數(shù)據(jù)挖掘領(lǐng)域的重要研究方向。
　　 隨著信息技術(shù)的飛速發(fā)展，越來越多的真實網(wǎng)絡(luò)出現(xiàn)在人們視野中。在具有極大規(guī)模的同時，種類紛繁的

2、內(nèi)容信息也出現(xiàn)在這些網(wǎng)絡(luò)中。傳統(tǒng)的緊密子圖發(fā)現(xiàn)問題主要基于圖的拓撲結(jié)構(gòu)特征而忽略了圖上的內(nèi)容信息，而利用這些極具價值的內(nèi)容信息對傳統(tǒng)的緊密子圖發(fā)現(xiàn)問題進行擴展將能夠產(chǎn)生更多新的有意義的應(yīng)用。
　　 本文提出一種新的結(jié)合圖的結(jié)構(gòu)特征和節(jié)點內(nèi)容屬性的緊密子圖發(fā)現(xiàn)問題—top-k屬性差異q-clique查詢，找出圖中節(jié)點間屬性具有較大差異的q-clique。該問題旨在使所找出的緊密子圖中屬性內(nèi)容盡可能豐富且節(jié)點的屬性內(nèi)容各有特點。給定

3、q-clique的屬性差異度量，發(fā)現(xiàn)k個具有最大差異的q-clique稱為top-k屬性差異q-clique查詢。在科研合作關(guān)系圖中，該查詢可以發(fā)現(xiàn)諸如研究領(lǐng)域或所屬單位等屬性上不同的具有緊密合作關(guān)系的團隊，這類團隊可能具有更強的綜合競爭力。在股票市場圖中，該查詢可以發(fā)現(xiàn)彼此價格具有緊密相關(guān)性而來自于不同行業(yè)的股票組合。
　　 本文給出了三種q-clique的屬性差異度量，通過將節(jié)點間的屬性相異度轉(zhuǎn)換為鄰接邊的邊權(quán)值，使得問題轉(zhuǎn)

4、化為最大權(quán)值q-clique查詢問題，同時本文證明了該查詢問題為NP難問題。本文采用回溯法，利用圖的結(jié)構(gòu)性質(zhì)和邊的權(quán)值形成剪枝條件，提出了一種有效求解問題的算法AD-Qclique，同時依照best-first排序思想優(yōu)化節(jié)點訪問次序，提出基于優(yōu)先次序的AD-Qclique算法進一步提高算法性能。
　　 本文采用真實的ACM學者信息數(shù)據(jù)集進行實驗，分析了查詢算法的效率和查詢結(jié)果的質(zhì)量。實驗表明，本文所提出的算法AD-Qcliqu

5、e效率遠優(yōu)于基本算法BSL，而基于優(yōu)先次序的AD-Qclique算法也有效地改善了算法的性能。最后，本文對查詢結(jié)果q-clique中的節(jié)點的結(jié)構(gòu)中心性及結(jié)果q-clique的各類多樣性指數(shù)進行了分析，并比較了各屬性差異性度量的優(yōu)劣。實驗表明，帶層次簡單節(jié)點屬性相異度極好地滿足了本文所提出查詢問題的應(yīng)用需求，較高屬性差異度的查詢結(jié)果中的學者節(jié)點皆具有較強的結(jié)構(gòu)中心性、較高的H-index值及廣泛的研究領(lǐng)域。同時，結(jié)果q-clique都具有