本文關鍵詞：基于隨機游走的動態(tài)社團劃分算法

  更多相關文章： 社團劃分 馬爾科夫過程 隨機游走 線性方程組求解 正規(guī)拉普拉斯矩陣

【摘要】：網(wǎng)絡科學是近十多年來興起的一門交叉科學。對復雜網(wǎng)絡性質(zhì)的研究有重要的意義。社團性質(zhì)是復雜系統(tǒng)中網(wǎng)絡結構的一個重要結構特征。直觀上講,社團結構表示在同一個社團中圖的頂點之間的連邊比較密集,相對地,社團之間的連邊稀疏。社團劃分是一個NP-hard問題。本篇文章的第一部分介紹了一些典型的網(wǎng)絡和重要的社團劃分算法,例如空手道俱樂部網(wǎng)絡,蛋白質(zhì)網(wǎng)絡等以及二部劃分,層次劃分和動態(tài)劃分等。第二部分闡述了本人的社團劃分算法。在一個網(wǎng)絡中,隨機游走是從某一個頂點出發(fā)隨機地移動到與其相鄰的頂點,并繼續(xù)這樣的游走的過程。定性的認為從頂點i出發(fā)的游走將會大概率地滯留在頂點i的社團中(找不到錯綜復雜的迷宮的出口),這就意味著頂點i移動到其他社團的期望步長很大(不斷地做嘗試)�；谶@個思路,與馬爾科夫隨機過程理論結合,求出任意兩個頂點間的首次到達的期望步長,通過根據(jù)這個度量將頂點進行聚類的方式將頂點集合劃分成不同的社團。第三部分對此算法的復雜度和優(yōu)劣性進行了討論,在分析復雜度的過程中嘗試了很多種求解線性方程組的方法,利用標準化拉普拉斯矩陣的譜理論和柯西交錯定理證明了在頂點個數(shù)很大的情況下一般的迭代算法是不可取的,最終選擇的方法為共軛梯度法,本算法的復雜度為O(3)。最后利用了幾個典型的關系網(wǎng)絡和隨機圖來驗證算法的可靠性,通過測試的對比結果來看此算法在可靠性上具有一定優(yōu)越性。
【關鍵詞】：社團劃分 馬爾科夫過程 隨機游走 線性方程組求解 正規(guī)拉普拉斯矩陣
【學位授予單位】：上海交通大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 中文摘要6-7
• 英文摘要7-9
• 第一章 引言9-12
• 第二章 重要網(wǎng)絡和社團結構劃分算法介紹12-22
• 2.1 網(wǎng)絡介紹12-14
• 2.2 算法介紹14-22
• 2.2.1 社團量化標準14-16
• 2.2.2 社團發(fā)現(xiàn)和劃分算法16-22
• 第三章 復雜網(wǎng)絡的動態(tài)劃分算法22-28
• 3.1 經(jīng)典算法的局限性22-23
• 3.2 基于隨機游走的算法23-28
• 3.2.1 基本思想和理論基礎23-25
• 3.2.2 對距離矩陣的分析25-27
• 3.2.3 算法流程27-28
• 第四章 算法復雜度分析和改進28-33
• 4.1 復雜度分析28-31
• 4.2 算法的改進31-33
• 第五章 模型測試33-37
• 5.1 隨機圖33-35
• 5.2 空手道社團35
• 5.3 海豚圖35-37
• 第六章 總結與展望37-38
• 參考文獻38-41
• 附錄一 程序代碼41-46

【相似文獻】

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

1 吳迪;周利娟;林鴻飛;;基于隨機游走的就業(yè)推薦系統(tǒng)研究與實現(xiàn)[J];廣西師范大學學報(自然科學版);2011年01期

2 蘇浩航;張義門;張玉明;解敏;滿進財;;基于改進的壓縮式隨機游走算法對靜態(tài)電源/地網(wǎng)的模擬[J];計算物理;2007年06期

