融合多元信息的多關系社交網絡節點重要性研究

羅 浩 閆光輝 張 萌 包峻波 李俊成 劉 婷 楊 波 魏 軍

1(蘭州交通大學電子與信息工程學院 蘭州 730070)2(國網甘肅省電力公司信通公司 蘭州 730050)

Facebook,Twitter等大規模社交網絡的興起,為社會網絡研究提供了數據支撐,而復雜網絡工具的引入,為社會網絡分析提供了定量基礎.節點重要性研究作為社會網絡分析的關鍵問題之一,迄今發展起來的理論框架主要面向單關系網絡結構.作為一種簡化的網絡科學框架,單關系網絡結構不足以準確刻畫現實世界中相互關聯、彼此依存的復雜系統,即網絡的網絡(networks of networks, NoN),對NoN的研究已逐漸成為復雜網絡分析領域富有挑戰性的研究熱點[1-2].多關系網絡(multi-relational networks)作為NoN的一種典型存在方式,已成為刻畫現實世界各類關系構成復雜系統的常用模型.近年來,國內外學者面向多關系網絡,圍繞基本度量[3-6]、社團結構[7-10]、傳播擴散[11]、譜特征分析[12]等基礎問題進行了大量研究,也形成了較為豐富的理論成果.但針對多關系網絡節點重要性的研究,大多仍是通過構建多個單關系網絡,并通過某種規則進行復合的方式進行建模和分析,這種處理方式會喪失各類關系之間的特定結構信息.如何精確刻畫多關系網絡,探索推廣單個網絡上已有的節點重要性度量方法到多關系網絡中,研究設計符合多關系網絡結構特點和動力學特征的節點重要性分析方法,具有重要的理論價值和應用價值.

本文針對多關系社交網絡的節點重要性問題,著眼于在線社交平臺產生的海量關系數據,通過構建多關系有向網絡模型,應用基于張量代數的多層網絡數學框架對其進行表示和分析,融合刻畫節點中心性、聲望、傳遞性等影響社交網絡節點重要性因素的度量指標,借鑒單關系網絡ClusterRank,IO-ClusterRank等節點重要性方法和基于D-S(Dempster-Shafer)證據理論的信息融合方法,對多關系有向網絡的節點重要性進行了系統研究,提出了面向多關系有向網絡的IOMCR(in-degree out-degree multiplex ClusterRank)和IOMEC(in-degree out-degree multiplex evidential centrality)方法.在4個大規模多關系真實網絡數據集上的實驗結果表明,由于受多關系網絡耦合信息和傳遞機制的影響,直接借鑒ClusterRank和IO-ClusterRank所提出的IOMCR方法,會對節點重要性測量的準確性造成影響,而運用D -S證據理論進行多元信息融合的IOMEC方法能夠有效規避這種影響,相比于其他方法,能夠更加準確地測量節點的重要程度.在時間復雜度方面,相對于IOMCR,IOMEC方法由于引入了信息融合技術,具有更低的時間復雜度.本文所做工作不僅豐富了多關系網絡節點重要性的度量方法,也擴展了多關系網絡的基本度量和D -S證據理論的實際應場景.

1 相關工作

多關系網絡[13]的概念起源于社會學領域,社會學家根據行動者(actor)之間的關系屬性,對網絡中的邊進行分類[14-15].Mitchell[16]將此類網絡稱之為擁有“多重(multi-stranded)”關系的網絡.被用來研究多關系社會網絡的方法包括指數隨機圖模型、元網絡(meta-networks)、元矩陣(meta-matrices),以及通過塊模型(block modeling)和關系代數(relational algebras)來確定社會角色的其他方法等[17-18].但社會學領域所研究的網絡規模相對較小,定量分析復雜度較低,且常采用調查的方法對結果進行統計分析,不適用于大規模網絡.

對大規模多關系網絡進行研究,一個基本問題是如何對其進行建模和表示.隨著復雜網絡分析技術的不斷發展,對于單個網絡,已經建立了較為完備的理論分析框架.鑒于此,對多關系網絡的處理,起初的處理思路是利用“降維”的思想,圍繞特定領域網絡,針對性地運用社會學、可拓學等其他學科理論,通過構建加權網絡的方式將多關系網絡轉化為單關系網絡[19-20]；或是借助矩陣分解、多子網復合等理論方法對已有網絡進行時間劃分或快照處理,對單個網絡分別進行研究后再進行復合[21-22].此類簡化的處理方式,會導致原始數據中包含的特定結構信息和不同類型關系之間關聯信息的喪失,不利于后續研究的開展.一些研究圍繞“全連通網絡”,運用超圖理論開展分析[20],雖能夠對網絡進行融合,保留了信息的完整性,但“超圖”模型通常用于刻畫“全連通網絡”,局限性較強.

