復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)劃分方法及其研究.pdf

1、信息技術(shù)的高速發(fā)展使人類社會(huì)大步邁入了網(wǎng)絡(luò)時(shí)代，既有人們?nèi)粘Ｉ铍x不開的大型電力網(wǎng)絡(luò)和交通網(wǎng)絡(luò),更有用于獲取知識(shí)信息的Internet網(wǎng)絡(luò)，萬(wàn)維網(wǎng)以及科研合作網(wǎng)絡(luò)，人們已經(jīng)生活在一個(gè)充滿著各種各樣的復(fù)雜網(wǎng)絡(luò)的世界中。這些大規(guī)模網(wǎng)絡(luò)的廣泛存在，使得研究復(fù)雜網(wǎng)絡(luò)成為必要，其中主要關(guān)注的是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以及網(wǎng)絡(luò)上發(fā)生的動(dòng)力學(xué)行為。特別是隨著WS小世界網(wǎng)絡(luò)模型和BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的提出，吸引了更多科學(xué)家加入到對(duì)復(fù)雜網(wǎng)絡(luò)的研究中。
　　

2、社團(tuán)結(jié)構(gòu)是許多實(shí)際復(fù)雜網(wǎng)絡(luò)中的的一個(gè)重要特征。尋找和分析社團(tuán)結(jié)構(gòu)有助于更好地了解網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)，分析網(wǎng)絡(luò)的性質(zhì)。目前人們已經(jīng)提出了很多算法用于尋找復(fù)雜網(wǎng)絡(luò)中存在的社團(tuán)結(jié)構(gòu)。在本文我們將聚類分析方法引入到復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)中進(jìn)行研究。主要工作如下:
　　 1.介紹了復(fù)雜網(wǎng)絡(luò)的基本概念及其基本性質(zhì)包括度與度分布、聚集系數(shù)與最短路徑、社團(tuán)結(jié)構(gòu)以及常見的兩種網(wǎng)絡(luò)模型。這些屬性和網(wǎng)絡(luò)模型是我們研究復(fù)雜網(wǎng)絡(luò)的前提。
　　 2.綜述了

3、復(fù)雜網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)算法的研究歷史及其意義，并且詳細(xì)分析了尋找網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的幾種代表算法。其中主要包括社會(huì)學(xué)中的分級(jí)聚類和計(jì)算機(jī)圖形學(xué)的圖形分割兩大類算法。這些方法將復(fù)雜網(wǎng)絡(luò)劃分成若干個(gè)節(jié)點(diǎn)較少，結(jié)構(gòu)較簡(jiǎn)單的子網(wǎng)絡(luò)，從而使研究較為簡(jiǎn)便。本文對(duì)這些典型的算法進(jìn)行了介紹對(duì)其優(yōu)缺點(diǎn)的也進(jìn)行了分析，并引入聚類分析，簡(jiǎn)單介紹聚類的目的、意義以及目前常用的幾種聚類方法。
　　 3.本文提出一種基于Normal矩陣的多維特征向量的社團(tuán)劃分算法

4、，該算法在傳統(tǒng)譜平分法的基礎(chǔ)上，綜合了多個(gè)特征向量的信息并結(jié)合數(shù)據(jù)挖掘中的聚類分析來(lái)判斷社團(tuán)的劃分邊界，尤其是多維特征向量的綜合使得邊界不是很清晰的社團(tuán)也能夠被較準(zhǔn)確地劃分出來(lái)。數(shù)據(jù)挖掘中的聚類分析算法，是分析社團(tuán)結(jié)構(gòu)的重要工具，在本文中采用了常見的幾類聚類算法，并在仿真網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)中從初始敏感度、時(shí)間復(fù)雜度、和準(zhǔn)確率三方面進(jìn)行了實(shí)驗(yàn)對(duì)比，實(shí)驗(yàn)顯示該方法相對(duì)其它復(fù)雜網(wǎng)絡(luò)社團(tuán)劃分算法不僅對(duì)于社團(tuán)結(jié)構(gòu)明顯的網(wǎng)絡(luò)有效，而且在社團(tuán)結(jié)構(gòu)不明顯的