一種改進的組織發(fā)現算法研究

王 艷， 熊淑華， 梁 云

（①四川大學 電子信息學院，四川 成都 610064；②西南電子電信技術研究所，四川 成都 610041）

0 引言

現實世界中包含著各種類型的復雜網絡[1]，例如，科技文獻引用關系網絡、社會關系網絡等。通常人們采用關系網絡圖的方式對網絡中的各種關系進行描述。關系網絡圖由一組點和線構成，點代表網絡中存在的各種實體，線則代表實體與實體之間的相互作用、社會關系等。尋找和發(fā)現復雜網絡中的組織，有助于更加有效地理解和掌握網絡的結構和功能[2]。

Girvan和Newman把Freeman[3]提出的點介數（Vertex Betweenness）由點推廣到了邊，提出了基于邊介數（Edge Betweenness）的組織發(fā)現算法[4]，文中稱之為Betweenness算法。一條邊的邊介數表示任意兩節(jié)點對之間最短路徑中，有幾條路徑經過了該邊。Girvan和Newman發(fā)現組織與組織之間邊的邊介數遠遠高于組織內部邊的邊介數，依據這一點，Betweenness算法通過逐步移走邊介數最大的邊來實現組織發(fā)現。Betweenness算法簡單易懂，但是卻存在兩點不足：①計算速度慢。Girvan和Newman在文獻[5]中指出，最簡情形下Betweenness算法的計算復雜度為O( m2n)，其中m、n分別為網絡中的邊數和頂點數；②由于Betweenness算法并不能明確指出組織發(fā)現過程應當在何時結束，這就需要事先知道網絡中的組織總數。然而，在發(fā)現所有組織之前確定網絡包含的組織總數是很難的，這就進一步限制了Betweenness算法的適用范圍。

Ulrik Brandes提出了一種Betweenness的快速算法[6]，文中稱之為Brandes算法。Brandes算法的基本思想是：任選一個頂點為中心，找到該點到圖中其他頂點的最短路徑，根據這些最短路徑來計算每條邊的邊介數，然后改變中心點，再重復這個過程，直到每個頂點都被選做中心一次為止，這樣對每條邊的邊介數都計算了兩次。Brandes的計算復雜度為O( nm+n2lnn)。

Dennis M. Wilkinson和Bernardo A. Huberman提出了一種組織發(fā)現算法[7]，文中稱之為Wilkinson-Huberman算法。Wilkinson-Huberman算法在計算邊介數時對Brandes算法進行了改進，它不是將每個頂點都作為中心，而是循環(huán)的隨機選取至少n（n=10lnN-25，其中N為網絡中的頂點數，對于特別大的N，n取40就足夠了）個點作為中心，計算從這些點出發(fā)的每條邊的邊介數，然后移除邊介數最大的那條邊，最后將每次循環(huán)產生的組織進行整合，得到最終的結果。Wilkinson-Huberman算法在計算復雜度上優(yōu)于Brandes算法，但由于只是隨機選取了n個點作為中心，計算每條邊的邊介數，因此在準確度上有所損失。

鑒于Betweenness算法和Wilkinson-Huberman算法在復雜度和準確度上存在的局限性，文中對Wilkinson-Huberman算法進行了優(yōu)化，通過計算互信息[8]（MI），對之前形成的組織進行擴展，最大限度的發(fā)現組織的所有成員，稱這種新的組織發(fā)現算法為 WH-MI算法。該算法計算復雜度低，無需事先知道網絡中的組織總數，并且能夠發(fā)現已知組織的隱藏成員和確定未知組織的完整結構，因此該算法具有更廣闊的應用前景。

1 算法原理

首先，把數據記錄表示成關系網絡圖的形式。

接著，使用Wilkinson-Huberman算法對前面形成的關系網絡圖進行組織發(fā)現。首先循環(huán)的隨機選取50個點[7]為中心，計算所有邊的邊介數，然后移去邊介數最高的邊，將關系網絡圖分割成更小的連通子圖，接著反復進行這個過程，直到滿足停止條件為止，這樣將得到多個滿足停止條件的連通子圖。對于這些滿足停止條件的連通子圖稱為群體。所有這些群體的集合稱為一個結構。由于重復了50次，將得到50個結構。最后整合所有結構中的群體，得到要找的種子組織。