在計算機科學和計算機線性代數領域,研究者們運用張量分解(tensor-decomposition)[23-24]和多路數據(multiway data)分析[25]的方法研究了不同類型的多層網絡.在物理學領域,物理學家們圍繞多層網絡[26-29]、網絡的網絡[30-31]和節點著色網絡(node-colored networks),已經開展了許多重要的基礎性工作.Boccaletti等人[32]于2014年首次提出了多層網絡的基本數學定義,該定義統一了迄今文獻上關于多層網絡的不同提法.經過近幾年的發展,多層網絡模型已逐漸成熟,形成了一系列符合復雜網絡基本特征和動力學機制的理論方法,為后續研究奠定了基礎.對于多關系網絡,可將每一類關系對應于一個網絡層,同時考慮各類關系間的關聯信息,建立多層網絡模型開展相關研究.因此,多層網絡模型是表示多關系網絡的理想形式,將多層網絡模型運用到多關系網絡中,在應用層面進行拓展,是值得深入研究的一個基本問題.

在社會網絡分析領域,中心性、聲望和傳遞性是制約社會網絡中行動者顯著性或重要性的關鍵因素[13].在復雜網絡分析領域,對于單個網絡節點中心性的度量,已經建立了較完備和豐富的指標和方法[33].根據局部性質劃分,可分為全局中心性、局部中心性、半局部中心性3類.全局中心性的經典指標有介數中心性(betweenness centrality, BC)[34]、接近中心性(closeness centrality, CC)[35]、特征向量中心性(eigenvector centrality, EC)[36]等.局部中心性的典型指標有度中心性(degree centrality, DC)[37].為平衡全局中心性的復雜度和局部中心性的因素單一,Chen等人[38]提出了一種半局部中心性(semi-local centrality, SLC),通過考慮節點的4階鄰居信息來度量節點重要程度,Gao等人[39]在其基礎上通過引入D-S證據理論,提出了一種證據半局部中心性(evidential semi-local centrality, ESC).但上述經典指標都只關注了節點的中心性,而忽略了傳遞性在度量重要節點的關鍵作用.通常用節點的局部聚集系數刻畫節點的傳遞能力,Chen等人[40]綜合考慮了節點的中心性和傳遞性因素,同時考慮了節點的二階鄰居對節點重要性造成的影響,提出了ClusterRank指標,該指標在運行效率和準確度上都要優于前者.聲望的概念,主要通過可以區分行動者發出或者接收“選擇”關系的行為進行量化,因此只能利用有向網絡進行研究.在復雜網絡分析中,通常用節點的出度來刻畫中心性,用節點的入度來刻畫聲望[13].遺憾的是,聲望除用于早期社會網絡分析外,現階段對有向網絡節點重要性的研究中,研究者們更加關注節點的出度信息,關注節點的入度信息的研究很少.值得一提的是,Wang等人[41]研究了有向網絡節點出度和入度的分布關系,針對有向加權的單關系網絡提出了IO-ClusterRank指標,其對節點重要性的度量效果要優于傳統的ClusterRank指標.

面向多關系網絡,如何借用已有的物理量去描述其基本拓撲結構和性質尚面臨巨大挑戰,將單關系網絡中的成熟工具和方法擴展到多關系網絡中已成為當前復雜網絡研究的一大熱門方向.最初的做法是將不同關系的節點和連邊以不同權重的方式進行合并,從而將多關系網絡轉化成為單關系網絡,再利用傳統物理量去分析其各種結構屬性.將多關系網絡合并成單關系網絡,會導致一些關系間重要信息的丟失,同時還存在如何設定各種權重的問題[42].因此,發現一套適合多關系網絡的網絡理論框架的必要性開始凸顯.多層網絡模型的提出為多關系網絡的研究奠定了理論基礎,國內外學者針對多層網絡度量指標的研究做了大量研究工作,也取得了一些成果,多層網絡的中心性、路徑長度、聚集系數等概念被相繼提出,為后續研究奠定了基礎.但多層網絡的度量指標,大多數是在特定條件和應用場景下提出的,尚未形成類似于單關系網絡豐富經典的度量指標體系,其可擴展性需進一步增強.值得一提的是,Battiston等人[43]在向量的基礎上提出了多層網絡節點度(node degree)、節點強度(node strength)等概念,Cozzo等人[44]從路徑和環的概念出發,基于多層網絡的傳遞性提出了一種多層網絡聚集系數(clustering coefficient)的概念,二者都是從多層網絡的基本表征和動力學特性出發的,具有較好的可擴展性,成為目前比較經典的多層網絡度量指標,為后續研究提供了基本遵循.特別是在傳遞性研究方面,通過在實際數據上進行實驗和分析,表明在社會網絡和交通網絡中,層內聚集性和層間聚集性的差異是不同的,這實際上反映了在這些網絡中節點傳遞性的起源機制大不一樣.他們提供的聚集系數定義表達式為不同類型的網絡傳遞性研究提供了新的思路.

