基于節點相似性的并行啟發式網絡拓撲結構發現算法

董振亮, 陳志賓, 張 華, 何文海, 孫麗麗

(1. 華北電力大學 計算機系, 河北 保定 071003; 2. 河北省教育考試院 信息管理部, 河北 石家莊 050091; 3. 河北省科學院 應用數學研究所, 河北 石家莊 050081; 4. 石家莊醫學高等專科學校 公共課部, 河北 石家莊 050000)

隨著計算機和通信技術的快速普及,普通網絡的拓撲結構也呈現出大型化與模塊化的特點,從而逐漸轉化為具有生物、社交及通信等多種功能的復雜網絡。按照圖論原理,在復雜網絡中具有相似抽象屬性或功能的所有節點均可被歸納為連通子圖,這樣的劃分方式也被稱為社區結構。通常而言,復雜網絡中社區內部節點連接密度較高,而社區之間節點連接密度較低,這樣的組織結構大幅提高了復雜網絡的管理效率。然而,隨著網絡規模的不斷擴大,如何完成全局性的社區發現逐漸成為復雜網絡研究領域的主要問題。

針對大規模復雜網絡的全局性社區發現問題,國內外學者已做出了諸多具有較高借鑒價值的工作。劉旭[1]在開源平臺上給出了能夠評估社區劃分分數的目標函數,進而充分衡量了社區劃分的質量和水平。周旭[2]通過引入啟發式蟻群算法(ant clony optimization,ACO),首次提出高精確度的社區發現算法,該算法具有一定的啟發性和代表性。然而,上述工作依舊未能完全解決復雜網絡中的社區發現問題,且相應算法的執行效率及準確率仍有待提高。為了進一步優化該算法,文中在鄰接矩陣的基礎上,結合經典的評判準則,制定了更加精確的節點相似性評價規則,進而提出了具有并行化特點的社區發現算法。由社區發現算法實驗仿真可知,與基于Jaccard準則的社區發現算法相比,本文所提出的算法具有較高的精確度及更少的執行時間。

1 節點相似性

在復雜網絡中,由于網絡拓撲具有較高的不確定性且難以進行預測,因此復雜社區網絡的發現問題已成為橫跨多個研究領域的難題之一[3-5]。為描述該問題,多位學者引入圖論的鄰接矩陣對社區網絡發現問題進行了詳細闡述[6-7]。

不妨令G代表由n個節點與m條邊組成的復雜社區網絡,根據節點間的連接關系,可得到與G逐一對應的鄰接矩陣M。令i,j∈[1,n],則矩陣M中元素mij表示第i個節點與第j個節點間的連接關系。若節點i與節點j之間有邊連接,則mij=1;否則,mij=0。利用鄰接矩陣M的數據可以順利統計復雜網絡G中所有節點的連通狀態。對于節點i,與其連接的所有節點數量即為矩陣M的第i行或第i列的邊數之和,該數值又被稱為節點i的度數。在復雜網絡G中,令Ci表示與節點i具有連接關系的所有節點組成的鄰居集合。通常而言,鄰居集合Ci也是網絡G的非空子集。在鄰居集合Ci中,節點i的度數越大,則其與集合中其他節點的聯系就更為緊密。換言之,與其他節點的聯系越緊密,則當前節點的重要程度越高。

為了精確衡量社區網絡中節點間的相似性關系,文中對具有不同屬性的相鄰節點設置了不同的權重,從而實現節點相似性的計算與區分,具體設置方法如下:

1) 若鄰接矩陣元素mij=1,即節點i與節點j之間具有連接的邊,則這些邊的權重設置為w1;

2) 若節點i和節點j的鄰居集合Ci及Cj之間存在非空交集,且該交集的節點存在連接的邊,則這些邊的權重設置為w2;

3) 若節點i及節點j的鄰居集合Ci與Cj之間存在非空交集,且該交集中存在沒有連接的邊,則這些邊的權重設置為w3;

4) 若節點i和節點j的鄰居集合Ci及Cj之間存在非空交集,而其他節點與該交集以及節點i、j存在連接的邊,則這些邊的權重設置為w4;

