引 言

通俗地講，網(wǎng)絡(luò)就是由線連接的成對(duì)點(diǎn)的集合，在專業(yè)領(lǐng)域中，這些點(diǎn)又被稱為“頂點(diǎn)”或“節(jié)點(diǎn)”，線被稱為“連邊”。網(wǎng)絡(luò)常用于許多學(xué)科的分支中描述復(fù)雜系統(tǒng)中元素的連接方式。這其中也包括 internet 網(wǎng)，其頂點(diǎn)代表分布在各地的計(jì)算機(jī)，邊代表相連的數(shù)據(jù) ；生物學(xué)中的食物鏈網(wǎng)的頂點(diǎn)則代表生態(tài)系統(tǒng)中的物種，邊代表捕食者和被捕食者之間的交互 ；社會(huì)網(wǎng)絡(luò)的頂點(diǎn)代表不同的人，邊代表不同類型的社會(huì)關(guān)系，如朋友關(guān)系、合作關(guān)系、商業(yè)關(guān)系以及其他關(guān)系等。

在過(guò)去的幾十年，人類掀起了網(wǎng)絡(luò)研究的熱潮，其中包括經(jīng)驗(yàn)主義的學(xué)習(xí)，開(kāi)發(fā)數(shù)學(xué)和計(jì)算工具以用來(lái)提出網(wǎng)絡(luò)中的數(shù)據(jù)。研究網(wǎng)絡(luò)的一個(gè)普遍方法是著重分析單個(gè)或某一小組頂點(diǎn)的屬性，在研究過(guò)程中往往會(huì)提出一些“這個(gè)網(wǎng)絡(luò)中最重要的頂點(diǎn)是哪個(gè)？”“哪些是強(qiáng)連接？”等諸如此類的問(wèn)題。然而，這些方法用在大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)分析的時(shí)候，能夠得到的有用信息卻很少，為此，本文對(duì)大規(guī)模網(wǎng)絡(luò)做一些深入的討論。

1 網(wǎng)絡(luò)模塊化和社團(tuán)結(jié)構(gòu)的概念

研究網(wǎng)絡(luò)中的大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)的最好方式是模塊化和社團(tuán)結(jié)構(gòu)。本文中所討論的社團(tuán)結(jié)構(gòu)是指網(wǎng)絡(luò)中的頂點(diǎn)進(jìn)行不同的分組，它們往往具有組內(nèi)頂點(diǎn)連接比較稠密，而組間頂點(diǎn)連接比較稀疏的性質(zhì) [14]。舉例來(lái)說(shuō)，社會(huì)網(wǎng)絡(luò)中的一群密友、萬(wàn)維網(wǎng)中互聯(lián)的網(wǎng)頁(yè)等，都可以看作一個(gè)社團(tuán)。雖然社團(tuán)結(jié)構(gòu)不是研究網(wǎng)絡(luò)結(jié)構(gòu)的唯一方式 ( 其它的方式也可能會(huì)出現(xiàn) )，但是，目前它在此領(lǐng)域中有一個(gè)很好的例證，因?yàn)橥ㄟ^(guò)研究網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，能夠讓人們更加清晰地了解網(wǎng)絡(luò)的結(jié)構(gòu)和功能，所以，人們已開(kāi)始關(guān)注于這方面的研究。

社團(tuán)之所以會(huì)引起人們的興趣，主要可以歸結(jié)為幾個(gè)原因。首先，尋找結(jié)構(gòu)與功能的聯(lián)系已經(jīng)成為網(wǎng)絡(luò)研究領(lǐng)域中的一個(gè)熱點(diǎn)，而社團(tuán)結(jié)構(gòu)在本質(zhì)上對(duì)應(yīng)于網(wǎng)絡(luò)系統(tǒng)中的功能模塊。舉例來(lái)說(shuō)，在新陳代謝網(wǎng)中，如果把生物體內(nèi)的全部有序化學(xué)變化看成一個(gè)網(wǎng)絡(luò)，那么，社團(tuán)就對(duì)應(yīng)于特定的化學(xué)反應(yīng) ( 如將外界引入的營(yíng)養(yǎng)物質(zhì)轉(zhuǎn)變?yōu)樽陨硇枰慕Y(jié)構(gòu)元件。在社會(huì)網(wǎng)絡(luò)中，社團(tuán)與我們傳統(tǒng)觀念中的真實(shí)社團(tuán)意思相近，比如一組有共同愛(ài)好的人、有共同居所、共同工作環(huán)境或一家人都可以看作一個(gè)社團(tuán)。社團(tuán)給人一種“物以類聚，人以群分”的感覺(jué)。

