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

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

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

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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 孫甲申;基于主題模型和隨機游走的標(biāo)簽技術(shù)研究[D];北京郵電大學(xué);2013年

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

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

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

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

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

2 田新春;回火老化效應(yīng)及其擴散方程[D];蘭州大學(xué);2015年

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

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

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

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

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

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

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

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

，

本文編號：1082387