融合高階信息的社交網絡重要節點識別算法

閆光輝，張萌，羅浩，李世魁，劉婷

（蘭州交通大學電子與信息工程學院，甘肅 蘭州 730070）

1 引言

信息技術的多元化發展，使人們日常交流、互動的形式趨于多樣化，由此產生了海量的社交網絡數據[1]。社交網絡數據存在著大量人和人之間的交互信息，在這些數據中挖掘具有影響力的節點能夠幫助人們在理解傳播模式的基礎上，更好地引導或阻止信息的傳播。

節點重要性是節點影響力、地位或者其他因素的表現形式之一[2]。節點的重要性評價方法大體可以分為以下4 類。1)基于節點近鄰的排序方法，這類方法主要關注節點的鄰居信息。例如度中心性（DC,degree centrality）[3]，它是根據一個節點的鄰居數目來判斷該節點的影響力，這種方法能夠簡單直觀地刻畫節點的重要性。但是，由于沒有考慮網絡的全局結構，在多數情況下不夠精確[4-6]。2)基于路徑的排序方法，此類方法中，節點在傳遞過程中的重要程度決定著節點的重要性[4]。介數中心性（BC,betweenness centrality）[7]和接近中心性（CC,closeness centrality）[8]是基于路徑的2 種經典方法。BC 通過在2 個節點之間所有的最短路徑中計算某個節點的路徑占總路徑的比例，來刻畫該節點在網絡中的控制能力[4]。CC 通過一個節點與網絡中其他節點的平均距離得到節點的重要性。CC 值越大，說明該節點在網絡中對控制信息的流動越有意義[4]。雖然它們通過全局結構更好地識別了影響力更大的節點，但是計算復雜較高，很難應用于大規模網絡。3)基于特征向量的排序方法，主要代表有PageRank 算法[9]和LeaderRank 算法[10]。它們通過模擬用戶上網瀏覽網頁的過程，使節點的分值沿著訪問路徑增加，來識別網頁重要性[4]。4)基于節點移除和收縮的排序方法，其特點是網絡的結構會隨著重要節點排序的過程處于動態變化中，節點的重要性通過該節點被移除之后對網絡的破壞程度來體現[4]。

盡管上述文獻針對不同情況對網絡中節點的重要性進行了度量，但是它們都是以節點和邊為基本單元的研究方法。這些方法都忽略了在真實社交網絡中存在于節點之間的高階關系。大量研究表明，社交網絡包含著豐富的子圖結構，這些子圖結構內部具有一定的傳遞性、交互性、平衡性等特性。人們一般將這種子圖結構描述成網絡模體或者圖元結構[11-14]。同時，相較于以點和邊為研究對象的低階結構，這種以小子圖結構為研究單元的網絡結構被稱為高階網絡結構[15]。自2002 年模體的概念被提出后，人們的研究大多著眼于如何高效地統計網絡中模體的數量；直到2016 年，Benson 等[15-16]證明模體可以用于圖聚類和社團發現，并提出了一系列的理論基礎，高階網絡的研究成為當前研究的重點之一。

為了定量地度量社交網絡中節點的重要性，本文將模體作為節點之間高階關系的研究單元，采用高階網絡分析方法得到基于模體的加權鄰接矩陣，進而給出高階度定義，將節點度和高階度這2 個獨立的信息源融合得到新的基本概率指派，并結合半局部中心性的思想，得到基于高階結構的重要節點識別方法。最后，在3 個真實社交網絡上檢驗不同重要節點識別方法得到的節點影響力程度。

2 相關概念

2.1 復雜網絡中的高階結構

模體是高階網絡結構的一種表現形式[17]。將原始網絡表示為高階網絡結構過程如下。首先，在網絡中選定模體，此時，在指定階數的模體集合中，選取原始網絡中出現次數最多的連接形式。文獻[17]指出，針對不同領域，網絡中呈現的高階連接結構各有偏重，結合社會學的相關理論選取三階模體作為研究對象[18-19]。圖1 列舉了三階模體的所有存在形式。選定模體階數后，再對所選階數的模體逐個進行統計，最終選出原始網絡中出現次數最多的模體連接形式。本文采用文獻[20]提出的模體檢測算法來統計網絡中模體的數量。

