基于隨機游走的動態(tài)社團劃分算法.pdf

1、網(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ò)中，隨機游走是從某

2、一個頂點出發(fā)隨機地移動到與其相鄰的頂點，并繼續(xù)這樣的游走的過程。定性的認(rèn)為從頂點i出發(fā)的游走將會大概率地滯留在頂點i的社團中（找不到錯綜復(fù)雜的迷宮的出口），這就意味著頂點i移動到其他社團的期望步長很大（不斷地做嘗試）。基于這個思路，與馬爾科夫隨機過程理論結(jié)合，求出任意兩個頂點間的首次到達(dá)的期望步長，通過根據(jù)這個度量將頂點進行聚類的方式將頂點集合劃分成不同的社團。第三部分對此算法的復(fù)雜度和優(yōu)劣性進行了討論，在分析復(fù)雜度的過程中嘗試了很多種