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

1、網絡科學是近十多年來興起的一門交叉科學。對復雜網絡性質的研究有重要的意義。社團性質是復雜系統(tǒng)中網絡結構的一個重要結構特征。直觀上講，社團結構表示在同一個社團中圖的頂點之間的連邊比較密集，相對地，社團之間的連邊稀疏。社團劃分是一個NP-hard問題。本篇文章的第一部分介紹了一些典型的網絡和重要的社團劃分算法，例如空手道俱樂部網絡，蛋白質網絡等以及二部劃分，層次劃分和動態(tài)劃分等。第二部分闡述了本人的社團劃分算法。在一個網絡中，隨機游走是從某

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