基于重要節點刪除法的社會網絡層次結構分析

王 魁,馬 宏,黃瑞陽

(國家數字交換系統工程技術研究中心,鄭州 450002)

0 概述

社團結構是復雜網絡中的重要結構[1],一個最優的社團劃分方法是將所有同一屬性的節點劃到同一類,不同屬性的節點劃到不同類中。由于大多數網絡無法預知各節點的屬性,因此傳統的社團發現方法將連邊密集的節點劃為一個社團,連邊稀疏的劃為不同社團[2],如文獻[3]提出的GN算法、FN算法[4]與文獻[5]提出的Fast Unfolding算法等。然而,隨著研究的深入,研究者發現當節點增多時,社團結構互相融合,使網絡不再有最優的劃分[6]。這是由于現實網絡中節點根據重要程度不同呈現層次性關系[7],一些重要節點同時連接了多個社團,使得不同社團之間的界限不再明顯,根據連邊疏密對網絡劃分的方法不能得到最優的劃分結果。因此,有學者提出使用網絡分解方法來分析網絡的結構。

網絡分解方法最早由文獻[8]提出,他們首先驗證了現實網絡具有無標度性,然后分別把隨機網絡和無標度網絡置于2種類型的打擊策略之下:隨機移除網絡中的節點和選擇性移除度數最高的節點,發現無標度網絡在選擇性攻擊下更容易崩潰。2014年,文獻[9]提出了SlashBurn方法,將網絡分解與鄰接矩陣重排序結合起來,實現對大規模網絡的壓縮,但是該方法局限于將網絡快速分解,沒有分析網絡分解過程中產生的分支在網絡結構的作用。文獻[10]在此基礎上提出的MTP方法分析了刪除部分中心節點后對網絡結構產生的影響,通過對刪除部分中心節點后的網絡進行社團劃分,得出了更好的網絡劃分效果,但是該方法沒有找出所有使不同社團連接的節點,因此,沒有根本解決現實網絡中無最優劃分的問題。

上述網絡分解方法都是使用度數作為節點重要性的衡量方法,沒有比較使用其他中心指標的中心節點刪除后對網絡的影響。節點重要性可以用多種指標來衡量[11],如度、介數、k-shell、pagerank等,不同的指標在描述節點重要程度時側重的方面各有不同。度中心性[12]認為一個節點的鄰居越多則影響力越大,這是描述節點重要性最簡單的指標,度中心性計算簡單但忽略了節點的全局特征。因此,在以度為中心指標分解網絡時會使社團自身分解。介數中心性[13]是基于網絡全局屬性的指標,介數越高的節點越容易成為不同社團之間的橋節點,因此以介數為中心指標分解網絡可以使網絡以社團為單位分解,然而,介數中心性的計算時間復雜度較高,需要改進算法來提高計算節點介數的算法效率。

為利用節點的層次性特征分析社會網絡結構,本文提出一種改進的基于重要節點刪除的網絡分解方法對網絡結構進行劃分。

1 相關工作

1.1 節點介數定義

用圖G=(V,E)表示一個網絡,其中,V表示所有節點集合,E表示所有邊集合,用σst表示從節點s到節點t的最短路徑數量,σst(v)表示從節點s到節點t的最短路徑中經過節點v的數量,δst(v)表示節點s到節點t的最短路徑中經過節點v的比例,即:

用δs·(v)表示從s到所有其他節點的最短路徑中經過v的比例,即:

一個節點的介數中心性可以表示為所有最短路徑中經過該節點的最短路徑所占比例,定義為:

(1)

用傳統方法計算介數的時間復雜度為O(n3),n為網絡中節點數量。隨著網絡規模的增加,減少算法的計算復雜度成為亟待解決的問題。

1.2 圖的連通分支

在一個無向圖G中,若從頂點vi到頂點vj有邊相連,則稱vi和vj是連通的,如果圖中任意兩點都是連通的,那么圖被稱為連通圖[14],否則,稱該圖為非連通圖。圖G中的一個極大連通子圖稱為G的連通分支,連通分支中包含的節點數極大,即沒有除了連通分支外的其他節點與該連通分支相連。連通圖只有一個連通分支,即其自身,非連通圖有多個連通分支。

