本文選題：網(wǎng)絡(luò)聚類(lèi)　切入點(diǎn)：重疊社團(tuán)結(jié)構(gòu)　出處：《安徽大學(xué)》2017年碩士論文

【摘要】：近年來(lái),由于社交網(wǎng)絡(luò)的發(fā)展和大數(shù)據(jù)時(shí)代的興起,大規(guī)模復(fù)雜網(wǎng)絡(luò)社團(tuán)檢測(cè)已成為研究熱點(diǎn)之一。社團(tuán)檢測(cè)作為復(fù)雜網(wǎng)絡(luò)研究中一項(xiàng)基礎(chǔ)而又重要的工作,旨在挖掘網(wǎng)絡(luò)中一組節(jié)點(diǎn)集合,這些集合內(nèi)部的節(jié)點(diǎn)連接緊密,而集合之間的節(jié)點(diǎn)連接稀疏。然而在現(xiàn)實(shí)世界網(wǎng)絡(luò)中經(jīng)常存在一些節(jié)點(diǎn)可能會(huì)同時(shí)屬于多個(gè)社團(tuán)的情況,即重疊社團(tuán)結(jié)構(gòu)。因此,對(duì)重疊社團(tuán)結(jié)構(gòu)的檢測(cè)更加重要且具有應(yīng)用價(jià)值。隨著網(wǎng)絡(luò)科學(xué)的不斷發(fā)展,許多復(fù)雜網(wǎng)絡(luò)的規(guī)模甚至包含數(shù)百萬(wàn)數(shù)量的節(jié)點(diǎn)和數(shù)十億條邊。對(duì)如此大規(guī)模的復(fù)雜網(wǎng)絡(luò)進(jìn)行重疊社團(tuán)挖掘一直是該領(lǐng)域內(nèi)的難點(diǎn)之一�；诖�,本文對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)問(wèn)題進(jìn)行了深入研究,提出了一種基于弱團(tuán)滲流思想的重疊社團(tuán)檢測(cè)算法。此外,為了解決數(shù)百萬(wàn)數(shù)量級(jí)的超大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)檢測(cè)問(wèn)題,本文還提出一種基于局部鄰居信息的快速重疊社團(tuán)檢測(cè)算法。這兩種算法均是以檢測(cè)大規(guī)模復(fù)雜網(wǎng)絡(luò)重疊社團(tuán)結(jié)構(gòu)為目的,相比較其他重疊社團(tuán)檢測(cè)算法,本文所提算法計(jì)算效率更快,社團(tuán)檢測(cè)精度更高。本文的主要研究工作如下:(1)本文提出了一種基于弱團(tuán)滲流的重疊社團(tuán)檢測(cè)算法。k-團(tuán)滲流方法是當(dāng)前最常用的重疊社團(tuán)檢測(cè)算法之一,其基本思想是將社團(tuán)結(jié)構(gòu)定義為由一系列共享很多節(jié)點(diǎn)的完全連通子圖組成。k-團(tuán)滲流方法需要檢測(cè)網(wǎng)絡(luò)中所有k-團(tuán)(即,k-clique),然而k-團(tuán)的檢測(cè)是NP完全問(wèn)題,因此基于k-團(tuán)滲流方法的時(shí)間復(fù)雜度很高。為了提高重疊社團(tuán)檢測(cè)算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)上檢測(cè)重疊社團(tuán)的效率和準(zhǔn)確性,本文利用網(wǎng)絡(luò)中的局部拓?fù)湫畔⒖焖偻诰蚓W(wǎng)絡(luò)中的弱團(tuán)。本文將弱團(tuán)定義為由網(wǎng)絡(luò)中兩個(gè)關(guān)鍵節(jié)點(diǎn)及其公共鄰居組合而成,由于僅僅利用節(jié)點(diǎn)的鄰居信息,因此檢測(cè)弱團(tuán)要比檢測(cè)k-團(tuán)高效很多。同時(shí)在滲流過(guò)程中,提出新的相似度指標(biāo)來(lái)衡量?jī)蓚�(gè)弱團(tuán)之間的相似性,并以此來(lái)判斷兩個(gè)弱團(tuán)是否應(yīng)該合并,以提升算法的準(zhǔn)確性。在新的相似度指標(biāo)中不僅考慮了兩個(gè)弱團(tuán)之間共享的節(jié)點(diǎn)數(shù)目還統(tǒng)計(jì)了弱團(tuán)之間邊的連接數(shù)目。在LFR基準(zhǔn)數(shù)據(jù)集和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,與現(xiàn)有幾種重疊社團(tuán)檢測(cè)算法相比,基于弱團(tuán)滲流的重疊社團(tuán)檢測(cè)算法在計(jì)算效率和發(fā)現(xiàn)重疊社團(tuán)質(zhì)量方面都具有明顯優(yōu)勢(shì)。(2)本文提出一種基于局部鄰居信息的快速重疊社團(tuán)檢測(cè)算法。隨著社交網(wǎng)絡(luò)的興起和互聯(lián)網(wǎng)時(shí)代的發(fā)展,目前復(fù)雜網(wǎng)絡(luò)的規(guī)模變得越來(lái)越巨大。為了能夠在數(shù)百萬(wàn)數(shù)量級(jí)這種超大規(guī)模復(fù)雜網(wǎng)絡(luò)中檢測(cè)重疊社團(tuán)結(jié)構(gòu),本文提出了一種基于局部鄰居信息的快速重疊社團(tuán)檢測(cè)算法,稱之為OCLN(Overlapping Community detection by using Local-Neighborhood information)算法。OCLN 算法的基本思想在于首先利用網(wǎng)絡(luò)中節(jié)點(diǎn)的內(nèi)部度數(shù)和外部度數(shù)這些局部結(jié)構(gòu)快速擴(kuò)充社團(tuán),隨后根據(jù)社團(tuán)中每個(gè)節(jié)點(diǎn)的局部鄰居信息在該社團(tuán)中的貢獻(xiàn)度計(jì)算節(jié)點(diǎn)的隸屬度指標(biāo)。從社團(tuán)中刪除掉一些隸屬度較低的節(jié)點(diǎn),提高算法的準(zhǔn)確性。由于整個(gè)算法全部利用網(wǎng)絡(luò)的局部結(jié)構(gòu),因此OCLN算法的時(shí)間復(fù)雜度為線性,即O(n+m),n為網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目,m為邊的數(shù)目。通過(guò)對(duì)LFR基準(zhǔn)網(wǎng)絡(luò)和大規(guī)模真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)分析表明,OCLN算法在算法運(yùn)行時(shí)間和NMI精度性能上都明顯優(yōu)于其他幾種重疊社團(tuán)檢測(cè)算法。
[Abstract]:In recent years , because of the development of social networks and the rise of large data era , large - scale complex network community detection has become one of the hot topics . This paper proposes a fast overlapping community detection algorithm based on local neighbor information . With the rise of social network and the development of Internet age , the scale of complex network becomes more and more huge . In order to detect overlapping community structure in the large - scale complex network on the order of millions of orders , this paper proposes a fast overlapping community detection algorithm based on local neighbor information .

