基于重要節(jié)點刪除法的社會網(wǎng)絡(luò)層次結(jié)構(gòu)分析

王 魁,馬 宏,黃瑞陽

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

0 概述

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

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

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

為利用節(jié)點的層次性特征分析社會網(wǎng)絡(luò)結(jié)構(gòu),本文提出一種改進的基于重要節(jié)點刪除的網(wǎng)絡(luò)分解方法對網(wǎng)絡(luò)結(jié)構(gòu)進行劃分。

1 相關(guān)工作

1.1 節(jié)點介數(shù)定義

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

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

一個節(jié)點的介數(shù)中心性可以表示為所有最短路徑中經(jīng)過該節(jié)點的最短路徑所占比例,定義為:

(1)

用傳統(tǒng)方法計算介數(shù)的時間復雜度為O(n3),n為網(wǎng)絡(luò)中節(jié)點數(shù)量。隨著網(wǎng)絡(luò)規(guī)模的增加,減少算法的計算復雜度成為亟待解決的問題。

1.2 圖的連通分支

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

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

2 基于重要節(jié)點刪除的網(wǎng)絡(luò)層次劃分

根據(jù)復雜網(wǎng)絡(luò)中社團之間普遍存在橋節(jié)點且刪除少量節(jié)點可以使網(wǎng)絡(luò)分解的特點,本文采用基于重要節(jié)點刪除的網(wǎng)絡(luò)分解方法對網(wǎng)絡(luò)層次結(jié)構(gòu)進行分析。

2.1 相關(guān)定義

2.1.1 圖的鄰接矩陣

用鄰接矩陣A來表示一個具有n個節(jié)點的網(wǎng)絡(luò),矩陣中的元素sij表示網(wǎng)絡(luò)中節(jié)點的連接情況,在無權(quán)無向圖中,若sij=0表示節(jié)點i和j沒有連接,sij=1表示節(jié)點i和節(jié)點j有連接。

2.1.2 星型結(jié)構(gòu)及模型

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

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

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

圖1 星型網(wǎng)絡(luò)結(jié)構(gòu)模型

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

2.2 介數(shù)計算方法

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

對于網(wǎng)絡(luò)G,用D1表示所有度為1的節(jié)點集合,R表示所有度為1的節(jié)點的鄰居節(jié)點集合。刪除G中度為1的節(jié)點得到G’,G’中節(jié)點v的介數(shù)表示為:

(2)

任意取一個節(jié)點t’∈D1,恢復其到鄰居節(jié)點t∈R的連接,此時v的介數(shù)變?yōu)?

(3)

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

(4)

同理,當原網(wǎng)絡(luò)中所有度為1的節(jié)點加入后,得到:

(5)

其中,DS表示節(jié)點s所連接的度為1的節(jié)點個數(shù)。

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

圖2 推特網(wǎng)絡(luò)的度分布及刪除度為1節(jié)點后網(wǎng)絡(luò)規(guī)模變化

2.3 基于網(wǎng)絡(luò)分解的鄰接矩陣重排序與網(wǎng)絡(luò)簡化

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

圖3 網(wǎng)絡(luò)分解與鄰接矩陣重排序

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

算法1基于網(wǎng)絡(luò)分解的鄰接矩陣重排序方法

輸入網(wǎng)絡(luò)G的鄰接矩陣A,常數(shù)k、m

輸出重排序后鄰接矩陣B

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

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

while size(GCC)>k

for i ∈GCC

根據(jù)2.2節(jié)算法計算betweenness(i);

end

將節(jié)點按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

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

3 實驗結(jié)果與分析

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

表2 真實社會網(wǎng)絡(luò)數(shù)據(jù)集

3.1 社團屬性未知的網(wǎng)絡(luò)

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

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

圖4 rt-copen網(wǎng)絡(luò)鄰接矩陣重排序結(jié)果

圖5 rt-bahrain網(wǎng)絡(luò)鄰接矩陣重排序結(jié)果

圖6 rt-alwefaq網(wǎng)絡(luò)鄰接矩陣重排序結(jié)果

圖7 rt-dash網(wǎng)絡(luò)鄰接矩陣重排序結(jié)果

3.2 社團屬性已知的網(wǎng)絡(luò)

為了驗證本文算法對社會網(wǎng)絡(luò)結(jié)構(gòu)劃分是否具有實際意義,本文使用屬性已知的Facebook網(wǎng)絡(luò)進行驗證。

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

圖8對比了5種按不同的網(wǎng)絡(luò)鄰接矩陣重排序方法得到的結(jié)果。

圖8 Facebook網(wǎng)絡(luò)的分解情況

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

3.3 算法運行效率

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

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

圖9不同分解方法使網(wǎng)絡(luò)完全分解時移除的節(jié)點數(shù)在網(wǎng)絡(luò)中比例

圖10 傳統(tǒng)介數(shù)計算方法和本文算法的運行時間

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

圖11 不同算法劃分網(wǎng)絡(luò)所用時間

4 結(jié)束語

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

[1] 李曉佳,張 鵬,狄增如,等.復雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)[J].復雜系統(tǒng)與復雜性科學,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] 龐 垠.復雜網(wǎng)絡(luò)社團結(jié)構(gòu)探測方法及社團內(nèi)節(jié)點層次關(guān)系研究[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] 任曉龍,呂琳媛.網(wǎng)絡(luò)重要節(jié)點排序方法綜述[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] 羅由平,周召敏,李麗娟,等.基于冪率分布的社交網(wǎng)絡(luò)規(guī)律分析[J].計算機工程,2015,41(7):299-304.