【摘要】：復(fù)雜網(wǎng)絡(luò)在對(duì)現(xiàn)實(shí)中諸多系統(tǒng)的描述方面有著突出貢獻(xiàn),諸如物流、互聯(lián)網(wǎng)等等現(xiàn)實(shí)系統(tǒng)都可以使用復(fù)雜網(wǎng)絡(luò)來(lái)進(jìn)行描述。復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要的特征為社區(qū)結(jié)構(gòu)特征,具體表現(xiàn)為:在同一社區(qū)內(nèi),結(jié)點(diǎn)間邊較為稠密;在不同社區(qū)之間邊則較為稀疏。社區(qū)發(fā)現(xiàn)方法可以有效探測(cè)網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu),發(fā)現(xiàn)不同網(wǎng)絡(luò)中潛在的規(guī)律,這對(duì)于我們理解網(wǎng)絡(luò)功能,預(yù)測(cè)網(wǎng)絡(luò)行為有著重要意義和價(jià)值。目前,社區(qū)發(fā)現(xiàn)算法大致可分為以下三種:基于優(yōu)化的算法、啟發(fā)式算法及其他算法。但是,這些算法或多或少的存在著運(yùn)行速度不夠快、精確度較低等問(wèn)題。為了解決上述問(wèn)題,本文針對(duì)社區(qū)發(fā)現(xiàn)方法,主要進(jìn)行如下工作:1、針對(duì)傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法時(shí)間復(fù)雜度高的問(wèn)題,本文將傳統(tǒng)閾值與結(jié)構(gòu)相似度的概念結(jié)合,提出一種新的社區(qū)發(fā)現(xiàn)算法STCA。該算法主要思想如下:(1)對(duì)于給定閾值k,計(jì)算網(wǎng)絡(luò)兩點(diǎn)間的結(jié)構(gòu)相似度作為這兩點(diǎn)間的邊權(quán)值。(2)刪除結(jié)構(gòu)相似度小于k的邊,并重復(fù)以上步驟(1)(2),直到?jīng)]有邊可以刪除,計(jì)算此時(shí)社區(qū)對(duì)應(yīng)的模塊函數(shù)Q的值;(3)將閾值增加一定量,并重復(fù)上述過(guò)程;(4)取最大模塊度對(duì)應(yīng)社區(qū)為最終劃分結(jié)果。通過(guò)大量的實(shí)驗(yàn)測(cè)試,結(jié)果表明:本文提出的STCA算法可以在確保劃分精度的前提下,提升算法的運(yùn)行速度。2、針對(duì)傳統(tǒng)遺傳算法在社區(qū)發(fā)現(xiàn)方面生成初始種群精確度較低的問(wèn)題,本文提出一種新的基于改進(jìn)遺傳算法的社區(qū)發(fā)現(xiàn)方法SSGA。該方法主要思想為:將傳統(tǒng)的遺傳算法輪盤賭選擇法與社區(qū)網(wǎng)路中結(jié)構(gòu)相似度的概念結(jié)合,使染色體上的每一個(gè)基因都趨于選擇結(jié)構(gòu)相似度比較大的鄰居結(jié)點(diǎn),從而大大提升初始種群的劃分精度。本算法在人工基準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)與真實(shí)世界網(wǎng)絡(luò)數(shù)據(jù)下進(jìn)行了實(shí)驗(yàn)。結(jié)果表明,本文提出的SSGA算法在提升初始種群劃分精度的同時(shí),整體劃分精度也有所提升,具有更高的整體劃分性能。
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2019
【分類號(hào)】：TP18;O157.5
【圖文】：

