本文選題：社團(tuán)發(fā)現(xiàn) + 社團(tuán)重疊�。� 參考：《東北大學(xué)》2014年碩士論文

【摘要】：自然界中存在的大量復(fù)雜系統(tǒng)都可以通過復(fù)雜網(wǎng)絡(luò)加以描述,而社團(tuán)結(jié)構(gòu)是繼小世界特性和無標(biāo)度特性之后發(fā)現(xiàn)的最為重要的復(fù)雜網(wǎng)絡(luò)特性。社團(tuán)是網(wǎng)絡(luò)中關(guān)聯(lián)緊密的一群節(jié)點,往往具有某些共同特征,具有一定的實際物理意義�；ヂ�(lián)網(wǎng)是典型的復(fù)雜網(wǎng)絡(luò),深入研究互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)可以幫助我們以分而治之的方式研究網(wǎng)絡(luò)的功能及演化過程,更加準(zhǔn)確的理解互聯(lián)網(wǎng)的組織原則、拓?fù)浣Y(jié)構(gòu)等。目前針對互聯(lián)網(wǎng)網(wǎng)絡(luò)特性的社團(tuán)發(fā)現(xiàn)研究還不足,傳統(tǒng)社團(tuán)發(fā)現(xiàn)算法并不能很好的反映互聯(lián)網(wǎng)獨(dú)有的特性。同時傳統(tǒng)的社團(tuán)發(fā)現(xiàn)算法大多數(shù)不能同時發(fā)現(xiàn)社團(tuán)的重疊性和層次性。本文在局部適應(yīng)度值最優(yōu)化算法(LFM)思想的基礎(chǔ)上,提出了基于共同鄰居加權(quán)的社團(tuán)發(fā)現(xiàn)算法(稱之為CNW-LFM算法)。算法中通過共同鄰居信息對邊進(jìn)行加權(quán),其權(quán)值大小表示節(jié)點之間的緊密程度,并將適應(yīng)度函數(shù)以網(wǎng)絡(luò)中邊的權(quán)值重新定義。然后在多個不同類型和不同規(guī)模的真實網(wǎng)絡(luò)進(jìn)行實驗,發(fā)現(xiàn)CNW-LFM算法的重疊模塊度高于原LFM算法,說明CNW-LFM算法優(yōu)于原算法,使得社團(tuán)劃分結(jié)果更加合理,而且該算法可以同時發(fā)現(xiàn)社團(tuán)的重疊性以及層次性。從而證明了結(jié)合網(wǎng)絡(luò)特性進(jìn)行加權(quán)的方法是可以提高社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)的準(zhǔn)確度以及合理性,為本文重點研究互聯(lián)網(wǎng)社團(tuán)結(jié)構(gòu)打下了堅實的基礎(chǔ)。針對互聯(lián)網(wǎng)的宏觀拓?fù)浣Y(jié)構(gòu)下的社團(tuán)研究,在CNW-LFM算法的基礎(chǔ)上,本文提出了基于地理位置加權(quán)的社團(tuán)發(fā)現(xiàn)算法(稱之為BGW-LFM算法)。針對互聯(lián)網(wǎng)數(shù)據(jù)量龐大的問題,算法中提出了網(wǎng)絡(luò)規(guī)模的縮減方法,從而明顯地提高了時間效率。同時該算法充分考慮了互聯(lián)網(wǎng)的地理特性,將地理位置信息和共同鄰居信息相結(jié)合對邊進(jìn)行加權(quán),邊的權(quán)值依然表示節(jié)點之間聯(lián)系的緊密程度。然后在多個不同規(guī)模的互聯(lián)網(wǎng)網(wǎng)絡(luò)進(jìn)行實驗,總結(jié)了算法中參數(shù)對社團(tuán)劃分結(jié)果的影響規(guī)律。對比實驗中發(fā)現(xiàn)BGW-LFM算法的重疊模塊度最高,其次是CNW-LFM算法,說明BGW-LFM算法使得社團(tuán)劃分結(jié)果更加合理。最后對比分析了社團(tuán)結(jié)構(gòu)的地理分布情況,發(fā)現(xiàn)BGW-LFM算法使得社團(tuán)結(jié)構(gòu)的地理分布更為緊湊。通過兩方面的對比說明BGW-LFM算法使得對于互聯(lián)網(wǎng)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)更加準(zhǔn)確,地理分布更為合理。而且該算法可以同時發(fā)現(xiàn)社團(tuán)的重疊性以及層次性。
[Abstract]:A large number of complex systems in nature can be described by complex networks, and the community structure is the most important complex network characteristics found after the characteristics of the small world and the scale-free characteristics. The community is a closely connected group of nodes in the network, which often has some common characteristics and has some practical physical meaning. Network is a typical complex network. The in-depth study of the community structure of the Internet can help us to study the function and evolution process of the network in a divide and conquer way, and more accurately understand the organization principles and topology of the Internet. It can well reflect the unique characteristics of the Internet. At the same time, the traditional association discovery algorithm can not find the overlap and hierarchy of the community at the same time. On the basis of the local fitness value optimization algorithm (LFM), a community discovery algorithm based on the common neighbor weighting (called the CNW-LFM algorithm) is proposed. The weight value of the same neighbor is weighted, the weight value represents the close degree between the nodes, and the fitness function is redefined with the weight value of the edge of the network. Then the experiment is carried out in several different types and different sizes of real networks. It is found that the overlap module degree of the CNW-LFM algorithm is higher than the original LFM algorithm, indicating that the CNW-LFM algorithm is superior to the original algorithm. The method makes the division result more reasonable, and the algorithm can find the overlap and the hierarchy of the community at the same time. Thus, it is proved that the method of weighting with the network characteristics can improve the accuracy and rationality of the association structure discovery, which lays a solid foundation for the study of the interconnected community structure. On the basis of CNW-LFM algorithm, a community discovery algorithm based on geographic location weighting (called BGW-LFM algorithm) is proposed on the basis of the macro topological structure of the Internet. In view of the large amount of Internet data, a reduction method of network size is proposed in the algorithm, and the time efficiency is obviously improved. The geographical features of the Internet are fully considered, the geographical location information is combined with the common neighbor information to weigh the edges. The edge weights still represent the close degree of the connections between the nodes. Then, the experiments are carried out on the Internet networks with different sizes. The influence rules of the number of the algorithms on the results of the community division are summarized. It is found that the overlap module of the BGW-LFM algorithm is the highest, followed by the CNW-LFM algorithm, which shows that the BGW-LFM algorithm makes the community division more reasonable. Finally, the geographical distribution of the community structure is compared and analyzed. It is found that the BGW-LFM algorithm makes the geographical distribution of the community structure more compact. Through the comparison of the two aspects, the BGW-LFM algorithm makes the algorithm make the right The structure of the Internet community is more accurate and the geographical distribution is more reasonable. Moreover, the algorithm can detect the overlapping and hierarchy of the community simultaneously.
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.02;O157.5

