基于社交網(wǎng)絡的社團劃分算法研究.pdf

1、社交網(wǎng)絡可以用來描述現(xiàn)實社會中的實際網(wǎng)絡，它包括人與人之間的社會關(guān)系，物種之間的捕食關(guān)系，科學研究中的合作關(guān)系等。大量研究已經(jīng)表明在真實世界中各種不同的社交網(wǎng)絡具有許多共同的結(jié)構(gòu)特征，例如小世界性質(zhì)、無標度性、社團結(jié)構(gòu)等。而其中對于社團結(jié)構(gòu)這一性質(zhì)的研究受到了來各種學科的研究者的廣泛關(guān)注，通過研究發(fā)現(xiàn)任一學科領域中各知識點、概念以及學科領域之間具有明顯的層次關(guān)系，同一概念中的知識點、同一學科的概念等聯(lián)系比較緊密，而與其它不同領域的知識聯(lián)

2、系比較稀疏。本文所研究的重點就是社團結(jié)構(gòu)，它的性質(zhì)可以幫助了解網(wǎng)絡結(jié)構(gòu)與分析網(wǎng)絡特性，探測分析網(wǎng)絡的社團結(jié)構(gòu)對我們認識和理解真實復雜網(wǎng)絡的結(jié)構(gòu)以及功能有著重要意義。目前，已經(jīng)有許多研究者投身到社團結(jié)構(gòu)探測的研究當中并提出了各種各樣的算法以便能夠快速而準確的找到網(wǎng)絡中的社團結(jié)構(gòu)，比較經(jīng)典的算法如 GN算法，譜平分法，Kernighan-Lin算法等。但是劃分社團的算法時間復雜度和準確性之間的矛盾仍然是大規(guī)模網(wǎng)絡的社團結(jié)構(gòu)分析面臨的重要問題

3、。在本文中，系統(tǒng)分析了已研究出的社團結(jié)構(gòu)劃分算法，比較了各幾種算法的優(yōu)缺點，在此基礎上我們提出了兩種改進的社團劃分算法。
　　本文主要做了以下幾方面的工作:
　　(1)研究了社交網(wǎng)絡理論的基本知識，介紹了社交網(wǎng)絡一些表示方法和一些基本概念，以后尋找社團劃分算法奠定了理論基礎。然后又介紹了幾種比較經(jīng)典的算法，并總結(jié)出了它們的優(yōu)點和缺點。
　　(2)利用相鄰節(jié)點之間的距離差值構(gòu)造了一種新的社團劃分算法—基于相鄰節(jié)點聚類的社

4、團劃分算法。首先要找到每個社團的初始聚類中心，以M個節(jié)點作為初始社團，計算與初節(jié)點距離最小的節(jié)點并入到相應社團中，以此類推直到網(wǎng)絡中的所有節(jié)點都聚類到社團中，算法完成。把本文中的算法應用在網(wǎng)絡實例上，通過檢測本算法具有很高的正確率。
　　(3)通過計算節(jié)點之間的相似性系數(shù)判斷節(jié)點之間相似度，利用相似度大的節(jié)點在同一個社團的可能性大，相似度小的節(jié)點可能處于不同的社團來進行層次聚類。層次聚類按節(jié)點之間的相似性進行分組，采用自底向上的策

5、略首先將每個節(jié)點作為一個社團，然后合并這些原子社團成為越來越大的社團，用模塊度 Q來判斷在算法何時停止。
　　本文的創(chuàng)新點:
　　(1)相鄰節(jié)點聚類的社團劃分算法定義了相鄰節(jié)點的距離差值，用這個參數(shù)定量的表示出了不同社團節(jié)點之間的差異程度。
　　(2)把網(wǎng)絡中的兩個節(jié)點的相似度，層次聚類算法和模塊度相結(jié)合構(gòu)造了一種算法，這個算法有了較高的準確率。
　　本論文提出的社團劃分算法肯定還有許多不完善的地方，相關(guān)工作還有