王笑顏，陳伯倫，許 雪，王 凌，劉曉孌，王珊珊

（淮陰工學院 計算機與軟件工程學院,江蘇 淮安 223003）

在自然界和社會中,許多復雜的系統(tǒng)都可以用網絡和圖來描述,在復雜網絡中挖掘關鍵節(jié)點作為其主要研究方向,目的是為了發(fā)現在網絡結構和信息傳遞過程中起著重要作用的節(jié)點［1］。當出現新思想或新行為時,人們對新事物的接受程度受到周圍人的影響,這些新事物可能很快消亡,也可能形成廣泛深入的影響,這與影響該行為的關鍵傳播節(jié)點的影響力有直接關系［2］。因此在復雜網絡的研究和實踐中分析網絡中各節(jié)點的重要性進而挖掘關鍵節(jié)點具有重要意義。在網絡影響力傳播的過程中,具有影響力的節(jié)點也就是重要節(jié)點,指的是能夠引發(fā)信息進行廣泛的傳播或阻止擴散的節(jié)點。影響力最大化是從復雜網絡中確定一小組有影響的節(jié)點,以最大化激活節(jié)點的數量。由于選擇種子節(jié)點的準確性、穩(wěn)定性和時間復雜度等關鍵問題,近十年來出現的大多數影響力最大化算法都遇到了挑戰(zhàn),例如缺乏最佳種子節(jié)點選擇,不合適的影響力傳播和高時間復雜度［3］。

目前許多學者正對網絡中重要節(jié)點的挖掘展開研究,Liu 等［4］提出了一種基于改進結構洞和K殼分解算法的重要節(jié)點識別算法,用于識別復雜網絡中影響安全的重要節(jié)點,并且在考慮網絡的全局結構的基礎上,提出了一個基于節(jié)點度和最近鄰域信息的無網絡組織先驗知識的重要節(jié)點的網絡安全評價指標。陳文杰等［5］提出一種基于節(jié)點向量表示的模糊社區(qū)劃分算法,該方法由節(jié)點重要性引導的隨機游走策略生成節(jié)點序列,通過最大化模塊度得到最佳的社區(qū)數目。對于PageRank方法結果過于集中,未考慮復雜網絡社區(qū)結構特性的問題,王安等［6］提出了一種基于復雜網絡社區(qū)劃分的節(jié)點重要性排序方法CD-PR,將社區(qū)的內外連接關系轉化為社區(qū)選擇的概率表示,得到關鍵節(jié)點排序結果。從社區(qū)結構上來看,鄭黎黎等［7］采用分裂算法中的GN 算法,提出道路交通網絡模塊度函數實現路網區(qū)域劃分。Jing 等［8］研究了目標影響最大化問題,提出了一種基于索引的MSTIM 問題求解方法,實現了MSTIM 的高效求解。目前,經典的社區(qū)劃分算法已經不能滿足需要,因此本文采用改進的社區(qū)劃分算法挖掘重要節(jié)點,旨在提高節(jié)點的傳播效率。

過去的若干年中,學者都在節(jié)點特征的基礎上進行關于重要節(jié)點的挖掘,卻忽略了節(jié)點之間的重疊影響力。本文針對此問題在使用GN 方法進行社區(qū)劃分的基礎上,提出了社區(qū)重要性的概念并對節(jié)點進行識別和排序,同時也考慮了邊的差異和節(jié)點的PR 值對節(jié)點排序的影響。為了評估該算法是否有效,我們應用獨立級聯（Independent Cascade Model,IC）模型模擬了真實網絡中的擴散過程,通過實驗對節(jié)選出的節(jié)點傳播能力進行測評。實驗結果表明,該方法節(jié)選出的節(jié)點傳播效率較高,在控制節(jié)點的傳播方面具備較好的優(yōu)勢,在識別傳播能力強的節(jié)點方面比其他方法更加有效。

1 算法描述

本文對復雜網絡中節(jié)點的挖掘問題用圖的結構來進行模擬,提出了一種改進的網絡重要節(jié)點挖掘算法GN-PR（Girvan Newman and PageRank,GN-PR）,該算法首先通過GN 算法對圖進行社區(qū)劃分,其次從每個社區(qū)內部計算節(jié)點的PR 值,接下來將PR值最大的節(jié)點選為首位節(jié)點,最后按照社區(qū)的重要程度對節(jié)點進行排序輸出。算法的流程如圖1所示。

