發(fā)布時間：2020-12-21 03:53

　　通過社團(tuán)檢測和社團(tuán)分析可以獲取復(fù)雜網(wǎng)絡(luò)中的重要信息,幫助控制網(wǎng)絡(luò)、預(yù)測網(wǎng)絡(luò)演化。最初的社團(tuán)檢測研究集中在無向網(wǎng)絡(luò)和非重疊社團(tuán)上,但由于現(xiàn)實世界存在大量有向網(wǎng)絡(luò),以及網(wǎng)絡(luò)中普遍存在的重疊性,重疊社團(tuán)檢測和有向網(wǎng)絡(luò)社團(tuán)檢測逐漸成為社團(tuán)檢測研究的重點和熱點。重疊社團(tuán)檢測一直是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的重點和難點之一。由于真實網(wǎng)絡(luò)普遍存在層次結(jié)構(gòu),結(jié)合層次性的重疊社團(tuán)檢測方法將更適用于現(xiàn)實世界復(fù)雜網(wǎng)絡(luò)的研究分析。本文基于領(lǐng)導(dǎo)度和從屬度概念,并對計算領(lǐng)導(dǎo)度的條件做了適合本文重疊社團(tuán)檢測模型的改動。在此基礎(chǔ)上結(jié)合網(wǎng)絡(luò)層次性建立了一種基于領(lǐng)導(dǎo)度和從屬度的重疊社團(tuán)檢測算法模型——從屬度樹算法模型。模型根據(jù)從屬度值將網(wǎng)絡(luò)重新組織為樹結(jié)構(gòu),通過劃分樹來發(fā)現(xiàn)重疊節(jié)點和重疊社團(tuán)。實驗表明從屬度樹算法模型可以結(jié)合層次性檢測重疊社團(tuán),并且能找到其他算法不能找到的重疊節(jié)點。劃分社團(tuán)的擴(kuò)展模塊度值大于對比算法,社團(tuán)劃分結(jié)果更接近實際社團(tuán)結(jié)構(gòu)。相比于無向網(wǎng)絡(luò)社團(tuán)檢測,有向網(wǎng)絡(luò)社團(tuán)檢測要考慮網(wǎng)絡(luò)的方向信息,社團(tuán)檢測更加復(fù)雜困難,要將無向網(wǎng)絡(luò)社團(tuán)檢測算法改進(jìn)以適用于有向網(wǎng)絡(luò),關(guān)鍵在于將網(wǎng)絡(luò)的方向性融入算法模型中。本文利用包含網(wǎng)絡(luò)方... 

【文章來源】：西安科技大學(xué)陜西省

【文章頁數(shù)】：70 頁

【學(xué)位級別】：碩士

【部分圖文】：

“歌尼斯堡七橋”簡化網(wǎng)絡(luò)圖

1緒論11緒論1.1研究背景和意義1.1.1復(fù)雜網(wǎng)絡(luò)復(fù)雜網(wǎng)絡(luò)的引入是為了研究現(xiàn)實中的復(fù)雜系統(tǒng)，復(fù)雜網(wǎng)絡(luò)的“復(fù)雜”之處在于結(jié)構(gòu)復(fù)雜、節(jié)點復(fù)雜和影響因素復(fù)雜。對應(yīng)到復(fù)雜系統(tǒng)就是系統(tǒng)成員之間的關(guān)系復(fù)雜、成員和關(guān)系的含義多樣、這些含義可能還隨著時間不斷變化、復(fù)雜系統(tǒng)可能會受到許多內(nèi)力外力因素的影響和作用。復(fù)雜網(wǎng)絡(luò)一般都具有一些特殊的共有性質(zhì)，比如自組織、自相似、吸引子、小世界、無標(biāo)度等性質(zhì)。對于復(fù)雜網(wǎng)絡(luò)的研究經(jīng)歷了四個階段。第一個階段數(shù)學(xué)家歐拉提出圖論(GraphTheory)作為復(fù)雜網(wǎng)絡(luò)的研究工具。歐拉在對“歌尼斯堡七橋問題”進(jìn)行研究時將普萊格爾河上的七座橋和河中間的兩座島和河岸抽象為了圖形，如圖1.1和圖1.2所示。抽象后的圖形很像我們現(xiàn)在常見的網(wǎng)絡(luò)圖，七橋問題也被簡化為一筆畫圖形問題。圖論現(xiàn)在是數(shù)學(xué)中一個獨立的分支，對復(fù)雜網(wǎng)絡(luò)的研究起著至關(guān)重要的作用。圖1.1“歌尼斯堡七橋”示意圖圖1.2“歌尼斯堡七橋”簡化網(wǎng)絡(luò)圖第二個階段是20世紀(jì)60年代，匈牙利兩位數(shù)學(xué)家提出了ER隨機(jī)圖理論[1]，該理論中描述了一種比較簡單的隨機(jī)圖網(wǎng)絡(luò)，圖中包括n個節(jié)點，并且以概率p隨機(jī)連接任意兩個節(jié)點形成最終網(wǎng)絡(luò)。學(xué)術(shù)界中公認(rèn)ER隨機(jī)圖理論是開啟復(fù)雜網(wǎng)絡(luò)系統(tǒng)性研究的開創(chuàng)性理論。