圖1 三階網絡模體的所有存在形式

定義1網絡模體（network motif）。用一個元組(B,A)表示由k個節點組成的模體。其中，B是k×k的二進制矩陣，矩陣B中的元素代表節點之間是否有連邊，A 是一個目標節點的集合，A?{1,2,…,k}。一般而言，選取的目標節點是B中所有的節點。圖2 表示由3 個節點組成的模體M7。

圖2 模體7M 的定義

定義2基于模體的鄰接矩陣（motif-based adjacency matrix）。給定一個模體M，模體鄰接矩陣可以定義為矩陣元素wij為在G中節點對(vi,vj)在選定的模體中出現的次數，可定義為

定義3高階網絡（higher-order network）。高階網絡可以表示為G=(V,E,WM)，其中，表示點集，…,m}表示弧集，eij是一條由節點vi指向節點vj的有向邊，WM是基于模體M 的加權鄰接矩陣。

在社交網絡中識別重要個體可以轉化為識別用戶之間關系構成的圖中重要節點的問題。同時，文獻[17]指出在不同的場景下，模體的主要存在形式各有偏重。本文以社交網絡為研究對象，結合社交網絡中三元必包的理論，選取三階模體中1M～7M 這7 種存在形式作為基本研究單元。

2.2 D-S 證據理論

D-S 證據理論本質是對概率論的一種推廣，將概率論中的基本事件空間拓展到基本事件的冪集空間，以便更好地表達事件的不確定性，并在其上建立基本概率指派函數[21-22]。本節內容給出辨識框架以及它的冪集這些概念，并將其拓展到網絡中的節點上[5]。

定義4辨識框架（frame of discernment）。Θ={θ1,θ2,…,θ N}是由N個兩兩互斥的元素組成的有限完備集合，則稱Θ為辨識框架。辨識框架是所考察判斷的事物或對象的全體集合Θ。Θ的冪集2Θ所構成的集合表示為

本文將網絡中節點是否重要作為考察判斷的對象。因此，節點的辨識框架可以定義為其中h和l分別表示節點重要和不重要這2 個互斥的元素。

定義5基本概率指派（BPA,basic probability assignment）。設Θ是辨識框架，Θ的冪集2Θ構成命題集合2Θ，?A?Θ，若函數m:2Θ→[ 0,1]滿足以下2 個條件

則稱m為基本概率指派，m(A)為命題A的基本概率數，即準確分配給A的信度。

定義6Dempster 組合規則。設m1和m2為兩組基本概率指派，對應的焦元分別為A1,A2,…,Ak和B1,B2,…,Bl，用m表示m1和m2組合后的新證據。Dempster 組合規則表示為

2.3 半局部中心性

半局部中心性（SCL,semi-local centrality）是一種基于半局部信息的節點重要性排序方法，它不僅考慮了節點的直接鄰居，還考慮了直接鄰居的一階、二階鄰居數，即最多涉及節點的四階鄰居信息[23]。節點vi的計算過程為

其中，N(k)是節點vk的兩層鄰居度和，其值等于從vk出發兩步內可到達的鄰居的數目；Γ(i)是節點vi的一階鄰居節點集合，Γ(j)是節點vj的一階鄰居節點集合。

可見，高階網絡分析方法可以更加具體地表達節點之間的交互關系，在算法復雜度上也有一定的優勢。因此，需要考慮如何將高階信息融合在證據理論中，以達到刻畫節點重要性這個模糊概念的目的。

3 基于高階結構的中心性算法

本節先定義了高階網絡中高階度的概念，再規定2 個基本的獨立信息源，最后將這2 個獨立信息源用作證據理論的BPA，融合得到一種高階證據中心性度量方法。簡單來說，該方法不僅考慮了節點的度，還將節點參與網絡的程度，即節點的高階度作為考慮因素。隨后，結合半局部中心性的思想對算法進一步優化。相比之前的方法，本文提出的算法不僅考慮了多個節點之間存在的高階結構，并且結合了半局部中心性的思想。

3.1 高階度

定義7高階度（higher-order degree）。節點vi在選定的模體中出現的次數，即在模體鄰接矩陣中節點vi在第i行或第i列最大的元素值，記為HDi，即