綜上,現階段對于多關系網絡的研究比較理想的處理方式是構建多層網絡模型并運用相關指標進行分析,而對于多層網絡2種較為經典的度量指標,主要是圍繞多層網絡的拓撲結構和傳遞機制進行研究,如何從多層網絡的基本模型和表示框架出發,運用這些指標對多關系網絡的節點重要性開展研究還存在很多問題,也是本文工作的出發點之一.

2 基礎理論

本節主要對文中用到的基礎理論和符號記法進行介紹和說明.

2.1 愛因斯坦求和約定和符號記法

在張量計算體系中,為使計算公式簡潔,通常將求和符號∑省略,即采用愛因斯坦求和約定.滿足2個規則[45]：

1) 啞指標規則

① 在同一項中,以一個上標與一個下標成對地出現,表示遍歷其取值范圍求和.如：

(1)

(2)

(3)

② 每一對啞指標的字母可以用相同取值范圍的另一對字母任意替換,其意義不變(必須指代明確).如：

AαBα=AβBβ,

(4)

(5)

在式(5)中,由于已經存在β,若將γ替換為β,則會造成指代不明.

③ 涉及張量積之間比率的方程式,應將愛因斯坦求和約定分別應用到分子與分母.如：

(6)

2) 自由指標規則

若一個指標在表達式的各項中都在同一水平上出現并且只出現一次,或者全為上標,或者全為下標,表示該表達式在該自由指標的N維取值范圍內都成立,即代表了N個表達式：

(7)

其中，β為啞指標,α和γ均為自由指標.

同理,一個表達式中的某個自由指標可以全體地換用相同取值范圍的其他字母,意義不變.

在歐幾里德空間中,張量的協變向量通常用列向量a∈N來表示,其分量記為aα,(α=1,2,…,N),對偶向量(逆變向量)可用對應的轉置向量(行向量)表示,其分量記為aα.

為避免混淆,本文對張量代數框架下的符號記法做2個約定：

2.2 ClusterRank與IO-ClusterRank指標

節點的局部聚集系數與信息傳播的范圍及網絡進化中節點的度增長能力均呈負相關.鑒于此,Chen等人[40]提出的ClusterRank指標是一種針對有向網絡節點重要性的半局部中心性指標,該指標不僅將鄰居節點數量作為衡量中心性的一個指標,同時考慮了傳遞性對節點重要程度的影響,即聚集系數越大節點的傳播能力越弱.ClusterRank算法定義為

(8)

(9)

但是,ClusterRank指標只考慮了節點的出度,并沒有考慮節點的入度信息,Wang等人[41]通過對有向網絡出入度的分析,基于ClusterRank提出了一種針對加權有向網絡的節點重要性度量指標IO-ClusterRank,定義為

(10)

(11)

(12)

2.3 D-S證據理論

D-S證據理論是由Dempster和Shafer[46]建立的一套數學理論,是對概率論的進一步擴充,在表示和處理有限個不確定問題時具有明顯優勢,適用于專家系統、人工智能、模式識別和系統決策等領域的實際問題.本節主要介紹證據理論處理流程涉及到的辨識框架(frame of discernment)、基本概率指派(basic probability assignment, BPA)以及Dempster-Shafer證據組合規則等基本概念和計算方法.

定義1.辨識框架.在證據理論中,通常將所考察判斷對象的全體用一個兩兩互斥的有限完備集合來表示,該集合稱為辨識框架,記為

Ψ={ψ1,ψ2,…,ψN},

(13)

Ψ的冪集2Ψ記為

2Ψ={?,ψ1,…,ψN,ψ1∪ψ2,…,ψ1∪
ψ2∪ψ3,…,Ψ}.

(14)

定義2.基本概率指派.設Ψ是辨識框架,2Ψ構成命題集合,?A?Ψ,若函數m:2Ψ→[0,1]滿足2個條件：

(15)

則稱m為基本概率指派,m(A)為命題A的基本概率數,被視為準確分配給A的信度.

定義3.Dempster-Shafer組合規則.設m1和m2為2組基本概率指派,對應的對象分別為A1,A2,…,Ak和B1,B2,…,Bl,用m表示m1和m2組合后的新證據.Dempster-Shafer組合規則定義：

(16)

3 多關系網絡的張量表示和基本度量

為研究多關系網絡,首先需構建一種精確的數學表示方法,以及與之配套的分析工具.本文采用基于張量代數的多層網絡表示框架對多關系網絡進行建模和分析.該框架的優勢在于可擴展性強,多重網絡、時序網絡、相互依賴網絡等均可用多層網絡模型進行構建.本節主要介紹多關系網絡的基本模型和張量表示方法,以及本文中所用到的一些基本度量指標的計算方法.

3.1 多關系網絡的基本模型

參考Boccaletti等人[32]提出的多層網絡數學定義,給出多關系網絡的圖定義：