除了上述本質(zhì)原因外，還有一個(gè)容易忽略的原因，那就是人們經(jīng)常會(huì)問(wèn)為什么社團(tuán)結(jié)構(gòu)那么重要呢？在許多網(wǎng)絡(luò)中都發(fā)現(xiàn)了一個(gè)問(wèn)題，那就是社團(tuán)之間的屬性有明顯的不同。同時(shí)，我們也注意到，不同社團(tuán)的結(jié)構(gòu)特征是有變化的。這些屬性對(duì)于了解系統(tǒng)具有重要意義，只有在社團(tuán)結(jié)構(gòu)層次上了解了系統(tǒng)的架構(gòu)，這種意義才會(huì)更明顯。

2 復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)

2.1 社團(tuán)結(jié)構(gòu)和分析算法

近年來(lái)，隨著研究人員對(duì)復(fù)雜網(wǎng)絡(luò)研究的越來(lái)越多，人們發(fā)現(xiàn)了一個(gè)網(wǎng)絡(luò)的共同結(jié)構(gòu)，也就是社團(tuán)結(jié)構(gòu)。目前人們所說(shuō)的社團(tuán)結(jié)構(gòu)，還沒(méi)有形成統(tǒng)一的概念，往往會(huì)被認(rèn)為網(wǎng)絡(luò)的頂點(diǎn)可以分組，而組內(nèi)頂點(diǎn)連接比較稠密，組間頂點(diǎn)連接比較稀疏。事實(shí)上，研究人員為了搞清網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的特性，對(duì)尋找網(wǎng)絡(luò)中社團(tuán)結(jié)構(gòu)的多種方法進(jìn)行了實(shí)驗(yàn)和研究，以期找到有效的算法，盡量用比較少的信息去尋找盡量準(zhǔn)確的社團(tuán)結(jié)構(gòu)。到目前為止，研究人員已經(jīng)提出了若干社團(tuán)發(fā)現(xiàn)算法，包括譜分析算法、最優(yōu)目標(biāo)函數(shù)算法、基于連邊密度、介數(shù)、信息中心度、隨機(jī)行走等，計(jì)算機(jī)領(lǐng)域中的圖分割 (GraphPartitioning) 算法、社會(huì)科學(xué)中的層次聚類算法 (HierarchicalClustering 算法 )、W-H 算法和 GN 算法是最有代表性的方法。

但是在社團(tuán)檢測(cè)中，人們一般會(huì)遇到兩個(gè)難題 ：一是不知道一個(gè)網(wǎng)絡(luò)到底含有多少個(gè)社團(tuán) ；二是網(wǎng)絡(luò)中的頂點(diǎn)可能屬于不同的社團(tuán)，即網(wǎng)絡(luò)中存在重疊節(jié)點(diǎn)，這些節(jié)點(diǎn)也稱為“騎墻”節(jié)點(diǎn)。重疊社團(tuán)的檢測(cè)對(duì)現(xiàn)實(shí)生活中的網(wǎng)絡(luò)比較有效，所以，本文重點(diǎn)討論重疊社團(tuán)檢測(cè)算法。

2.2 社團(tuán)結(jié)構(gòu)的定義形式

2.2.1 局部定義

社團(tuán)是網(wǎng)絡(luò)的一部分，它與網(wǎng)絡(luò)的其它部分有少許的連接。在某種程度上，它們可以看作一個(gè)獨(dú)立實(shí)體。所以，通常會(huì)單獨(dú)評(píng)估一個(gè)社團(tuán)。局部定義關(guān)注于子圖的研究，包括它可能的鄰近節(jié)點(diǎn)，但會(huì)忽略網(wǎng)絡(luò)的其它部分。這里以在社會(huì)網(wǎng)絡(luò)分析中常用的定義來(lái)分析，在局部社團(tuán)中，主要有 4種相關(guān)的標(biāo)準(zhǔn) [21]，全連、可達(dá)性、頂點(diǎn)度、內(nèi)部和外部結(jié)合比較。所對(duì)應(yīng)的社團(tuán)往往是最大子圖，最大子圖不能再增加新的頂點(diǎn)或邊。社團(tuán)可以定義成其子圖的成員，彼此之間都是“朋友”( 也就是說(shuō)成員之間完全互聯(lián) )。在網(wǎng)絡(luò)術(shù)語(yǔ)中，稱它們?yōu)榕上?，也就是由彼此相連的頂點(diǎn)組成的子集。在社會(huì)網(wǎng)絡(luò)分析中，一個(gè)派系就是一個(gè)最大子圖。三角形是最常見(jiàn)的派系，同時(shí)也是真實(shí)網(wǎng)絡(luò)中最常見(jiàn)的。在許多實(shí)際的應(yīng)用中，人們期望社團(tuán)的頂點(diǎn)有明顯的分級(jí)，在一個(gè)中心點(diǎn)周圍環(huán)繞著其它的頂點(diǎn)。但是，人們也注意到，一個(gè)頂點(diǎn)可能同時(shí)屬于不同的派系，這也是 Palla 等人提出派系過(guò)濾算法的基礎(chǔ)。比較子圖內(nèi)部和外部的凝聚情況很重要，這也是最近社團(tuán)定義所做的一項(xiàng)工作，我們比較常見(jiàn)的是有關(guān)強(qiáng)社團(tuán)和弱社團(tuán)的定義。