然而實際數據中常常有一個實體屬于多個組織的情況，如圖1所示，包含了2個組織[9]，左邊的組織包含點A，右邊的組織包含點C。在圖1中的所有連線中，AB和BC都具有很高的邊介數。如果先移除連線BC，那么AB就會因為具有較低的邊介數不會被移除，點B就會被劃分到左邊的組織中。而如果先移除連線AB，那么同樣的BC也會因為具有較低的邊介數不會被移除，點B就會被劃分到右邊的組織中。因此需要找到一種方法解決一個實體屬于多個組織的情況。眾所周知，互信息能夠用于描述兩個隨機變量之間的相互依賴性，即如果它們彼此獨立，則它們之間的互信息為0；如果它們互相依賴很緊密，則互信息就會很大。于是，在使用Wilkinson-Huberman算法得到種子組織集合G{G1,G2,…,Gn}之后，對G中的每一個子組織Gi(i=1,2,…,n)和在原始的關系網絡圖中與Gi存在聯系的一級聯系人建立互信息模型，分別計算這些聯系人與Gi內每個成員的互信息值，當所有互信息的平均值超過預先指定的閾值β時，就將這個點加入到子組織Gi中。通過這個過程，就能夠較好地解決同一實體屬于多個組織的情況。關于閾值β的選取，通常是針對不同類型的數據集，采用實驗法來確定的[8]。

綜上所述，假設對包含N個頂點的關系圖進行組織發(fā)現，WH-MI算法的步驟如下所示：

1）進行50次[7]迭代。

2）檢測關系圖是否包含多個連通子圖。

3）對每個連通子圖，檢查其是否滿足停止條件：

如果連通子圖滿足停止條件，把它從關系圖中移出。

如果不滿足，則計算連通子圖內每條邊的邊介數，然后移去具有最大邊介數的邊，直到連通子圖被分成兩個更小的連通子圖。

4）重復步驟3)，直到所有的實體從關系圖中全部移出，這時形成了1個組織集合Si。

5）對步驟1)～4)之后形成的50個組織集合中的組織進行重新整合，形成1個組織集合G。

6）通過計算互信息，對G進行擴充。

從算法的步驟中可以看出，步驟1)～5)是Wilkinson-Huberman算法，WH-MI算法是在Wilkinson-Huberman算法的基礎上，結合互信息進行組織成員的擴展。因此，與Wilkinson-Huberman算法相比，WH-MI算法得到的組織成員更為完整。

Wilkinson-Huberman算法的基本原理可以參考相關文獻[7、9]深入了解。下面將詳細闡述利用互信息擴展隱藏組織成員的過程和原理。

在得到種子組織之后，嘗試通過查找與一個或多個種子成員有著密切聯系的實體，來確定種子組織的附加成員。為了找到這些與種子組織具有密切聯系的實體，就需要統計它們與種子組織中的已知成員之間的聯系程度，這就需要通過建立互信息模型來實現。

以電話通信為例，知道兩個電話號碼之間的通話行為具有不確定性，也就是說可以把兩個電話號碼的一次通話看作一個隨機事件，顯然該隨機事件的結果只有2個，要么是這兩個電話號碼之間有通話，要么是沒有通話。如果用一個兩維隨機變量(X,Y)的取值來表示該隨機事件，則該隨機變量的定義域為{P，φ}，其中P代表隨機變量X與Y有通話行為，φ表示沒有發(fā)生通話行為。因此，兩個電話號碼之間的關聯度就可以用其相應的隨機變量的互信息來度量。從信息論的角度來看，一次通話的過程其實也是傳遞信息的過程，通過傳遞信息來消除通話行為的不確定性，因此，兩個隨機變量的互信息可以解釋為知道一個隨機變量的取值后對另一個隨機變量的不確定性的減少量，或者一個隨機變量包含的另一個隨機變量的信息量。根據經典的信息論[10]，定義兩個隨機變量X和Y的互信息如下：

式中，P(x)=Prob(X=x),P(y)=Prob(Y=y)。

所以，對種子組織進行成員擴展的過程如下所示：

