本文關(guān)鍵詞：基于局部擴(kuò)充的重疊社區(qū)發(fā)現(xiàn)算法研究和改進(jìn)

  更多相關(guān)文章： 重疊社區(qū)發(fā)現(xiàn) 節(jié)點(diǎn)影響力 局部優(yōu)化 并行計(jì)算

【摘要】：隨著網(wǎng)絡(luò)的飛速發(fā)展以及社交媒體的廣泛應(yīng)用,使得人與人之間的聯(lián)系尤為密切。這種錯(cuò)綜復(fù)雜的關(guān)系組成一個(gè)龐大的社交網(wǎng)絡(luò),因此吸引了眾多學(xué)者致力于復(fù)雜網(wǎng)絡(luò)的研究,從復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)并抽取其中的模塊結(jié)構(gòu)這就是所謂的社區(qū)發(fā)現(xiàn)。以前學(xué)者都致力于非重疊網(wǎng)絡(luò)的研究,然后這在現(xiàn)實(shí)生活中是不實(shí)用的,由此引發(fā)了大家對(duì)重疊網(wǎng)絡(luò)的研究,近幾年來取得了不小的進(jìn)展。本文即針對(duì)重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行改進(jìn)。重疊社區(qū)即網(wǎng)絡(luò)中包含的節(jié)點(diǎn)不止屬于一個(gè)社區(qū),能夠有效地識(shí)別這些重疊節(jié)點(diǎn)是本文算法研究的重點(diǎn)。比較有名的算法有LFM算法和GCE算法,它們都是利用網(wǎng)絡(luò)的局部信息,對(duì)單個(gè)種子節(jié)點(diǎn)進(jìn)行成長的理念。本文鑒于局部擴(kuò)充的核心思想,對(duì)種子選擇、社區(qū)擴(kuò)充剪枝、相似度判斷、并行化模型等提出了自己的改進(jìn)方案。(1)由于LFM算法選擇種子節(jié)點(diǎn)過于隨機(jī),影響算法準(zhǔn)確性;而GCE算法需要找到網(wǎng)絡(luò)圖的所有團(tuán)結(jié)構(gòu),影響算法效率;本文采取折中策略,通過刪除網(wǎng)絡(luò)中影響力較小的節(jié)點(diǎn)來得到核心結(jié)構(gòu)。主要基于度數(shù)較多的點(diǎn)在社團(tuán)結(jié)構(gòu)中是比較重要的節(jié)點(diǎn),如果一個(gè)節(jié)點(diǎn)的影響力較大那么它鄰居節(jié)點(diǎn)也是重要的。(2)LFM算法和GCE算法在對(duì)一個(gè)種子進(jìn)行擴(kuò)充時(shí)并未對(duì)其候選集進(jìn)行判斷,這嚴(yán)重影響了算法性能。本文對(duì)擴(kuò)充過程進(jìn)行了細(xì)致的推導(dǎo)和嚴(yán)格的數(shù)學(xué)證明,對(duì)社區(qū)擴(kuò)充過程產(chǎn)生的候選集進(jìn)行了剪枝處理,以進(jìn)一步的提升算法效率。(3)種子擴(kuò)充后生成的社區(qū)存在一定的相似性,如果不加以判斷會(huì)對(duì)結(jié)果準(zhǔn)確性產(chǎn)生影響。本文提到的相似度度量公式除了考慮社區(qū)節(jié)點(diǎn)集合還考慮了社區(qū)鄰居節(jié)點(diǎn)的影響,更具有實(shí)際意義。(4)對(duì)擴(kuò)充過程進(jìn)行并行化處理。并行化是提高算法性能的一個(gè)很重要的手段,通過分析本文算法過程,可以方便的解除數(shù)據(jù)依賴,并且引入生產(chǎn)者消費(fèi)者模型來解決線程通信問題。由于硬件環(huán)境限制實(shí)驗(yàn)在多核CPU上進(jìn)行操作。(5)通過應(yīng)用到實(shí)際網(wǎng)絡(luò)圖中驗(yàn)證了種子選擇策略在一定范圍之內(nèi)的可行性,以及綜合改進(jìn)算法ISA對(duì)于社區(qū)發(fā)現(xiàn)的準(zhǔn)確性以及時(shí)間損耗。準(zhǔn)確性用NMI(標(biāo)準(zhǔn)互信息量)進(jìn)行度量,發(fā)現(xiàn)本文算法對(duì)于混淆參數(shù)以及社區(qū)結(jié)構(gòu)敏感,總體性能優(yōu)于LFM算法,且不遜于GCE算法。
【關(guān)鍵詞】：重疊社區(qū)發(fā)現(xiàn) 節(jié)點(diǎn)影響力 局部優(yōu)化 并行計(jì)算
【學(xué)位授予單位】：重慶大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：O157.5;TP301.6
【目錄】：

