本文關鍵詞：基于BFS的局部社區(qū)發(fā)現(xiàn)算法研究

  更多相關文章： 局部社區(qū)發(fā)現(xiàn) 最大結合性節(jié)點 共同好友數(shù)目 廣度優(yōu)先搜索

【摘要】：近年來隨著互聯(lián)網(wǎng)技術的飛速發(fā)展,越來越多的數(shù)據(jù)以網(wǎng)狀的結構呈現(xiàn)于人們面前,而社團結構正是研究網(wǎng)絡拓撲結構的一個重要方面。發(fā)現(xiàn)網(wǎng)絡中存在的社區(qū)結構也成了一個很熱門的話題,許多學者對此進行了研究。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法關注于整個全局網(wǎng)絡結構,這樣會具有較高的時間復雜度。而有的時候我們也不需要獲得網(wǎng)絡的全局社區(qū)結構。比如對于網(wǎng)絡中的一個核心節(jié)點,我們想知道的是這個核心節(jié)點的覆蓋范圍,也即找到它所在的社區(qū)就可以了。因此本文提出了一種新的局部社區(qū)發(fā)現(xiàn)算法。本文提出的局部社區(qū)發(fā)現(xiàn)算法以起始節(jié)點相對應的最大結合性節(jié)點為出發(fā)點,以節(jié)點相似性(兩個節(jié)點的共同鄰居節(jié)點數(shù)目)為度量并基于圖的廣度優(yōu)先搜索來進行社區(qū)發(fā)現(xiàn)。從起始節(jié)點相對應的最大結合性節(jié)點出發(fā)進行社區(qū)發(fā)現(xiàn)可以避免邊界節(jié)點找不到社區(qū)的情況,提高算法的魯棒性和普適性。基于圖的廣度優(yōu)先搜索可以得到與圖的邊數(shù)呈線性規(guī)模的時間復雜度。將本文提出的算法運行在四個經(jīng)典數(shù)據(jù)集上,在不降低社區(qū)發(fā)現(xiàn)精度的情況下依然顯著降低了社區(qū)發(fā)現(xiàn)的時間復雜度,提高了算法魯棒性。
【關鍵詞】：局部社區(qū)發(fā)現(xiàn) 最大結合性節(jié)點 共同好友數(shù)目 廣度優(yōu)先搜索
【學位授予單位】：上海交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要3-4
• ABSTRACT4-10
• 第一章 緒論10-13
• 1.1 課題研究背景和意義10
• 1.2 國內(nèi)外研究現(xiàn)狀10-12
• 1.3 論文主要工作12
• 1.4 論文組織結構12-13
• 第二章 社區(qū)發(fā)現(xiàn)綜述13-34
• 2.1 社區(qū)發(fā)現(xiàn)定義13-24
• 2.1.1 基本概念13-15
• 2.1.2 局部定義15-17
• 2.1.3 全局定義17
• 2.1.4 基于節(jié)點相似度的定義17-19
• 2.1.5 基于分割的定義19-21
• 2.1.6 基于模塊度的定義21-24
• 2.2 全局社區(qū)發(fā)現(xiàn)算法24-27
• 2.2.1 圖分割24
• 2.2.2 等級聚類24-25
• 2.2.3 分割聚類25-26
• 2.2.4 譜聚類26
• 2.2.5 Girvan-Newman算法26-27
• 2.3 局部社區(qū)發(fā)現(xiàn)方法27-33
• 2.3.1 Clauset算法28-30
• 2.3.2 Luo算法30
• 2.3.3 Lee算法30-31
• 2.3.4 LMD算法31-32
• 2.3.5 Zhu算法32-33
• 2.4 本章小結33-34
• 第三章 基于BFS的局部社區(qū)發(fā)現(xiàn)算法設計34-47
• 3.1 相似度定義34-35
• 3.2 節(jié)點最大結合性35-36
• 3.2.1 節(jié)點結合性35-36
• 3.2.2 最大結合性節(jié)點36
• 3.3 算法過程描述36-44
• 3.3.1 算法發(fā)現(xiàn)步驟37-39
• 3.3.2 算法偽代碼描述39-44
• 3.4 算法復雜度分析44-46
• 3.5 本章小結46-47
• 第四章 基于BFS的局部社區(qū)發(fā)現(xiàn)算法實現(xiàn)與分析47-74
• 4.1 實驗數(shù)據(jù)集介紹47-53
• 4.1.1 數(shù)據(jù)集格式介紹47
• 4.1.2 空手道俱樂部網(wǎng)絡47-49
• 4.1.3 海豚網(wǎng)絡49-50
• 4.1.4 美國足球俱樂部網(wǎng)絡50-51
• 4.1.5 美國政治書籍網(wǎng)絡51-53
• 4.2 實驗框架設計53
• 4.3 實驗評價標準53-55
• 4.4 實驗結果驗證與分析55-73
• 4.4.1 空手道俱樂部網(wǎng)絡數(shù)據(jù)驗證56-59
• 4.4.2 海豚網(wǎng)絡數(shù)據(jù)驗證59-61
• 4.4.3 美國足球俱樂部網(wǎng)絡數(shù)據(jù)驗證61-66
• 4.4.4 美國政治書籍網(wǎng)絡數(shù)據(jù)驗證66-69
• 4.4.5 實驗總結69-73
• 4.5 本章小結73-74
• 第五章 全文總結與展望74-76
• 5.1 論文工作總結74-75
• 5.2 創(chuàng)新點75
• 5.3 后續(xù)研究工作75-76
• 參考文獻76-80
• 致謝80-81
• 攻讀碩士學位期間已發(fā)表或錄用的論文81-83