1）對于種子組織中的每一個成員，在原始關系網絡圖中找到與之有聯系的實體，并將它們添加到種子組織中，形成一個新的群體。這樣就得到了一個擴展的組織。

2）將擴展后的組織看作是一個整體，計算所有新增實體與種子組織中各成員之間的互信息值。

3）計算每一個新增實體與種子成員中所有成員互信息值的平均值，當這個平均值高于預先指定的閾值β時，則保留這個實體，否則將實體從擴展組織中刪去。

4）對步驟3)得到的擴展后的組織，再重復一次組織擴展的過程。

為了便于理解，借助圖2、表1和表2來說明建立互信息模型的過程。假設得到的實體關系圖如圖2所示，統計各實體之間發(fā)生的事件如表1所示，計算得到各實體之間的互信息如表2所示。

圖2 實體關系

表1 各實體之間發(fā)生的事件表

表 2 各實體之間的互信息

2 實驗結果分析

現將使用網絡分析領域中的經典數據集“空手道俱樂部網絡（Karate Club Network）數據” 和“大學生足球聯賽網絡（College Football Network）數據”，對WH-MI算法進行可靠性驗證。

2.1 空手道俱樂部網絡數據實驗

空手道俱樂部網絡數據是社會網絡分析領域中的經典數據集，由社會學家 Zachary耗時兩年觀察美國一所大學中空手道俱樂部 34名成員間的社會關系而得到的。由于俱樂部的管理者和老師之間就是否提高俱樂部的費用發(fā)生了爭論，結果俱樂部分成了兩個分別以管理者和老師為中心的俱樂部。圖3中，圓形頂點和方形頂點分別代表俱樂部分開后形成的兩個新俱樂部的成員。

圖 3 Karate Club Network數據示意

利用 WH-MI算法對空手道俱樂部網絡數據進行組織發(fā)現，得到兩個組織，兩個組織包含的成員如表3所示。

表 3 Karate Club Network數據實驗結果

將表3與圖4對比后發(fā)現，使用WH-MI算法發(fā)現的兩個組織結構完全正確。

2.2 大學生足球聯賽網絡數據實驗

大學生足球聯賽網絡數據模型是Newman等人對美國大學生足球聯賽情況分析整理而建立的一個復雜網絡模型。參加足球聯賽的有若干支球隊，網絡的每個節(jié)點分別代表一支球隊，2個節(jié)點之間的邊代表2 支球隊之間進行過一場比賽。聯賽中存在若干的聯盟，每個球隊都屬于其中一個聯盟。該模型中存在115支球隊（個節(jié)點）及616場比賽（條邊），包含了12個聯盟。

使用WH-MI算法進行聯盟劃分，得到11個組織。組織結構如表4所示。

表4 WH-MI算法劃分結果

使用Wilkinson-Huberman算法進行聯盟劃分，得到11個組織。組織結構如表5所示。

表5 Wilkinson-Huberman算法劃分結果

對比表4與實際情況發(fā)現，劃分正確的節(jié)點為99個，正確率約為86%。對比表5與實際情況發(fā)現，劃分正確的節(jié)點為97個，正確率約為84.3%。由此可見，使用 WH-MI算法進行組織發(fā)現的準確率，比使用Wilkinson-Huberman算法進行組織發(fā)現的準確率高。

3 結語

文中分析了經典的Betweenness算法和Wilkinson-Huberman算法，針對Betweenness算法在組織發(fā)現方面的不足，結合Wilkinson-Huberman算法以及互信息技術，提出了一種新的組織發(fā)現算法(WH-MI算法)。與目前其他一些劃分算法相比，該方法不必事先知道網絡中的組織總數；同時，由于使用了互信息技術對形成的組織成員進行擴展，得到的組織結構更為完整。最后采用空手道俱樂部網絡數據和大學生足球聯賽網絡數據對算法進行了實驗驗證，實驗結果與實際的劃分基本吻合，說明該算法是可行的。

[1] 陳文華,蔡皖東,趙煜.基于數據挖掘的匿名通信關系分析模型研究[J].信息安全與通信保密,2008(06):51-52.

[2] 孫義明,曾繼東.數據挖掘技術及其應用[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.