• 中文摘要3-4
• 英文摘要4-8
• 1 緒論8-13
• 1.1 研究背景8-9
• 1.2 國內(nèi)外研究現(xiàn)狀9-12
• 1.3 本文的主要研究內(nèi)容和組織結(jié)構(gòu)12
• 1.4 本章小結(jié)12-13
• 2 復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)基本理論13-24
• 2.1 復(fù)雜網(wǎng)絡(luò)概述13
• 2.2 社區(qū)的概念13-17
• 2.2.1 社區(qū)的定義14-15
• 2.2.2 社區(qū)的評(píng)價(jià)標(biāo)準(zhǔn)15-17
• 2.3 非重疊社區(qū)發(fā)現(xiàn)算法17-20
• 2.3.1 劃分算法17-18
• 2.3.2 基于模塊度的算法18-19
• 2.3.3 譜聚類算法19
• 2.3.4 動(dòng)態(tài)算法19-20
• 2.4 重疊社區(qū)發(fā)現(xiàn)算法20-22
• 2.4.1 基于團(tuán)過濾算法20-21
• 2.4.2 基于連接劃分算法21
• 2.4.3 基于局部擴(kuò)充算法21-22
• 2.4.4 基于模糊檢測算法22
• 2.4.5 基于代理的動(dòng)態(tài)檢測算法22
• 2.5 本章小結(jié)22-24
• 3 基于局部擴(kuò)充的重疊社區(qū)發(fā)現(xiàn)算法24-29
• 3.1 基于局部擴(kuò)充優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法簡介24
• 3.2 常見的局部擴(kuò)充優(yōu)化的重疊社區(qū)發(fā)現(xiàn)算法24-28
• 3.2.1 LFM算法24-26
• 3.2.2 GCE算法26-28
• 3.3 本章小結(jié)28-29
• 4 基于局部擴(kuò)充的重疊社區(qū)發(fā)現(xiàn)算法改進(jìn)29-43
• 4.1 種子選擇的改進(jìn)29-33
• 4.1.1 尋找核心節(jié)點(diǎn)集合29-32
• 4.1.2 形成仿團(tuán)集32-33
• 4.1.3 種子集形成算法流程33
• 4.2 局部優(yōu)化質(zhì)量函數(shù)的優(yōu)化33-36
• 4.3 相似性度量36-37
• 4.4 并行化改進(jìn)37-40
• 4.4.1 并行化理論概述37-38
• 4.4.2 并行化分析38-40
• 4.5 算法綜合描述40-42
• 4.6 本章小結(jié)42-43
• 5 實(shí)驗(yàn)結(jié)果及分析43-53
• 5.1 實(shí)驗(yàn)準(zhǔn)確性評(píng)價(jià)標(biāo)準(zhǔn)43
• 5.2 實(shí)驗(yàn)數(shù)據(jù)源43-44
• 5.3 種子選擇算法實(shí)驗(yàn)對(duì)比44-46
• 5.4 綜合算法實(shí)驗(yàn)對(duì)比46-52
• 5.4.1 NMI準(zhǔn)確性實(shí)驗(yàn)對(duì)比46-50
• 5.4.2 速度指標(biāo)的實(shí)驗(yàn)對(duì)比50-52
• 5.5 本章小結(jié)52-53
• 6 總結(jié)與展望53-55
• 6.1 本文總結(jié)53-54
• 6.2 研究展望54-55
• 致謝55-56
• 參考文獻(xiàn)56-59
• 附錄59
• A. 作者在攻讀碩士學(xué)位期間發(fā)表的論文59

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 鄒汪平;;一種基于網(wǎng)絡(luò)安全控制的蜂群算法應(yīng)用研究[J];吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

2 郭毅可;韓銳;;云計(jì)算中的彈性算法:概要和展望[J];上海大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

3 劉江華;戴新喜;白似雪;;基于模式矩陣的P_Matrix算法[J];南昌大學(xué)學(xué)報(bào)(理科版);2007年05期

4 胡俊鵬;;基于雙向選擇的蟻群相遇算法的優(yōu)化[J];湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年01期

5 張麗;;關(guān)聯(lián)規(guī)則挖掘算法的研究[J];赤峰學(xué)院學(xué)報(bào)(自然科學(xué)版);2013年02期