所謂的強(qiáng)社團(tuán)，是指社團(tuán)任何一個(gè)頂點(diǎn)在社團(tuán)內(nèi)的度大于該頂點(diǎn)與其它社團(tuán)內(nèi)頂點(diǎn)相連的邊的數(shù)量，可用公式表述如下：

而所謂的弱社團(tuán)，是指社團(tuán)內(nèi)所有頂點(diǎn)在社團(tuán)內(nèi)的度之和大于該社團(tuán)內(nèi)的頂點(diǎn)與其它社團(tuán)內(nèi)頂點(diǎn)相連的邊的數(shù)量，用公式描述為 ：

2.2.2 全局定義

許多算法要求對(duì)網(wǎng)絡(luò)的整體結(jié)構(gòu)有個(gè)了解，社團(tuán)也可以以網(wǎng)絡(luò)的整體去定義，這是因?yàn)樵谶@種情況下，團(tuán)簇作為網(wǎng)絡(luò)的基本組成部分，在不嚴(yán)重影響系統(tǒng)功能的情況下，是不能被剖析的。過(guò)去的研究工作給我們提供了許多確定社團(tuán)的全局標(biāo)準(zhǔn)，它們往往不是直接定義的。通常一些全局屬性都是在算法中體現(xiàn)出來(lái)的。這一系列的定義都是基于一個(gè)網(wǎng)絡(luò)不同于隨機(jī)網(wǎng)絡(luò)那么有社團(tuán)結(jié)構(gòu)。隨機(jī)網(wǎng)絡(luò)通常被認(rèn)為沒(méi)有社團(tuán)結(jié)構(gòu)，因?yàn)槿魏蝺蓚€(gè)頂點(diǎn)都具有相同的毗鄰可能性，所以它不會(huì)有一組優(yōu)先連接的特別頂點(diǎn)。因此，人們可以做出一個(gè)“空模型”。所謂的空模型是指它能具有一些所給網(wǎng)絡(luò)的結(jié)構(gòu)特征，但其本身還是一個(gè)隨機(jī)網(wǎng)絡(luò)。最流行的空模型是由 Newman 和Girvan 提出的，它是由原始網(wǎng)絡(luò)的隨機(jī)版本組成的，是在人們期望的頂點(diǎn)的度與原始網(wǎng)絡(luò)中頂點(diǎn)的度保持一致的約束條件下，讓其邊隨機(jī)連接得到的。這也是后來(lái)的模塊度概念的基礎(chǔ)，事實(shí)上，模塊度是社團(tuán)結(jié)構(gòu)的一個(gè)重要的檢驗(yàn)標(biāo)準(zhǔn)。

2.2.3 模塊度

網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部頂點(diǎn)間的邊的比例與擁有相同社團(tuán)結(jié)構(gòu)但頂點(diǎn)間隨機(jī)連接的網(wǎng)絡(luò)中連接社團(tuán)內(nèi)部頂點(diǎn)間的邊的比例的期望值的差值為 :

其中，Aij 代表連接矩陣中的元素 ；ki 表示頂點(diǎn) i 的度 ；ci 是頂點(diǎn) i 分配的社團(tuán)；函數(shù) δ(i, j) 的定義為當(dāng) i=j 時(shí)其值為 1，否則為 0；

2.2.4 歸一化互信息

