圖與其屬性結(jié)構(gòu)相關(guān)性的度量研究.pdf

1、本文提出了一個(gè)新的研究問(wèn)題即考察屬性信息與圖拓?fù)涞年P(guān)聯(lián)程度，它涵蓋了相當(dāng)廣泛的一類現(xiàn)實(shí)問(wèn)題，有著很強(qiáng)的實(shí)際背景和應(yīng)用前景。比如，人們常常會(huì)因?yàn)榕笥训耐扑]而去購(gòu)買某種商品，這種購(gòu)買行為與消費(fèi)者所在的社交網(wǎng)絡(luò)有著深刻的聯(lián)系。對(duì)商家來(lái)說(shuō)，如果能了解購(gòu)買行為與社交網(wǎng)絡(luò)關(guān)聯(lián)性的強(qiáng)弱，便能通過(guò)優(yōu)化廣告的投放策略而獲利，因此對(duì)這個(gè)問(wèn)題的研究蘊(yùn)含著很大的商業(yè)價(jià)值。
　　 在一些直觀思想的引導(dǎo)下，本文提出了一個(gè)有意義的度量屬性與圖結(jié)構(gòu)關(guān)聯(lián)程度強(qiáng)弱

2、的方式——p-measure。p-measure直觀意義明顯，計(jì)算簡(jiǎn)便，并且易于拓展。利用p-measure，我們可以很容易地看出某種屬性與圖結(jié)構(gòu)關(guān)聯(lián)程度的強(qiáng)弱，了解關(guān)聯(lián)性程度隨著時(shí)間演化的特點(diǎn)，也可以發(fā)掘不同屬性與圖結(jié)構(gòu)關(guān)聯(lián)程度的差異。
　　 本文給出了計(jì)算p-measure的核心算法——M算法。度數(shù)限制規(guī)則的引進(jìn)則大大提高了算法的效率。我們還從理論上分析了算法的復(fù)雜度。
　　 本文通過(guò)大量有代表性的實(shí)例來(lái)考察算法的有