在現實網絡中,同一社團內的節點具有相似性從而容易產生連邊,因此,一般處在同一個連通分支中。不同的社團通過一些中心節點的連接而合并到同一個連通分支中。還有一些孤立節點,如微博中剛注冊的賬號,可以通過關注推薦的中心節點加入連通分支,或者關注自己現實中的好友加入社團從而并入連通分支。因此,現實網絡中的大多數節點都處在同一個最大連通分支[15]中,而通過節點刪除的策略可以從網絡中分解出多個連通分支。

2 基于重要節點刪除的網絡層次劃分

根據復雜網絡中社團之間普遍存在橋節點且刪除少量節點可以使網絡分解的特點,本文采用基于重要節點刪除的網絡分解方法對網絡層次結構進行分析。

2.1 相關定義

2.1.1 圖的鄰接矩陣

用鄰接矩陣A來表示一個具有n個節點的網絡,矩陣中的元素sij表示網絡中節點的連接情況,在無權無向圖中,若sij=0表示節點i和j沒有連接,sij=1表示節點i和節點j有連接。

2.1.2 星型結構及模型

星型結構是一種基本網絡結構[16],星型結構中所有節點只和中心節點相連,星型網絡結構模型如圖1所示。圖1(a)給出了星型結構和其鄰接矩陣,可見星型結構中的節點分為兩類:中心節點和葉子節點,星型結構的鄰接矩陣呈倒L型。

定義星型結構模型為一種廣義的星型結構,從星型結構到星型結構模型的演化過程中,包含兩部分:葉子節點的泛化與中心節點的泛化。

葉子節點的泛化如圖1(b)所示,與中心節點相連的節點中有一部分互相連接,即鄰接矩陣的對角線上出現塊狀區域,將互相連接的這部分節點視為一個超級葉子節點。中心節點的泛化如圖1(c)所示,網絡中增加若干個中心節點,即鄰接矩陣網絡中出現多個倒L型結構,則將多個中心節點合并為一個超級中心節點。如圖1(d)所示,經泛化后的網絡仍然可以看作一個星型結構,稱為星型結構模型。表1列舉出了本文常用符號。

圖1 星型網絡結構模型

符號描述G(V,E)無權無向網絡G,V為節點,E為邊size(G)G中的節點個數betweenness(i)節點i的介數hub中心節點hubset所有中心節點的集合CC連通分支branch所有CC組成的分支集合GCC最大連通分支k每次刪除的中心節點個數m把CC作為超級葉子節點的最少節點數

2.2 介數計算方法

根據式(1)可以得出,計算一個節點的介數需要計算最短路徑數量。顯而易見,度數為1的節點到任何一個節點的最短路徑都要經過該節點的鄰居節點,因此,根據網絡中剩余節點即可計算出原網絡中節點的介數,同時由于度數為1的節點在網絡中不可能成為連接2個社團的節點,因此,沒有必要計算它們的介數。基于此,本文提出將度數為1的節點刪除,結合原節點度數信息計算剩余網絡中節點的介數,從而減少運算復雜度。下文就如何根據剩余網絡計算原網絡中度數大于1的節點介數給出推導。

對于網絡G,用D1表示所有度為1的節點集合,R表示所有度為1的節點的鄰居節點集合。刪除G中度為1的節點得到G’,G’中節點v的介數表示為:

(2)

任意取一個節點t’∈D1,恢復其到鄰居節點t∈R的連接,此時v的介數變為:

(3)

由于從t’出發的所有最短路徑都經過t,因此δt·(v)=δt’·(v)。

(4)

同理,當原網絡中所有度為1的節點加入后,得到:

(5)

其中,DS表示節點s所連接的度為1的節點個數。

根據文獻[17]的研究,現實中大多數網絡的節點度數服從冪率分布,即度數越低的節點數量越多,如圖2展示的是一個度數服從冪律分布的推特網絡rt-alwefaq,在刪除度為1的節點后網絡規模會大大縮小,因此,本文方法可以有效減少介數計算的時間復雜度。

圖2 推特網絡的度分布及刪除度為1節點后網絡規模變化

2.3 基于網絡分解的鄰接矩陣重排序與網絡簡化