5) 對于其他連接情況的邊,則設置其權重為w5。

需要說明的是,不同的邊對節點相似性產生的影響不同,所以權重遵循遞減的順序,即w1>w2>w3>w4>w5。

定義1根據邊權重的設置方法,節點i和節點j之間相似性的計算表達式為

(1)

式中,N1、N2、N3、N4和N5分別為節點相似性權重設置時5種不同類型邊的數目。

2 并行化策略

在復雜網絡中,數據信息的快速增長及不合理分配會造成計算資源的浪費[8-9],從而大幅降低整體的運行效率,而其根源在于社區發現中的串行算法結構。為了改變這一現狀,文中通過改變社區數據的組織結構,提出具有并行化特點的存儲與檢索策略[10]。

通常而言,傳統的復雜網絡采用數組及鏈表的結構來實現數據的存儲和檢索。其優點在于數據的插入及刪除較為便捷,但其尋址仍存在較大困難。為克服這一缺點,文中引入哈希表完成對數據的存儲,從而實現數據的快速查詢、插入、刪除與尋址等多種操作[11]。令a～f表示拓撲圖中的6個節點,F表示節點之間的邊存儲信息,H表示對應的哈希函數,wi表示第i個邊權重數值,則并行化存儲策略的框架如圖1所示。

圖1 并行化存儲策略框架示意圖Fig.1 Schematic diagram of parallelized storage strategy framework

由圖1可知,在策略框架中,網絡G利用哈希表計算存儲發射方向與入射方向的節點信息,其實現步驟如下:

1) 按照邊的方向對G中所有邊進行分類,即分別使用Table-in和Table-out表格存儲入邊與出邊;

2) 利用邊的節點信息及函數F,計算入邊和出邊的實際存儲信息,令“|”表示位或運算,“?”表示位左移運算,則節點i和j之間邊的存儲信息計算表達式為

F(i,j)=j|(i?16)

(2)

3) 利用哈希函數[12]對邊的存儲信息進行計算,獲取對應的哈希值,再結合邊的權值信息,形成具有固定格式的三元組信息,并分別存儲于對應的哈希表中。令H0表示斐波那契哈希函數,S表示哈希表的最大容量,φ表示黃金分割率,常數m=264-1,則自變量x的哈希值計算方式為

(3)

綜上所述,文中通過綜合節點相似性及哈希函數,將復雜網絡的節點數據存儲轉化為哈希表格式,進而實現節點關系數據的高效存儲與檢索。同時利用并行化策略,計算節點相似性時無須掃描所有網絡節點,便可順利地將串行計算模式轉換為并行計算模式,并降低發現算法的計算成本。

3 社區發現算法

復雜網絡社區結構的發現和劃分與其拓撲結構之間具有較為緊密的關系[13-15],這意味著社區發現算法需根據網絡節點的相似性計算結果來考慮圖中邊權值的影響,并對復雜網絡的所有節點屬性進行識別及劃分,再以較高的精確度判定復雜網絡的社區結構。實際算法步驟如下:

1) 針對復雜網絡抽象化之后的網絡G建立存儲入邊和出邊的Table-in與Table-out表格,并加入邊的哈希存儲表;

2) 按照節點相似性的設置方式,利用降序法設置邊的權重影響因子(w1>w2>w3>w4>w5);

3) 從G中任選兩個網絡節點i和j,并利用并行化存儲策略構建哈希表,同時獲取這兩個節點的所有鄰居三元組信息,再計算節點i和j之間的相似性;

4) 重復執行步驟3,直至G中所有n個網絡節點之間的相似性計算完成,并形成節點相似性矩陣;

5) 根據節點相似性矩陣結果,對G中所有n個節點執行聚類操作,即按照相似性計算結果實現復雜網絡所有節點的層次劃分;

6) 依據節點的層次劃分結果,完成對復雜網絡的社區劃分。

4 實驗仿真