3 宋銳;湯建勛;周健;;工作電流對二頻機抖激光陀螺角隨機游走影響的研究[J];激光雜志;2010年02期

4 周持中;一類具有吸收點的平面隨機游走[J];岳陽大學學報;1996年02期

5 雷鈺麗;李陽;王崇駿;劉紅星;謝俊元;;基于權重的馬爾可夫隨機游走相似度度量的實體識別方法[J];河北師范大學學報(自然科學版);2010年01期

6 俞琰;邱廣華;;基于局部隨機游走的在線社交網(wǎng)絡朋友推薦算法[J];系統(tǒng)工程;2013年02期

7 何建軍;李仁發(fā);;改進的隨機游走模型節(jié)點排序方法[J];計算機工程與應用;2011年12期

8 鄧貴仕,賴寶全;反饋式隨機游走模型及其在股票投資中應用[J];大連理工大學學報;2004年06期

9 戴穎;;深圳股票市場的隨機游走檢驗[J];商業(yè)經(jīng)濟;2005年11期

10 周軍軍;王明文;何世柱;石松;;基于隨機游走和聚類平滑的協(xié)同過濾推薦算法[J];廣西師范大學學報(自然科學版);2011年01期

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

1 鄭偉;王朝坤;劉璋;王建民;;一種基于隨機游走模型的多標簽分類算法[A];NDBC2010第27屆中國數(shù)據(jù)庫學術會議論文集A輯一[C];2010年

2 朱松豪;羅青青;梁志偉;;一種改進圖像標注的新方法[A];第24屆中國控制與決策會議論文集[C];2012年

3 燕飛;張銘;譚裕韋;唐建;鄧志鴻;;綜合社會行動者興趣和網(wǎng)絡拓撲的社區(qū)發(fā)現(xiàn)方法[A];NDBC2010第27屆中國數(shù)據(jù)庫學術會議論文集(B輯)[C];2010年

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

1 長盛基金管理有限公司研究部副總監(jiān) 李驥;投資自己熟悉的股票[N];證券時報;2006年

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

1 鄧凱英;復雜網(wǎng)絡搜索策略及相關模型的數(shù)值方法[D];東北師范大學;2015年

2 徐曉華;圖上的隨機游走學習[D];南京航空航天大學;2008年

3 孫甲申;基于主題模型和隨機游走的標簽技術研究[D];北京郵電大學;2013年

4 呂強;面向高性能和強表達力的自動規(guī)劃[D];中國科學技術大學;2013年

5 趙學華;統(tǒng)計網(wǎng)絡模型若干關鍵問題研究[D];吉林大學;2014年

6 廖振;基于查詢點擊核心圖的查詢推薦問題研究[D];南開大學;2013年

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

1 何岱洧;Z~d上使Schramm的上界達到的旋轉(zhuǎn)配置[D];復旦大學;2014年

2 田新春;回火老化效應及其擴散方程[D];蘭州大學;2015年

3 鞠薇;基于隨機游走和圖割算法的PET-CT肺腫瘤分割[D];蘇州大學;2015年

4 祝霖;基于隨機游走的動態(tài)社團劃分算法[D];上海交通大學;2015年

5 陸林;圖上的智能隨機游走分類算法研究及應用[D];揚州大學;2014年

6 王麗莎;基于隨機游走模型的個性化信息推薦[D];大連理工大學;2011年

7 胡潔;基于圖論的醫(yī)學圖像分割隨機游走算法研究[D];南方醫(yī)科大學;2013年

8 鄭偉;基于增強語義和隨機游走的分類算法研究[D];清華大學;2011年

9 沈敬欣;結合最大度與隨機游走策略的復雜網(wǎng)絡搜索技術研究[D];大連海事大學;2012年

10 康宗戰(zhàn);協(xié)同標注系統(tǒng)中基于隨機游走的個性化推薦研究[D];云南大學;2015年

，

本文編號：1082387