歸一化互信息 (normalized mutual information，NMI) 是Lancichinetti 等人在 2009 年提出的，歸一化互信息應(yīng)用在重疊社團(tuán)檢測(cè)上面。對(duì)于圖 C' 中的每個(gè)頂點(diǎn) i，其社團(tuán)隸屬度可以描述成一個(gè)長(zhǎng)度為 |C'| 的二元向量 (|C'| 為 C' 中團(tuán)簇的數(shù)量 )。如果頂點(diǎn) i 屬于第 k 個(gè)團(tuán)簇Clk，那么 (xi)k=1，否則為 0。第 k 個(gè)向量可以看做隨機(jī)變量 Xk，其概率分布為 P(Xk=1)=nk/n，其中nk=| Clk | 為團(tuán)簇Clk頂點(diǎn)的個(gè)數(shù)，n 是總的頂點(diǎn)數(shù)量。同理，也可以求出圖 C″中第 l 個(gè)團(tuán)簇的隨機(jī)變量 Yl，那么，P(Xk,Yl)的聯(lián)合概率密度就可定義為 ：

其 中，Xk 是 給 定 Yl 的 情 況 下 的 條 件 熵， 可 以 定 義 為H(Xk|Yl )=H(Xk,Yl )-H(Yl)。Xk 相對(duì)于整個(gè)向量 Y 的熵是基于 Xk與 Y 中團(tuán)簇的最佳匹配，故可表示為 ：

X 相對(duì)于 Y 的歸一條件熵可以表示為 ：

同理，也可以得到 H(Y|X)。最后得到的兩個(gè)圖 C′ 和 C″的歸一化互信息為 :

NMI(X|Y)=1-[H(X|Y)+H(Y|X)]/2           (10)

一般情況下，擴(kuò)展歸一化互信息的值在 0~1 之間，等于 1時(shí)相當(dāng)于最佳匹配。

3 分類聚集

對(duì)網(wǎng)絡(luò)社團(tuán)的研究可以追溯到上世紀(jì) 70 年代，那時(shí)就提出了一些檢測(cè)社團(tuán)的方法，特別是在計(jì)算機(jī)科學(xué)和社會(huì)學(xué)領(lǐng)域。計(jì)算機(jī)科學(xué)中的圖分割問(wèn)題，與社團(tuán)檢測(cè)相似，但又不完全相同，其工程上的應(yīng)用受到了關(guān)注，與此同時(shí)，一些成熟的算法 ( 比如譜分割和 Kernigh-Lin 算法 ) 在其它領(lǐng)域的應(yīng)用也取得了豐碩成果。然而，也許社會(huì)學(xué)家才是真正社團(tuán)檢測(cè)技術(shù)的始祖。

在社會(huì)網(wǎng)絡(luò)中，早期出現(xiàn)并且目前還在廣泛使用的探測(cè)社團(tuán)結(jié)構(gòu)的技術(shù)是分級(jí)聚類。事實(shí)上，分級(jí)聚類不是單一的技術(shù)，而是一類技術(shù)。它有一個(gè)中心思想 ：如果能導(dǎo)出網(wǎng)絡(luò)中頂點(diǎn)的連接強(qiáng)度，然后把連接最強(qiáng)的進(jìn)行分組，那么就可以把網(wǎng)絡(luò)分成不同的社團(tuán)。特定的分級(jí)聚類方法與使用的特定測(cè)量強(qiáng)度有關(guān)，這也是根據(jù)這些測(cè)試強(qiáng)度把頂點(diǎn)分成組的。最常見(jiàn)的測(cè)量是所謂的結(jié)構(gòu)等價(jià)測(cè)量，這種測(cè)量關(guān)注于網(wǎng)絡(luò)中兩個(gè)頂點(diǎn) i，j 共有的臨近頂點(diǎn)的數(shù)量 nij。以社會(huì)網(wǎng)中的朋友關(guān)系舉例來(lái)說(shuō)，擁有許多共同朋友的兩個(gè)人，往往比很少有共同朋友的兩個(gè)人關(guān)系密切。此時(shí)共同朋友的數(shù)量就可以用作連接強(qiáng)度的測(cè)量。然而，為了不是僅僅使用生疏的 nij，提出了測(cè)量的標(biāo)準(zhǔn)形式，例如 jaccard 系數(shù)和余弦相似度。本文將頂點(diǎn) i 與 j之間的頂點(diǎn)相似度定義為 ：

其中，ki 是頂點(diǎn) i 的度 ( 也就是說(shuō)它具有連接的數(shù)量 )，這種測(cè)量具有良好的屬性，其值一般在 0 和 1 之間，0 的時(shí)候代表它們沒(méi)有公共臨近點(diǎn)，1 代表它們具有所有的臨近頂點(diǎn)。