傳統的社團定義是社團內部邊密集而社團間稀疏。文獻[6]在研究中發現,隨著網絡規模的增大,社團逐漸與網絡中其余部分互連在一起,出現分層、嵌套的現象,使社團間變得不再稀疏,從而不容易分割。為解決社團不易劃分的問題,本文從相反的角度出發,先找出這些使不同社團連接起來的節點,再通過刪除這些節點使網絡分解,則原本通過這些節點相連的社團就會逐個與整體網絡分離開,從而達到分析網絡結構的目的。如圖3所示,將不同社團相連的節點設為中心節點,即hub,在找出并刪除hub后,計算剩余GCC中節點的中心性,找出GCC中的hub并刪除,對每次產生的GCC做相同操作直到整個網絡不可分解,其中,圖1(b)、圖1(d)節點數為15。對分解過程中產生的一系列分支進行篩選,若CC的規模較小,說明這部分節點在網絡中僅與少量的hub相連,可以當作不具代表性的節點;若CC的規模較大,說明這部分節點具有較強的相似性,可以作為網絡中一個社團。

圖3 網絡分解與鄰接矩陣重排序

用鄰接矩陣重排序來表示上述分解過程,首先將網絡表示為鄰接矩陣A,再將每次刪除的中心節點放在鄰接矩陣頭部,產生的連通分支按大小順序放在尾部,直到網絡不可分解,詳細步驟見算法1。

算法1基于網絡分解的鄰接矩陣重排序方法

輸入網絡G的鄰接矩陣A,常數k、m

輸出重排序后鄰接矩陣B

將節點在A中的排列順序設為A= (hubset;GCC;branch);

初始化:hubset=?;GCC=A;branch=?

while size(GCC)>k

for i ∈GCC

根據2.2節算法計算betweenness(i);

end

將節點按betweenness(i)降序排列得V [n];

hub=V(1)～V(k);

hubset=hubset+hub;

計算刪除hub后圖的連通分支,降序排列得CC[s];

GCC=CC(1);

branch=CC(2)～CC(s)+branch;

B=(hubset;GCC;branch);

return B

由于在鄰接矩陣重排序的過程中,本文將中心節點放到了鄰接矩陣的頭部,因此頭部的節點應服從星型結構的倒L型分布,分支放在鄰接矩陣的尾部,則尾部節點的鄰接矩陣服從社團結構的塊狀分布。通過重排序后的鄰接矩陣,將hub設為超級中心節點,視為在網絡中其連接作用的中樞節點,將節點數大于m的CC作為超級葉子節點,視為網絡中聚集而成的社團。因此,本文方法可以從原網絡中找出社團結構與節點之間的層次關系,從而將原網絡簡化為一個星型結構模型。

3 實驗結果與分析

為進一步驗證節點刪除法對網絡結構分析的效果,將在不同規模的真實網絡數據集上測試本文方法。數據集來自斯坦福 SNAP數據集和network repository網站,包括臉書網絡和推特網絡。具體參數如表2所示。

表2 真實社會網絡數據集

3.1 社團屬性未知的網絡

現實社會網絡中節點的屬性常常是未知的,為了能更好地展示本文算法在劃分一般社會網絡結構時的適用性,首先對4個屬性未知的社會網絡分別使用傳統的社團劃分方法和幾個不同的網絡分解方法進行劃分,劃分的結果以鄰接矩陣重排序的形式表示。

從圖4～圖7可以看出,使用Fast Unfolding算法對網絡中的節點進行社團劃分,在鄰接矩陣中對節點重排序后,節點排列成若干個密集的塊狀區域,說明這些塊中的節點連接密集而塊間連接稀疏,形成了社團結構。但是鄰接矩陣中除了塊狀區域,還有一些離散的點分布在塊狀區域周圍,這些節點便是沒有得到最優劃分的節點,它們在不同的塊中存在連接,因此,沒有一個公認的標準來判定它們屬于哪一個社團。Slashburn方法將網絡中度數最高的節點抽取出來,對剩下的分支進行排序,可以看出對網絡具有較好的壓縮效果,但是刪除度數最高的節點之后分支過于零散,不利于分析網絡的結構。MTP方法兼顧了Slashburn和傳統社團劃分方法的優點,刪除部分度數最高的節點之后對網絡進行社團探測,但對于如何確定刪除中心節點的數目沒有給出最優的解決方法。因此,仍有部分節點的連接存在于不同社團之間,沒有得到正確的劃分。本文算法以介數作為節點重要性指標,刪除這部分節點后使網絡完全分解,根據重排序的結果可以看出,所有網絡都可以被總結為星型結構模型,鄰接矩陣頭部的節點呈現出“倒L型”結構,因此,可以視為一個超級中心節點;對角線上的節點排列成若干個互不相連的塊狀結構,組成超級葉子節點。使用本文算法對網絡進行劃分,既可以得出更清晰的社團結構,同時又可以明顯看出網絡中的層次劃分。

