本文關(guān)鍵詞：社會(huì)網(wǎng)絡(luò)的鄰域重疊社團(tuán)劃分

  更多相關(guān)文章： 社團(tuán)劃分 派系 模塊度 劃分密度 時(shí)間復(fù)雜度

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

【相似文獻(xiàn)】

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

1 饒正嬋;范林柏;;基于二分排序法時(shí)間復(fù)雜度的求解過程[J];銅仁學(xué)院學(xué)報(bào);2011年03期

2 武鵬;李美安;;具有O(n)時(shí)間復(fù)雜度的分布式請(qǐng)求集生成算法[J];計(jì)算機(jī)應(yīng)用;2013年02期

3 隆永紅;;關(guān)于在W簽名方案中偽造簽名的時(shí)間復(fù)雜度[J];通信保密;1993年01期

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

5 明仲;利用雙堆棧降低時(shí)間復(fù)雜度的新算法[J];深圳大學(xué)學(xué)報(bào);1998年Z1期

6 殷超;;刪除值相同元素的時(shí)間復(fù)雜度的改進(jìn)算法[J];科技信息;2011年21期

7 霍錫真;網(wǎng)絡(luò)靈敏度的拓?fù)浞治龊退惴ǖ臅r(shí)間復(fù)雜度[J];電子學(xué)報(bào);1992年02期

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

9 黃杰;運(yùn)用簡(jiǎn)化法則估算算法的時(shí)間復(fù)雜度[J];雁北師范學(xué)院學(xué)報(bào);2000年04期

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

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

1 宋旭東;紀(jì)秀花;;穩(wěn)定婚姻問題的研究[A];全國(guó)第19屆計(jì)算機(jī)技術(shù)與應(yīng)用（CACIS）學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];2008年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 陳智罡;算法復(fù)雜度的分析方法及其運(yùn)用[N];中國(guó)電腦教育報(bào);2002年

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

1 李仁杰;零抽樣斷點(diǎn)距離的一個(gè)改進(jìn)算法[D];山東大學(xué);2015年

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

3 任成磊;社會(huì)網(wǎng)絡(luò)的鄰域重疊社團(tuán)劃分[D];華東師范大學(xué);2016年

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

5 馬振宇;加權(quán)分治技術(shù)在Set Packing問題中的應(yīng)用與研究[D];中南大學(xué);2007年

6 郝勇;計(jì)算生物學(xué)中有關(guān)基因組移位—?jiǎng)h除排序問題的研究[D];山東大學(xué);2011年

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

8 朱泓丞;設(shè)施選址問題的研究與應(yīng)用[D];中國(guó)科學(xué)技術(shù)大學(xué);2009年

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

10 許寶亮;用于異常檢測(cè)的進(jìn)化非選擇算法性能分析[D];中國(guó)科學(xué)技術(shù)大學(xué);2010年

，

本文編號(hào)：1137250