復(fù)雜網(wǎng)絡(luò)的社團(tuán)劃分算法研究.pdf

1、對(duì)于任何包含大量個(gè)體單元的復(fù)雜系統(tǒng)來(lái)說(shuō)，我們都可以將其看作復(fù)雜網(wǎng)絡(luò)來(lái)研究，復(fù)雜網(wǎng)絡(luò)具有小世界、無(wú)標(biāo)度和社團(tuán)結(jié)構(gòu)等諸多特征。社團(tuán)結(jié)構(gòu)主要刻畫(huà)了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的相互關(guān)系，社團(tuán)結(jié)構(gòu)具有處于社團(tuán)內(nèi)部的節(jié)點(diǎn)聯(lián)系較為緊密，處于社團(tuán)之間的節(jié)點(diǎn)聯(lián)系較為稀疏的顯著特點(diǎn)，深入了解復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)有助于發(fā)現(xiàn)網(wǎng)絡(luò)中潛藏著的規(guī)律和預(yù)測(cè)網(wǎng)絡(luò)的行為。
　　本文依據(jù)優(yōu)化、啟發(fā)式和相似度等不同的策略對(duì)常用社團(tuán)劃分算法進(jìn)行了分類(lèi)，并對(duì)其中的典型代表算法進(jìn)行了詳細(xì)

2、的研究分析。針對(duì)相似度算法中存在的問(wèn)題，本文提出了基于相似度的三元社團(tuán)合并算法(Ternary Community Merging Algorithm based on Similarity，STCMA)。然后，本文將三元社團(tuán)的概念應(yīng)用于傳統(tǒng)標(biāo)簽傳播算法(Label PropagationAlgorithm，LPA)，進(jìn)一步提出了基于三元社團(tuán)的LPA算法(Label Propagation Algorithm based onTerna

3、ry Community，TCLPA)。
　　(1)基于相似度的三元社團(tuán)合并算法
　　為解決在使用相似度判別哪些節(jié)點(diǎn)應(yīng)該被放入同一個(gè)社團(tuán)時(shí)可能出現(xiàn)的沖突問(wèn)題，該算法構(gòu)建了三元社團(tuán)，并將三元社團(tuán)作為網(wǎng)絡(luò)中社團(tuán)合并的基本元素。該算法通過(guò)引入三元社團(tuán)，有效地增強(qiáng)了社團(tuán)內(nèi)部節(jié)點(diǎn)之間連接的緊密程度，更加清晰的凸顯了網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)。該算法的時(shí)間復(fù)雜度為?O tm2 n?，其中n代表網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)目，m代表連邊數(shù)目，t代表節(jié)點(diǎn)相似度閾值

4、更新的次數(shù)，該算法的提出能夠較好的均衡時(shí)間復(fù)雜度與正確劃分率兩者之間的關(guān)系。
　　(2)基于三元社團(tuán)的LPA算法
　　針對(duì)傳統(tǒng)LPA算法中存在的兩大不確定問(wèn)題，一是在對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的標(biāo)簽信息進(jìn)行更改時(shí)其節(jié)點(diǎn)更新順序的不確定問(wèn)題；二是在鄰居節(jié)點(diǎn)集合中具有節(jié)點(diǎn)數(shù)目最多的標(biāo)簽信息類(lèi)型不惟一時(shí)從中選取標(biāo)簽信息的不確定問(wèn)題，該算法在三元社團(tuán)的基礎(chǔ)上構(gòu)建了網(wǎng)絡(luò)的初始核心社團(tuán)，然后結(jié)合局部最優(yōu)規(guī)則和深度計(jì)算規(guī)則計(jì)算網(wǎng)絡(luò)中其他節(jié)點(diǎn)的標(biāo)簽依賴度