【相似文獻(xiàn)】

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

1 劉晉霞;曾建潮;薛耀文;;復(fù)雜網(wǎng)絡(luò)強(qiáng)社團(tuán)結(jié)構(gòu)探測[J];小型微型計算機(jī)系統(tǒng);2011年04期

2 賈寧寧;封筠;;復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)[J];河北省科學(xué)院學(xué)報;2013年02期

3 宣照國;苗靜;黨延忠;劉建國;;科研領(lǐng)域關(guān)聯(lián)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析[J];上海理工大學(xué)學(xué)報;2008年02期

4 王伊蕾;王遠(yuǎn)志;李濤;田生文;;偽度優(yōu)先演化網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)研究[J];計算機(jī)工程與應(yīng)用;2009年20期

5 汪小帆;劉亞冰;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J];電子科技大學(xué)學(xué)報;2009年05期

6 司夏萌;劉云;丁飛;熊菲;;具有社團(tuán)結(jié)構(gòu)的有界信任輿論涌現(xiàn)模型研究[J];系統(tǒng)仿真學(xué)報;2009年23期

7 謝軍;;復(fù)雜網(wǎng)絡(luò)中分析社團(tuán)結(jié)構(gòu)算法研究概述[J];信息通信;2010年04期

8 朱大勇;張新麗;李樹全;;利用局部拓?fù)湫畔l(fā)現(xiàn)模糊社團(tuán)結(jié)構(gòu)[J];電子科技大學(xué)學(xué)報;2011年01期

