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

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

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

【參考文獻(xiàn)】

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

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

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

本文編號(hào)：2624539