圖4 rt-copen網絡鄰接矩陣重排序結果

圖5 rt-bahrain網絡鄰接矩陣重排序結果

圖6 rt-alwefaq網絡鄰接矩陣重排序結果

圖7 rt-dash網絡鄰接矩陣重排序結果

3.2 社團屬性已知的網絡

為了驗證本文算法對社會網絡結構劃分是否具有實際意義,本文使用屬性已知的Facebook網絡進行驗證。

Facebook網絡由10個互有交集的個人中心網絡組成,同一個節點可能出現在不同用戶的朋友圈中。通過用不同方式對鄰接矩陣排序,可以直觀地看到不同網絡結構分析方法的特點。

圖8對比了5種按不同的網絡鄰接矩陣重排序方法得到的結果。

圖8 Facebook網絡的分解情況

圖8(a)是按真實劃分得出的排列結果,可以看出以這10個人為中心組成了10個大小不同的朋友圈,每個朋友圈中存在一些影響力較大的節點對在不同朋友圈之中都有影響力。圖8(b)說明對網絡隨機劃分無法得到與真實劃分相同的劃分結果。圖8(c)使用傳統社團劃分方法雖然得到了85%的節點的正確網絡劃分,但對于不同朋友圈中有較大影響力的節點沒有得出正確的劃分,這是由于傳統的社團衡量指標劃分在不同社團之間具有大量連接的節點時還存在局限。圖8(d)SlashBurn方法雖然得到了若干個社團結構,但丟失了大部分節點的正確網絡劃分,劃分準確率僅為45%。這是由于度中心性屬于局部中心性指標,度數大的節點更容易成為一個社團的核心而非社團之間的連接點,刪除度數較大的節點使得原來同一社團內的節點被分解開從而無法得到真實社團結構。圖8(e)中MTP方法通過刪除一部分度數較大的節點后排除了部分干擾,因此可以看出,其劃分效果比傳統社團劃分方法有了較大的提升,劃分準確率達到了89%,但由于MTP方法沒有對所有跨社團的節點進行識別,因此仍有部分節點沒有得到正確劃分。本文算法通過比較不同節點重要性的定義,以介數作為節點在不同社團連接程度的判定標準,將使社團連接的節點刪除,得到剩余節點的社團劃分,在去除中心節點的情況下,本文算法對剩余節點劃分的準確率達到了95%。如圖8(f)所示,在網絡分解的過程中,鄰接矩陣的左側和上側組成一個倒L型,說明矩陣頭部的中心節點構成了一個星型結構,對角線上依次出現了大約10個正方形塊,這10個正方形塊沒有交集,僅與中心節點連接,構成了星型結構的葉子節點。其中對角線上的矩形塊代表以這10個用戶為核心的朋友圈,越靠右的正方形塊對應的中心節點越少,說明越靠右的節點與整體網絡的聯系越少。因此,利用分解方法可以得出和原網絡一致的社團劃分,同時將網絡中這10個中心用戶以及在不同朋友圈中影響力較大的用戶挖掘出來,將中心用戶作為中心節點,節點數超過50的分支作為葉子節點,這樣原網絡可以被總結為一個具有10個葉子節點的星型網絡結構,如圖8(g)所示。

3.3 算法運行效率

算法的運行效率取決于兩個方面,一方面是使網絡完全分解時所需刪除的重要節點數量,另一方面是每次運行節點刪除算法所需的時間。首先將本文算法與Slashburn方法在分解不同網絡時所需刪除的節點數進行對比,從圖9可以看出,本文方法通常只需刪除比Slahburn方法少一半的節點就可以使網絡完全分解,這說明介數比度更能用來衡量節點在網絡結構中的連接作用,刪除介數高的節點能更快地使網絡分解。