1緒論3的事，但越大型的網(wǎng)絡(luò)，社團(tuán)檢測越有意義。因為對大型網(wǎng)絡(luò)直接進(jìn)行結(jié)構(gòu)分析和動態(tài)演化預(yù)測是相當(dāng)復(fù)雜的，這時候就可以通過研究社團(tuán)的結(jié)構(gòu)來研究整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，通過研究社團(tuán)的功能揭示網(wǎng)絡(luò)的功能，通過研究社團(tuán)的規(guī)律和演化趨勢來推斷網(wǎng)絡(luò)的規(guī)律、預(yù)測網(wǎng)絡(luò)的演化趨勢。社團(tuán)結(jié)構(gòu)之所以具有這樣由部分推整體的特殊功能，是因為復(fù)雜網(wǎng)絡(luò)普遍具有自相似特性。網(wǎng)絡(luò)的自相似性是指網(wǎng)絡(luò)和它的一部分子網(wǎng)絡(luò)即社團(tuán)在結(jié)構(gòu)、性質(zhì)、功能上幾乎或者完全相同。圖1.3具有社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)最初研究者們一直致力于非重疊社團(tuán)檢測研究，就是將網(wǎng)絡(luò)劃分成不相交的社團(tuán)結(jié)構(gòu)，一個節(jié)點只能被劃分在一個社團(tuán)中。這是因為最初的研究一般都在人工網(wǎng)絡(luò)上做實驗，人為設(shè)置了非重疊的網(wǎng)絡(luò)，而且非重疊社團(tuán)檢測更加簡單清晰地反映了社團(tuán)檢測的意義。但隨著研究者們開始研究真實世界的復(fù)雜網(wǎng)絡(luò)，發(fā)現(xiàn)了非重疊社團(tuán)檢測算法用于一些具有重疊特性的現(xiàn)實網(wǎng)絡(luò)中時有較大的局限性。比如社交網(wǎng)絡(luò)中的人們自然地?fù)碛卸鄠�社團(tuán)成員的身份特征；一個人通常與家人、朋友和同事等幾個社交群體有聯(lián)系；研究人員可能在幾個研究領(lǐng)域都很活躍；比如生物網(wǎng)絡(luò)中節(jié)點可能具有多個功能。因此重疊確實是許多現(xiàn)實世界網(wǎng)絡(luò)尤其是社交網(wǎng)絡(luò)的重要特征。出于這個原因，研究者們越來越關(guān)注重疊社團(tuán)檢測算法的研究。重疊社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中可能有多個節(jié)點屬于多個群集。例如圖1.4就是一個含有重疊社團(tuán)結(jié)構(gòu)的小網(wǎng)絡(luò)。在圖1.4中，節(jié)點7、8、9組成一個社團(tuán)，這個社團(tuán)與其他的社團(tuán)不存在重疊。節(jié)點1、2、3、4組成一個社團(tuán)，節(jié)點4、5、6組成一個社團(tuán)，這兩個社團(tuán)之間有重疊，重疊節(jié)點為節(jié)點4。重疊社團(tuán)檢測的另一個重要意義是能同時找到重疊節(jié)點，這些重疊節(jié)點往往在現(xiàn)實中具有特殊地性質(zhì)或者功能。比如

【參考文獻(xiàn)】：
期刊論文
[1]節(jié)點不對稱轉(zhuǎn)移概率的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法[J]. 許平華,胡文斌,邱振宇,聶聰,唐傳慧,高曠,劉中舟.  軟件學(xué)報. 2019(12)
[2]從屬度樹算法檢測復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)[J]. 付立東,李丹,李占利.  計算機(jī)科學(xué). 2019(12)
[3]結(jié)合概率矩陣的改進(jìn)譜聚類社區(qū)發(fā)現(xiàn)算法[J]. 張書博,任淑霞,吳濤.  西安電子科技大學(xué)學(xué)報. 2019(03)
[4]基于多層復(fù)雜網(wǎng)絡(luò)理論的海洋貨運網(wǎng)絡(luò)的抗毀性研究[J]. 劉澤羲,王文俊,潘林.  海洋通報. 2018(06)
[5]基于復(fù)雜網(wǎng)絡(luò)的危險品道路運輸網(wǎng)絡(luò)優(yōu)化策略研究[J]. 種鵬云,尹惠.  復(fù)雜系統(tǒng)與復(fù)雜性科學(xué). 2018(03)
[6]新型社交網(wǎng)絡(luò)謠言傳播演化模型研究[J]. 吳曉,劉萬平,楊武,盧玲,劉小洋,黃詩雯.  復(fù)雜系統(tǒng)與復(fù)雜性科學(xué). 2018(02)
[7]基于進(jìn)化譜分方法的動態(tài)社團(tuán)檢測[J]. 付立東,聶靖靖.  計算機(jī)科學(xué). 2018(02)
[8]一種改進(jìn)的網(wǎng)絡(luò)魯棒性與有效性增強方法[J]. 慕彩紅,柴文壹,劉逸,劉敬.  西安電子科技大學(xué)學(xué)報. 2018(04)
[9]在線社會網(wǎng)絡(luò)謠言檢測綜述[J]. 陳燕方,李志宇,梁循,齊金山.  計算機(jī)學(xué)報. 2018(07)
[10]基于矢量影響力聚類系數(shù)的高效有向網(wǎng)絡(luò)社團(tuán)劃分算法[J]. 鄧小龍,翟佳羽,尹欒玉.  電子與信息學(xué)報. 2017(09)



本文編號：2929137