本文關(guān)鍵詞：基于密度峰值的重疊社區(qū)發(fā)現(xiàn)算法研究

  更多相關(guān)文章： 復(fù)雜網(wǎng)絡(luò) 社區(qū)發(fā)現(xiàn) 重疊社區(qū) 小世界特性 模塊度函數(shù)

【摘要】：在現(xiàn)實(shí)世界中，許多復(fù)雜系統(tǒng)是由大量組成單元或子系統(tǒng)構(gòu)成的，因而可以將該它們抽象成復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)中的節(jié)點(diǎn)是復(fù)雜系統(tǒng)的構(gòu)成單元，而網(wǎng)絡(luò)中的邊則是單元之間的相互關(guān)系。復(fù)雜網(wǎng)絡(luò)的應(yīng)用領(lǐng)域非常廣泛，如社會(huì)領(lǐng)域中的演員合作網(wǎng)、友誼網(wǎng)、科研合作網(wǎng)、Email網(wǎng)；生態(tài)領(lǐng)域中的食物鏈網(wǎng)、新陳代謝網(wǎng)、蛋白質(zhì)網(wǎng)、基因調(diào)控網(wǎng)絡(luò)；技術(shù)領(lǐng)域中的電力網(wǎng)、Internet網(wǎng)絡(luò)以及電話線路網(wǎng)絡(luò)，等等。尤其是近幾十年間，互聯(lián)網(wǎng)技術(shù)的迅猛發(fā)展使世界變得更小了，人與人之間的聯(lián)系更加緊密，人類已經(jīng)生活在充滿形形色色的復(fù)雜網(wǎng)絡(luò)的世界中。因此，復(fù)雜網(wǎng)絡(luò)的相關(guān)研究也越來越成為一個(gè)研究的熱點(diǎn)。 目前，學(xué)者們?cè)趯?duì)復(fù)雜網(wǎng)絡(luò)的研究過程中，發(fā)現(xiàn)現(xiàn)實(shí)網(wǎng)絡(luò)不僅具有小世界和無標(biāo)度等特征，而且還具有社區(qū)結(jié)構(gòu)特征。社區(qū)與社區(qū)之間的連接雖然較為稀疏，但是社區(qū)內(nèi)部的節(jié)點(diǎn)之間的連接卻非常稠密。因此，社區(qū)結(jié)構(gòu)的研究在當(dāng)前復(fù)雜網(wǎng)絡(luò)發(fā)展過程中占據(jù)著相當(dāng)重要的地位。 傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法主要分為圖形分割和層次聚類兩大類方法,其中，層次聚類又包括凝聚算法和分裂算法兩類。隨著對(duì)社區(qū)發(fā)現(xiàn)的深入研究，Newman等人提出了模塊度函數(shù)，隨后又出現(xiàn)了某些基于模塊度極值優(yōu)化的方法。然而，在現(xiàn)實(shí)生活中的網(wǎng)絡(luò)，其節(jié)點(diǎn)并不是完全只屬于某一個(gè)社區(qū)，而是可能屬于多個(gè)社區(qū)，也就是說網(wǎng)絡(luò)中存在著重疊部分。因此，學(xué)者們?yōu)榱四芨诱鎸?shí)地刻畫網(wǎng)絡(luò)的結(jié)構(gòu)特征，又提出了許多重疊社區(qū)劃分方法。一些研究者將統(tǒng)計(jì)推理應(yīng)用到重疊社區(qū)劃分算法中，取得了較好的效果，如GN算法、SPAEM算法等。 本文主要針對(duì)復(fù)雜網(wǎng)絡(luò)重疊社區(qū)發(fā)現(xiàn)算法進(jìn)行研究，通過借鑒最近Science上提出的基于快速搜索和發(fā)現(xiàn)密度峰值的聚類方法思想，提出了“基于密度峰值的重疊社區(qū)發(fā)現(xiàn)算法”。本文首先對(duì)社區(qū)發(fā)現(xiàn)算法的相關(guān)文獻(xiàn)進(jìn)行了綜述，介紹了復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)算法的類別以及相應(yīng)優(yōu)缺點(diǎn)等，，對(duì)一些經(jīng)典算法的核心思想、適用范圍、時(shí)間復(fù)雜度等方面進(jìn)行了分析。之后，論文還詳細(xì)介紹了Science上提出的基于快速搜索和發(fā)現(xiàn)密度峰值的聚類方法，分析了該算法的核心思想。 在深入理解基于快速搜索和發(fā)現(xiàn)密度峰值的聚類方法的基礎(chǔ)上，本文提出了基于密度峰值的重疊社區(qū)發(fā)現(xiàn)算法。算法首先通過給出新的距離矩陣算法避免了現(xiàn)有鄰接矩陣都為整數(shù)，且有大量重復(fù)的問題。之后在搜索中心的過程中與原有算法一樣，認(rèn)為那些具有高局部密度并且到更高局部密度的點(diǎn)的最短距離相對(duì)較高的節(jié)點(diǎn)才是類簇中心。得到類簇中心后，不再限制每個(gè)節(jié)點(diǎn)屬于某一單個(gè)社區(qū)，而是以一定概率屬于各個(gè)社區(qū)，計(jì)算社區(qū)內(nèi)節(jié)點(diǎn)的概率分布矩陣，得到相應(yīng)的劃分結(jié)果，從而使得重疊社區(qū)的劃分成為可能。為驗(yàn)證所提出算法的有效性，將其應(yīng)用于實(shí)際網(wǎng)絡(luò)中，如空手道網(wǎng)絡(luò)、海豚關(guān)系網(wǎng)等。對(duì)karate數(shù)據(jù)和dolphins數(shù)據(jù)的劃分結(jié)果與原數(shù)據(jù)的社區(qū)劃分結(jié)果基本相類似，對(duì)于稍大規(guī)模的網(wǎng)絡(luò)得到的重疊社區(qū)劃分結(jié)果要比其它算法好。 論文主要是通過將基于快速搜索和發(fā)現(xiàn)密度峰值的聚類方法引入到重疊社區(qū)劃分問題中，通過定義新的距離矩陣算法克服鄰接矩陣為整數(shù)的缺陷，并以概率形式刻畫每個(gè)節(jié)點(diǎn)屬于不同類別的可能性，實(shí)現(xiàn)了重疊社區(qū)的劃分。所提出的基于密度峰值的重疊社區(qū)發(fā)現(xiàn)算法簡(jiǎn)單易懂，既能夠用于非重疊社區(qū)的劃分，也可以進(jìn)行重疊社區(qū)的劃分，而且還可以擴(kuò)展到加權(quán)網(wǎng)絡(luò)。此外，該算法不用事先預(yù)設(shè)社區(qū)的個(gè)數(shù)，可以通過決策圖來判斷社區(qū)個(gè)數(shù)以及類簇中心節(jié)點(diǎn)。并且，基于真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)證明了本文提出算法的有效性。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O157.5

