【摘要】：隨著Facebook, Twitter等網(wǎng)站的興起,社交網(wǎng)絡(luò)的規(guī)模日趨復(fù)雜和龐大。通常,網(wǎng)絡(luò)呈現(xiàn)社區(qū)分布結(jié)構(gòu),而社區(qū)間非冗余關(guān)系的存在形成了網(wǎng)絡(luò)的漏洞。分析這些社區(qū)和漏洞可以了解網(wǎng)絡(luò)中的群落分布和競爭優(yōu)勢,是社會關(guān)系網(wǎng)絡(luò)分析中重要的基礎(chǔ)性研究,并已成為當(dāng)今學(xué)術(shù)界和工業(yè)界的熱點話題。目前,經(jīng)典的社區(qū)發(fā)現(xiàn)算法包括Newman等人提出的GN算法及其改進(jìn)、基于評價社區(qū)結(jié)構(gòu)的Q函數(shù)算法和基于clique發(fā)現(xiàn)的算法等。然而,這些算法時間復(fù)雜度較高,不適用于大型社交網(wǎng)絡(luò)的處理。本文借鑒COPRA算法的標(biāo)簽傳播機制,簡化社區(qū)發(fā)現(xiàn)的過程,提出一種基于BSP模型的并行迭代算法PCOPRA,并最終應(yīng)用于BC-BSP系統(tǒng)中。與此同時,針對COPRA算法的缺點,本文進(jìn)行了兩點改進(jìn)：(1)為避免因COPRA算法的同步標(biāo)簽傳播而導(dǎo)致的標(biāo)簽振蕩現(xiàn)象,使得算法無法收斂；也為避免因異步標(biāo)簽傳播而導(dǎo)致挖掘結(jié)果的不穩(wěn)定,本文提出了標(biāo)簽傳播的半異步迭代機制。通過同/異步交替運行的方式,算法可結(jié)合兩種迭代各自的優(yōu)點,在確保結(jié)果穩(wěn)定性的同時加快算法收斂速度,獲得更好的性能。(2)為避免COPRA算法因?qū)W(wǎng)絡(luò)未知全局參數(shù)的過度依賴而影響社區(qū)挖掘結(jié)果的準(zhǔn)確性,本文通過各節(jié)點對周圍鄰居社區(qū)情況的判別來自主決定網(wǎng)絡(luò)參數(shù),增加了社區(qū)發(fā)現(xiàn)過程的靈活性,提高了挖掘效率。除此之外,為支持標(biāo)簽的異步迭代更新,本文對BC-BSP系統(tǒng)的同步模型做了擴(kuò)展。通過在當(dāng)前超步提前獲取下一超步的消息來實現(xiàn)頂點的跨步更新,用以支持對增量迭代、標(biāo)簽傳播等應(yīng)用的快速處理。社交網(wǎng)絡(luò)上的結(jié)構(gòu)洞挖掘仍缺乏一個完備的理論算法,特別是對大型網(wǎng)絡(luò)的挖掘。針對以上問題,本文貢獻(xiàn)如下：(1)基于社區(qū)發(fā)現(xiàn)的結(jié)果,并借鑒Tang等人提出的HIS結(jié)構(gòu)洞模型,設(shè)計并實現(xiàn)了一種改進(jìn)后的基于BSP模型的并行結(jié)構(gòu)洞挖掘算法PHIS,并最終應(yīng)用于BC-BSP系統(tǒng)之上。(2)通過對節(jié)點更新規(guī)則的分析,從減少節(jié)點計算量和消息通信量的角度對算法進(jìn)行了優(yōu)化,很大程度地提升了性能。本文所提出的并行化算法基于BSP模型。實驗表明,在大規(guī)模社交網(wǎng)絡(luò)中,算法可以在有效的時間內(nèi)挖掘出高質(zhì)量的社區(qū)和結(jié)構(gòu)洞。
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP393.09

【相似文獻(xiàn)】

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

1 葛磊;武芳;王鵬波;張冬林;;3維建筑綜合中基于最小特征的面平移算法[J];測繪科學(xué)技術(shù)學(xué)報;2009年02期

2 駱雯,孫延明,陳振威,陳錦昌;判斷點與封閉多邊形相對關(guān)系的改進(jìn)算法[J];機械;1999年03期

3 李林;盧顯良;;一種基于切割映射的規(guī)則沖突消除算法[J];電子學(xué)報;2008年02期

4 劉巧玲;張紅英;林茂松;;一種簡單快速的圖像去霧算法[J];計算機應(yīng)用與軟件;2013年07期

5 林亞平,楊小林;快速概率分析進(jìn)化算法及其性能研究[J];電子學(xué)報;2001年02期

6 章郡鋒;吳曉紅;黃曉強;何小海;;基于暗原色先驗去霧的改進(jìn)算法[J];電視技術(shù);2013年23期

7 楊鐵軍;靳婷;;一種動態(tài)整周模糊值求解算法及其仿真分析[J];系統(tǒng)工程與電子技術(shù);2007年01期