一旦定義了連接強(qiáng)度的測(cè)量值，那么就可以給頂點(diǎn)分組，并以分級(jí)的形式完成。首先把孤立的節(jié)點(diǎn)分成小的組，然后把這些小的組再分成較大的組，可以通過(guò)不同的方法讓這些分組得以實(shí)現(xiàn)。常見(jiàn)的分組方式有單連接法、全連接法、平均連接法三種。目前，單連接聚類是使用最廣的，因?yàn)樗鼞?yīng)用比較簡(jiǎn)單，但是事實(shí)上，平均連接聚類算法通常能得出更好的結(jié)果，而且使用也挺方便。

圖 1 所示是使用平均連接聚類得到的結(jié)果，它是基于有名的空手道俱樂(lè)部網(wǎng)的余弦相似度。這個(gè)網(wǎng)絡(luò)模型是觀察了美國(guó)一所大學(xué)空手道俱樂(lè)部34名成員之間的社會(huì)關(guān)系得出的，這個(gè)網(wǎng)絡(luò)之所以有趣，是因?yàn)樵谑欠裉岣呔銟?lè)部會(huì)費(fèi)上存在爭(zhēng) 議，由于不能達(dá)成一致，俱樂(lè)部成員分成了兩個(gè)派別，一個(gè)派系又建立了另外一個(gè)俱樂(lè)部。據(jù)說(shuō)，通過(guò)了解網(wǎng)絡(luò)中描述的友誼關(guān)系 ( 沒(méi)有分裂之前的俱樂(lè)部 )，可以對(duì)兩個(gè)派別的成員作出預(yù)測(cè)。

圖1 小規(guī)模社會(huì)網(wǎng)絡(luò)的平均聚類

圖 1 以樹(shù)狀圖的形式表示了分類聚集的輸入結(jié)果，其代表了頂點(diǎn)分組成社團(tuán)時(shí)的順序，一般需從下往上讀取。在底部有孤立的節(jié)點(diǎn)，它們被分組成對(duì)，我們沿著樹(shù)狀圖往上移動(dòng)，將被分成更大點(diǎn)的組，當(dāng)?shù)竭_(dá)最頂端，所有的頂點(diǎn)被分到一個(gè)組里面。在單幅圖中，樹(shù)狀結(jié)構(gòu)捕獲了分類聚集的整個(gè)過(guò)程。在圖中做一個(gè)水平切割，則可代表中間階段的分組。

猶如我們看到的一樣，本方法把頂點(diǎn)分到兩個(gè)較大的組，每個(gè)組包含的頂點(diǎn)約占整個(gè)網(wǎng)絡(luò)的一半，最后這兩個(gè)組在樹(shù)狀結(jié)構(gòu)的頂端合并成一個(gè)組。事實(shí)證明，算法劃分成的兩個(gè)組與實(shí)際的俱樂(lè)部分裂成的恰恰一致，圖中用不同的顏色標(biāo)出。因此，本例中這個(gè)方法非常有效。它有效地預(yù)測(cè)了社會(huì)未來(lái)的現(xiàn)象，通過(guò)定量數(shù)據(jù)的測(cè)量，推斷了俱樂(lè)部的分割現(xiàn)象。分級(jí)聚類方法簡(jiǎn)單明了，易于使用，但是它不一定都能獲得滿意的結(jié)果。因?yàn)樗泻芏嘧兞?( 不同的測(cè)量長(zhǎng)度和不同的連接規(guī)則 )，而且不同的變量會(huì)導(dǎo)致不同的結(jié)果，又不清楚哪個(gè)結(jié)果是最“恰當(dāng)”的結(jié)果。本方法有聚集較強(qiáng)連接的頂點(diǎn)，但有遺漏較弱連接頂點(diǎn)的趨勢(shì)。所以，其產(chǎn)生的分類不一定是完整的分類，而是幾個(gè)稠密中心加上環(huán)繞其外圍的孤立頂點(diǎn)。理想中，我們希望出現(xiàn)一個(gè)更可靠的方法。

4 優(yōu)化方法

