【摘要】：復(fù)雜網(wǎng)絡(luò)是眾多現(xiàn)實復(fù)雜系統(tǒng)的抽象表現(xiàn)形式,其節(jié)點代表復(fù)雜系統(tǒng)中的個體,網(wǎng)絡(luò)連邊蘊含著系統(tǒng)個體間的某種內(nèi)在聯(lián)系。隨著復(fù)雜網(wǎng)絡(luò)的物理意義和數(shù)學(xué)特性的深入研究,實際網(wǎng)絡(luò)中的一個共同性質(zhì),即社區(qū)結(jié)構(gòu),引起學(xué)者們的廣泛關(guān)注。研究發(fā)現(xiàn):整個網(wǎng)絡(luò)是由若干個“社區(qū)”構(gòu)成的,并且每個社區(qū)內(nèi)部節(jié)點之間的連接相對緊密,但各個社區(qū)之間的連接卻比較稀疏。復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)研究對分析復(fù)雜網(wǎng)絡(luò)的拓撲和層次結(jié)構(gòu)、理解社區(qū)的形成過程、預(yù)測復(fù)雜網(wǎng)絡(luò)的演化趨勢、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)的獨有特征等具有十分重要的理論意義與應(yīng)用價值。成功挖掘復(fù)雜網(wǎng)絡(luò)社區(qū)的關(guān)鍵在于根據(jù)網(wǎng)絡(luò)節(jié)點或邊的特性設(shè)計合適且高效的社區(qū)發(fā)現(xiàn)算法。本文選擇網(wǎng)絡(luò)節(jié)點之間的余弦相似性和樸素相異性等指標(biāo)作為劃分社區(qū)節(jié)點的標(biāo)準(zhǔn),分別設(shè)計出網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)新算法,并基于其他幾種重要的相似性指標(biāo)獲得多種相似性指標(biāo)的最優(yōu)組合,進一步獲得Zachary空手道網(wǎng)絡(luò)、海豚關(guān)系網(wǎng)絡(luò)、美國足球網(wǎng)絡(luò)和電力網(wǎng)絡(luò)等真實網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)結(jié)果。本文首先簡要介紹復(fù)雜網(wǎng)絡(luò)及其社區(qū)發(fā)現(xiàn)的概念、基本方法與研究意義。在此基礎(chǔ)上,重點介紹了幾類重要的社區(qū)發(fā)現(xiàn)算法及其劃分思想,如K-L算法、譜二分法、GN算法、Newman快速算法等。然后,選擇節(jié)點間的余弦相似性作為劃分社區(qū)節(jié)點的標(biāo)準(zhǔn),利用社區(qū)間的全局相似信息,通過迭代凝聚具有最大相似性的兩個社區(qū),得到網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)結(jié)果;而最優(yōu)社區(qū)數(shù)量由迭代過程中的模塊度的最大值自動獲得。利用新算法,獲得Zachary空手道網(wǎng)絡(luò)、海豚關(guān)系網(wǎng)絡(luò)、美國足球網(wǎng)絡(luò)和電力網(wǎng)絡(luò)等真實網(wǎng)絡(luò)的社區(qū)數(shù)量和最大模塊度值,并通過實證分析獲得多種相似性指標(biāo)的最優(yōu)組合結(jié)果。進一步,基于節(jié)點屬于不同社區(qū)的相異特征,定義節(jié)點間的相異性度量,結(jié)合分裂算法思想進而設(shè)計出基于節(jié)點間相異性度量的新社區(qū)發(fā)現(xiàn)算法。實證發(fā)現(xiàn),此算法的時間復(fù)雜度和社區(qū)發(fā)現(xiàn)結(jié)果的準(zhǔn)確性等稍微優(yōu)于GN算法。最后,總結(jié)了本文的研究工作,并對進一步的研究工作進行了展望。
【圖文】：

杭州電子科技大學(xué)碩士學(xué)位論文網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的定義和評價指標(biāo)結(jié)構(gòu)的定義究的深入階段，相關(guān)學(xué)者注意到復(fù)雜網(wǎng)絡(luò)的又一個非常普遍的特點，就是是由一些相對較小的“區(qū)”或者“群”組成[23]。所有的這些群滿足群里群彼此的連接十分松散。例如，就像圖 2.1 表示的那樣，，該網(wǎng)絡(luò)具有三個解，在圖內(nèi)已經(jīng)把它們用虛線圈起來了。在復(fù)雜網(wǎng)絡(luò)中，根據(jù)各個節(jié)點不分類從而得到各個社區(qū)[34-36]。

杭州電子科技大學(xué)碩士學(xué)位論文元素ijS 是第i個社區(qū)和第 j 個社區(qū)之間的相似度，矩陣維相似性矩陣中除了 1 以外（因為社區(qū)和自身合并沒有意義為maxS 相應(yīng)的兩個社區(qū)歸為一個新的社區(qū)。社區(qū)結(jié)構(gòu)的模塊度值。（2）（3）（4）到網(wǎng)絡(luò)中社區(qū)個數(shù)變?yōu)?1。最高的社區(qū)劃分結(jié)果就認為是網(wǎng)絡(luò)的最優(yōu)社區(qū)結(jié)構(gòu)。介紹算法的步驟，如圖 3.1：
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【參考文獻】

相關(guān)期刊論文 前2條

1 黃承慧;印鑒;侯f ;;一種結(jié)合詞項語義信息和TF-IDF方法的文本相似度量方法[J];計算機學(xué)報;2011年05期

2 王小黎;;一種改進的圖聚類的相異度度量方法[J];計算機應(yīng)用與軟件;2011年05期

本文編號：2624539