基于節(jié)點相似性的并行啟發(fā)式網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法

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

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

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

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

1 節(jié)點相似性

在復(fù)雜網(wǎng)絡(luò)中,由于網(wǎng)絡(luò)拓?fù)渚哂休^高的不確定性且難以進行預(yù)測,因此復(fù)雜社區(qū)網(wǎng)絡(luò)的發(fā)現(xiàn)問題已成為橫跨多個研究領(lǐng)域的難題之一[3-5]。為描述該問題,多位學(xué)者引入圖論的鄰接矩陣對社區(qū)網(wǎng)絡(luò)發(fā)現(xiàn)問題進行了詳細(xì)闡述[6-7]。

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

為了精確衡量社區(qū)網(wǎng)絡(luò)中節(jié)點間的相似性關(guān)系,文中對具有不同屬性的相鄰節(jié)點設(shè)置了不同的權(quán)重,從而實現(xiàn)節(jié)點相似性的計算與區(qū)分,具體設(shè)置方法如下:

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

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

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

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

5) 對于其他連接情況的邊,則設(shè)置其權(quán)重為w5。

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

定義1根據(jù)邊權(quán)重的設(shè)置方法,節(jié)點i和節(jié)點j之間相似性的計算表達(dá)式為

(1)

式中,N1、N2、N3、N4和N5分別為節(jié)點相似性權(quán)重設(shè)置時5種不同類型邊的數(shù)目。

2 并行化策略

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

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

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

由圖1可知,在策略框架中,網(wǎng)絡(luò)G利用哈希表計算存儲發(fā)射方向與入射方向的節(jié)點信息,其實現(xiàn)步驟如下:

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

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

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

(2)

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

(3)

綜上所述,文中通過綜合節(jié)點相似性及哈希函數(shù),將復(fù)雜網(wǎng)絡(luò)的節(jié)點數(shù)據(jù)存儲轉(zhuǎn)化為哈希表格式,進而實現(xiàn)節(jié)點關(guān)系數(shù)據(jù)的高效存儲與檢索。同時利用并行化策略,計算節(jié)點相似性時無須掃描所有網(wǎng)絡(luò)節(jié)點,便可順利地將串行計算模式轉(zhuǎn)換為并行計算模式,并降低發(fā)現(xiàn)算法的計算成本。

3 社區(qū)發(fā)現(xiàn)算法

復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)和劃分與其拓?fù)浣Y(jié)構(gòu)之間具有較為緊密的關(guān)系[13-15],這意味著社區(qū)發(fā)現(xiàn)算法需根據(jù)網(wǎng)絡(luò)節(jié)點的相似性計算結(jié)果來考慮圖中邊權(quán)值的影響,并對復(fù)雜網(wǎng)絡(luò)的所有節(jié)點屬性進行識別及劃分,再以較高的精確度判定復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。實際算法步驟如下:

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

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

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

4) 重復(fù)執(zhí)行步驟3,直至G中所有n個網(wǎng)絡(luò)節(jié)點之間的相似性計算完成,并形成節(jié)點相似性矩陣;

5) 根據(jù)節(jié)點相似性矩陣結(jié)果,對G中所有n個節(jié)點執(zhí)行聚類操作,即按照相似性計算結(jié)果實現(xiàn)復(fù)雜網(wǎng)絡(luò)所有節(jié)點的層次劃分;

6) 依據(jù)節(jié)點的層次劃分結(jié)果,完成對復(fù)雜網(wǎng)絡(luò)的社區(qū)劃分。

4 實驗仿真

在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集基礎(chǔ)上,針對節(jié)點相似性社區(qū)發(fā)現(xiàn)算法,本文設(shè)計了算法的綜合性測試仿真,從而充分地衡量復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)算法的計算效率與準(zhǔn)確度。

4.1 仿真數(shù)據(jù)集

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

(4)

4.2 評估指標(biāo)