在高階網絡中，模體鄰接矩陣刻畫的是節點對(vi,vj)的局部連接密度，其權值越高表示以節點對(vi,vj)為邊的模體結構越多，說明該節點對的抗攻擊性越差，重要性也就越高。因此，高階度反映的是節點所在邊參與網絡的程度。

3.2 定義2 個基本概率指派函數

本文將節點的度和高階度看作2 種重要性指標，由不同的獨立信息源可以得到關于度和高階度的2 個基本概率指派函數。此時，節點vi的2 個基本概率分布分別為

文獻[24]用網絡中的度分布，對基于度的基本概率指派函數進行改進，得到了一種更符合真實情況的概率指派函數，避免了證據理論計算所得到結果是均勻分布，而真實網絡中的節點呈冪律分布這一沖突。因此，基于度和高階度的BPA 通過式(8)～式(11)計算得到。

其中，σ和δ分別通過式(12)和式(13)計算得到。

此時，0＜μ,ε1≤ 。文獻[5]指出和ε 的取值對節點的排序沒有影響。

引入Dempster 證據合成規則，將節點的度和高階度融合在一起形成一個新的指標M(i)。

通過式(4)分別計算節點重要的基本概率指派mi(h)、節點不重要的基本概率指派mi(l)和不確定節點是否重要的基本概率指派m i(θ)。通常情況下，為了計算方便將m i(θ)的值平分給mi(h)和mi(l)，得到M i(h)和M i(l)。此時，Mi(h)和M i(l)分別代表節點重要和節點不重要的信任程度。對于一個節點來說，M i(h)越大，同時M i(l)越小，節點的重要性就越大[5]。

3.3 高階證據中心性

在上述定義的基礎上，提出節點的高階證據中心性（HEC,higher-order evidence centrality）方法。HEC通過節點的重要程度和不重要程度的差值來表示

為了確保數值為正，對式(15)進行歸一化處理，即

例1圖3 所示是一個簡單的有向無權圖。根據上述定義計算圖3 中每個節點的高階證據中心性值。選取圖3 中模體存在形式最多的一種，即7M 。表1 為例1 中所有節點計算高階證據中心性所需要的相關指標及高階證據中心性值。本文取μ和ε 的值為0.15。

圖3 有向無權圖的例子

表1 高階證據中心性計算

3.4 高階證據半局部中心性

通過上述計算，得到了網絡中每一個節點的高階證據中心性值。為了更精確地表達節點在網絡中的傳遞性，結合半局部中心性的思想，計算網絡中每一個節點的直接鄰居和直接鄰居的兩層鄰居HEC(i)的和。因此，高階證據半局部中心性（HESC,higher-order evidence semi-local centrality）為

基于高階結構的HESC 重要節點識別算法如算法1 所示。

算法1HESC 重要節點識別算法

輸入有向網絡G=(V,E)

輸出原始網絡中每個節點的HESC 值

1)統計G中的模體，選取模體數量最多的形式M；

2)得到基于M 的加權鄰接矩陣WM；

3)for nodeiinVdo:

4)根據式(6)得到HDi；

5)根據式(7)～式(16)計算HEC(i)；

6)根據式(17)計算HESC(i)；

7)end for

8)returnV中每個節點的HESC 值

對于給定的G，網絡中節點的個數為n，邊的個數為m，文獻[20]提出統計原始網絡中模體個數的算法，該算法的復雜度為O(m1.5)。半局部中心性由于計算N(k)需要在2 個步驟中遍歷節點vk的鄰居，因此，時間復雜度為O(n＜k＞2)，即同時考慮了節點直接鄰居的一階和二階鄰居數，其中＜k＞為網絡的平均度。證據理論只是在節點本身進行計算，時間復雜度為O(n)。所以，HEC 的時間復雜度為O(m1.5+n)，HESC 的時間復雜度為O(m1.5+n＜k＞2)。表2 給出了本文用到的各算法的時間復雜度。從表2 可以看出，BC 和CC 的時間復雜度過高，不適合大規模網絡。

表2 各算法時間復雜度

4 實驗