9 邵斐;蔣國平;;基于社團(tuán)結(jié)構(gòu)的負(fù)載傳輸優(yōu)化策略研究[J];物理學(xué)報;2011年07期

10 談煜;梁潤鵬;;一種基于層次化社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)可視化方法[J];微型電腦應(yīng)用;2012年04期

相關(guān)會議論文 前5條

1 苗清影;汪小帆;;基于社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)可控性研究[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

2 李曉佳;張鵬;狄增如;樊瑛;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[A];第四屆全國網(wǎng)絡(luò)科學(xué)學(xué)術(shù)論壇暨研究生暑期學(xué)校論文集[C];2008年

3 胡延慶;趙爾波;張丹;狄增如;樊瑛;;社團(tuán)結(jié)構(gòu)的局域和自適應(yīng)比較性定義及其相應(yīng)探測方法[A];第五屆全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文（摘要）匯集[C];2009年

4 吳文濤;肖仰華;何震瀛;汪衛(wèi);余韜;;基于權(quán)重信息挖掘社會網(wǎng)絡(luò)中的隱含社團(tuán)[A];第26屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）[C];2009年

5 樊瑛;李夢輝;張鵬;吳金閃;狄增如;;權(quán)重對網(wǎng)絡(luò)結(jié)構(gòu)和性質(zhì)的影響——社團(tuán)結(jié)構(gòu)中權(quán)重的作用[A];2006全國復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會議論文集[C];2006年

相關(guān)博士學(xué)位論文 前10條

1 程建軍;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測方法研究[D];蘭州大學(xué);2015年

2 李琳;基于多元統(tǒng)計分析的社團(tuán)挖掘算法研究[D];上海交通大學(xué);2014年

3 武志昊;復(fù)雜網(wǎng)絡(luò)中的重疊社團(tuán)發(fā)現(xiàn)問題研究[D];北京交通大學(xué);2013年

4 魏芳;基于圖挖掘的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)[D];復(fù)旦大學(xué);2008年

5 劉傳建;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)劃分及分析應(yīng)用[D];山東大學(xué);2014年

6 何東曉;復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法研究[D];吉林大學(xué);2014年

7 劉晉霞;復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測及其在資金融通網(wǎng)絡(luò)中的應(yīng)用研究[D];蘭州理工大學(xué);2013年

8 劉瑤;社會網(wǎng)絡(luò)特征分析與社團(tuán)結(jié)構(gòu)挖掘[D];電子科技大學(xué);2013年

9 鄔盈盈;基于V穩(wěn)定性理論的復(fù)雜網(wǎng)絡(luò)穩(wěn)定性分析與牽制控制方法研究[D];浙江大學(xué);2010年

10 于樂;社會網(wǎng)絡(luò)中社團(tuán)發(fā)現(xiàn)及網(wǎng)絡(luò)演化分析[D];北京郵電大學(xué);2014年

相關(guān)碩士學(xué)位論文 前10條

1 劉微;復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn)[D];遼寧師范大學(xué);2011年

2 王大軍;基于標(biāo)簽傳播的社團(tuán)檢測算法研究[D];遼寧大學(xué);2015年

3 楊強(qiáng);微博社交網(wǎng)絡(luò)模型的建立及其性質(zhì)研究[D];北京化工大學(xué);2015年

4 付世海;基于社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)多傳播源定位算法研究[D];東北大學(xué);2013年

5 馬驍騎;復(fù)雜網(wǎng)絡(luò)中社團(tuán)檢測技術(shù)研究[D];黑龍江大學(xué);2015年

6 張獻(xiàn)鵬;基于P4結(jié)構(gòu)的社團(tuán)挖掘方法[D];西安電子科技大學(xué);2014年

7 陳奔燕;復(fù)雜網(wǎng)絡(luò)的社團(tuán)探測[D];湘潭大學(xué);2015年

8 杜梅;基于半監(jiān)督的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法研究[D];合肥工業(yè)大學(xué);2014年

9 韓凌霄;復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分及城市公交網(wǎng)絡(luò)研究[D];青島理工大學(xué);2015年

10 董哲;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法研究[D];解放軍信息工程大學(xué);2014年

，

本文編號：2054432