社區(qū)結(jié)構(gòu)在復(fù)雜網(wǎng)絡(luò)中普遍存在，應(yīng)用領(lǐng)域不同，相應(yīng)的社區(qū)結(jié)構(gòu)含義逡逑不同。如：科學(xué)家協(xié)作網(wǎng)絡(luò)中的社區(qū)代表學(xué)術(shù)研宄相似的科學(xué)家群體；共享逡逑單車網(wǎng)絡(luò)中社區(qū)代表具有相似功能的區(qū)域范圍的集合，如同屬學(xué)校范疇的區(qū)逡逑域。社區(qū)結(jié)構(gòu)具有非重疊社區(qū)結(jié)構(gòu)和重疊社區(qū)結(jié)構(gòu)（Ｐａｌｌａｅ／ｆｌ／，邋２００５）之分。逡逑非重疊社區(qū)結(jié)構(gòu)即網(wǎng)絡(luò)的每個(gè)結(jié)點(diǎn)只屬于一個(gè)社區(qū)，而重疊社區(qū)則表示網(wǎng)絡(luò)逡逑中存在同時(shí)屬于多個(gè)社區(qū)的結(jié)點(diǎn)，如在社會(huì)網(wǎng)絡(luò)中每個(gè)結(jié)點(diǎn)（人）在家庭網(wǎng)絡(luò)逡逑中扮演父母角色，而在單位又扮演職工角色；在蛋白質(zhì)交互網(wǎng)絡(luò)中，一個(gè)蛋逡逑白質(zhì)分子可能因與其他多個(gè)蛋白質(zhì)分子簇相互作用而具有不同功能＞８］。目逡逑前，人們對(duì)于社區(qū)結(jié)構(gòu)的研究己經(jīng)滲透到了計(jì)算機(jī)、物理、社會(huì)學(xué)、生物學(xué)、逡逑數(shù)學(xué)等多個(gè)領(lǐng)域，與社區(qū)發(fā)現(xiàn)相關(guān)的文獻(xiàn)也層出不窮，《Ｎａｔｕｒｅ》、《Ｓｃｉｅｎｃｅ》逡逑等國(guó)際頂級(jí)期刊均有呈現(xiàn)；麻省理工、斯坦福大學(xué)等知名高校均設(shè)置了復(fù)雜逡逑網(wǎng)絡(luò)課程［９￣。社區(qū)發(fā)現(xiàn)己經(jīng)成為當(dāng)前多領(lǐng)域研究的前沿?zé)狳c(diǎn)之一。逡逑正因復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)普遍存在，因此研究網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)具有巨大的逡逑

“七橋”向翻示宜民

邐社區(qū)發(fā)現(xiàn)概述邐逡逑作網(wǎng)絡(luò)圖。按照邊是否有方向，可將網(wǎng)絡(luò)圖劃分為有向圖和無(wú)向圖；逡逑按照邊是否有權(quán)值，將網(wǎng)絡(luò)劃分為有權(quán)圖和無(wú)權(quán)圖。下面給出圖的定義：逡逑定義２－１（圖）令Ｇ＝（Ｋ￡）表示圖，其中，吟｛Ｖｌ，ｖ２，…＿ｖｎ｝為網(wǎng)絡(luò)結(jié)點(diǎn)集合，逡逑門為結(jié)點(diǎn)個(gè)數(shù)，佐｛０＾』）｜１，」６７｜＾尹＿／｝為網(wǎng)絡(luò)邊的集合，｜五｜邋＝邋？７為邊數(shù)。逡逑定義２－２邋（圖的矩陣表示）對(duì)于給定非賦權(quán)圖Ｇ，采用ｎｘｎ的鄰接矩陣Ａ表逡逑示，構(gòu)造矩陣」＝邋（％）＿，貝Ｕ有：逡逑＿＼ｌ邋＾邋ｖＪ＾ｅＥ邐ｎ邋ｎ逡逑％邋＝叫0邋（ｖ，＋，ｖ＞￡邐（）逡逑為了直觀描述上述定義，給定圖４邋（ａ）所示網(wǎng)絡(luò)Ｇ，其鄰接矩陣Ａ如圖４邋（ｂ）逡逑所示：逡逑

【參考文獻(xiàn)】

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

1 陳建芮;洪志敏;汪麗娜;烏蘭;;Dynamic evolutionary community detection algorithms based on the modularity matrix[J];Chinese Physics B;2014年11期

2 馬昱欣;徐佳逸;彭帝超;張婷;金呈哲;屈華民;陳為;彭群生;;A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks[J];Journal of Computer Science & Technology;2013年05期

3 Le Yug;Bin Wug;Bai Wang;;LBLP:Link-Clustering-Based Approach for Overlapping Community Detection[J];Tsinghua Science and Technology;2013年04期

4 Ping LIU;Fenglin CHEN;Yunlu MA;Yuehong HU;Kai FANG;Rui MENG;;Research community detection from multi-relation researcher network based on structure/attribute similarities[J];Chinese Journal of Library and Information Science;2013年01期

5 吳英駿;黃翰;郝志峰;陳豐;;Local Community Detection Using Link Similarity[J];Journal of Computer Science & Technology;2012年06期

6 公茂果;張嶺軍;馬晶晶;焦李成;;Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J];Journal of Computer Science & Technology;2012年03期

本文編號(hào)：2744568