大約 10 年前，物理學(xué)和應(yīng)用數(shù)學(xué)界的學(xué)者們對(duì)社團(tuán)檢測(cè)問(wèn)題產(chǎn)生了極高的熱情，并且提出了若干富有成效的方法。在第一次提議中，有些方法是基于對(duì)介數(shù)的測(cè)量。這些方法之一是計(jì)算通過(guò)網(wǎng)絡(luò)邊中的交通流得到的測(cè)量值，然后把那些交通量大的邊移除。另外兩種相關(guān)的方法是使用液體流算法和電流算法。另一大類方法是利用社團(tuán)結(jié)構(gòu)之間的連接以及網(wǎng)絡(luò)的進(jìn)程，如隨機(jī)行走、Potts 模型等。另外，能形成鮮明對(duì)比的方法集則關(guān)注于局部社團(tuán)的探測(cè)，其力圖解決在沒(méi)有發(fā)現(xiàn)網(wǎng)絡(luò)中全部社團(tuán)的情況下，對(duì)于給定的孤立點(diǎn)，如何確定它屬于哪個(gè)社團(tuán)的問(wèn)題。優(yōu)化算法中最常用的方式是基于模塊度的優(yōu)化。

圖 2 所示是科學(xué)家合作網(wǎng)的模式圖，也是使用模塊度最大化的一個(gè)例子。模塊度方法的優(yōu)點(diǎn)之一是不需要事先知道網(wǎng)絡(luò)中含有幾個(gè)社團(tuán)，而且自由的模塊度可最大化，其社團(tuán)的數(shù)量可以改變，并會(huì)告訴最優(yōu)越的數(shù)量，并且能找到社團(tuán)之間頂點(diǎn)的精確劃分。

圖 2 科學(xué)家合作網(wǎng)

基于適應(yīng)度函數(shù)的局部?jī)?yōu)化算法應(yīng)用越來(lái)越廣，這里也對(duì)其進(jìn)行詳細(xì)介紹。本算法是為了解決分級(jí)重疊社團(tuán)而提出的，算法運(yùn)用了基于適應(yīng)度函數(shù)的局部?jī)?yōu)化方法，社團(tuán)結(jié)構(gòu)由適應(yīng)度直方圖的頂點(diǎn)構(gòu)成，社團(tuán)的不同等級(jí)可以通過(guò)參數(shù)的調(diào)整來(lái)實(shí)現(xiàn)。實(shí)驗(yàn)證明，該算法在人工和現(xiàn)實(shí)網(wǎng)絡(luò)中都取得了較好的效果。

在微觀模塊層次的網(wǎng)絡(luò)架構(gòu)一般非平凡，這一事實(shí)阻礙了解決方案。原因至少有二 ：一是整體等級(jí)模塊，因?yàn)樯鐖F(tuán)是鑲套的，小社團(tuán)組建成大社團(tuán)，大社團(tuán)再依次組建更大社團(tuán)等。比如，一個(gè)大的公司組織，甚至復(fù)雜的生命也可以用網(wǎng)絡(luò)等級(jí)描圖出來(lái)。二是組織的等級(jí)形式有限，每個(gè)模塊負(fù)責(zé)系統(tǒng)里不同的功能。社團(tuán)結(jié)構(gòu)的概念因?yàn)榈燃?jí)而變得更為豐富，它需要一種方法可以探測(cè)出所有組合等級(jí)，而不是單個(gè)。分類聚集是社會(huì)網(wǎng)絡(luò)分析、生物和金融中一種眾所周知的技術(shù)，從單個(gè)節(jié)點(diǎn)作為一個(gè)社團(tuán)或所有的節(jié)點(diǎn)作為一個(gè)社團(tuán)開(kāi)始，根據(jù)頂點(diǎn)間相似度的拓?fù)浞椒?，合并或者分裂一個(gè)團(tuán)簇。這樣，建立起等級(jí)樹(shù)狀結(jié)構(gòu)，也叫做生物樹(shù)圖。通過(guò)這種方法，盡管能夠產(chǎn)生一個(gè)分級(jí)分割，但對(duì)分割的質(zhì)量無(wú)從判斷。Newman 和 Girvan 兩人提出了衡量分割好壞的算法，但是它只對(duì)單個(gè)分割有效。

本算法的假定條件是社團(tuán)本來(lái)是局部結(jié)構(gòu)，最多讓模塊中頂點(diǎn)鄰近的點(diǎn)添加進(jìn)來(lái)，這對(duì)大規(guī)模網(wǎng)絡(luò)來(lái)說(shuō)是合理的，那里的頂點(diǎn)與其對(duì)等點(diǎn)相關(guān)性不大。例如在萬(wàn)維網(wǎng)中，一個(gè)頂點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的影響不大，局部的網(wǎng)絡(luò)只能傳送局部的信息。與此類似，社會(huì)團(tuán)體往往是一個(gè)小的區(qū)域生活的人們。

這里的社團(tuán)是通過(guò)子圖頂點(diǎn)的屬性或適應(yīng)度最大化形成的，本算法比較了幾種適應(yīng)度的方法，最后給出了比較優(yōu)化的簡(jiǎn)單表達(dá)式 ：

