李圓媛，余汪建，何敏華

（1.武漢工程大學理學院，湖北 武漢 430074；2.智能機器人湖北省重點實驗室，湖北 武漢 430074）

0 引 言

二十世紀末以來，隨著Internet等信息技術的迅猛發(fā)展，人類社會已經(jīng)進入了網(wǎng)絡時代［1］，人們也把目光聚焦到復雜網(wǎng)絡的研究上來.近些年來，復雜網(wǎng)絡研究滲透到了各個領域，科學的理解復雜網(wǎng)絡的各種定量與定性的特征是網(wǎng)絡時代的一個非常有挑戰(zhàn)性的科學研究課題［2］.

許多真實網(wǎng)絡研究顯示絕大部分的網(wǎng)絡存在一個相同的特征，被稱之為網(wǎng)絡中的社團結構.它是指網(wǎng)絡中的全部節(jié)點可以被劃分成若干個群體，每個群體里面的節(jié)點的連接相對稠密，而群體之間的節(jié)點的連接相對稀疏［3］.對網(wǎng)絡中社團結構的研究是了解整個網(wǎng)絡結構和功能的重要途徑［4］.

1 網(wǎng)絡圖的定義和基本概念

對網(wǎng)絡進行社團分解的操作是基于網(wǎng)絡圖的表示，在介紹復雜網(wǎng)絡的社團分解算法前首先介紹網(wǎng)絡圖的定義和基本概念.網(wǎng)絡圖G可以用集合（V，Ψ）表示，V（G）＝｛1，2，...，N｝表示網(wǎng)絡圖G的節(jié)點集合，N表示網(wǎng)絡圖的節(jié)點總數(shù)，Ψ（G）＝｛（i1，j1），（i2，j2），...，（iE，jE）｝表示邊的集合，用E 表示邊的總數(shù)目，若（i，j）＝（j，i）則該網(wǎng)絡圖被稱為無向網(wǎng)絡圖，反之則被稱為有向網(wǎng)絡圖，在本文中只討論無向無權網(wǎng)絡圖.無向無權網(wǎng)絡圖的鄰接矩陣A（i，j）是一個對稱的0－1矩陣，如果節(jié)點i，j之間有聯(lián)系則ai，j＝1，否則為0.對于一個節(jié)點i的度定義為與節(jié)點i相連接的邊的數(shù)目.

2 社團分解算法綜述

現(xiàn)在對于復雜網(wǎng)絡的社團分解有許多成熟的方法，如基于圖的Laplace矩陣特征向量的譜平分法［5］，GN 算法［3］、NF算法［6］等.一個 有n 個節(jié)點的無向圖G的Laplace矩陣是一個n×n維的對稱矩陣L，理論上已經(jīng)證明，不為零的特征值所對應的特征向量的各元素中，同一個社團內的節(jié)點對應的元素是近似相等的.譜平分法的基本思想就是根據(jù)網(wǎng)絡的Laplace矩陣的第二小的特征值λ2將網(wǎng)絡分成兩個社團.如果網(wǎng)絡實際是由兩個社團構成，用譜平分法效果很好，但是如果由多個以上的社團構成，則體現(xiàn)不出其優(yōu)點.GN算法是Girvan和Newman提出的一種探索網(wǎng)絡社團結構的分裂算法.Girvan和Newman提出用邊介數(shù)來標記每條邊對網(wǎng)絡連通性的影響.GN算法能夠彌補一些傳統(tǒng)算法的缺陷，但是在復雜網(wǎng)絡中社團的數(shù)目未知的情況下，GN算法無法確定這種分解要在哪一步終止.GN算法雖然準確度比較高，但是其算法復雜度比較大，Newman在GN算法的基礎上基于貪婪算法思想提出了一種快速的凝聚算法 （簡稱NF算法），該算法可以用于處理節(jié)點數(shù)達到100萬的大型網(wǎng)絡［7］.

3 集合擴充的社團分解算法

3.1 算法原理

對復雜網(wǎng)絡進行社團分解的本質就是要找出某些節(jié)點聯(lián)系是緊密的，對于每一個點來說，它必可以劃分到一個聯(lián)系最緊密的點集中，在這里需要做的就是判斷每個點是否和某個社團聯(lián)系緊密，如果是，那么該點就可以劃分到這個社團中.

假設有了一個節(jié)點的集合S＝（V，G），V表示該集合中的所有節(jié)點，G表示該集合中節(jié)點間的邊.現(xiàn)在對于一個新的節(jié)點vn，為了判斷vn是否可以加入集合S，先定義一個參數(shù)：PQ＝oe／ie，式中的oe表示一個節(jié)點在S內而另一個節(jié)點不在S中的邊的總數(shù)，ie表示S中的邊的總數(shù).該式的物理意義就是社團同外部聯(lián)系的邊的數(shù)目與社團內部邊的數(shù)目的比值.在此先計算PQ（S），再計算出加入點vn之后的PQ（Sn），如果PQ（Sn）＜ PQ（S），那么就認為vn和集合S＝（V，G）的聯(lián)系是比較緊密的，就把節(jié)點vn加入到集合S＝（V，G）中來.

3.2 算法流程

參照算法原理，給出該算法如下運行流程：

步驟一：在已知的節(jié)點集中選取一個度最大的節(jié)點，找到與該點有關聯(lián)的所有節(jié)點，選取其中一個度最小的點，和第一個節(jié)點構成一個集合.

