基于隨機(jī)游走的動(dòng)態(tài)社團(tuán)劃分算法.pdf

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

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