8 周秀玲;郭平;陳寶維;王靜;;幾種計算超體積算法的比較研究[J];計算機工程;2011年03期

9 吳一戎,胡東輝,彭海良;Chirp Scaling SAR成象算法及其實現(xiàn)[J];電子科學(xué)學(xué)刊;1995年03期

10 王貴竹;一種產(chǎn)生單向分解值的算法[J];安徽大學(xué)學(xué)報(自然科學(xué)版);2001年03期

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

1 尹冀鋒;;一種新的圖象自適應(yīng)增強算法[A];四川省通信學(xué)會一九九二年學(xué)術(shù)年會論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計算機輔助增強、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價值[A];中華醫(yī)學(xué)會第十次全國超聲醫(yī)學(xué)學(xué)術(shù)會議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進(jìn)[A];第二十一屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實現(xiàn)[A];中國光學(xué)學(xué)會2010年光學(xué)大會論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進(jìn)展——第十三屆全國青年通信學(xué)術(shù)會議論文集（上）[C];2008年

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標(biāo)TBD算法[A];第十四屆全國圖象圖形學(xué)學(xué)術(shù)會議論文集[C];2008年

7 周磊;張衛(wèi)華;王曉奇;張軍;;基于流水算法的智能路障機器人設(shè)計[A];2011年全國電子信息技術(shù)與應(yīng)用學(xué)術(shù)會議論文集[C];2011年

8 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

9 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測算法[A];第六屆和諧人機環(huán)境聯(lián)合學(xué)術(shù)會議（HHME2010)、第19屆全國多媒體學(xué)術(shù)會議（NCMT2010）、第6屆全國人機交互學(xué)術(shù)會議（CHCI2010）、第5屆全國普適計算學(xué)術(shù)會議（PCC2010）論文集[C];2010年

10 楊任爾;陳懇;勵金祥;;基于棱邊方向檢測的運動自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

相關(guān)重要報紙文章 前1條

1 國泰君安資產(chǎn)管理部;“算法交易”是道指暴跌罪魁禍?zhǔn)?[N];上海證券報;2010年

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

1 馮輝;網(wǎng)絡(luò)化的并行與分布式優(yōu)化算法研究及應(yīng)用[D];復(fù)旦大學(xué);2013年

2 許玉杰;云計算環(huán)境下海量數(shù)據(jù)的并行聚類算法研究[D];大連海事大學(xué);2014年

3 李琰;基于貓群算法的高光譜遙感森林類型識別研究[D];東北林業(yè)大學(xué);2015年

4 陳加順;海洋環(huán)境下聚類算法的研究[D];南京航空航天大學(xué);2014年

5 王洋;基于群體智能的通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘算法研究[D];太原理工大學(xué);2015年

6 雷雨;面向考試時間表問題的啟發(fā)式進(jìn)化算法研究[D];西安電子科技大學(xué);2015年

7 熊霖;大數(shù)據(jù)下的數(shù)據(jù)選擇與學(xué)習(xí)算法研究[D];西安電子科技大學(xué);2015年

8 周雷;基于圖結(jié)構(gòu)的目標(biāo)檢測與分割算法研究[D];上海交通大學(xué);2014年

9 王冰;人工蜂群算法的改進(jìn)及相關(guān)應(yīng)用的研究[D];北京理工大學(xué);2015年

10 蔣亦樟;多視角和遷移學(xué)習(xí)識別方法和智能建模研究[D];江南大學(xué);2015年

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

1 姚鑫宇;EMD去噪與MUSIC算法在DOA估計中的聯(lián)合應(yīng)用[D];昆明理工大學(xué);2015年

2 陸進(jìn);面向含噪數(shù)據(jù)聚類相關(guān)算法的研究[D];復(fù)旦大學(xué);2014年

3 李家昌;基于能量約束的超聲圖像自動分割算法[D];華南理工大學(xué);2015年

4 陳堅;基于密度和約束的數(shù)據(jù)流聚類算法研究[D];蘭州大學(xué);2015年

5 高健;基于Zynq7000平臺的去霧算法研究及實現(xiàn)[D];南京理工大學(xué);2015年

6 顧磊;基于Hadoop的聚類算法的數(shù)據(jù)優(yōu)化及其應(yīng)用研究[D];南京信息工程大學(xué);2015年

7 楊燕霞;基于Hadoop平臺的并行關(guān)聯(lián)規(guī)則挖掘算法研究[D];四川師范大學(xué);2015年

8 王羽;基于MapReduce的社區(qū)發(fā)現(xiàn)算法的設(shè)計與實現(xiàn)[D];南京理工大學(xué);2015年

9 許振佳;流式數(shù)據(jù)的并行聚類算法研究[D];曲阜師范大學(xué);2015年

10 董琴;人工蜂群算法的改進(jìn)與應(yīng)用[D];大連海事大學(xué);2015年

，

本文編號：2578771