在大規模網絡數據集基礎上,針對節點相似性社區發現算法,本文設計了算法的綜合性測試仿真,從而充分地衡量復雜網絡中社區發現算法的計算效率與準確度。

4.1 仿真數據集

基于Jaccard準則及節點相似性的社區發現算法,文中引入了反映客觀網絡狀態的大型數據集,即Email Euall數據集。該數據集由某研究機構所有發送和接收的電子郵件組成,共包含42個研究部門的通信信息。經過抽象化之后,與Email Euall數據集對應的圖包含1 005個節點與25 571條邊,且其平均聚類系數為0.339 4。此外,在復雜網絡中節點重要程度與節點的度成正比關系。按照此原則,文中引入節點相似性因子δ對原始數據集進行了必要處理,從而充分評估中心節點的重要程度。其中,令Mi和Mj分別表示鄰接矩陣的第i行和第j行,即節點i和j的鄰域集合,則節點i和j之間的相似性因子δ表達式為

(4)

4.2 評估指標

為了衡量算法發現結構與客觀網絡結構間的匹配度,文中引入標準化信息交互評估機制,即利用社區層次劃分的一致程度評估發現算法的準確性。

(5)

對于同樣復雜網絡結構,通過計算算法劃分結果及復雜網絡之間的標準化互信息指標可獲取不同算法劃分結果的相似程度,從而衡量社區發現算法的劃分質量。一般而言,標準化互信息量I(rp,rq)的計算結果位于[0,1]之間,其數值越接近于0,則表明準確劃分結果與發現算法運行結果的相關性越低;而數值越接近于1,則發現算法運行結果越接近準確的劃分結果。

4.3 仿真過程

對于具有不同節點相似性因子的Email Euall數據集,本文分別對基于Jaccard準則及基于節點相似性的社區發現算法進行必要的測試對比。需要說明的是,針對兩種社區發現算法,文中主要從準確度和計算效率進行衡量。在不同相似性因子的實驗數據集條件下,文中對兩種算法的運行結果與實驗數據集之間的標準化互信息量進行了精確統計,結果如圖2所示;在不同相似性因子的實驗數據集條件下,兩種社區發現算法達到相同的標準化互信息量(0.7)所需的運行時間不同,文中對算法的運行時間進行了統計與對比,結果如圖3所示。

圖2 不同相似性因子時兩種算法的標準化互信息量Fig.2 Normalized mutual information of two algorithms under different similarity factors

圖3 在不同相似性因子時兩種算法的運行時間Fig.3 Running time of two algorithms under different similarity factors

由圖2的統計結果可知,當節點相似性因子數值增加時,基于Jaccard準則與基于節點相似性的社區發現算法的標準化互信息量均呈現了先小幅下降再大幅提升的趨勢;且當相似性因子相等時,基于節點相似性的社區發現算法的標準化互信息量優于經典的Jaccard準則社區發現算法。換言之,與基于Jaccard準則的社區發現算法相比,本文算法具有更優的準確度。從圖3可以看出,隨著相似性因子數值的增加,兩種算法的運行時間逐步增加,部分情況下會出現小幅下降;但當相似性因子相等時,為達到相同的拓撲發現精確度,基于節點相似性的社區發現算法所需運行時間均小于經典的Jaccard準則社區發現算法,表明文中算法的計算效率更高。綜上所述,與經典Jaccard準則的社區發現算法相比,基于節點相似性的社區發現算法具備更高的發現準確度及計算效率。

5 結束語

基于節點相似性和并行化策略,文中提出具有較高準確度和計算效率的復雜網絡社區發現算法,并對該算法進行了必要的仿真對比及分析。與經典Jaccard準則的社區發現算法相比,基于節點相似性的社區發現算法并未進行實際應用環境下的反復實驗與仿真,這意味著該算法仍停留在實驗階段,在大面積應用時仍然可能存在潛在的缺陷和問題,尤其是社區發現算法在更大應用范圍內的安全性和穩定性未能得到充分的實驗和分析,將在未來的工作中致力于這一問題的研究,從而實現基于節點相似性的并行拓撲結構發現算法的推廣和應用。