【共引文獻(xiàn)】

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

1 淦文燕;赫南;李德毅;王建民;;一種基于拓?fù)鋭?shì)的網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)方法[J];軟件學(xué)報(bào);2009年08期

2 李琳;李生紅;陸松年;陳秀珍;;基于PCA的社團(tuán)結(jié)構(gòu)譜聚類改進(jìn)算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2013年10期

3 劉伍穎;易綿竹;張興;;一種時(shí)空高效的多類別文本分類算法[J];山東大學(xué)學(xué)報(bào)(理學(xué)版);2013年11期

4 王庚;宋傳超;盛玉曉;王童童;李盛恩;;基于標(biāo)簽傳播的穩(wěn)定重疊社區(qū)挖掘算法研究[J];山東科學(xué);2013年05期

5 You-Ping Li;Wei-Qun Gan;Li Feng;Si-Ming Liu;A.Struminsky;;The breakdown of the power-law frequency distributions for the hard X-ray peak count rates of solar flares[J];Research in Astronomy and Astrophysics;2013年12期

6 陽(yáng)廣元;曹霞;甯佐斌;潘煦;;國(guó)內(nèi)社區(qū)發(fā)現(xiàn)研究進(jìn)展[J];情報(bào)資料工作;2014年02期

7 劉倩;劉群;;基于引力度擴(kuò)展的重疊社區(qū)發(fā)現(xiàn)算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2014年03期

8 周秋菊;楊立英;岳婷;丁潔蘭;;基于期刊同被引和互引網(wǎng)絡(luò)的學(xué)科結(jié)構(gòu)和知識(shí)流動(dòng)研究[J];情報(bào)雜志;2014年08期

9 董哲;伊鵬;賀成龍;;基于鏈路標(biāo)簽傳播的重疊社團(tuán)發(fā)現(xiàn)算法[J];計(jì)算機(jī)工程與設(shè)計(jì);2014年10期

10 侯思權(quán);張振宇;文少杰;;基于邊權(quán)重局部擴(kuò)展的機(jī)會(huì)網(wǎng)絡(luò)社區(qū)檢測(cè)方法[J];計(jì)算機(jī)工程與設(shè)計(jì);2014年11期

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

1 ;Fuzzy Analysis for Overlapping Community Structure of Complex Network[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

2 伍勇;鐘志農(nóng);景寧;李星;;適于社區(qū)挖掘分析與可視化的布局算法[A];第29屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）（NDBC2012）[C];2012年

3 Hongbo Li;Wenjing Geng;Yu Wu;Xian Wang;;An Improved Force-Directed Algorithm Based on Emergence for Visualizing Complex Network[A];2013年中國(guó)智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（第二分冊(cè)）[C];2013年

4 Yun Li;Gang Liu;Song-yang Lao;;Overlapping Community Detection in Complex Networks based on the Boundary Information of Disjoint Community[A];第25屆中國(guó)控制與決策會(huì)議論文集[C];2013年

5 李杰;張皎娟;;C2C電子商務(wù)顧客重復(fù)購(gòu)買冪分布規(guī)律及其影響因素[A];2013中國(guó)信息經(jīng)濟(jì)學(xué)會(huì)學(xué)術(shù)年會(huì)暨博士生論壇論文集[C];2013年

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

1 沈項(xiàng)軍;基于語(yǔ)義學(xué)習(xí)的圖像檢索研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2006年

2 萬里;時(shí)間序列中的知識(shí)發(fā)現(xiàn)[D];北京郵電大學(xué);2009年

3 馬瑞新;基于粒子群的網(wǎng)絡(luò)社區(qū)動(dòng)態(tài)角色挖掘研究[D];大連理工大學(xué);2012年

4 朱巖;面向文本數(shù)據(jù)的半監(jiān)督學(xué)習(xí)研究[D];北京交通大學(xué);2012年

5 黃亮;社會(huì)網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)與鏈接預(yù)測(cè)算法研究[D];華中科技大學(xué);2012年

6 何邊;復(fù)雜網(wǎng)絡(luò)上的分塊問題[D];上海交通大學(xué);2012年

7 高雅純;基于復(fù)雜系統(tǒng)理論的金融市場(chǎng)動(dòng)力學(xué)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2013年

8 吳聯(lián)仁;基于人類動(dòng)力學(xué)的社交網(wǎng)絡(luò)信息傳播實(shí)證分析與建模研究[D];北京郵電大學(xué);2013年

9 陳t

本文編號(hào)：1244013