6 吳秋峰;尹海東;孟翔燕;;基于和積和最大積的信念傳播算法的收斂性分析[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2011年09期

7 趙吉東;;蟻群算法的改進(jìn)策略研究[J];中國科技信息;2012年12期

8 胡森森;周賢善;;一種改進(jìn)蟻群算法的研究[J];長江大學(xué)學(xué)報(bào)(自科版);2006年10期

9 王恒娜;趙曉靜;;基于屬性覆蓋的關(guān)聯(lián)規(guī)則挖掘算法[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2007年03期

10 曹建軍;刁興春;李凱齊;邵衍振;;基于進(jìn)化強(qiáng)度的蟻群算法過程性能評(píng)價(jià)[J];解放軍理工大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年01期

中國重要會(huì)議論文全文數(shù)據(jù)庫 前10條

1 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)——2004年學(xué)術(shù)年會(huì)論文集[C];2004年

2 黃紀(jì)武;毛澤華;李松濤;張錦雄;;SPMD并行查找算法的MPI實(shí)現(xiàn)[A];廣西計(jì)算機(jī)學(xué)會(huì)2004年學(xué)術(shù)年會(huì)論文集[C];2004年

3 符麗錦;覃華;鄧海;孫欣;;一種改進(jìn)的Apriori算法的研究[A];廣西計(jì)算機(jī)學(xué)會(huì)2012年學(xué)術(shù)年會(huì)論文集[C];2012年

4 王東鋒;王軍民;陳英武;;模糊定性仿真理論研究與算法實(shí)現(xiàn)[A];'2000系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)交流會(huì)論文集[C];2000年

5 趙唯;;晶粒度評(píng)級(jí)的改進(jìn)算法[A];中國圖象圖形科學(xué)技術(shù)新進(jìn)展——第九屆全國圖象圖形科技大會(huì)論文集[C];1998年

6 劉啟文;;可擴(kuò)展的圖形學(xué)算法演示系統(tǒng)的研究[A];’2004計(jì)算機(jī)應(yīng)用技術(shù)交流會(huì)議論文集[C];2004年

7 佘智;蔣泰;朱延生;;基于Type C協(xié)議的防沖突改進(jìn)算法[A];廣西計(jì)算機(jī)學(xué)會(huì)25周年紀(jì)念會(huì)暨2011年學(xué)術(shù)年會(huì)論文集[C];2011年

8 朱紹文;趙培;朱秋云;;基于pSPADE并行挖掘序列算法的研究[A];2003年中國智能自動(dòng)化會(huì)議論文集（下冊(cè)）[C];2003年

9 楊霞;;新的基于啟發(fā)式蟻群算法的QoS路由算法[A];廣西計(jì)算機(jī)學(xué)會(huì)2009年年會(huì)論文集[C];2009年

10 陳黎飛;姜青山;董槐林;;基于圖形輪廓的快速聚類算法[A];第二十三屆中國數(shù)據(jù)庫學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 鐘永騰;基于近場MUSIC算法的復(fù)合材料結(jié)構(gòu)健康監(jiān)測研究[D];南京航空航天大學(xué);2014年

2 劉燕;入侵雜草優(yōu)化算法在陣列天線綜合中的應(yīng)用[D];西安電子科技大學(xué);2015年

3 苗義烽;突發(fā)事件下的列車運(yùn)行調(diào)度模型與算法研究[D];中國鐵道科學(xué)研究院;2015年

4 楊玉婷;頭腦風(fēng)暴優(yōu)化算法與基于視頻的非接觸式運(yùn)動(dòng)定量分析方法研究[D];浙江大學(xué);2015年

5 劉杰;全局優(yōu)化問題的幾類新算法[D];西安電子科技大學(xué);2015年

6 柏靜;基于多種混合策略的人工蜂群算法改進(jìn)研究[D];山東師范大學(xué);2016年

7 孔翔宇;幾類優(yōu)化問題的人工蜂群算法[D];西安電子科技大學(xué);2016年

8 匡立;分形網(wǎng)絡(luò)的理論、算法及應(yīng)用研究[D];武漢大學(xué);2015年

9 單美靜;求解非線性實(shí)代數(shù)系統(tǒng)的混合算法研究[D];華東師范大學(xué);2008年

10 邱劍鋒;人工蜂群算法的改進(jìn)方法與收斂性理論的研究[D];安徽大學(xué);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 安世勇;命題邏輯中隨機(jī)3-SAT問題算法研究[D];西南交通大學(xué);2015年

2 畢曉慶;油氣探礦權(quán)競爭性出讓系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D];中國地質(zhì)大學(xué)(北京);2015年

3 王明明;鐵路大機(jī)與線路固定設(shè)施間距檢測算法研究[D];西南交通大學(xué);2015年

4 李靜;基于視頻圖像序列的運(yùn)動(dòng)目標(biāo)檢測與跟蹤算法研究[D];寧夏大學(xué);2015年

5 劉貝玲;基于天地圖的租房平臺(tái)開發(fā)及其關(guān)鍵技術(shù)研究[D];西南交通大學(xué);2015年

6 曹海鋒;IDS中串匹配臭算法并行優(yōu)化研究[D];西安建筑科技大學(xué);2015年

7 周攀;基于蟻群算法的山區(qū)高速鐵路隧道火災(zāi)應(yīng)急疏散最優(yōu)路徑研究[D];西南交通大學(xué);2015年

8 張路奇;基于改進(jìn)蟻群算法的WSN路由協(xié)議的研究[D];中國地質(zhì)大學(xué)(北京);2015年

9 王曉晨;入侵雜草優(yōu)化算法的應(yīng)用與改進(jìn)[D];長安大學(xué);2015年

10 信琴琴;手勢控制和識(shí)別算法研究[D];閩南師范大學(xué);2015年

，

本文編號(hào)：770244