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

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

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

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

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

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