步驟二：對于步驟一中得到的集合，找到與該集合相關的所有節(jié)點，分別計算這些節(jié)點加入該集合后的PQ值并和之前集合的PQ值進行比較，判斷能否加入該集合，如果可以加入，則加入該集合.

步驟三：重復步驟二，將這個兩點的集合不斷的擴充，直到整個網(wǎng)絡中剩余的點都不符合加入該集合的條件為止，這樣就得到了劃分出來的一個社團.

步驟四：從網(wǎng)絡圖中去掉已經(jīng)找出的社團，重復步驟一、步驟二、步驟三直到網(wǎng)絡中的節(jié)點完全劃分.

3.3 算法分析

這個算法的優(yōu)點是不需要考慮整個網(wǎng)絡的結構，劃分的思維比較清晰，同時可以根據(jù)不同的需求對網(wǎng)絡進行不同的劃分.在某些網(wǎng)絡中，并不需要對整個網(wǎng)絡進行社團結構劃分，只是需要找出其中的部分社團，在這種情況下，運用筆者提出的算法具有運算簡便、運算量小的特點.而GN算法和NF算法在運算的時候都需要考慮整個網(wǎng)絡的拓撲結構，運算量很大.同時本文的算法可以通過調整起始規(guī)則或者起始集合來得到不同的社團結構劃分.同譜平分算法相比，筆者提出的算法可以將整個復雜網(wǎng)絡分成任意個社團結構，而譜平分法僅能將網(wǎng)絡分成兩個社團.

3.4 算法測試

為了測試程序的正確性和算法的可行性，構造了一個社團結構很清晰的網(wǎng)絡圖，如圖1所示.從圖中可以很清楚的看到該網(wǎng)絡可以劃分為四個比較合理的社團.將四個社團以節(jié)點集合的形式表現(xiàn)出來為（11，12，24，27，29，16，28，22），（6，8，18，19），（9，21，17，7，3，23，25），（1，4，15，2，5，30，20，13，14，26，10）.先將該網(wǎng)絡的鄰接矩陣進行存儲，然后應用筆者提出的算法，得到如表1所示的結果.從該表中看到，算法也將網(wǎng)絡分成了四個社團，并且結果與預期的一致，那么說明文中提出的算法在此社團結構比較清晰的網(wǎng)絡中是可以實現(xiàn)的.

圖1 社團結構清晰的網(wǎng)絡圖Fig.1 Aschematic representation of a network with community structure

表1 圖1的測試結果Table 1 The test results of figure 1

為了進一步測試算法的可行性，使用了著名的Wayne Zachary觀察的美國大學空手道俱樂部成員間的人際關系網(wǎng)絡的例子［8］，如圖2所示，該例子具有很強的實際意義，把該例子應用到筆者提出的算法程序測試中來，將該網(wǎng)絡的鄰接矩陣進行運算后得到如表2所示的結果.從表2中看到該算法將網(wǎng)絡分成了兩個社團，第一個社團和圖2中圓形表示的社團基本符合，第二個社團和圖2中方形表示的社團基本符合.除了節(jié)點3的劃分和GN算法的劃分有區(qū)別外，其余的結果和使用GN算法的結果一致.從直觀上來說，也不能確定節(jié)點3到底分在哪一個社團比較合適，這說明筆者提出的算法在結構不是很清晰的實際網(wǎng)絡中進行社團劃分還是具有一定意義的.

圖2 空手道俱樂部網(wǎng)絡圖Fig.2 The friendship network from Zachary＇s karate club

表2 圖2的測試結果Table 2 The test results of figure 2

4 結 語

復雜網(wǎng)絡的社團結構分解是一個富有挑戰(zhàn)性和應用前景性的研究領域.本文提出了通過集合擴充的方式劃分復雜網(wǎng)絡中社團結構的算法.并對提出的算法進行了詳細的介紹，給出了算法的理論基礎和算法流程，并對算法進行了實例測試.從測試結果可以看出，本文提出的基于集合擴充的社團分解算法具有不錯的效率，本文中僅僅討論了復雜網(wǎng)絡社團分解算法在無向無權圖中的運行，而現(xiàn)實生活中很多實際網(wǎng)絡都是有向的有權的.因此如何定義和劃分有向網(wǎng)中的社團結構，有向網(wǎng)中的環(huán)型結構與集團結構的關系，以及如何探索有向網(wǎng)中的層次問題都是一些值得我們關注的問題.

［1］汪小帆，李翔，陳關榮.復雜網(wǎng)絡理論及其應用［M］.北京：清華大學出版社，2006.

［2］Barabasi A L，F(xiàn)rangos J.Linked：The New Science of Networks［M］.Massachusetts：Perseus Books Group，2002.

［3］Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2001，99（12）：7821－7826.

［4］李曉佳，張鵬，狄增如，等.復雜網(wǎng)絡中的社團結構［J］.復雜系統(tǒng)與復雜性科學，2008，5（3）：20－42.LI Xiao－jia，ZHANG Peng，DI Zeng－ru，et al.Community Structure in Complex Networks［J］.Complex Systems and Complexity Science，2008，5（3）：19－42.（in Chinese）

［5］Pothen A，Simon H D，Liou K P.Partitioning sparse matrices with eigenvectors of graphs［J］.SIAM Journal on Matrix Analysis and Applications，1990，11（3）：430－452.

［6］Newman M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69（6）： 066133－ 066137.

［8］Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33（4）：452－473.