【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：O157.5

【相似文獻(xiàn)】

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

1 劉晉霞;曾建潮;薛耀文;;復(fù)雜網(wǎng)絡(luò)強(qiáng)社團(tuán)結(jié)構(gòu)探測(cè)[J];小型微型計(jì)算機(jī)系統(tǒng);2011年04期

2 賈寧寧;封筠;;復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)[J];河北省科學(xué)院學(xué)報(bào);2013年02期

3 宣照國(guó);苗靜;黨延忠;劉建國(guó);;科研領(lǐng)域關(guān)聯(lián)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)分析[J];上海理工大學(xué)學(xué)報(bào);2008年02期

4 王伊蕾;王遠(yuǎn)志;李濤;田生文;;偽度優(yōu)先演化網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)研究[J];計(jì)算機(jī)工程與應(yīng)用;2009年20期

5 汪小帆;劉亞冰;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J];電子科技大學(xué)學(xué)報(bào);2009年05期

6 司夏萌;劉云;丁飛;熊菲;;具有社團(tuán)結(jié)構(gòu)的有界信任輿論涌現(xiàn)模型研究[J];系統(tǒng)仿真學(xué)報(bào);2009年23期

7 謝軍;;復(fù)雜網(wǎng)絡(luò)中分析社團(tuán)結(jié)構(gòu)算法研究概述[J];信息通信;2010年04期

8 朱大勇;張新麗;李樹(shù)全;;利用局部拓?fù)湫畔l(fā)現(xiàn)模糊社團(tuán)結(jié)構(gòu)[J];電子科技大學(xué)學(xué)報(bào);2011年01期