圖1 算法流程圖

1.1 詳細描述

1.1.1 基于GN算法的社區(qū)劃分

本文選用的GN 算法是基于邊介數的方法。某邊的邊介數的定義是網絡中全部節(jié)點間的最短路徑經過該邊的次數。網絡中有社團內部關系比較緊湊、社團之間關系比較疏松的特點,根據這個特點來逐次刪除社團之間的邊,獲得關系比較緊湊的社團結構［7］。GN算法的根源就是基于這種思想,逐次刪掉邊介數最大的邊,直至完全淘汰全部的邊,最終在特定的模塊度條件下,取得效果最優(yōu)的網絡社區(qū)結構。Girvan和Newman提出模塊度Q的概念的目的是為了描述社區(qū)劃分的成功程度,能夠對社區(qū)模塊化地進行描述。對一個能夠表示為n×n矩陣的無向網絡,對Q函數模塊化如下：

其中,i 表示第i 個社區(qū),eii 代表社區(qū)i 的邊占最初網絡全部邊的比例,ai代表全部將社區(qū)i中的頂點連接起來的邊占總邊數的比例。

經過持續(xù)的迭代運算,得到模塊度最大的情 況并完成社區(qū)劃分（見表1）。

表1 社區(qū)劃分步驟

1.1.2 使用PageRank算法進行社區(qū)內部節(jié)點的排序

PageRank算法屬于圖數據上的無監(jiān)督學習方法。Google 公司首先提出了網頁重要性的排序算法——PageRank 算法,算法主要根據網頁之間的超鏈接關系對網頁的重要程度進行評估。本文中的節(jié)點指的是概念中的網頁,邊指的是網頁間的超鏈接,則PageRank 算法是指有向網絡中在對節(jié)點重要性進行評價的基礎上挖掘這之中的關鍵節(jié)點。計算公式為：

DPR（i）為節(jié)點i 的PageRank 值,d 為阻尼因子,0

PageRank 是遞歸定義的,PageRank 可由迭代算法進行計算,PR 值必須經由多次循環(huán)迭代才能達到一個穩(wěn)定值。如果某節(jié)點與其它節(jié)點之間沒有出鏈,這就是Spider Traps,這將導致節(jié)點偏移（經過多輪迭代后,沒有出鏈的節(jié)點的權重越來越大,趨近于1）,需要對M進行修正：

其中β表示跟隨出鏈打開節(jié)點的概率；1-β表示隨機轉到其他節(jié)點的概率；eeT表示由1 填滿的n×n矩陣。

計算每個節(jié)點的PageRank值并按從大到小的順序排序,選擇每個社區(qū)內PR 值最大的節(jié)點（見表2）。

1.1.3 根據社區(qū)重要性進行節(jié)點的挖掘

根據社區(qū)內節(jié)點數量進行社區(qū)重要性評估,每個社區(qū)的種子節(jié)點數量集合跟社區(qū)的重要性成正比,社區(qū)內的種子節(jié)點數越多,說明本社區(qū)的重要性越大。最后將每個社區(qū)中PR 值最大的節(jié)點再根據社區(qū)的重要性進行從大到小的順序排序輸出,得到最終的節(jié)點序列（見表3）。

表3 社區(qū)重要性算法步驟

1.2 影響力傳播模型

獨立級聯IC 模型（Independent Cascade Model）最初為一個概率模型。在IC模型中的信息擴散過程如下：

1）當節(jié)點u在t時刻被激活后,在最初的活躍節(jié)點集合A 中,節(jié)點u 就可以產生一次對u 的鄰居節(jié)點w作出影響的機會,成功的概率是pu,w,其為隨機賦予的參數,其他節(jié)點對它產生不了影響,參數值越大,節(jié)點w被影響的概率越大。

2）如果新被激活的節(jié)點都是w 的鄰居節(jié)點,那這些節(jié)點會以隨機次序嘗試激活節(jié)點w。若節(jié)點u 把節(jié)點w 激活,則節(jié)點w 可以在t+1 時刻變成活躍狀態(tài)。

