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

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

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