為了衡量算法發(fā)現(xiàn)結(jié)構(gòu)與客觀網(wǎng)絡(luò)結(jié)構(gòu)間的匹配度,文中引入標(biāo)準(zhǔn)化信息交互評估機制,即利用社區(qū)層次劃分的一致程度評估發(fā)現(xiàn)算法的準(zhǔn)確性。

(5)

對于同樣復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu),通過計算算法劃分結(jié)果及復(fù)雜網(wǎng)絡(luò)之間的標(biāo)準(zhǔn)化互信息指標(biāo)可獲取不同算法劃分結(jié)果的相似程度,從而衡量社區(qū)發(fā)現(xiàn)算法的劃分質(zhì)量。一般而言,標(biāo)準(zhǔn)化互信息量I(rp,rq)的計算結(jié)果位于[0,1]之間,其數(shù)值越接近于0,則表明準(zhǔn)確劃分結(jié)果與發(fā)現(xiàn)算法運行結(jié)果的相關(guān)性越低;而數(shù)值越接近于1,則發(fā)現(xiàn)算法運行結(jié)果越接近準(zhǔn)確的劃分結(jié)果。

4.3 仿真過程

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

圖2 不同相似性因子時兩種算法的標(biāo)準(zhǔn)化互信息量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的統(tǒng)計結(jié)果可知,當(dāng)節(jié)點相似性因子數(shù)值增加時,基于Jaccard準(zhǔn)則與基于節(jié)點相似性的社區(qū)發(fā)現(xiàn)算法的標(biāo)準(zhǔn)化互信息量均呈現(xiàn)了先小幅下降再大幅提升的趨勢;且當(dāng)相似性因子相等時,基于節(jié)點相似性的社區(qū)發(fā)現(xiàn)算法的標(biāo)準(zhǔn)化互信息量優(yōu)于經(jīng)典的Jaccard準(zhǔn)則社區(qū)發(fā)現(xiàn)算法。換言之,與基于Jaccard準(zhǔn)則的社區(qū)發(fā)現(xiàn)算法相比,本文算法具有更優(yōu)的準(zhǔn)確度。從圖3可以看出,隨著相似性因子數(shù)值的增加,兩種算法的運行時間逐步增加,部分情況下會出現(xiàn)小幅下降;但當(dāng)相似性因子相等時,為達(dá)到相同的拓?fù)浒l(fā)現(xiàn)精確度,基于節(jié)點相似性的社區(qū)發(fā)現(xiàn)算法所需運行時間均小于經(jīng)典的Jaccard準(zhǔn)則社區(qū)發(fā)現(xiàn)算法,表明文中算法的計算效率更高。綜上所述,與經(jīng)典Jaccard準(zhǔn)則的社區(qū)發(fā)現(xiàn)算法相比,基于節(jié)點相似性的社區(qū)發(fā)現(xiàn)算法具備更高的發(fā)現(xiàn)準(zhǔn)確度及計算效率。

5 結(jié)束語

基于節(jié)點相似性和并行化策略,文中提出具有較高準(zhǔn)確度和計算效率的復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法,并對該算法進行了必要的仿真對比及分析。與經(jīng)典Jaccard準(zhǔn)則的社區(qū)發(fā)現(xiàn)算法相比,基于節(jié)點相似性的社區(qū)發(fā)現(xiàn)算法并未進行實際應(yīng)用環(huán)境下的反復(fù)實驗與仿真,這意味著該算法仍停留在實驗階段,在大面積應(yīng)用時仍然可能存在潛在的缺陷和問題,尤其是社區(qū)發(fā)現(xiàn)算法在更大應(yīng)用范圍內(nèi)的安全性和穩(wěn)定性未能得到充分的實驗和分析,將在未來的工作中致力于這一問題的研究,從而實現(xiàn)基于節(jié)點相似性的并行拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)算法的推廣和應(yīng)用。