3）當處于t+1時刻,其他節(jié)點將會被w影響,重復上述過程。

在上述傳播中,不管節(jié)點u 的鄰居節(jié)點在t 時刻是否能被激活,在之后的過程中,u 本身即使一直是活躍狀態(tài),但也不再有影響力,沒有任何影響力的活躍節(jié)點就是指這類節(jié)點。當網絡中不再有具備影響力的活躍節(jié)點時,結束傳播。

1.3 影響力傳播評價指標

在影響力的傳播過程中,需要選取傳播能力較高的節(jié)點集合,這樣可以在有限的成本下最大化的完成節(jié)點的傳播。本文設計了選擇重要節(jié)點的有效方法,為了評估節(jié)點的傳播能力,我們將感染的節(jié)點數量與迭代次數的比值定義為傳播效率,計算公式為：

其中Eff表示節(jié)點的傳播效率,vol為感染的節(jié)點總數量,N為迭代的次數。

2 結果與分析

2.1 實驗環(huán)境及數據集

算法使用的開發(fā)語言為python,利用python中的networkx 編程語言軟件包對復雜網絡進行創(chuàng)建和操作。在Windows10系統(tǒng)上進行訓練和測試,硬件環(huán)境為i7-1165G7 CPU @2.80GHz、NVIDIA GeForce GTX 1650 Ti with Max-Q Design,顯卡的共享內存為16G,能夠滿足深度學習的最低要求。

實驗采用了兩個公共數據集,分別為polbooks數據集和football 數據集。polbooks 數據集,是由V.Krebs從Amazon上銷售的美國政治相關書籍頁面上建立起來的網絡［9］。該數據集中包含105 個點和441 條邊,其中每一個節(jié)點代表一本在Amazon上銷售的政治類書籍,節(jié)點之間的連邊代表兩本書被同時購買的可能性高［10］。該網絡的節(jié)點被分為l、n和c三類,分別代表“自由派”、“保守派”和“中間派”。football數據集是根據美國大學生足球聯賽而創(chuàng)建的一個復雜的社會網絡。該網絡包含115個節(jié)點和616條邊,每一個節(jié)點代表一只球隊,節(jié)點之間的連邊代表球隊之間曾經進行過比賽,由于球隊屬于不同的州,每個州內的比賽場次多,因此該網絡被分為12個社區(qū)［10］。

對網絡社團結構的研究來自于社團學,已經歷經了很長時間。社團結構分析與計算機科學中的圖分割和社會學中的分級聚類密不可分,并且在大規(guī)模的復雜網絡中尋找社區(qū)或者發(fā)現社區(qū)的過程中,可以符合客觀條件的使用。

2.2 實驗結果

GN-PR的總體算法思想是首先對圖進行基于GN方法的社區(qū)劃分,其次使用PageRank算法在每個社區(qū)內部進行節(jié)點的排序,最后根據社區(qū)重要性進行節(jié)點的挖掘。為了驗證算法的性能,我們使用polbooks和football兩個數據集進行實驗。

2.2.1 社區(qū)劃分的結果示意圖

圖2 為polbooks 數據集的可視化結果,該數據集中包含105 個點和441 條邊；圖3 為football 數據集的可視化結果,該數據集中包含115 個節(jié)點和616 條邊。（a）（c）分別為polbooks 網絡和football 網絡的原始結構示意圖,根據GN 算法進行社區(qū)劃分,可視化結果如（b）（d）所示,其中社區(qū)以不同顏色進行區(qū)分,在Q 值最大的情況下,polbooks 網絡中實驗結果顯示網絡被劃分為四個社區(qū),football網絡被劃分為五個社區(qū)。

圖2 polbooks數據集

圖3 football數據集

2.2.2 節(jié)點排序輸出

在社區(qū)劃分的基礎上,我們在每個社區(qū)內部使用PageRank 算法計算每個節(jié)點的PR 值并按從大到小的順序排序,選出每個社區(qū)內PR值最大的節(jié)點,接下來統(tǒng)計每個社區(qū)內的節(jié)點數目,根據節(jié)點數目的大小對社區(qū)進行排序,在社區(qū)排序的基礎上,對每個社區(qū)內的首位節(jié)點進行排序。