這里的kinG和kou分別代表模塊 G 中頂點(diǎn)的入度和出度 ；α 是一個(gè)正實(shí)數(shù)類型的參數(shù)，它用來(lái)控制社團(tuán)的規(guī)模。入度在數(shù)值上等于模塊內(nèi)部連接數(shù)量的兩倍，出度等于模塊內(nèi)成員與其它頂點(diǎn)連接的數(shù)量。本算法想從節(jié)點(diǎn) A 開(kāi)始確定一個(gè)子圖，通過(guò)添加或刪除子圖中的一個(gè)節(jié)點(diǎn)達(dá)到減弱適應(yīng)度函數(shù) fG 的目的。我們稱子圖為節(jié)點(diǎn) A 的自然社團(tuán)，這就相當(dāng)于給定一個(gè)參數(shù) α 后，去尋找適應(yīng)度函數(shù)的最大值。事實(shí)上，每個(gè)節(jié)點(diǎn)的最大值相當(dāng)于整個(gè)網(wǎng)絡(luò)，因?yàn)樵诮o定參數(shù) α 后，當(dāng)koutG為零時(shí)，fG 會(huì)取得最大值。

當(dāng)給定一個(gè)適應(yīng)度函數(shù) fG 后，節(jié)點(diǎn) A 關(guān)于子圖 G 的適應(yīng)度函數(shù) fGK 可由子圖 G 在有節(jié)點(diǎn) A 時(shí)的適應(yīng)度減去子圖 G在沒(méi)有節(jié)點(diǎn) A 時(shí)的適應(yīng)度得出。其函數(shù)如下：

式中，G+{A}(G-{A}) 表示模塊 G 在包含節(jié)點(diǎn) A( 和不包含節(jié)點(diǎn)A) 的情況下獲得的子圖。

節(jié)點(diǎn) A 的自然社團(tuán)可以由下面的過(guò)程得出，設(shè)想有包括節(jié)點(diǎn) A 的子圖 G，最初 G 被視為節(jié)點(diǎn) A，那么，算法的重疊部分包括下面的步驟 ：

(1) 找出 G 周圍相鄰但是不屬于社團(tuán) G 內(nèi)的點(diǎn) ；(2) 將相鄰點(diǎn)中擁有最大適應(yīng)度的點(diǎn)添加到 G 中，并組成一個(gè)新的社團(tuán) G' ；

(3) 重新計(jì)算 G' 中每個(gè)頂點(diǎn)的適應(yīng)度 ；(4) 如果一個(gè)頂點(diǎn)的適應(yīng)度為負(fù)數(shù)，那么將它從G' 中刪除，

并且組成新的社團(tuán) G″；

(5) 如果步驟 (4) 出現(xiàn)，那么回到步驟 (3)，其它情況下返回到步驟 (1)。

當(dāng)步驟 (1) 中計(jì)算出來(lái)的適應(yīng)度都為負(fù)數(shù)時(shí)，整個(gè)過(guò)程結(jié)束。這個(gè)過(guò)程相當(dāng)于自適應(yīng)函數(shù)的貪婪優(yōu)化過(guò)程，因?yàn)槊恳徊降母淖?，函?shù)值看起來(lái)都會(huì)有較大的增長(zhǎng)，別的方法也許能實(shí)現(xiàn)一樣的功能。例如，除非團(tuán)簇停止增長(zhǎng)，否則我們會(huì)舍棄那些適應(yīng)度為負(fù)數(shù)的節(jié)點(diǎn)，或者把那些能增加適應(yīng)度的臨近節(jié)點(diǎn)添加進(jìn)去。這種做法往往能在短時(shí)間內(nèi)獲得較大的適應(yīng)度。

5 k-means 算法的最佳聚類數(shù)確定

k-means 算法的基本流程由 S?nmez 在 2009 年提出。其算法描述如下：

首先，在 N 個(gè)對(duì)象中隨機(jī)選取 k 個(gè)點(diǎn)并形成 k 個(gè)團(tuán)簇，這 k 個(gè)點(diǎn)分別作為所在團(tuán)簇的初始聚類中心。

其次，將余下的點(diǎn) (N-K 中的點(diǎn) ) 與其他團(tuán)簇的中心的相似度進(jìn)行比較，并得出相似度。

