面向網(wǎng)絡(luò)的重疊社區(qū)發(fā)現(xiàn)方法研究.pdf

1、現(xiàn)實(shí)世界中存在著大量的復(fù)雜網(wǎng)絡(luò)，例如朋友網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、生物學(xué)網(wǎng)絡(luò)、網(wǎng)絡(luò)中頁(yè)面之間相互鏈接而形成的網(wǎng)絡(luò)、論文合著網(wǎng)絡(luò)、文獻(xiàn)引用網(wǎng)絡(luò)等等。許多研究表明，復(fù)雜網(wǎng)絡(luò)除了擁有無(wú)標(biāo)度和小世界特性，還具有社區(qū)結(jié)構(gòu)特性。近年來(lái)，復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)發(fā)現(xiàn)在學(xué)術(shù)界得到了深入的研究和探索，社區(qū)結(jié)構(gòu)發(fā)現(xiàn)算法的設(shè)計(jì)已成為復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)。在現(xiàn)實(shí)生活中，社區(qū)間是有可能重疊的，如，在科研合作網(wǎng)絡(luò)中，一個(gè)學(xué)者可能同時(shí)在多個(gè)領(lǐng)域與人合作;在社會(huì)網(wǎng)絡(luò)中，一個(gè)興

2、趣廣泛的人可能參與多個(gè)不同的社區(qū)活動(dòng)，這樣，就可能有某些節(jié)點(diǎn)同時(shí)屬于多個(gè)社區(qū)，為多個(gè)社區(qū)所共享。揭示復(fù)雜網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)可以幫助我們更好的理解網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，對(duì)重疊部分的研究有助于我們開(kāi)啟新的思路去解決網(wǎng)絡(luò)擁塞、輿論的傳播、計(jì)算機(jī)病毒和流行病毒傳播等問(wèn)題。
　　針對(duì)現(xiàn)有社區(qū)發(fā)現(xiàn)算法大多假定社區(qū)是不重疊的問(wèn)題，本文將模糊合作博弈應(yīng)用于重疊社區(qū)發(fā)現(xiàn)，設(shè)計(jì)了基于模糊合作博弈的重疊社區(qū)發(fā)現(xiàn)算法，通過(guò)隸屬函數(shù)來(lái)確定節(jié)點(diǎn)屬于社區(qū)的程度，通

3、過(guò)收益函數(shù)來(lái)確定節(jié)點(diǎn)加入社區(qū)后社區(qū)的收益，隸屬函數(shù)和收益函數(shù)共同決定節(jié)點(diǎn)是否加入社區(qū)。本文的主要工作包括:
　　(1)根據(jù)重疊社區(qū)發(fā)現(xiàn)中重疊節(jié)點(diǎn)所代表的實(shí)際意義，本文將模糊合作博弈應(yīng)用于重疊社區(qū)的發(fā)現(xiàn)，給出了算法的思路，并且對(duì)隸屬函數(shù)和收益函數(shù)的計(jì)算給出了詳細(xì)的過(guò)程，網(wǎng)絡(luò)中的節(jié)點(diǎn)以一定的隸屬度屬于社區(qū)，同時(shí)節(jié)點(diǎn)加入社區(qū)后社區(qū)會(huì)獲得相應(yīng)的收益，通過(guò)隸屬度和收益共同決定節(jié)點(diǎn)加入相應(yīng)的社區(qū)。
　　(2)設(shè)計(jì)了一種改進(jìn)的基于模糊合作

4、博弈的重疊社區(qū)發(fā)現(xiàn)算法，該算法以非重疊社區(qū)發(fā)現(xiàn)算法的社區(qū)劃分結(jié)果作為初始的社區(qū)，也就是社區(qū)結(jié)構(gòu)是已知的，通過(guò)計(jì)算社區(qū)的鄰接點(diǎn)的隸屬度以及鄰接點(diǎn)加入到社區(qū)后社區(qū)的收益，確定社區(qū)的重疊點(diǎn)，該算法的效率依賴于初始算法的選取，本文選取BGLL算法作為初始的算法，該算法是目前比較優(yōu)秀的非重疊社區(qū)發(fā)現(xiàn)算法。該方法很大程度上提高了發(fā)現(xiàn)重疊社區(qū)的效率。
　　(3)對(duì)本文中所提出的兩種算法在三種真實(shí)數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，并對(duì)其進(jìn)行性能評(píng)價(jià)與算法分析