本文選題：社區(qū)發(fā)現(xiàn)　切入點(diǎn)：復(fù)雜網(wǎng)絡(luò)　出處：《北京理工大學(xué)》2016年碩士論文

【摘要】：社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中一個(gè)常見的特性,它由一組連接緊密的結(jié)點(diǎn)組成,同時(shí)這些結(jié)點(diǎn)與社區(qū)外部結(jié)點(diǎn)連接稀疏。通過研究社區(qū)結(jié)構(gòu),研究者能夠更深刻地理解網(wǎng)絡(luò)所對應(yīng)的復(fù)雜系統(tǒng),因?yàn)樯鐓^(qū)結(jié)構(gòu)往往揭示著網(wǎng)絡(luò)的組織結(jié)構(gòu)。同時(shí),由于社區(qū)結(jié)構(gòu)有著廣泛的實(shí)際用途,所以在復(fù)雜網(wǎng)絡(luò)中發(fā)現(xiàn)社區(qū)結(jié)構(gòu)有著重要的研究意義。提出了一種衡量結(jié)點(diǎn)中心性的方法�；诮Y(jié)點(diǎn)核心值以及局部擴(kuò)展框架,提出了一種新的重疊社區(qū)發(fā)現(xiàn)算法。該算法不僅能夠發(fā)現(xiàn)重疊社區(qū)結(jié)構(gòu),同時(shí)還可發(fā)現(xiàn)網(wǎng)絡(luò)中的部分橋接結(jié)點(diǎn)。該算法包括四個(gè)步驟:首先,根據(jù)結(jié)點(diǎn)的核心值將它們降序排序,以形成種子優(yōu)先級列表;其次,列表頂端的結(jié)點(diǎn)被選出,以形成一個(gè)社區(qū)的核心區(qū)域;然后,擴(kuò)展這個(gè)核心區(qū)域直到一個(gè)社區(qū)結(jié)構(gòu)或者橋接結(jié)點(diǎn)被發(fā)現(xiàn);最后,分配橋接結(jié)點(diǎn)到那些它的大多數(shù)鄰居所在的社區(qū)中。其中,交替執(zhí)行第二、第三步,直至所有社區(qū)都被發(fā)現(xiàn),然后再進(jìn)行第四步。實(shí)驗(yàn)結(jié)果證明了算法的有效性。針對當(dāng)前已有的社區(qū)發(fā)現(xiàn)算法無法有效處理海量級數(shù)據(jù)的問題,提出了一種基于局部擴(kuò)展的并行化算法,并且借助Spark框架將其實(shí)現(xiàn)。該算法包含四個(gè)步驟:首先,挑選出一組互不相關(guān)的中心結(jié)點(diǎn)并使用中心結(jié)點(diǎn)與它們的鄰居所形成的局部網(wǎng)絡(luò)作為種子;其次,通過刪除那些本身連接比較稀疏的局部網(wǎng)絡(luò)來過濾選出的種子;然后,采用一種批量式的擴(kuò)展策略來擴(kuò)展種子,即一次向局部社區(qū)中添加一批鄰居結(jié)點(diǎn)或從社區(qū)中刪除一批結(jié)點(diǎn);最后,融合相似度比較高的社區(qū)。實(shí)驗(yàn)結(jié)果證明了算法的有效性。
[Abstract]:Community structure is a common feature in complex networks. It consists of a group of closely connected nodes which are sparsely connected to the external nodes of the community.By studying the community structure, researchers can understand the complex system of the network more deeply, because the community structure often reveals the organization structure of the network.At the same time, because community structure has a wide range of practical applications, it is of great significance to find community structure in complex networks.A method of measuring node centrality is proposed.A new overlapping community discovery algorithm is proposed based on node core values and local extension framework.The algorithm can not only find overlapping community structures, but also find some bridging nodes in the network.The algorithm consists of four steps: first, ranking the nodes in descending order according to their core values to form a seed priority list; secondly, the nodes at the top of the list are selected to form the core area of a community; then,The core area is extended until a community structure or bridging node is found; finally, the bridging node is allocated to the community where most of its neighbors live.Alternately, perform step two, step three, until all communities are found, and then step 4.Experimental results show that the algorithm is effective.Aiming at the problem that the existing community discovery algorithms can not deal with the massive data effectively, a parallelization algorithm based on local extension is proposed and implemented with the help of Spark framework.The algorithm consists of four steps: first, selecting a group of unrelated central nodes and using the local network formed by the center node and their neighbors as seeds; secondly,The selected seeds are filtered by deleting the local networks with sparse connections; then, a batch expansion strategy is used to extend the seeds.That is, adding a group of neighbor nodes to the local community or deleting a group of nodes from the community at a time. Finally, the communities with high similarity are fused.Experimental results show that the algorithm is effective.
【學(xué)位授予單位】：北京理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O157.5

【相似文獻(xiàn)】

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

1 李德勝;張才仙;陳淑銘;;選擇策略對進(jìn)化算法性能的影響[J];科技資訊;2007年11期

2 梁民,孫仲康;多層前饋神經(jīng)網(wǎng)絡(luò)的快速學(xué)習(xí)算法及其仿真研究[J];系統(tǒng)工程與電子技術(shù);1993年09期

3 王忠;陳伏虎;;基于陣元域數(shù)據(jù)的聯(lián)合檢測與跟蹤算法[J];聲學(xué)學(xué)報(bào)(中文版);2007年06期

4 蘇開樂;關(guān)于D.W.Etherington的擴(kuò)充產(chǎn)生算法的一個(gè)注記[J];計(jì)算機(jī)工程與科學(xué);1998年04期