本文采用SIR 模型對上述提出的基于高階結構的中心性算法進行評價。文獻[4]指出SIR 模型是一種基于傳播動力學的評價方法，被廣泛應用到評價各種節點重要性挖掘方法中。在SIR 模型中，一般通過節點的傳播范圍和達到穩態時所用的時間作為節點重要性的評判標準。

4.1 SIR 傳播模型

SIR 傳播模型中的節點在任意時刻都有3 種可能的存在狀態：易感染態（S,susceptible）、感染態（I,infected）和恢復態（R,recover）。在t迭代步，這3 類人在人群中的比例分別用S(t)、I(t)和R(t)表示[25]。S(t)代表在一個網絡中處于S 狀態的節點占比；I(t)代表處于I 狀態且能向S 狀態節點傳播疾病的節點占比，每一個被感染節點都可以通過一定的概率隨機地向它的鄰居節點傳染疾病；R(t)表示感染過疾病但已經恢復且具有免疫能力的節點占比[25]。在復雜網絡SIR 模型中，假設被感染的節點周圍所有的鄰居節點都有機會被感染。在第t個時間迭代步，感染態和恢復態的節點在整個網絡中所占的比例F(t)作為傳播范圍衡量指標。F(t)隨迭代次數t的增大而增大，最后趨于穩定。

4.2 數據集描述

Wiki-vote：維基百科為了從用戶中選舉出詞條管理員，通過公開投票的方式選舉。該數據集構建的是維基百科用戶之間的投票關系網絡。網絡中的節點代表的是維基百科的用戶，有向連邊是由投票人指向被選舉人。

Advogato：該數據集構建的是Advogato 這個在線社交平臺上用戶信任關系的有向網絡。網絡中的節點是Advogato 中的用戶，有向邊為用戶之間的信任關系。

soc-Epinions1：該數據集描述的是消費者在評論網站上的信任關系，是否信任對方由網站上的成員自行決定。由此形成的信任關系網絡，可以有針對性地向用戶展示消費者的評論。網絡中節點代表的是消費者，有向邊是消費者之間的信任關系。

表3 展示了上述提到的3 個數據集中節點、邊數和模體總數的具體情況。

表3 數據集的統計量

同時，對上述3 個數據集上1M～7M 各個模體的數量進行統計。表4 列舉了1M～7M 的具體數量。可以看出，本文選取的數據集中模體出現次數最多的形式恰好都是5M 。因為Wiki-Vote 數據集描述的是用戶之間的投票關系，5M 可以解釋為用戶更愿意給自己投過票的人所選舉的對象再投出一票。Advogato 和soc-Epinions1 數據集是用戶之間的信任關系，5M 可以解釋為當一個用戶選擇信任另一個用戶時，后者所信任的用戶會作為前者信任的參考對象。因此，在這3 個數據集上選取5M 對原始網絡進行處理，得到基于模體5M 的加權鄰接矩陣。

表4 各個數據集中M1～M7的數量

4.3 實驗方法介紹

為了比較各排序算法之間的差異性和傳播能力，本文選取了經典排序算法DC、BC 和CC 與本文提出的算法進行比較。首先得到各個算法的節點排序，選取各個算法在不同網絡上節點排序的Top10、Top20、Top50 和Top100，然后將這些TopN節點作為初始傳染源在SIR 模型上進行傳播，最后比較傳播范圍及達到穩態時所用的時間。

4.4 實驗結果分析

將3 個數據集上各方法排序中的Top10、Top20、Top50 和Top100 作為SIR 模型中的傳染源進行傳播，并比較各方法傳播的差異性，如圖4～圖6 所示。

圖4 Wiki-vote 數據集TopN 節點的傳播

圖5 Advogato 數據集TopN 節點的傳播

圖6 soc-Epinions1 數據集TopN 節點的傳播

圖4 是Wiki-vote 數據集上各種方法在SIR 模型上的傳播。Top10 節點作為傳染源進行傳播時，本文提出的中心性方法HEC 和HESC 在傳播范圍和傳播速率上基本與DC 相似，如圖4(a)所示。但是，從圖4(b)～圖4(d)可以看出，隨著傳染源節點的增加，HESC 不管是在傳播速率還是傳播范圍上都好于傳統的度量方法，并且網絡達到穩態時所用的迭代步最少。

