【摘要】：網(wǎng)絡節(jié)點的親密程度或近似特征使社交網(wǎng)絡往往呈現(xiàn)出特定的社區(qū)結(jié)構(gòu),因此,社區(qū)劃分是社交網(wǎng)絡結(jié)構(gòu)研究的重要手段之一,研究劃分后的網(wǎng)絡社區(qū)可以獲得網(wǎng)絡的內(nèi)部結(jié)構(gòu)、作用關系以及規(guī)律特性,從而更好地理解和應用網(wǎng)絡。現(xiàn)有的多種社區(qū)劃分算法主要利用節(jié)點間連接的密切程度進行社區(qū)劃分。本文把網(wǎng)絡理解為一個信息隨機擴散的系統(tǒng),即節(jié)點信息擴散到其他節(jié)點的分布情況反映了他們之間的密切程度,這與PageRank算法的排序原理相一致。在此基礎上,提出基于PageRank算法和信息擴散原理的社區(qū)劃分算法(PR-DCS)。PR-DCS算法依據(jù)信息擴散的隨機游走性質(zhì),將PageRank中的排序向量擴展為信息擴散矩陣,利用該矩陣反應出的節(jié)點間密切程度,分析得到社區(qū)結(jié)構(gòu)。通過將PR-DCS算法與其他代表性社區(qū)劃分算法進行實驗對比分析,確定了PR-DCS算法能夠準確的提取網(wǎng)絡的社區(qū)結(jié)構(gòu)。結(jié)合PageRank算法中的威望概念和PR-DCS算法中的主觀意愿概念,對PR-DCS算法做了進一步的優(yōu)化。算法的核心思想是同一社區(qū)節(jié)點間的信息交流更通暢,他們之間的信息交流比不同社區(qū)內(nèi)節(jié)點間的交流更快達到穩(wěn)定值。算法通過計算節(jié)點每次信息擴散之后的信息變化量來確定信息量率先穩(wěn)定的節(jié)點關系,社區(qū)的核心節(jié)點在信息擴散過程中會先達到穩(wěn)態(tài),將先達到穩(wěn)態(tài)的關系中的節(jié)點劃分在一起能夠更準確地提取社區(qū)結(jié)構(gòu)。實驗證明了社區(qū)核心節(jié)點擴散值達到穩(wěn)態(tài)的速度高于其他節(jié)點,在對同一社區(qū)的劃分中,優(yōu)化算法的模塊度更高,其結(jié)果也能更好地解釋真實的社區(qū)劃分。在對算法的探索中,分析了信息擴散次數(shù)對于劃分結(jié)果的影響,將“六度分割”作為約束信息擴散次數(shù)的理論依據(jù),保證了信息擴散矩陣中元素含義的正確性:既可以防止因擴散次數(shù)的增多而導致元素值轉(zhuǎn)化為節(jié)點的威望值,同時也可以保證節(jié)點的基礎交流行為。實驗證明,將信息擴散次數(shù)定義為6能夠客觀地約束節(jié)點交流程度,準確提取社區(qū)結(jié)構(gòu)。
文內(nèi)圖片：
圖片說明： 沈陽航空航天大學碩士學位論文為 k 的概率。完全隨機網(wǎng)絡的度分布近似為泊松分布(Possion)，而大量研究表明許多實網(wǎng)絡的度分布與泊松分布差異較大，以冪率分布形式出現(xiàn)，表示為 P(k)~k-r，例如影演員網(wǎng)絡和電力網(wǎng)絡[32]。冪率分布在雙對數(shù)坐標系下繪制的結(jié)果近似一條斜率為負直線，當系數(shù) r∈[2,3]時，表明網(wǎng)絡中的絕大部分節(jié)點的度數(shù)很低，同時也存在少量度數(shù)較高的節(jié)點。圖 2.1 表示具有 34 點的空手道網(wǎng)絡的度數(shù)統(tǒng)計，橫坐標表示節(jié)點的數(shù)，縱坐標表示度為 k 的節(jié)點占整個網(wǎng)絡節(jié)點數(shù)的比例。圖 2.2 是將統(tǒng)計值在對數(shù)坐中繪制的情況，這條曲線近似冪率分布。
文內(nèi)圖片：
圖片說明： 沈陽航空航天大學碩士學位論文為 k 的概率。完全隨機網(wǎng)絡的度分布近似為泊松分布(Possion)，而大量研究表明許多實網(wǎng)絡的度分布與泊松分布差異較大，以冪率分布形式出現(xiàn)，表示為 P(k)~k-r，例如影演員網(wǎng)絡和電力網(wǎng)絡[32]。冪率分布在雙對數(shù)坐標系下繪制的結(jié)果近似一條斜率為負直線，當系數(shù) r∈[2,3]時，表明網(wǎng)絡中的絕大部分節(jié)點的度數(shù)很低，同時也存在少量度數(shù)較高的節(jié)點。圖 2.1 表示具有 34 點的空手道網(wǎng)絡的度數(shù)統(tǒng)計，橫坐標表示節(jié)點的數(shù)，，縱坐標表示度為 k 的節(jié)點占整個網(wǎng)絡節(jié)點數(shù)的比例。圖 2.2 是將統(tǒng)計值在對數(shù)坐中繪制的情況，這條曲線近似冪率分布。
【學位授予單位】：沈陽航空航天大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：TP393.02

【參考文獻】

相關期刊論文 前6條

1 黃賢英;陳紅陽;;基于用戶興趣度的PageRank改進算法[J];重慶理工大學學報(自然科學);2014年05期

2 周東浩;韓文報;;DiffRank:一種新型社會網(wǎng)絡信息傳播檢測算法[J];計算機學報;2014年04期

3 楊博;陳賀昌;朱冠宇;趙學華;;基于超鏈接多樣性分析的新型網(wǎng)頁排名算法[J];計算機學報;2014年04期

4 張s

本文編號：2514072