然后，把相似度比較強(qiáng)的點(diǎn)增加到團(tuán)簇中，這樣團(tuán)簇就會(huì)越來(lái)越大。當(dāng)一定的點(diǎn)都被劃分到這個(gè)團(tuán)簇的時(shí)候，團(tuán)簇的中點(diǎn)會(huì)被重新定義。

接下來(lái)，再不斷重復(fù)后面兩個(gè)步驟，直到劃分成一個(gè)完整的 K 派系團(tuán)簇。

團(tuán)簇種子是隨機(jī)分配的，被認(rèn)為是本算法的缺點(diǎn)，由于這種原因，可能不能獲得最佳的劃分。為了解決這個(gè)問(wèn)題，k-means 算法中允許點(diǎn)在團(tuán)簇內(nèi)移動(dòng)，因此，團(tuán)簇內(nèi)的相似度會(huì)隨著其它團(tuán)簇的增大而增大。另一方面，事物的轉(zhuǎn)移會(huì)有利于社團(tuán)的劃分，但它并不能保證 100% 的成功，一種有效的檢驗(yàn)團(tuán)簇劃分的方法是評(píng)估每個(gè)事物的輪廓值，也就是我們所說(shuō)的 Silhouette 指標(biāo)。輪廓值定義如下：

式中，a(i) 是第 i 個(gè)事物與同團(tuán)簇內(nèi)其它成員的平均相似度，b(i, k) 代表第 i 個(gè)事物與第 k 個(gè)團(tuán)簇內(nèi)成員之間的平均相似度。輪廓值 s(i) 的取值范圍在 -1~+1 之間，+1 說(shuō)明第 i 個(gè)物體被放在了很正確的團(tuán)簇中，與其它團(tuán)簇中不相似的事物之間的分割也比較好，0 表示第 i 個(gè)事物沒(méi)有明顯地劃分到任何一個(gè)團(tuán)簇中，-1 代表第 i 個(gè)事物劃分到錯(cuò)誤的團(tuán)簇中?？傊骄膕(i) 為具有 N 個(gè)物體的 k 派系劃分的評(píng)估提供了一個(gè)粗略的方法。s(i) 系數(shù)的值越大，說(shuō)明劃分越好。

本文通過(guò) perason 相關(guān)系數(shù)分析了 273 種股票之間的相似度，并用 k-means 算法對(duì)其進(jìn)行了分析。在確定最佳聚類時(shí)，其做法如下：

第一，選取聚類中心的探索范圍，這里設(shè)定為[ 2, n],由于股票數(shù)為 273，所以其范圍可以設(shè)為 [2,16] ；

第二，分別取 k 值在 [2,16] 之間的一個(gè)數(shù)作為聚類中心的個(gè)數(shù)，并轉(zhuǎn)向 k-means 算法進(jìn)行聚類 ；

第三，分別計(jì)算聚類中心為 k 時(shí)的聚類結(jié)果所對(duì)應(yīng)的Silhouette 值 ；

第四，比較 k 在 [2,16] 之間分別得到的 Silhouette 值，其中最大的就是我們所要求的最佳聚類數(shù)。

至此，便可用實(shí)驗(yàn)得出如圖 3 所示的數(shù)。本設(shè)計(jì)最后選取 k 為 11 進(jìn)行聚類，其得出的結(jié)果和現(xiàn)實(shí)

世界中的真實(shí)情況接近。

6 結(jié) 語(yǔ)

隨著新成果的日益出現(xiàn)和研究人員對(duì)方法和應(yīng)用上的熱情，網(wǎng)絡(luò)結(jié)構(gòu)的研究以及它與復(fù)雜系統(tǒng)功能和行為的聯(lián)系，已經(jīng)成為熱門領(lǐng)域。本文討論了已提出并已經(jīng)得到較好應(yīng)用的一些方法 ( 如塊結(jié)構(gòu)模型方法，現(xiàn)在正是研究的熱門領(lǐng)域 )。

許多其它的算法由于篇幅的問(wèn)題，本文沒(méi)有一一講解。開(kāi)發(fā)的步伐也在加速，本領(lǐng)域?yàn)槲锢?、生物、社?huì)科學(xué)以及其它學(xué)科的研究提供了一些有用的資料，如果有人有能力搞清社團(tuán)的大小結(jié)構(gòu)，那么就相當(dāng)于他為了解復(fù)雜系統(tǒng)開(kāi)辟了一個(gè)窗口。

圖 3 聚類計(jì)算出的 Silhouette

20210915_6141ea329c7b5__復(fù)雜網(wǎng)絡(luò)中的鄰域重疊社團(tuán)結(jié)構(gòu)探測(cè)