Advogato 數據集上將各種方法得到的節點排序在SIR 模型上傳播，可以看出，本文提出的HESC不管是在傳播范圍還是傳播速率都優于經典的方法，如圖5 所示。同時還可以看出，本文提出的HESC所得到的排序與BC的結果最為相似。而HEC的方法傳播速率和傳播范圍卻相對較差，可能是因為在此數據集中各個模體之間的數量比較接近（如表4 所示），此時以網絡中個數最多的模體作為分析對象體現不出該方法的優勢。

圖6 展示的是soc-Epinions1 數據集上各種方法通過不同TopN節點進行傳播的差異性。可以看出，Top10 節點作為傳染源進行傳播時，HESC 的傳播范圍和傳播效率都比其他方法好，如圖6(a)所示。但是，隨著傳染源節點的增多，HESC 的優勢逐漸減退，BC 的傳播范圍和傳播速率優勢突顯，如圖6(b)～圖6(d)所示。

對上述不同數據集實驗結果分析，雖然本文方法HESC 能夠篩選出更重要的節點，但是針對不同的網絡存在一定的差異性。在soc-Epinions1 網絡中只有當選取Top10 節點作為傳染源時，傳播能力才會好于其他排序結果，其原因可能是該網絡中強連通子圖連接的節點比較多，而BC 是基于路徑的排序方法。所以，當選取的傳染源節點較多時，BC的優勢就顯現出來。

圖7 展示的是靜態攻擊下從網絡中移除TopN節點時，網絡中最大連通子圖相對大小的變化。橫坐標表示從網絡中移除TopN節點，縱坐標表示網絡中最大連通子圖的相對大小。最大連通子圖的相對大小是強連通子圖連接的節點個數占總節點數的比例。可以看出，當移除TopN節點時，BC 得到的節點排序相較于HESC 對網絡的破壞程度更大，所以才會出現圖6 中隨著傳染源節點的增加，BC的傳播能力好于HESC 的現象。

表5 列舉的是在soc-Epinions1 網絡上，各種方法得到的Top10 節點。本文通過Top1 節點在原始網絡中的自我中心網絡展示其在網絡中的重要程度，如圖8 所示。自我中心網絡是指以一個節點為中心，由其直接相連的節點和這些節點之間的連邊組成的網絡結構[26]。圖8 中處于中間位置直徑較大的節點是各種方法得到的Top1 節點，即v18、v44和v645，周圍直徑較小的節點是Top1 節點的出度所相連的節點。顯然，本文提出的中心性方法得到的節點連接了更多的節點，即在網絡中所處的位置更為關鍵。同時，在soc-Epinions1 數據集上，本文提出的方法與BC 方法更為接近的現象也得以說明。

圖7 靜態攻擊下的最大連通子圖相對大小

表5 soc-Epinions1 數據集Top10 節點

5 結束語

高階網絡作為一種中尺度的網絡結構，相較于從宏觀和微觀層面入手的研究，高階網絡考慮了節點之間的交互性、傳遞性等因素。因此，可以更精確地描述網絡內部連接的特定模式，同時簡化了網絡結構。本文主要基于高階結構提出了重要節點識別算法。該方法以D-S 證據理論為理論基礎，融合了高階網絡分析方法，同時，考慮了網絡的度分布、半局部中心性。在3 個真實社交網絡數據集上，用SIR 模型評價該方法得到的節點重要程度，并與傳統的中心性度量方法（DC、BC 和CC）進行對比。通過實驗結果分析，本文所提的重要節點識別算法與其他典型的算法相比較，可以更加精確地識別網絡中的重要節點。

圖8 soc-Epinions1 的各種方法Top1 節點的自我中心網絡

本文的工作雖然在有向網絡上結合了高階網絡分析方法，得到了節點重要性排序，但仍然缺乏對有向網絡上節點重要性因素的綜合考慮。因此，進一步的工作可以考慮如何將交互行為在時間上的差異性作為影響節點重要程度的因素，以及度量網絡拓撲結構隨時間的變化與節點在網絡中影響力的關系。