復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究.pdf

1、隨著WS小世界網(wǎng)絡(luò)模型和BA無標(biāo)度網(wǎng)絡(luò)模型的提出，國內(nèi)外掀起了研究復(fù)雜網(wǎng)絡(luò)的熱潮。復(fù)雜網(wǎng)絡(luò)的研究以系統(tǒng)的觀點來看待真實系統(tǒng)，如Internet網(wǎng)絡(luò)、電力網(wǎng)、新陳代謝網(wǎng)絡(luò)等。復(fù)雜網(wǎng)絡(luò)通常會呈現(xiàn)出社區(qū)結(jié)構(gòu)特性，如何在實際網(wǎng)絡(luò)中高效地發(fā)現(xiàn)社區(qū)結(jié)構(gòu)是近年來復(fù)雜網(wǎng)絡(luò)的研究熱點之一。本文基于譜算法的思想提出了一種基于共鄰矩陣和增益函數(shù)的有效算法來劃分復(fù)雜網(wǎng)絡(luò)中的社區(qū)，并把此算法推廣到了加權(quán)的復(fù)雜網(wǎng)絡(luò)中。主要工作如下： 1.定義了共鄰矩陣和增

2、益函數(shù)這兩個概念，在此基礎(chǔ)上提出一種有效算法來劃分復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。其中共鄰矩陣中的元素定義為結(jié)點對之間擁有相同鄰居的數(shù)目。以增益函數(shù)作為網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的目標(biāo)函數(shù)，進一步推導(dǎo)出基于增益矩陣和增量矩陣的特征值和特征向量的社區(qū)結(jié)構(gòu)劃分方法。最后把這種算法應(yīng)用于三個常用的實際網(wǎng)絡(luò)數(shù)據(jù)中，并和Newman基于模塊度矩陣的譜算法結(jié)果做了比較，以驗證算法的可行性和有效性。 2.重新定義了在加權(quán)網(wǎng)絡(luò)中結(jié)點對之間擁有共同鄰居的數(shù)目，把基于

3、共鄰矩陣和增益函數(shù)的復(fù)雜網(wǎng)絡(luò)社區(qū)劃分算法推廣到加權(quán)的復(fù)雜網(wǎng)絡(luò)中。在以往許多復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法中，網(wǎng)絡(luò)中的邊常被看作是無權(quán)重的，但是現(xiàn)實世界中存在許多加權(quán)網(wǎng)絡(luò)。如果忽略邊的權(quán)重，僅僅把劃分無權(quán)網(wǎng)絡(luò)社區(qū)的算法應(yīng)用到這些加權(quán)網(wǎng)絡(luò)中，將會忽略許多包含在邊權(quán)重中的重要信息，從而得出不盡合理的結(jié)果。借鑒Newman把加權(quán)網(wǎng)絡(luò)映射到無權(quán)多重圖的思想，重新定義了在加權(quán)網(wǎng)絡(luò)中結(jié)點對之間擁有共同鄰居的數(shù)目，然后將基于共鄰矩陣和增益函數(shù)的算法推廣到加權(quán)