復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法的-.研究與實(shí)現(xiàn)

《復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法的-.研究與實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、1．1．1背景1．1人們生活在一個(gè)充斥著各種復(fù)雜網(wǎng)絡(luò)的世界中，現(xiàn)實(shí)世界中的諸多系統(tǒng)都以網(wǎng)絡(luò)的形式存在的，各種現(xiàn)實(shí)存在的和抽象的網(wǎng)絡(luò)出現(xiàn)在人們生活的各個(gè)角落，隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同的性質(zhì)，即社團(tuán)結(jié)構(gòu)【l】。大量的實(shí)證研究表明，許多網(wǎng)絡(luò)是異構(gòu)的，也就是說(shuō)復(fù)雜網(wǎng)絡(luò)不是由一大批性質(zhì)完全相同的節(jié)點(diǎn)隨機(jī)地連接在一起的，而是許多不通類型的節(jié)點(diǎn)的組合，相同類型的節(jié)點(diǎn)之間存在較多的連接，而不同類型的節(jié)點(diǎn)之間的連接則相對(duì)較少，我們把滿足同一類型中的節(jié)點(diǎn)以及這

2、些節(jié)點(diǎn)之間的邊所構(gòu)成的子圖被稱為網(wǎng)絡(luò)中的社團(tuán)(community)。整個(gè)網(wǎng)絡(luò)是由若干個(gè)社團(tuán)構(gòu)成的，每個(gè)社團(tuán)內(nèi)部的節(jié)點(diǎn)之間的連接相對(duì)非常緊密，但是各個(gè)社團(tuán)之間的連接相對(duì)來(lái)說(shuō)比較稀疏，由于這些網(wǎng)絡(luò)具有很高的復(fù)雜性，因此被稱為“復(fù)雜網(wǎng)絡(luò)(complexnetwork)"，這些發(fā)現(xiàn)直接導(dǎo)致了網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的研究。1．1．2意義信息技術(shù)的迅猛發(fā)展使人類快速進(jìn)入了網(wǎng)絡(luò)時(shí)代，從Intemet到WWW，從大型電力網(wǎng)絡(luò)到全球交通網(wǎng)絡(luò)，從生物的大腦到新陳代謝網(wǎng)絡(luò)，從科研合作網(wǎng)絡(luò)到各種經(jīng)濟(jì)、政治、社會(huì)關(guān)系網(wǎng)絡(luò)SNS等，

3、人們生活在充滿格式各樣的復(fù)雜網(wǎng)絡(luò)的世界當(dāng)中，人類社會(huì)日益網(wǎng)絡(luò)化，需要人類對(duì)各種人工和自然的復(fù)雜網(wǎng)絡(luò)的行為有更好的認(rèn)識(shí)[21，復(fù)雜網(wǎng)絡(luò)中自動(dòng)搜尋或發(fā)現(xiàn)社團(tuán)具有重要的實(shí)用價(jià)值，社團(tuán)劃分有很多實(shí)際的用途，如社會(huì)網(wǎng)絡(luò)中的社團(tuán)代表根據(jù)興趣或背景而形成的真實(shí)的社會(huì)團(tuán)體；引文網(wǎng)絡(luò)中的社團(tuán)代表針對(duì)同一主題的相關(guān)論文；萬(wàn)維網(wǎng)中的社團(tuán)就是討論相關(guān)主題的若干網(wǎng)站13州：而生物化學(xué)網(wǎng)絡(luò)或者電子電路網(wǎng)絡(luò)中的社團(tuán)可以是某一類功能單元。發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社團(tuán)有助于我們更加有效地理解和開發(fā)這些網(wǎng)絡(luò)。例如多處理器并行計(jì)算中的處理器

4、分配，人際關(guān)系網(wǎng)絡(luò)的團(tuán)體劃分等等。因此，對(duì)復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)劃分算法的研究有較現(xiàn)實(shí)的意義。目前這一研究方向正逐漸受到更多的關(guān)注15J。2復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法的研究與實(shí)現(xiàn)1．2國(guó)內(nèi)外研究現(xiàn)狀由于復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分研究具有重要的理論意義和應(yīng)用價(jià)值，它不僅成為計(jì)算機(jī)領(lǐng)域中最具挑戰(zhàn)性的基礎(chǔ)性研究課題之一，也吸引了來(lái)自物理、數(shù)學(xué)、生物、社會(huì)學(xué)和復(fù)雜性科學(xué)等眾多領(lǐng)域的研究者，掀起了一股研究熱潮。目前這一領(lǐng)域的理論研究還處于起步階段，雖然已經(jīng)提出了很多經(jīng)典的復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)劃分算法，但是還沒能有一種相對(duì)統(tǒng)一的