5 江宇聞;;Overcomplete ICA算法研究[J];中山大學(xué)研究生學(xué)刊(自然科學(xué)、醫(yī)學(xué)版);2004年02期

6 王杰;王加銀;;Mean Shift算法的收斂性討論[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年05期

7 胡夢佑;陳鈞量;;快速加權(quán)滑窗RLS格型算法[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);1992年02期

8 裴炳南;吳顯鼎;張明武;;MLMS算法的偽收斂現(xiàn)象[J];河南科學(xué);1993年Z1期

9 張承慧;一種工業(yè)過程時(shí)變參數(shù)估計(jì)新算法——修正目標(biāo)函數(shù)法[J];中國工程科學(xué);2001年11期

10 丁海軍;李峰磊;;蜂群算法在TSP問題上的應(yīng)用及參數(shù)改進(jìn)[J];中國科技信息;2008年03期

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

1 何敏;陳中顯;梅松濤;;蟻群算法的研究與進(jìn)展[A];中國計(jì)量協(xié)會(huì)冶金分會(huì)2010年會(huì)論文集[C];2010年

2 高瑋;;免疫連續(xù)蟻群算法[A];第二十六屆中國控制會(huì)議論文集[C];2007年

3 唐乾玉;韓曾晉;;基于擾動(dòng)分析的優(yōu)化算法[A];1994中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1994年

4 金成勛;周廣祿;郭恒業(yè);;對ICP算法中穩(wěn)定采樣的研究[A];立體圖象技術(shù)及其應(yīng)用研討會(huì)論文集[C];2005年

5 陳元琰;閆友彪;羅曉曙;;REM算法的改進(jìn)[A];廣西計(jì)算機(jī)學(xué)會(huì)2005年學(xué)術(shù)年會(huì)論文集[C];2005年

6 范瑛;;改進(jìn)蟻群算法結(jié)合BP網(wǎng)絡(luò)用于入侵檢測[A];中國運(yùn)籌學(xué)會(huì)模糊信息與模糊工程分會(huì)第五屆學(xué)術(shù)年會(huì)論文集[C];2010年

7 萬麗芬;鐘炎平;;約束LMS算法研究[A];第二十屆電工理論學(xué)術(shù)年會(huì)論文集[C];2008年

8 云飛;薛青;姚義軍;;改進(jìn)型LMBP算法在軍事數(shù)據(jù)分析中的應(yīng)用研究[A];'2010系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

9 朱雙東;艾智斌;閻夏;;BP網(wǎng)絡(luò)學(xué)習(xí)算法的改進(jìn)方案探析[A];1998年中國智能自動(dòng)化學(xué)術(shù)會(huì)議論文集（上冊）[C];1998年

10 唐乾玉;陳翰馥;韓曾晉;;串行生產(chǎn)線的參數(shù)優(yōu)化[A];1994年中國控制會(huì)議論文集[C];1994年

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

1 楊擴(kuò)軍;TIADC系統(tǒng)校準(zhǔn)算法研究與實(shí)現(xiàn)[D];電子科技大學(xué);2015年

2 黃亞魁;幾類優(yōu)化問題的BB型算法研究[D];西安電子科技大學(xué);2015年

3 王戈;通信信號若干聯(lián)合處理技術(shù)研究[D];解放軍信息工程大學(xué);2013年

4 王可心;大規(guī)模過程系統(tǒng)非線性優(yōu)化的簡約空間理論與算法研究[D];浙江大學(xué);2008年

5 鮑吉鋒;平衡問題和優(yōu)化問題若干算法的收斂性分析[D];浙江大學(xué);2013年

6 韓飛;基于先驗(yàn)信息編碼的約束學(xué)習(xí)算法研究[D];中國科學(xué)技術(shù)大學(xué);2006年

7 袁東輝;蟻群算法在飛行模擬器平臺(tái)中若干應(yīng)用問題的研究[D];吉林大學(xué);2011年

8 厲丹;視頻目標(biāo)檢測與跟蹤算法及其在煤礦中應(yīng)用的研究[D];中國礦業(yè)大學(xué);2011年

9 滕月陽;正電子發(fā)射斷層成像中的數(shù)學(xué)模型與算法[D];東北大學(xué);2012年

10 張曉偉;全局優(yōu)化的若干隨機(jī)性算法[D];西安電子科技大學(xué);2008年

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

1 楊展;城軌列車自動(dòng)調(diào)整系統(tǒng)模型與算法研究[D];西南交通大學(xué);2015年

2 馬英鈞;基于人工蜂群算法的約束優(yōu)化問題研究[D];華中師范大學(xué);2015年

3 錢其;電網(wǎng)諧波和間諧波功率的計(jì)量算法研究[D];中國科學(xué)技術(shù)大學(xué);2015年

4 蔣玉冰;無線通信信號到達(dá)角跟蹤算法研究[D];電子科技大學(xué);2014年

5 孫方亮;基于粒子群與中心引力的一種新混合算法及應(yīng)用[D];西安電子科技大學(xué);2014年

6 于詩杰;基于無波前探測的大氣光通信自適應(yīng)補(bǔ)償方法研究[D];西安電子科技大學(xué);2014年

7 柯家龍;壓縮感知算法及其在成像中的應(yīng)用[D];南京郵電大學(xué);2015年

8 劉光泓;并行磁共振圖像全變分恢復(fù)一階算法研究[D];南京郵電大學(xué);2015年

9 張德祥;基于改進(jìn)蟻群算法的機(jī)器人三維路徑規(guī)劃研究[D];青島科技大學(xué);2015年

10 張申利;基于蜂群算法的GIS優(yōu)化選址及其并行化研究與應(yīng)用[D];中國石油大學(xué)(華東);2014年

，

本文編號：1729233