進一步,針對多關系有向網絡,可將其分層表示為層內網絡(intra-layer network)和層間網絡(inter-layer network)兩部分,每一層對應于一種關系.其中,層內網絡用GRI=(V,ERI)表示,層內邊集可記為

(17)

(18)

不同于層內網絡,由于多關系網絡各層間均存在彼此的交互關系,故層間邊集中各層對應節點間為一種雙向關系(也可視為無向關系).

為避免與節點標號混淆,在多關系網絡的抽象定義中,我們用帶有[]的希臘字母([α],[β]等)的上標來指示多層網絡的層標號.E[α]組成元素稱為多層網絡層內連邊,區別于每個E[α,β]的表示層間連邊的組成元素.

由定義4可得,用于構建多關系網絡的多層網絡模型是一種“層間節點對齊”型的多層網絡,稱之為多重網絡(multiplex network).圖1展示了一個具有3層的無向多層網絡和多重網絡的示意圖,可以看出,多重網絡屬于多層網絡的特殊類型,其唯一的層間連接模式是來自不同層之間對應節點的連接.

3.2 多關系網絡的張量表示框架

由3.1節可知,可用多重網絡模型對多關系網絡進行建模,本節主要介紹基于張量代數的多關系網絡框架,本文中關于張量運算的公式符號記法采用2.1節介紹的愛因斯坦求和約定.下面分別介紹單層網絡和多層網絡的張量表示方法[47]：

1) 單層網絡的張量表示

有別于通常情況下的單關系網絡,本文中所討論的單層網絡(monoplex networks)屬于多層網絡的特殊情況,需滿足與時間無關和同構2個條件.

記單層網絡為Gmonoplex={V,E},節點集記為V={v1,v2,…,vN},將節點集中每一個節點與向量空間N中狀態向量相對應,例如,節點vi所對應的狀態向量分量為：此式中第i個元素為1,其余元素全為0,它在向量空間N中所對應的逆變(對偶)向量分量記為：通過克羅內克積來構建描述節點間關系的張量空間,即：N?N=N×N.由此,二階標準基張量可定義為

(19)

(20)

(21)

2) 多層網絡的張量表示

(22)

事實上,根據定義4和克羅內克積的運算規則,可以很方便地得到該矩陣,所得結果與通過動力學擴散方程得到的矩陣是一致的[49].下面以構造多關系網絡的鄰接矩陣為例,對其構造方法予以說明：

根據定義4,可分別構建層內網絡和層間網絡所對應的鄰接矩陣.

定義5.層內鄰接矩陣.多關系網絡第α類關系所對應的層內連接可由一個鄰接矩陣來表示,記為A[α]∈N×N,則多關系網絡的層內鄰接矩陣定義為

(23)

定義6.層間鄰接矩陣.多關系網絡所對應的層間連接可由一個加權鄰接矩陣來表示,記為WC∈M×M,取單位矩陣E∈N×N,則多關系網絡的層間鄰接矩陣定義為

WRC=WC?E∈MN×MN.

(24)

由定義5和定義6可得到多關系網絡的鄰接矩陣,即：

AR=ARI+WRC∈MN×MN.

(25)

3.3 多關系網絡的基本度量

1) 多關系網絡的度中心性

在張量代數框架下首先給出單層網絡度中心性的表示方法[47],并在多層網絡上進行推廣：

① 單層網絡的度中心性

首先定義“1-向量”,即分量元素全為1的向量,記為

uα=(1,1,…,1)T∈N.

(26)

通過將度向量投影到對應于節點vi的標準基向量上,可得到節點vi的度中心性,即：

(27)

② 多關系網絡的度中心性

與單層網絡相似,通過使用適當階的“1-張量”對單層網絡情況進行相同的投影,可以得到多關系網絡的度中心性張量(multiplex degree centrality, MDC),即

(28)

節點度(node degree)：

(29)

平均度(mean degree)：

(30)

度的二階矩(the second moment of the degree)：

(31)

度的方差(the variance of the degree)：

(32)

對于有向網絡,使用不同的克羅內克積,可分別得到出度中心性和入度中心性的張量表示：

(33)

(34)

由式(33)和式(34)可得,使用張量代數的網絡表征框架有助于理解有向網絡中的方向性,因為入度與出度的克羅內克積的運算規則是不同的.

2) 多關系網絡的局部聚集系數

Cozzo等人[44]從路徑和環的概念出發,提出了多層網絡局部聚集系數和全局聚集系數的概念.在單層網絡中,可用鄰接矩陣來計算網絡中路徑和環的數量[51-52].類似地,將多層網絡中的行走稱之為“超行走(supra-walk)”,并通過層內鄰接矩陣和層間鄰接矩陣來計算多層網絡的局部聚集系數.按照Cozzo等人提出的多層網絡聚集系數的計算方法,本文給出一種多關系網絡局部聚集系數(multiplex local clustering coefficient, MLCC)的簡化計算方法.由3.1節可知,本文運用多重網絡模型來表示多關系網絡,則在多關系網絡中,通過“超行走”得到的三元閉環結構有且僅有圖2所示的5種基本形式,其中較大節點(紅色)代表閉環的起始節點,層內路徑用實線表示,層間路徑用虛線表示,較粗實線(橙色)代表層內第2步行走路徑.通過“超行走”所構成的三元閉環可通過將各網絡層聚合到一層得到.