5、算法解決大多數(shù)網(wǎng)絡(luò)劃分的問(wèn)題，另外，目前算法在效率和精度上都尚不能滿足很多實(shí)際應(yīng)用需求。從2002年至今，新的方法層出不窮，新的應(yīng)用領(lǐng)域不斷被拓展，不同領(lǐng)域的權(quán)威國(guó)際雜志和多個(gè)重要的國(guó)際學(xué)術(shù)會(huì)議多次報(bào)道這方面的研究工作。復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分方法已成為圖論、復(fù)雜網(wǎng)絡(luò)、數(shù)據(jù)挖掘等基礎(chǔ)理論的重要組成部分和相關(guān)課程的核心內(nèi)容，國(guó)際知名的研究性大學(xué)計(jì)算機(jī)系也開設(shè)了“TheStructureofInformationNetworks’’和“NetworksandDynamics"課程．國(guó)內(nèi)也出現(xiàn)了一些研究復(fù)雜網(wǎng)

6、絡(luò)的專著和圖書。1．3本文工作本文工作主要圍繞以下幾個(gè)方面展開。首先對(duì)現(xiàn)有的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法進(jìn)行深入研究，歸納現(xiàn)有算法的研究思路，在此工作基礎(chǔ)上對(duì)現(xiàn)有算法的優(yōu)缺點(diǎn)進(jìn)行總結(jié)，明確當(dāng)前復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法尚需解決的問(wèn)題，對(duì)本文算法的設(shè)計(jì)給出指導(dǎo)。其次，在綜合前人的研究成果基礎(chǔ)上，本文將對(duì)筆者提出的兩種復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法的設(shè)計(jì)思路以及算法效果給出論證。文中提出的第一種算法是基于遺傳規(guī)律的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法，本文將詳細(xì)論述如何將遺傳算法應(yīng)用到了復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分的過(guò)程中，文中還將提供針對(duì)此算法提出

7、的可擴(kuò)展的基因編碼方案，對(duì)文中引入的可提高收斂速度的孤立點(diǎn)修復(fù)策略進(jìn)行說(shuō)明，還將對(duì)該算法具有在復(fù)雜網(wǎng)絡(luò)的海量社團(tuán)劃分方案中搜索到較優(yōu)可接受劃分方案的能力給出證明。文中提出的第二種算法是基于引力定律的復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法，本文將圍繞該算法的兩個(gè)主要部分進(jìn)行說(shuō)明，本算法第一個(gè)要點(diǎn)是利用節(jié)點(diǎn)相對(duì)位置關(guān)系對(duì)節(jié)點(diǎn)進(jìn)行分類的引力聚類算法，第二個(gè)要點(diǎn)是生成節(jié)點(diǎn)相對(duì)位置關(guān)系的彈性算法。該部分將重點(diǎn)論述彈性算法是如何將復(fù)雜網(wǎng)絡(luò)鄰接關(guān)系快速映射到二維空間，使關(guān)聯(lián)度較高的節(jié)點(diǎn)形成相對(duì)致密的節(jié)點(diǎn)簇，從而使原本不存在位置

8、信息的節(jié)點(diǎn)具有了相對(duì)位置關(guān)系這以過(guò)程的。文中給出了一種近似計(jì)算方法優(yōu)化彈性算法的緒論3執(zhí)行效率。論文最后用實(shí)驗(yàn)證明此算法能識(shí)別出復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)，并且在不需要先驗(yàn)信息的情況下表現(xiàn)出較優(yōu)的劃分速度和劃分精度。最后，論文將介紹為輔助上述劃分算法研究而進(jìn)行的輔助研究和開發(fā)工作，文中給出了復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法的驗(yàn)證實(shí)驗(yàn)原理和過(guò)程，實(shí)現(xiàn)了多個(gè)對(duì)比算法，做了大量的實(shí)驗(yàn)和分析，給出了構(gòu)建測(cè)試復(fù)雜網(wǎng)絡(luò)的方法，搭建了用于算法研究的可擴(kuò)展實(shí)驗(yàn)平臺(tái)。1．4論文章節(jié)安排按照論述的內(nèi)容，本文對(duì)各個(gè)章節(jié)的寫作進(jìn)行了如下安排