由于在刪除節點過程中主要步驟是找到介數最高的節點,而介數的計算復雜度比度數計算要高,因此本文針對大規模網絡提出了介數的快速計算方法,根據定義可知介數計算與網絡規模有直接關系,本文通過刪除度為1的節點使網絡規模平均縮小了一半左右,因此介數的計算復雜度大約只有傳統方法的12%,圖10比較了傳統的介數計算方法和本文所提的介數計算方法在每次運行節點刪除算法時所需的時間。

圖9不同分解方法使網絡完全分解時移除的節點數在網絡中比例

圖10 傳統介數計算方法和本文算法的運行時間

通過減少刪除節點的次數以及每次刪除節點所需的時間,本文算法得到了更高的運行效率。圖11對比不同網絡結構分析方法劃分不同網絡的總時間,可以看出,本文算法在不同網絡中的表現與其他方法沒有較大差別,因此,本文算法在未犧牲計算復雜度的情況下得到了更好的網絡劃分效果。

圖11 不同算法劃分網絡所用時間

4 結束語

本文將網絡分解方法應用到社會網絡的結構分析上,并提出一種大規模網絡中節點介數的快速計算方法。以介數作為節點重要性指標,運用重要節點刪除法對網絡進行分解,將分解出的分支和中心節點在網絡的鄰接矩陣中重排序,發現社會網絡中的層次結構。在真實網絡數據上的實驗結果表明,該方法可以對較大規模的社會網絡進行結構分析,能夠將網絡簡化為一種以中心節點為核心、分支為葉子的星型結構模型。與現有的網絡結構分析方法相比,本文方法根據少數在網絡結構中起重要連接作用的節點,發現了社會網絡中的層次結構以及社團性質,避免了傳統的社團發現方法中社團定義不明確、沒有最優劃分等問題。本文方法為研究大規模網絡中的結構提供了新的思路,但還需要在不同類型的網絡中進行檢驗,此外,如何將該方法對網絡中的節點進行更精細的分類是下一步研究的目標。

[1] 李曉佳,張 鵬,狄增如,等.復雜網絡中的社團結構[J].復雜系統與復雜性科學,2008,5(3):19-42.

[2] FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486(3):75-174.

[3] GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.

[4] NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6).

[5] BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of community hierarchies in large networks[J].Journal of Statistical Mechanics Theory and Experiment,2008,2008(10):155-168.

[6] LESKOVEC J,LANG K J,DASGUPTA A,et al.Statistical properties of community structure in large social and information networks[C]//Proceedings of WWW’08.Washington D.C.,USA:IEEE Press,2008:695-704.

[7] 龐 垠.復雜網絡社團結構探測方法及社團內節點層次關系研究[D].北京.北京理工大學,2015.

[8] BARABASI A L,ALBERT R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[9] KANG U,FALOUTSOS C.Beyond caveman communities:hubs and spokes for graph compression and maining[C]//Proceedings of ICDM’11.Washington D.C.,USA:IEEE Press,2011:121-132.

[10] YONGSUB L,LEE W J,CHOI H J,et al.Discovering large subsets with high quality partitions in real world graphs[C] //Proceedings of International Conference on Big Data & Smart Computing.Washington D.C.,USA:IEEE Press,2015:186-193.

[11] 任曉龍,呂琳媛.網絡重要節點排序方法綜述[J].科學通報,2014,59(13):1175-1197.

[12] FREEMAN L C.A set of measures of centrality based on betweenness[J].Sociometry,1977,40(1):35-41.

[13] BONACICH P.Factoring and weighting approaches to status scores and clique identification[J].Journal of Mathematical Sociology,1972,2(1):113-120.

[14] PARSONS T D.The search number of a connected graph[C]//Proceedings of the 9th Conference on Combinatorics,Graph Theory,and Computing.Winnipeg,Canada:[s.n.],1978:549-554.

[15] NEWMAN M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409.

[16] BORGATTI S P,MEHRA A,BRASS D J,et al.Network analysis in the social sciences[J].Science,2009,323(5916):892-895.

[17] 羅由平,周召敏,李麗娟,等.基于冪率分布的社交網絡規律分析[J].計算機工程,2015,41(7):299-304.