【相似文獻】

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

1 龍騰芳,高金文;“分而治之”方法在算法設計中的應用[J];渤海大學學報(自然科學版);2004年01期

2 田翠華;王偉杰;許衛(wèi)平;;《算法設計與分析》的理論研究與教學實踐[J];赤峰學院學報(自然科學版);2012年15期

3 仇棣;;算法設計與分析——計算機理論領域中的一本好書[J];應用數(shù)學;1991年02期

4 張銀明;元素判別值分配法及其算法設計[J];計算機工程與應用;1995年06期

5 沈灝;;信息與計算科學專業(yè)的算法設計能力培養(yǎng)方法[J];學園;2014年10期

6 李秦;;建構主義教學模式與算法設計與分析課程教學[J];甘肅科技;2013年24期

7 夏夢;;《算法設計與分析》的教學方法研究[J];科技資訊;2009年18期

8 許道云;;算法機制設計的數(shù)學基礎[J];貴州大學學報(自然科學版);2013年03期

9 張銀明;貨郎擔問題的新解法及其算法設計[J];華僑大學學報(自然科學版);1995年04期

10 陳云霞;聶士澄;;試談學生算法設計能力的培養(yǎng)[J];揚州師院學報(自然科學版);1995年03期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 雷詠梅;;橢圓曲線密碼體制的算法設計與實現(xiàn)[A];西部大開發(fā) 科教先行與可持續(xù)發(fā)展——中國科協(xié)2000年學術年會文集[C];2000年

2 楊盤洪;朱軍祥;趙建安;楊靜;;機動目標跟蹤的模糊變結構交互多模算法[A];2007'中國儀器儀表與測控技術交流大會論文集（二）[C];2007年

3 徐子珊;;《算法設計與分析》課程中的工程教育[A];2005年全國理論計算機科學學術年會論文集[C];2005年

4 王輝;劉治昌;;用一種新算法設計的安全系統(tǒng)[A];2007年中國智能自動化會議論文集[C];2007年

5 舒輝;柳清峰;杜祝平;周蓓;;實踐教學模式在本科專業(yè)課程教學中的應用[A];中國電子教育學會高教分會2010年論文集[C];2010年

6 彭小宏;陽東升;劉忠;;基于聚類算法的組織協(xié)作網(wǎng)設計[A];2006中國控制與決策學術年會論文集[C];2006年

7 李皓;羅熊;;云存儲部署優(yōu)化的進化算法設計[A];2013年中國智能自動化學術會議論文集（第三分冊）[C];2013年

8 羅長政;李熙瑩;王鎮(zhèn)波;羅東華;;一種大流量交叉路口的背景提取與更新算法[A];第十五屆全國圖象圖形學學術會議論文集[C];2010年

9 楊利;李霖;昌月樓;陽國貴;;對稱位向量及啟發(fā)式并行散列連接算法[A];數(shù)據(jù)庫研究與進展95——第十三屆全國數(shù)據(jù)庫學術會議論文集[C];1995年

10 張晉;;嵌入式電腦鼠運行算法的研究[A];全國第20屆計算機技術與應用學術會議（CACIS·2009）暨全國第1屆安全關鍵技術與應用學術會議論文集（上冊）[C];2009年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 ;算法設計的策略[N];電腦報;2003年

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

1 谷偉哲;齊次光滑算法及其應用[D];天津大學;2010年

2 龍海俠;進化算法及其在生物信息中的應用[D];江南大學;2010年

3 譚躍;具有混沌局部搜索策略的粒子群優(yōu)化算法研究[D];中南大學;2013年

4 尤海峰;求解隱式目標優(yōu)化問題的交互式進化算法研究[D];中國科學技術大學;2011年

5 張常淳;基于MapReduce的大數(shù)據(jù)連接算法的設計與優(yōu)化[D];中國科學技術大學;2014年

6 郭崇慧;地區(qū)中長期發(fā)展規(guī)劃若干定量模型、算法及應用研究[D];大連理工大學;2002年

7 蔣蔚;粒子濾波改進算法研究與應用[D];哈爾濱工業(yè)大學;2010年

8 孫賀;算法設計中的若干前沿問題[D];復旦大學;2009年

9 陳寧濤;基于二分技術的高效算法設計及其應用[D];華中科技大學;2006年

10 婁曉文;無符號基因組切割再粘貼重組問題的算法研究[D];山東大學;2010年

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

1 王豫中;基于BFS的局部社區(qū)發(fā)現(xiàn)算法研究[D];上海交通大學;2015年

2 陳艷瓊;若干算法設計模式的研究與應用[D];江西師范大學;2008年

3 賀國華;交互變鄰域微分進化群搜索優(yōu)化算法[D];太原科技大學;2011年

4 蔡平梅;結構化稀疏信號的恢復算法研究[D];上海大學;2015年

5 李枝勇;蝙蝠算法及其在函數(shù)優(yōu)化中的應用研究[D];上海理工大學;2013年

6 房娟艷;混合群搜索優(yōu)化算法及其應用研究[D];太原科技大學;2010年

7 劉文錦;雙收縮人工植物算法[D];太原科技大學;2012年

8 張園;遞推技術在算法設計中的應用研究[D];江西師范大學;2012年

9 李旭明;基于小世界模型的社會情感優(yōu)化算法及應用研究[D];太原科技大學;2012年

10 賈瑞民;人工蜂群算法的改進及應用研究[D];廣西民族大學;2013年

，

本文編號：967813