發(fā)布時間：2017-11-03 17:33

  本文關鍵詞：社會網(wǎng)絡的鄰域重疊社團劃分

  更多相關文章： 社團劃分 派系 模塊度 劃分密度 時間復雜度

【摘要】：在復雜系統(tǒng)中,鄰域重疊社團是網(wǎng)絡普遍存在的一種特性。因為鄰域重疊社團可以直觀形象地揭示網(wǎng)絡內(nèi)部的組織結構以及各個社團之間的關系,所以鄰域重疊社團的探測研究對網(wǎng)絡拓撲結構的分析、功能的理解以及動力學行為的預測等有著重要的意義。目前,大多數(shù)的鄰域重疊社團劃分算法時間復雜度較高,難以準確地實現(xiàn)網(wǎng)絡的社團劃分。針對以上問題,本文主要貢獻如下：1.提出了一種改進型派系過濾算法,通過優(yōu)化派系搜索過程,加快網(wǎng)絡鄰域重疊社團劃分�；诰W(wǎng)絡中的完全子圖,通過縮小節(jié)點搜索范圍,采用由大到小、迭代回歸的方式挖掘網(wǎng)絡中的派系,快速地實現(xiàn)網(wǎng)絡的鄰域重疊社團劃分。將改進型派系過濾算法應用到模擬網(wǎng)絡和實證網(wǎng)絡中,準確地實現(xiàn)了網(wǎng)絡的鄰域重疊社團劃分。2.基于社團的劃分測度,提出了一種時間復雜度近線性的鄰域重疊社團劃分算法。首先,利用堆數(shù)據(jù)結構,通過更新模塊度增量矩陣,合并使網(wǎng)絡模塊度值增益最大的社團,完成社團成員矩陣的初始化；其次,逐條分析網(wǎng)絡中的連邊,結合劃分密度,準確地挖掘網(wǎng)絡中的重疊節(jié)點；最后,將基于社團劃分測度的鄰域重疊社團劃分算法應用到模擬網(wǎng)絡中,檢驗算法的準確性,并從理論上分析算法的時間復雜度近線性。3.選取經(jīng)典的社會網(wǎng)絡數(shù)據(jù)集,驗證基于社團劃分測度的鄰域重疊社團劃分算法的準確性與高效性�；谏鐖F劃分測度,對已知社團結構的空手道俱樂部網(wǎng)和海豚網(wǎng)進行社團劃分,實驗結果與實際情況一致,證實了算法的準確性；對未知網(wǎng)絡結構的悲慘世界角色網(wǎng)和科學家合作網(wǎng)進行社團劃分,實驗結果揭示了網(wǎng)絡內(nèi)部拓撲特性,反映了小說主要人物的作用以及科學家之間的合作模式。通過分析以上四個網(wǎng)絡的耗時情況,發(fā)現(xiàn)新方法可以快速地實現(xiàn)網(wǎng)絡的鄰域重疊社團劃分。
【學位授予單位】：華東師范大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP393.02

【相似文獻】

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

1 饒正嬋;范林柏;;基于二分排序法時間復雜度的求解過程[J];銅仁學院學報;2011年03期

2 武鵬;李美安;;具有O(n)時間復雜度的分布式請求集生成算法[J];計算機應用;2013年02期

3 隆永紅;;關于在W簽名方案中偽造簽名的時間復雜度[J];通信保密;1993年01期

4 李之棠,程鵬,李漢菊;時間復雜度為O(N)的聯(lián)接算法[J];計算機工程與科學;1997年01期

5 明仲;利用雙堆棧降低時間復雜度的新算法[J];深圳大學學報;1998年Z1期

6 殷超;;刪除值相同元素的時間復雜度的改進算法[J];科技信息;2011年21期

7 霍錫真;網(wǎng)絡靈敏度的拓撲分析和算法的時間復雜度[J];電子學報;1992年02期

8 余新國,黃文奇,賴楚生;多元整系數(shù)多項式因式分解（Ⅱ）——關于時間復雜度算法的討論[J];華中理工大學學報;1996年S2期

9 黃杰;運用簡化法則估算算法的時間復雜度[J];雁北師范學院學報;2000年04期

10 戰(zhàn)俊偉;李美安;裴喜春;申二威;;基于時間復雜度優(yōu)化的分布式互斥請求集生成算法[J];微計算機信息;2010年27期

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

1 宋旭東;紀秀花;;穩(wěn)定婚姻問題的研究[A];全國第19屆計算機技術與應用（CACIS）學術會議論文集（下冊）[C];2008年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 陳智罡;算法復雜度的分析方法及其運用[N];中國電腦教育報;2002年

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

1 李仁杰;零抽樣斷點距離的一個改進算法[D];山東大學;2015年

2 黃磊;WSN中基于時間信道的溯源數(shù)據(jù)安全節(jié)能傳輸[D];江蘇大學;2016年

3 任成磊;社會網(wǎng)絡的鄰域重疊社團劃分[D];華東師范大學;2016年

4 李彬;三個圖修改問題的固定參數(shù)可解算法研究[D];山東大學;2013年

5 馬振宇;加權分治技術在Set Packing問題中的應用與研究[D];中南大學;2007年

6 郝勇;計算生物學中有關基因組移位—刪除排序問題的研究[D];山東大學;2011年

7 呂旭光;基因組斷點標本字符串聯(lián)提取算法[D];山東大學;2011年

8 朱泓丞;設施選址問題的研究與應用[D];中國科學技術大學;2009年

9 申佳麗;復雜網(wǎng)絡節(jié)點影響力及影響力傳播相關問題研究[D];燕山大學;2015年

10 許寶亮;用于異常檢測的進化非選擇算法性能分析[D];中國科學技術大學;2010年

，

本文編號：1137250