Fig. 2 Sketch of elementary cycles圖2 基本閉環結構

根據3.2節多關系網絡鄰接矩陣的構造方法,可得到多關系網絡節點聚集系數的定義.

定義7.多關系網絡的局部聚集系數.令M,I,C分別表示多關系網絡的鄰接矩陣、層內鄰接矩陣、層間鄰接矩陣,

Ω={III,IICIC,ICIIC,ICICI,ICICIC}

為多關系網絡中基本三元閉環結構集合,ξ為集合Ω中的元素,

(35)

4 融合多元信息的節點中心性度量方法

現實世界的社交數據中存在許多有向關系,比如微博網絡中的轉發、關注關系,引文網絡中的引用和被引用關系,都可以用有向邊予以刻畫.因此,本節基于第2節和第3節介紹的基礎理論,用有向多重網絡的張量表示框架刻畫多關系社交網絡,綜合考慮社交網絡中節點中心性、聲望、傳遞性對節點重要性造成的影響,分別用多關系網絡中節點的出度中心性、入度中心性、局部聚集系數進行量化,運用信息融合的思想,對多關系網絡中的節點重要性度量方法進行了研究.

4.1 基于IO-ClusterRank的節點重要性排序方法

借鑒2.2節介紹的ClusterRank和IO-ClusterRank的思想方法,并利用多關系網絡的度量指標進行推廣,提出了一種基于ClusterRank的多關系社交網絡節點的半局部中心性度量方法IOMCR.IOMCR在考慮節點本身及其鄰居節點中心性和聲望的同時,還考慮了節點的傳遞能力.IOMCR的定義：

(36)

(37)

(38)

(39)

4.2 融合多元信息的節點重要性排序方法

4.1節提出的IOMCR指標采用了一種正相關性融合方法,即認為節點的中心性和聲望越顯著,其傳遞性也就越強.但在真實網絡中,很多節點往往不具備這種正相關關系,例如在微博網絡中,一些用戶雖然中心性和聲望都很顯著(即關注和被關注的用戶都很多),其可以接收到很多消息,但卻不喜歡轉發(即傳遞性很弱),還有一些用戶熱衷于轉發自己的消息(即傳遞能力較強),但關注和被關注的用戶卻很少(即中心性和聲望不顯著).綜上,中心性、聲望、傳遞性之間往往呈現出的是一種不確定性關系,而IOMCR方法往往需要在中心性、聲望、傳遞性三者之間具有相對明確的正相關性條件下,才能表現出較好性能.而在多關系網絡中,由于傳遞機制具有差異性,往往三者之間不具備明確的正相關關系.故IOMCR指標具有一定的局限性,其在度量節點重要性程度時,節點中心性、聲望、傳遞性三者信息之間有可能會相互抵消,從而對度量節點重要程度造成影響.

考慮到D-S證據理論[39,46,53]是處理不確定性問題的理想辦法,本文引入D-S證據理論,對IOMCR進行了改進,分別將節點的中心性和聲望信息與節點的傳遞性信息進行融合,進一步提出了IOMEC方法：

(40)

其中,υOMEC,i為中心性信息和傳遞性信息進行融合后的度量值,υIMEC,i為聲望信息和傳遞性信息融合后的度量值,取二者的平均值作為最終的度量值.以計算υOMEC,i為例,介紹D-S證據理論融合節點中心性和傳遞性信息的方法步驟：

1) 計算節點中心性和傳遞性量化指標

分別計算節點的出度中心性向量Kα和節點的聚集系數向量CM,記Ki和CM,i分別為Kα和CM中對應第i個位置的元素值,分別計算f(CM,i)=10-CM,i,所得結果向量記為F.統計Kα和F中元素的最大值和最小值,分別記為KM,Km,FM,Fm.一般情況下,KM≠Km,FM≠Fm.

2) 確定節點重要程度的辨識框架

按照2.3節中D -S證據理論的處理流程,首先應確定考察對象的辨識框架Ψ.本文所考察的是節點的重要程度,簡單起見,可將網絡中節點的重要性分為節點重要和節點不重要2類,用I表示節點重要,NI表示節點不重要,則記Ψ={I,NI}.顯然,Ψ中的元素兩兩互斥且為有限完備集合.

3) 構建基本概率指派函數

令mK,I(i)和mK,NI(i)分別為在Ki下節點vi重要和不重要的概率,mF,I(i)和mF,NI(i)分別代表在f(CM,i)下節點vi重要和不重要的概率.在無特定條件情況下,通常約定該概率指派服從均勻分布,根據均勻分布的概率密函數,可定義上述4個指標的BPA函數：

