王 艷, 熊淑華, 梁 云
(①四川大學(xué) 電子信息學(xué)院,四川 成都 610064;②西南電子電信技術(shù)研究所,四川 成都 610041)
現(xiàn)實世界中包含著各種類型的復(fù)雜網(wǎng)絡(luò)[1],例如,科技文獻(xiàn)引用關(guān)系網(wǎng)絡(luò)、社會關(guān)系網(wǎng)絡(luò)等。通常人們采用關(guān)系網(wǎng)絡(luò)圖的方式對網(wǎng)絡(luò)中的各種關(guān)系進(jìn)行描述。關(guān)系網(wǎng)絡(luò)圖由一組點(diǎn)和線構(gòu)成,點(diǎn)代表網(wǎng)絡(luò)中存在的各種實體,線則代表實體與實體之間的相互作用、社會關(guān)系等。尋找和發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的組織,有助于更加有效地理解和掌握網(wǎng)絡(luò)的結(jié)構(gòu)和功能[2]。
Girvan和Newman把Freeman[3]提出的點(diǎn)介數(shù)(Vertex Betweenness)由點(diǎn)推廣到了邊,提出了基于邊介數(shù)(Edge Betweenness)的組織發(fā)現(xiàn)算法[4],文中稱之為Betweenness算法。一條邊的邊介數(shù)表示任意兩節(jié)點(diǎn)對之間最短路徑中,有幾條路徑經(jīng)過了該邊。Girvan和Newman發(fā)現(xiàn)組織與組織之間邊的邊介數(shù)遠(yuǎn)遠(yuǎn)高于組織內(nèi)部邊的邊介數(shù),依據(jù)這一點(diǎn),Betweenness算法通過逐步移走邊介數(shù)最大的邊來實現(xiàn)組織發(fā)現(xiàn)。Betweenness算法簡單易懂,但是卻存在兩點(diǎn)不足:①計算速度慢。Girvan和Newman在文獻(xiàn)[5]中指出,最簡情形下Betweenness算法的計算復(fù)雜度為O( m2n),其中m、n分別為網(wǎng)絡(luò)中的邊數(shù)和頂點(diǎn)數(shù);②由于Betweenness算法并不能明確指出組織發(fā)現(xiàn)過程應(yīng)當(dāng)在何時結(jié)束,這就需要事先知道網(wǎng)絡(luò)中的組織總數(shù)。然而,在發(fā)現(xiàn)所有組織之前確定網(wǎng)絡(luò)包含的組織總數(shù)是很難的,這就進(jìn)一步限制了Betweenness算法的適用范圍。
Ulrik Brandes提出了一種Betweenness的快速算法[6],文中稱之為Brandes算法。Brandes算法的基本思想是:任選一個頂點(diǎn)為中心,找到該點(diǎn)到圖中其他頂點(diǎn)的最短路徑,根據(jù)這些最短路徑來計算每條邊的邊介數(shù),然后改變中心點(diǎn),再重復(fù)這個過程,直到每個頂點(diǎn)都被選做中心一次為止,這樣對每條邊的邊介數(shù)都計算了兩次。Brandes的計算復(fù)雜度為O( nm+n2lnn)。
Dennis M. Wilkinson和Bernardo A. Huberman提出了一種組織發(fā)現(xiàn)算法[7],文中稱之為Wilkinson-Huberman算法。Wilkinson-Huberman算法在計算邊介數(shù)時對Brandes算法進(jìn)行了改進(jìn),它不是將每個頂點(diǎn)都作為中心,而是循環(huán)的隨機(jī)選取至少n(n=10lnN-25,其中N為網(wǎng)絡(luò)中的頂點(diǎn)數(shù),對于特別大的N,n取40就足夠了)個點(diǎn)作為中心,計算從這些點(diǎn)出發(fā)的每條邊的邊介數(shù),然后移除邊介數(shù)最大的那條邊,最后將每次循環(huán)產(chǎn)生的組織進(jìn)行整合,得到最終的結(jié)果。Wilkinson-Huberman算法在計算復(fù)雜度上優(yōu)于Brandes算法,但由于只是隨機(jī)選取了n個點(diǎn)作為中心,計算每條邊的邊介數(shù),因此在準(zhǔn)確度上有所損失。
鑒于Betweenness算法和Wilkinson-Huberman算法在復(fù)雜度和準(zhǔn)確度上存在的局限性,文中對Wilkinson-Huberman算法進(jìn)行了優(yōu)化,通過計算互信息[8](MI),對之前形成的組織進(jìn)行擴(kuò)展,最大限度的發(fā)現(xiàn)組織的所有成員,稱這種新的組織發(fā)現(xiàn)算法為 WH-MI算法。該算法計算復(fù)雜度低,無需事先知道網(wǎng)絡(luò)中的組織總數(shù),并且能夠發(fā)現(xiàn)已知組織的隱藏成員和確定未知組織的完整結(jié)構(gòu),因此該算法具有更廣闊的應(yīng)用前景。
首先,把數(shù)據(jù)記錄表示成關(guān)系網(wǎng)絡(luò)圖的形式。
接著,使用Wilkinson-Huberman算法對前面形成的關(guān)系網(wǎng)絡(luò)圖進(jìn)行組織發(fā)現(xiàn)。首先循環(huán)的隨機(jī)選取50個點(diǎn)[7]為中心,計算所有邊的邊介數(shù),然后移去邊介數(shù)最高的邊,將關(guān)系網(wǎng)絡(luò)圖分割成更小的連通子圖,接著反復(fù)進(jìn)行這個過程,直到滿足停止條件為止,這樣將得到多個滿足停止條件的連通子圖。對于這些滿足停止條件的連通子圖稱為群體。所有這些群體的集合稱為一個結(jié)構(gòu)。由于重復(fù)了50次,將得到50個結(jié)構(gòu)。最后整合所有結(jié)構(gòu)中的群體,得到要找的種子組織。
然而實際數(shù)據(jù)中常常有一個實體屬于多個組織的情況,如圖1所示,包含了2個組織[9],左邊的組織包含點(diǎn)A,右邊的組織包含點(diǎn)C。在圖1中的所有連線中,AB和BC都具有很高的邊介數(shù)。如果先移除連線BC,那么AB就會因為具有較低的邊介數(shù)不會被移除,點(diǎn)B就會被劃分到左邊的組織中。而如果先移除連線AB,那么同樣的BC也會因為具有較低的邊介數(shù)不會被移除,點(diǎn)B就會被劃分到右邊的組織中。因此需要找到一種方法解決一個實體屬于多個組織的情況。眾所周知,互信息能夠用于描述兩個隨機(jī)變量之間的相互依賴性,即如果它們彼此獨(dú)立,則它們之間的互信息為0;如果它們互相依賴很緊密,則互信息就會很大。于是,在使用Wilkinson-Huberman算法得到種子組織集合G{G1,G2,…,Gn}之后,對G中的每一個子組織Gi(i=1,2,…,n)和在原始的關(guān)系網(wǎng)絡(luò)圖中與Gi存在聯(lián)系的一級聯(lián)系人建立互信息模型,分別計算這些聯(lián)系人與Gi內(nèi)每個成員的互信息值,當(dāng)所有互信息的平均值超過預(yù)先指定的閾值β時,就將這個點(diǎn)加入到子組織Gi中。通過這個過程,就能夠較好地解決同一實體屬于多個組織的情況。關(guān)于閾值β的選取,通常是針對不同類型的數(shù)據(jù)集,采用實驗法來確定的[8]。
綜上所述,假設(shè)對包含N個頂點(diǎn)的關(guān)系圖進(jìn)行組織發(fā)現(xiàn),WH-MI算法的步驟如下所示:
1)進(jìn)行50次[7]迭代。
2)檢測關(guān)系圖是否包含多個連通子圖。
3)對每個連通子圖,檢查其是否滿足停止條件:
如果連通子圖滿足停止條件,把它從關(guān)系圖中移出。
如果不滿足,則計算連通子圖內(nèi)每條邊的邊介數(shù),然后移去具有最大邊介數(shù)的邊,直到連通子圖被分成兩個更小的連通子圖。
4)重復(fù)步驟3),直到所有的實體從關(guān)系圖中全部移出,這時形成了1個組織集合Si。
5)對步驟1)~4)之后形成的50個組織集合中的組織進(jìn)行重新整合,形成1個組織集合G。
6)通過計算互信息,對G進(jìn)行擴(kuò)充。
從算法的步驟中可以看出,步驟1)~5)是Wilkinson-Huberman算法,WH-MI算法是在Wilkinson-Huberman算法的基礎(chǔ)上,結(jié)合互信息進(jìn)行組織成員的擴(kuò)展。因此,與Wilkinson-Huberman算法相比,WH-MI算法得到的組織成員更為完整。
Wilkinson-Huberman算法的基本原理可以參考相關(guān)文獻(xiàn)[7、9]深入了解。下面將詳細(xì)闡述利用互信息擴(kuò)展隱藏組織成員的過程和原理。
在得到種子組織之后,嘗試通過查找與一個或多個種子成員有著密切聯(lián)系的實體,來確定種子組織的附加成員。為了找到這些與種子組織具有密切聯(lián)系的實體,就需要統(tǒng)計它們與種子組織中的已知成員之間的聯(lián)系程度,這就需要通過建立互信息模型來實現(xiàn)。
以電話通信為例,知道兩個電話號碼之間的通話行為具有不確定性,也就是說可以把兩個電話號碼的一次通話看作一個隨機(jī)事件,顯然該隨機(jī)事件的結(jié)果只有2個,要么是這兩個電話號碼之間有通話,要么是沒有通話。如果用一個兩維隨機(jī)變量(X,Y)的取值來表示該隨機(jī)事件,則該隨機(jī)變量的定義域為{P,φ},其中P代表隨機(jī)變量X與Y有通話行為,φ表示沒有發(fā)生通話行為。因此,兩個電話號碼之間的關(guān)聯(lián)度就可以用其相應(yīng)的隨機(jī)變量的互信息來度量。從信息論的角度來看,一次通話的過程其實也是傳遞信息的過程,通過傳遞信息來消除通話行為的不確定性,因此,兩個隨機(jī)變量的互信息可以解釋為知道一個隨機(jī)變量的取值后對另一個隨機(jī)變量的不確定性的減少量,或者一個隨機(jī)變量包含的另一個隨機(jī)變量的信息量。根據(jù)經(jīng)典的信息論[10],定義兩個隨機(jī)變量X和Y的互信息如下:
式中,P(x)=Prob(X=x),P(y)=Prob(Y=y)。
所以,對種子組織進(jìn)行成員擴(kuò)展的過程如下所示:
1)對于種子組織中的每一個成員,在原始關(guān)系網(wǎng)絡(luò)圖中找到與之有聯(lián)系的實體,并將它們添加到種子組織中,形成一個新的群體。這樣就得到了一個擴(kuò)展的組織。
2)將擴(kuò)展后的組織看作是一個整體,計算所有新增實體與種子組織中各成員之間的互信息值。
3)計算每一個新增實體與種子成員中所有成員互信息值的平均值,當(dāng)這個平均值高于預(yù)先指定的閾值β時,則保留這個實體,否則將實體從擴(kuò)展組織中刪去。
4)對步驟3)得到的擴(kuò)展后的組織,再重復(fù)一次組織擴(kuò)展的過程。
為了便于理解,借助圖2、表1和表2來說明建立互信息模型的過程。假設(shè)得到的實體關(guān)系圖如圖2所示,統(tǒng)計各實體之間發(fā)生的事件如表1所示,計算得到各實體之間的互信息如表2所示。
圖2 實體關(guān)系
表1 各實體之間發(fā)生的事件表
表 2 各實體之間的互信息
現(xiàn)將使用網(wǎng)絡(luò)分析領(lǐng)域中的經(jīng)典數(shù)據(jù)集“空手道俱樂部網(wǎng)絡(luò)(Karate Club Network)數(shù)據(jù)” 和“大學(xué)生足球聯(lián)賽網(wǎng)絡(luò)(College Football Network)數(shù)據(jù)”,對WH-MI算法進(jìn)行可靠性驗證。
空手道俱樂部網(wǎng)絡(luò)數(shù)據(jù)是社會網(wǎng)絡(luò)分析領(lǐng)域中的經(jīng)典數(shù)據(jù)集,由社會學(xué)家 Zachary耗時兩年觀察美國一所大學(xué)中空手道俱樂部 34名成員間的社會關(guān)系而得到的。由于俱樂部的管理者和老師之間就是否提高俱樂部的費(fèi)用發(fā)生了爭論,結(jié)果俱樂部分成了兩個分別以管理者和老師為中心的俱樂部。圖3中,圓形頂點(diǎn)和方形頂點(diǎn)分別代表俱樂部分開后形成的兩個新俱樂部的成員。
圖 3 Karate Club Network數(shù)據(jù)示意
利用 WH-MI算法對空手道俱樂部網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行組織發(fā)現(xiàn),得到兩個組織,兩個組織包含的成員如表3所示。
表 3 Karate Club Network數(shù)據(jù)實驗結(jié)果
將表3與圖4對比后發(fā)現(xiàn),使用WH-MI算法發(fā)現(xiàn)的兩個組織結(jié)構(gòu)完全正確。
大學(xué)生足球聯(lián)賽網(wǎng)絡(luò)數(shù)據(jù)模型是Newman等人對美國大學(xué)生足球聯(lián)賽情況分析整理而建立的一個復(fù)雜網(wǎng)絡(luò)模型。參加足球聯(lián)賽的有若干支球隊,網(wǎng)絡(luò)的每個節(jié)點(diǎn)分別代表一支球隊,2個節(jié)點(diǎn)之間的邊代表2 支球隊之間進(jìn)行過一場比賽。聯(lián)賽中存在若干的聯(lián)盟,每個球隊都屬于其中一個聯(lián)盟。該模型中存在115支球隊(個節(jié)點(diǎn))及616場比賽(條邊),包含了12個聯(lián)盟。
使用WH-MI算法進(jìn)行聯(lián)盟劃分,得到11個組織。組織結(jié)構(gòu)如表4所示。
表4 WH-MI算法劃分結(jié)果
使用Wilkinson-Huberman算法進(jìn)行聯(lián)盟劃分,得到11個組織。組織結(jié)構(gòu)如表5所示。
表5 Wilkinson-Huberman算法劃分結(jié)果
對比表4與實際情況發(fā)現(xiàn),劃分正確的節(jié)點(diǎn)為99個,正確率約為86%。對比表5與實際情況發(fā)現(xiàn),劃分正確的節(jié)點(diǎn)為97個,正確率約為84.3%。由此可見,使用 WH-MI算法進(jìn)行組織發(fā)現(xiàn)的準(zhǔn)確率,比使用Wilkinson-Huberman算法進(jìn)行組織發(fā)現(xiàn)的準(zhǔn)確率高。
文中分析了經(jīng)典的Betweenness算法和Wilkinson-Huberman算法,針對Betweenness算法在組織發(fā)現(xiàn)方面的不足,結(jié)合Wilkinson-Huberman算法以及互信息技術(shù),提出了一種新的組織發(fā)現(xiàn)算法(WH-MI算法)。與目前其他一些劃分算法相比,該方法不必事先知道網(wǎng)絡(luò)中的組織總數(shù);同時,由于使用了互信息技術(shù)對形成的組織成員進(jìn)行擴(kuò)展,得到的組織結(jié)構(gòu)更為完整。最后采用空手道俱樂部網(wǎng)絡(luò)數(shù)據(jù)和大學(xué)生足球聯(lián)賽網(wǎng)絡(luò)數(shù)據(jù)對算法進(jìn)行了實驗驗證,實驗結(jié)果與實際的劃分基本吻合,說明該算法是可行的。
[1] 陳文華,蔡皖東,趙煜.基于數(shù)據(jù)挖掘的匿名通信關(guān)系分析模型研究[J].信息安全與通信保密,2008(06):51-52.
[2] 孫義明,曾繼東.數(shù)據(jù)挖掘技術(shù)及其應(yīng)用[J].信息安全與通信保密,2007(08):80-82.
[3] FREEMAN L C. Centrality in Social Networks:Conceptual Clarification[J].Social Networks,1979(01):215-239.
[4] GIRVAN M, NEWMAN M E J. Community Structure in Social and Biological Networks[J]. PNAS,2002,99(12):7821-7826.
[5] NEWMAN M E J, GIRVAN M. Finding and Evaluating Community Structure in Networks[J]. Physical Review E, 2004, 69(02):26113-26128.
[6] BRANDES U. A Faster Algorithm for Betweenness Centrality[J]. Journal of Mathematical Sociology,2001, 25(02):163-177.
[7] WILKINSON D, HUBERMAN H. A Method for Finding Communities of Related Genes[J]. PNAS,2004(101):5241-5248.
[8] ADIBI J, CHALUPSKY H, MELZ E, et al. The KOJAK Group Finder: Connecting the Dots via Integrated Knowledge-based and Statistical Reasoning[C]// In Proceedings of the Sixteenth Innovative Applications of Artificial Intelligence Conference (IAAI-04).California: San Jose, 2004: 800-807.
[9] TYLER J R, WILKINSON D M, HUBERMAN B A. Email as Spectroscopy: Automated Discovery of Community Structure within Organizations[R]. The Netherlands:Hewlett-Packard Labs, 2003.
[10] SHANNON C.A Mathematical Theory of Communication[J].Bell System Tech,1948(27): 379-423.