引 言

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

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

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

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

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

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

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

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

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

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

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

2.2.1 局部定義

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

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

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

2.2.2 全局定義

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

2.2.3 模塊度

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

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

2.2.4 歸一化互信息

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

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

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

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

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

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

3 分類聚集

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

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

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

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

圖 1 所示是使用平均連接聚類得到的結(jié)果，它是基于有名的空手道俱樂部網(wǎng)的余弦相似度。這個網(wǎng)絡(luò)模型是觀察了美國一所大學(xué)空手道俱樂部34名成員之間的社會關(guān)系得出的，這個網(wǎng)絡(luò)之所以有趣，是因為在是否提高俱樂部會費上存在爭 議，由于不能達成一致，俱樂部成員分成了兩個派別，一個派系又建立了另外一個俱樂部。據(jù)說，通過了解網(wǎng)絡(luò)中描述的友誼關(guān)系 ( 沒有分裂之前的俱樂部 )，可以對兩個派別的成員作出預(yù)測。

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

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

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

4 優(yōu)化方法

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

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

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

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

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

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

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

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

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

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

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

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

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

并且組成新的社團 G″；

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

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

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

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

首先，在 N 個對象中隨機選取 k 個點并形成 k 個團簇，這 k 個點分別作為所在團簇的初始聚類中心。

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

然后，把相似度比較強的點增加到團簇中，這樣團簇就會越來越大。當(dāng)一定的點都被劃分到這個團簇的時候，團簇的中點會被重新定義。

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

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

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

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

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

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

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

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

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

世界中的真實情況接近。

6 結(jié) 語

隨著新成果的日益出現(xiàn)和研究人員對方法和應(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)域 )。

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

圖 3 聚類計算出的 Silhouette

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