(41)

(42)

(43)

(44)

μ和λ為修正參數,取值對節點排序沒有影響,通常取μ,λ∈(0,1).

4) 進行D -S證據組合

首先定義考察對象的集合,記為

M(i)={mI(i),mNI(i),mΨ(i)},

(45)

其中，mI(i)為表示節點vi重要的概率，mNI(i)表示節點vi不重要的概率,mΨ(i)表示節點vi或者重要或者不重要的概率.根據式(16),可分別計算mI(i),mNI(i),mΨ(i).

5) 計算OMEC.

根據貝葉斯理論,在無其他先驗知識的情況下,將mΨ(i)等可能分配給mI(i)和mNI(i),進一步修正節點vi重要的概率MI(i)和不重要的概率MNI(i),即：

(46)

(47)

由式(46)和式(47)可得,當MI(i)越大、MNI(i)越小時,說明節點vi越重要.鑒于此,對MI(i)和MNI(i)進行組合,可得到υOMEC,i的度量值：

υOMEC,i=MI(i)-MNI(i)=mI(i)-mNI(i).

(48)

為保證概率的非負性和歸一性,將式(48)進行標準化處理,進一步修正為

(49)

類似地,將υOMEC,i計算過程中的出度中心性向量Kα改為計算入度中心性向量Kα,即可得到融合聲望和傳遞性的υIMEC,i度量指標.

4.3 時空復雜度分析

多關系網絡中,記節點數為n,關系數為m.

1) 時間復雜度分析

計算多關系網絡出度中心性和入度中心性的時間復雜度均為O(mn),計算節點的局部聚集系數時間復雜度為O(m3n3).由于IOMCR方法和IOMEC方法的計算均考慮了衡量節點中心性、聲望和傳遞性的度量指標,故二者的計算復雜度均依賴于計算節點出度中心性、入度中心性和局部聚集系數的時間復雜度.在已知節點出度中心性、入度中心性和局部聚集系數的條件下,IOMCR方法由于考慮了節點的一階鄰居信息,其時間復雜度為O[mn(Kα+Kα)],而IOMEC方法將層間信息通過D-S證據理論進行了融合,僅關注了節點本身,故其時間復雜度為O(n).在單獨計算二者的時間復雜度方面,IOMEC方法要優于IOMCR方法,但綜合考慮節點的出度中心性、入度中心性和聚集系數的時間復雜度后,二者的時間復雜度均為O(m3n3).

2) 空間復雜度分析

鑒于通過構建4階張量對多關系網絡進行表征,故其空間復雜度為O(m2n2).在代碼實現過程中,由于考慮到鄰接張量的稀疏性,采用稀疏張量對其進行壓縮處理,可以有效降低多關系網絡的空間復雜度.

5 實驗與討論

通過在4個真實社交網絡數據集上進行相關實驗,從運行時間和度量節點重要程度準確性2個方面對所提出方法進行了評測,并選取多關系網絡的度中心性和特征向量中心性[47]2種經典指標進行對比來說明提出方法的有效性,為避免與單關系網絡中的度量指標進行混淆,將多關系網絡中的度中心性度中心性記為MDC、特征向量中心性記為MEVC.實驗平臺為Intel Core i9-9900K 3.6 GHz,64 GB RAM,操作系統為CentOS 7,代碼由Python實現.

選取了4個規模不同的真實社交網絡數據集[54]MoscowAthletics2013,NYClimateMarch2014,MLKing2013,Cannes2013,這4個數據集均是圍繞特定事件從Twitter平臺獲得的,包含轉發、提及、回復3種有向關系.4個數據集的基本統計信息如表1所示：

Table 1 The Basic Information of Experimental Data表1 實驗數據集的基本信息

5.1 評價標準

在節點重要性研究中,通常利用傳播動力學模型對節點重要性的排序結果進行評價,本文采用SIR模型[11,32,55-57].SIR模型包括3個狀態：

1) 易感(susceptible)狀態S(t).表示易感染但尚未感染疾病的個體數量.

2) 感染(infected)狀態I(t).表示已經感染,并且能夠將疾病傳播給易感個體的個體數量.

3) 恢復(recovered)狀態R(t).表示感染個體已經恢復,并且不會被再次感染的個體數量.

在SIR模型中,節點重要性的評價標準一般有2項：一種為節點的平均傳播范圍,即達到穩態時感染態I(t)和恢復態R(t)的數量之和,數量越大,說明該節點越重要.另一種為傳播速率,可從傳播初始階段感染態I(t)和恢復態R(t)的數量和達到穩態時所用時間2方面來評判,數量越大、所用時間越小,說明該節點越重要；為方便說明,將第t個時間迭代步時的感染態和恢復態的數量之和記為F(t),感染態的平均數量記為Fi(t),達到穩態時的數量記為F(tc).

(50)