9 邵斐;蔣國(guó)平;;基于社團(tuán)結(jié)構(gòu)的負(fù)載傳輸優(yōu)化策略研究[J];物理學(xué)報(bào);2011年07期

10 談煜;梁潤(rùn)鵬;;一種基于層次化社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)可視化方法[J];微型電腦應(yīng)用;2012年04期

相關(guān)會(huì)議論文 前5條

1 苗清影;汪小帆;;基于社團(tuán)結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)可控性研究[A];第五屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文（摘要）匯集[C];2009年

2 李曉佳;張鵬;狄增如;樊瑛;;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)[A];第四屆全國(guó)網(wǎng)絡(luò)科學(xué)學(xué)術(shù)論壇暨研究生暑期學(xué)校論文集[C];2008年

3 胡延慶;趙爾波;張丹;狄增如;樊瑛;;社團(tuán)結(jié)構(gòu)的局域和自適應(yīng)比較性定義及其相應(yīng)探測(cè)方法[A];第五屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文（摘要）匯集[C];2009年

4 吳文濤;肖仰華;何震瀛;汪衛(wèi);余韜;;基于權(quán)重信息挖掘社會(huì)網(wǎng)絡(luò)中的隱含社團(tuán)[A];第26屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（B輯）[C];2009年

5 樊瑛;李夢(mèng)輝;張鵬;吳金閃;狄增如;;權(quán)重對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和性質(zhì)的影響——社團(tuán)結(jié)構(gòu)中權(quán)重的作用[A];2006全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議論文集[C];2006年

相關(guān)博士學(xué)位論文 前10條

1 程建軍;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)檢測(cè)方法研究[D];蘭州大學(xué);2015年

2 李琳;基于多元統(tǒng)計(jì)分析的社團(tuán)挖掘算法研究[D];上海交通大學(xué);2014年

3 王文軍;飛機(jī)駕駛艙人機(jī)工效設(shè)計(jì)與綜合評(píng)估關(guān)鍵技術(shù)[D];西北工業(yè)大學(xué);2015年

4 崔耀祖;基于復(fù)雜網(wǎng)絡(luò)邊的密度探索社團(tuán)結(jié)構(gòu)算法研究[D];大連理工大學(xué);2016年

5 武志昊;復(fù)雜網(wǎng)絡(luò)中的重疊社團(tuán)發(fā)現(xiàn)問(wèn)題研究[D];北京交通大學(xué);2013年

6 魏芳;基于圖挖掘的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)[D];復(fù)旦大學(xué);2008年

7 劉傳建;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)劃分及分析應(yīng)用[D];山東大學(xué);2014年

8 何東曉;復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法研究[D];吉林大學(xué);2014年

9 劉晉霞;復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的探測(cè)及其在資金融通網(wǎng)絡(luò)中的應(yīng)用研究[D];蘭州理工大學(xué);2013年

10 劉瑤;社會(huì)網(wǎng)絡(luò)特征分析與社團(tuán)結(jié)構(gòu)挖掘[D];電子科技大學(xué);2013年

相關(guān)碩士學(xué)位論文 前10條

1 劉微;復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn)[D];遼寧師范大學(xué);2011年

2 王大軍;基于標(biāo)簽傳播的社團(tuán)檢測(cè)算法研究[D];遼寧大學(xué);2015年

3 楊強(qiáng);微博社交網(wǎng)絡(luò)模型的建立及其性質(zhì)研究[D];北京化工大學(xué);2015年

4 付世海;基于社團(tuán)結(jié)構(gòu)的網(wǎng)絡(luò)多傳播源定位算法研究[D];東北大學(xué);2013年

5 馬驍騎;復(fù)雜網(wǎng)絡(luò)中社團(tuán)檢測(cè)技術(shù)研究[D];黑龍江大學(xué);2015年

6 張獻(xiàn)鵬;基于P4結(jié)構(gòu)的社團(tuán)挖掘方法[D];西安電子科技大學(xué);2014年

7 陳奔燕;復(fù)雜網(wǎng)絡(luò)的社團(tuán)探測(cè)[D];湘潭大學(xué);2015年

8 杜梅;基于半監(jiān)督的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)方法研究[D];合肥工業(yè)大學(xué);2014年

9 韓凌霄;復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分及城市公交網(wǎng)絡(luò)研究[D];青島理工大學(xué);2015年

10 董哲;復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)算法研究[D];解放軍信息工程大學(xué);2014年

，

本文編號(hào)：1685575