復雜網(wǎng)絡中的社團劃分算法研究.pdf

1、復雜網(wǎng)絡分析始于二十世紀30年代，并快速發(fā)展成為了具有舉足輕重地位的研究領(lǐng)域。使用復雜網(wǎng)絡對現(xiàn)有的系統(tǒng)進行研究，可以極大地加深人們對復雜系統(tǒng)的認識。復雜網(wǎng)絡中的社團結(jié)構(gòu)是一項一直以來受到廣泛關(guān)注的特性。在復雜網(wǎng)絡中，連邊往往不會呈現(xiàn)完全均勻的分布，它們會在某些區(qū)域較為密集，而在其他部分較為稀疏。這些密集的區(qū)域就被稱為網(wǎng)絡社團結(jié)構(gòu)。網(wǎng)絡中的社團結(jié)構(gòu)往往和網(wǎng)絡的類型存在著極大的關(guān)系，它們之于網(wǎng)絡，就相當于組織器官之于人體。對網(wǎng)絡中的社團進行

2、研究，可以很快地發(fā)現(xiàn)網(wǎng)絡中節(jié)點和連邊之間的關(guān)系。這對于社會學、經(jīng)濟學、生物學，甚至是工程學的研究都具有非常重要的現(xiàn)實意義。但是，社團劃分算法的作用目標是未知社團結(jié)構(gòu)的網(wǎng)絡，它很早就被證明是一個NP難題，迄今為止沒有令人滿意的結(jié)果。針對復雜網(wǎng)絡中的社團發(fā)現(xiàn)方法，本文做了以下工作：
　　1.針對發(fā)現(xiàn)網(wǎng)絡中重要節(jié)點的方法進行了研究。對已有的聚類系數(shù)、環(huán)路系數(shù)、介數(shù)中心度等方法進行理論分析和編程實踐。通過實驗結(jié)果比較，確定了各種方法的最佳

3、作用對象和使用環(huán)境，找出了可以較好的發(fā)現(xiàn)社團核心節(jié)點和社團之間節(jié)點的方法。
　　2.提出了“虛擬力”的概念，即將網(wǎng)絡中每個節(jié)點看作是一個智能個體，相連的節(jié)點之間存在著引力，使節(jié)點相互靠近；而不相連的節(jié)點之間存在斥力，使節(jié)點相互分離。網(wǎng)絡節(jié)點在其受力環(huán)境下進行自由的移動，經(jīng)過若干次的作用，網(wǎng)絡中從屬于同一社團的節(jié)點將會聚集起來，而不同的兩個社團則會逐漸分開，從而找出網(wǎng)絡中的社團結(jié)構(gòu)。
　　3.在“虛擬力”概念的基礎(chǔ)上，提出了基