根據貝葉斯理論和條件概率,各層傳染概率設置為

(51)

其中，λi為放大系數,Nr為多關系網絡的關系數.恢復概率通常依賴于各層的平均度,類似地,各層恢復概率設置為

(52)

由于傳播過程是依概率進行感染傳播,即使2組實驗條件完全相同,最終得到的結果也會存在一定差異.為此,為此選取100次獨立實驗所得結果的期望值作為評價結果.

5.2 運行時間分析

(53)

(54)

由于4個網絡規模不同,我們通過統計各方法運行時間占總運行時間的比重來說明算法運行時間的長短,即：

(55)

其中，tmethod表示計算指定方法時所消耗的時間，ttotal表示計算各方法所消耗的總時間.

Fig. 3 The run time of IOMCR and IOMEC圖3 IOMCR方法和IOMEC方法運行時間統計圖

5.3 度量準確性分析

本節在4個數據集上進行了4組不同的實驗,并通過SIR進行評測,分別從傳播范圍和傳播速率2方面對各度量方法進行評價來驗證提出算法在度量節點重要程度的準確性.

實驗1.通過觀測SIR傳播曲線的傳播范圍和傳播速率,對各方法度量節點重要性的準確性進行評測.在4個網絡中,按照各方法對節點重要程度的度量值進行降序排序,分別選取前1%的節點作為初始傳染源節點,統計給定時間迭代步的F(t),并繪制SIR傳播曲線,其中橫軸代表時間迭代步數,在前3個網絡中,設定最大迭代步數為200,而由于Cannes2013規模較大,設置最大迭代步為500.縱軸代表對應的F(t),通過觀測曲線達到穩態時的時間和對應的F(tc)來說明傳染源節點的傳播范圍,通過觀測曲線的斜率變化來說明傳染源節點的傳播速率.圖5所示的實驗結果顯示：

1) 在4個網絡上,無論是傳播時間還是傳播范圍,IOMEC方法相比于其他方法,都能表現出較好結果,特別是隨著網絡規模的增加,該優勢愈發明顯,而多重特征向量中心性表現最差；

2) IOMCR方法的評測結果要劣于IOMEC方法和多重度中心性,特別是在MLKing2013數據集上表現最為突出,IOMEC方法和多重度中心性得到的重要節點的傳播范圍,約是IOMCR方法得到重要節點傳播范圍的3倍；

3) 多重度中心性總體表現良好,但要劣于提出的IOMEC方法,并且隨著網絡規模的增大,二者差距愈發明顯.

實驗2.由于在傳播過程中,傳染源節點在早期的傳播中起到主要作用,即對于節點傳播能力的評測,早期的傳播更為重要.本實驗主要通過觀測各節點傳播初期的F(t)與各方法測量值之間的相關關系,來說明節點的傳播能力.本實驗設置t=10.在理想狀態下,F(t)與對應的測量值應呈現正相關關系.

4個數據集上的實驗結果如表2所示.表2中,每列子圖分別對應同一數據集下4種不同方法,坐標軸采用雙對數坐標,橫軸表示每種方法下各節點的度量值,縱軸表示各節點作為傳染源節點,所對應的F(t)(t=10).由于網絡規模較大,故選取各方法得到前1 000個重要節點的并集作為實驗節點集合.

Table 2 The Correlation Between F(t)(t=10) and Its Measure表2 t=10時,F(t)與各方法度量值間的相關關系

實驗結果表明:多重度中心性和IOMEC方法在4個網絡中都呈現出一定的正相關性,而另2種方法均未呈現出明顯的正相關性.在多重度中心性方法中,一些度量值較低的節點反而F(t)更大且分布較為稠密,而在IOMEC方法中這類節點分布稀疏,故IOMEC方法總體上要優于多重度中心性方法.

實驗3.為進一步討論各方法節點的測量值與其傳播能力之間的相關關系,并評測各方法對節點重要性度量的準確性.本實驗對各節點在SIR模型中得到的穩態值F(tc)進行排序,并以此為基準,比較其與各方法對節點重要性度量值之間的相關關系.表3描述了在4個網絡中,各節點在SIR模型中的傳播能力與4種方法對節點度量值間的相關關系,表3中每一列子圖對應同一數據集的不同方法,坐標軸采用雙對數坐標,橫軸表示各節點在對應方法下的測量值,縱軸表示各節點在SIR模型中得到的穩態值F(tc),每一個數據點代表網絡中的一個節點,節點的顏色表示在傳播過程中,t=10時的傳播能力,即F(10).類似地,分別選取各方法得到前1 000個重要節點的并集作為實驗節點集合.

Table 3 The Correlation Between Each Measure and Spreading Ability of SIR表3 節點度量值與SIR傳播能力間的相關關系