表4 和表5 中為分別使用polbooks 數據集和football 數據集實驗的結果,根據緊密中心性（Closeness Centrality）、隨機選?。╮andom）、PR（PageRank）值和GN-PR 方法對節(jié)點進行排序,每列為按照降序排序節(jié)選出的節(jié)點ID。

表4 polbooks數據集節(jié)選出的節(jié)點

表5 football數據集節(jié)選出的節(jié)點

2.2.3 節(jié)點重疊影響力

表6 分別為polbooks 和football 數據集在進行獨立感染模擬后,感染節(jié)點交集數量的平均值。為了測試節(jié)點重疊影響力,我們使用IC 模型對節(jié)點進行獨立感染,對于每個被感染的節(jié)點,以0.15的概率感染周圍的節(jié)點,模擬次數為100。我們將被感染多于1次和2次的節(jié)點數量都取了平均值,P1：被感染多于1次的節(jié)點數量的平均值；P2：被感染多于2次的節(jié)點數量的平均值；雖然每次的測試具有隨機性,但本文GN-PR 方法的交集數量取平均后基本都小于其他方法的平均交集數量,因此GN-PR方法在節(jié)點的重疊影響力方面進行了一定程度的削弱。

表6 不同算法在不同數據集中的節(jié)點重疊影響力

2.2.4 評估節(jié)點傳播能力

針對實驗數據,本文引用節(jié)點的傳播效率作為影響力最大化的評價指標,使用獨立級聯模型（IC 模型）在polbooks 數據集和football 數據集中進行驗證,測試重要節(jié)點的傳播程度。為了測試GN-PR算法的性能,我們和傳統(tǒng)的算法：隨機選?。╮andom）、PR（PageRank）、緊密中心性（Closeness Centrality）進行了比較。本算法傳播效率與其他三種算法傳播效率對比示意圖如圖4所示。

圖4 不同算法在polbooks數據集（a）和football數據集（b）中實驗結果比較

由圖4 可以看出,隨著感染次數的增加,感染節(jié)點的數量也在增加。雖然經過有限的迭代之后所有節(jié)點基本都可以被成功感染,但在節(jié)點全部被感染之前,相同的迭代次數下,與傳統(tǒng)算法相比,本文提出的GN-PR 算法感染的節(jié)點數最多。復雜網絡中節(jié)點的傳播模型采用獨立級聯模型（IC 模型）,可視化節(jié)點的傳播能力如圖4 所示,其中橫坐標代表關鍵節(jié)點感染的迭代次數,縱坐標代表關鍵節(jié)點感染的節(jié)點數目?？梢钥闯?在相同的迭代次數中,GN-PR 算法效率最高。本文的實驗數據在網絡上取得了很好的結果,節(jié)點的傳播效率得到了明顯的提高,實驗結果表明GN-PR算法傳播效率最優(yōu)。

3 總結與展望

本文研究了復雜網絡中重要節(jié)點的挖掘問題,它在網絡中傳播或抑制都起著重要作用。本文首先使用GN算法進行了社區(qū)劃分,將節(jié)點劃分為多個集合。通過這種劃分,本文可以將整體節(jié)點排序轉化為局部節(jié)點排序。然后,在每個社區(qū)內部通過PageRank算法,選出每個社區(qū)內PR值最大的節(jié)點,通過節(jié)點的數量來計算社區(qū)的重要性,最后根據社區(qū)重要性進行節(jié)點的排序輸出。雖然基于社區(qū)性質的影響力最大化算法在某些網絡中可以取得比較好的效果,但是顯然這些算法也存在一些缺點,有的網絡具備明顯的社區(qū)結構,有的網絡社區(qū)結構并不明顯,而且還有網絡存在社區(qū)重疊現象的可能,所以有些網絡可能用GN-PR 算法效果并不明顯。通過節(jié)點數量來評判社區(qū)重要性,對于很多數據集并不適用,在進一步的研究中還需要一些更有效的改進。節(jié)點的排序輸出有很多拓展的可能性,也有很多應用場景,比如最優(yōu)路徑的選擇、微博信息推送等。與各種傳統(tǒng)的算法實驗比較表明,經過本文算法得到的重要節(jié)點,在復雜網絡中可獲得高效率的傳播。