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

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

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

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

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

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