實驗結果表明：表3所示的各節點相關性分布與表2所示的節點分布基本一致,說明各節點傳播能力在傳播過程初期起主要作用.從結果上分析,IOMEC方法和多重度中心性仍然能夠呈現出正相關態勢,IOMEC方法所得到的節點相關性分布要優于多重度中心性；IOMCR方法和多重證據中心性所得到的結果較差,沒有呈現出明顯的相關性態勢.

實驗4.為了進一步驗證各方法的性能,本實驗研究了按照某種度量方法對節點的重要程度進行排序后,節點排序與在SIR傳播過程中所對應的平均感染數量F(t)(t=10)之間的關系.從理論上分析,性能較好的度量指標,其圖像應該呈現遞減關系,即隨著節點重要程度的降低,對應的受感染節點的平均數會減少.為了對比,本實驗特意增加了隨機排序(random ranking)這種極端情況.實驗結果如圖6所示,其中橫軸代表各節點排序,縱軸代表對應的受感染節點平均數量.類似地,分別選取各方法得到前1 000個重要節點的并集作為實驗節點集合.4個網絡上的實驗結果表明：

1) 隨機排序和多重證據中心性情況最差.二者除未呈現出較好的遞減態勢外,平均感染數量也非常少,說明二者所得到的節點的傳播能力很弱.

2) IOMEC方法和多重度中心性在4個網絡上均能夠呈現出良好的遞減態勢,并且在平均感染數量上,IOMEC方法所得到的結果要優于多重證據中心性,進一步驗證了本文提出方法對節點重要程度度量的準確性.

3) 在MoscowAthletics2013和NYClimateMarch 2014上,IOMCR方法所得到的結果能夠呈現出較好的遞減態勢,并且篩選出部分節點的傳播能力要優于多重度中心性所得到的結果.但在其他2個網絡上,IOMCR方法所得到的結果表現較差,篩選出的節點傳播能力與IOMEC方法和多重度中心性得到的結果差距明顯,尤其在MLKing2013中,未呈現出明顯的遞減趨勢,并且平均感染數量很低.進一步說明,隨著網絡規模的增大,節點傳遞性的因素愈發重要,并且節點的中心性、聲望、傳遞性之間不具備絕對的正相關性,傳統的ClusterRank思想存在一定的局限性.

6 總 結

本文針對多關系社交網絡的節點重要性問題進行了研究,應用有向多重網絡模型和基于張量代數的數學框架對其進行建模和分析,綜合分析中心性、聲望和傳遞性對節點重要性的影響,提出了IOMCR節點重要性度量方法,并針對其存在問題,引入D-S證據理論信息融合方法對其進行改進,進一步提出了面向多關系網絡的IOMEC節點重要性度量方法.在4個真實網絡上的實驗表明4個主要結論：

1) 在多關系社交網絡中,由于受耦合信息和傳遞機制差異性的影響,節點的中心性、聲望和傳遞性之間不具有絕對的相關關系,對三者進行相關性融合的IOMCR度量方法會對計算結果造成誤差,降低了度量節點重要性的準確度,隨著網絡規模的增大,該問題會更加突出,說明傳統的ClusterRank思想具有局限性.

2) 通過引入D-S證據理論,對節點中心性、聲望、傳遞性進行依概率融合所提出的IOMEC度量方法,可以有效消除多關系網絡耦合信息和傳遞機制的差異性對節點重要信息造成的影響,相比于只關注中心性和聲望的多重度中心性和只關注節點傳遞能力的多重特征向量中心性,能夠更加準確地挖掘網絡中的重要節點,特別是在大規模網絡中優勢更為明顯.

3) 通過IOMEC方法、多重度中心性和多重特征向量中心性3種方法所得結果的橫向對比分析,說明在多關系網絡的節點重要性研究中,基于網絡拓撲結構的中心性和聲望因素占主導地位,而只關注節點傳遞特性,直接擴展單個網絡節點特征向量中心性的思路方法到多關系網絡上,并未得到理想效果.為更加準確的度量節點的重要性程度,在關注節點中心性和聲望的同時,也應該關注節點的傳遞特性,特別是在大規模網絡中,節點的傳遞性作用更加突出.

4) 由于考慮了節點的傳遞性指標,故提出方法總體具有較高的時間復雜度,相比于IOMCR方法,改進的IOMEC方法具有更低的時間復雜度.故本文提出方法適用于需要精準挖掘網絡中重要節點的應用場景,對于準確度不高的應用場景,可以考慮只關注節點中心性和聲望的多重度中心性.

綜上,本文所做工作不僅對多關系社交網絡的節點重要性研究提供了新的思路方法,也進一步拓展了D-S證據理論的應用場景.然而,本文的工作也并不完美,受實驗環境的限制,尚不適用于超大規模的多關系網絡.近年來,復雜網絡呈現出大規模、高維度和動態性的特點,如何建立合理的模型對網絡進行表示,設計有效的度量指標或算法識別大規模高維動態復雜網絡的關鍵節點是當前復雜網絡節點重要性研究面臨的一項挑戰,也是我們今后研究工作的重點.