一種基于排名聚合的社交網絡關鍵用戶挖掘方法

梁耀洲　郭強　劉建國

摘 要：帶有時間屬性的動態社交網絡逐步成為社交網絡研究熱點。相比靜態網絡，動態網絡考慮用戶交互發生的先后順序，能夠更直接地描述用戶的交互關系和順序。傳統社交網絡挖掘方法往往從用戶交互路徑進行評估，忽略了動態社交網絡中交互時間片段的相互影響。綜合考慮用戶的交互順序與時間影響，采用超鄰接矩陣描述動態網絡，并用排名聚合理論對用戶影響力進行綜合排名，提出了一種基于排名聚合的社交網絡關鍵用戶識別方法。Workspace實證數據集顯示，該方法在準確率對比結果中，Spearman相關系數最多提高了13.45%，說明該方法在社交網絡關鍵用戶挖掘中具有適用性和有效性。

關鍵詞：社交網絡;超鄰接矩陣;排名聚合;關鍵用戶挖掘

DOI：10. 11907/rjdk. 192562

中圖分類號：TP391 ? 文獻標識碼：A ??????????????? 文章編號：1672-7800（2020）003-0186-04

A Method of Key User Identification for Social Network

Based on Ranking Aggregation

LIANG Yao-zhou1， GUO Qiang1， LIU Jian-guo2

（1. Research Center of Complex Systems Science， University of Shanghai for Science and Technology， Shanghai 200093， China;

2. Institute of Fintech， Shanghai University of Finance and Economics， Shanghai 200433， China）

Abstract：In recent decades， the dynamic social network with time property has become a hot topic of social network research. Compared with static network， dynamic network considers the sequence of user interaction and can describe the interaction relationship and sequence of users more directly. Traditional social network mining methods are often evaluated by the communication path of users and ignore the interaction time segments in dynamic social networks. In this paper， considering the influence of the interaction sequence and time of users， the hyper adjacency matrix is used to describe the dynamic network， and the ranking aggregation theory is used to rank users comprehensively， and a ranking aggregation based key user identification method of social network is proposed. The result of Workspace data set shows that compared with the traditional method， Spearman correlation coefficient of this method is up to 13% higher in the result of accuracy comparison， indicating the applicability and effectiveness of this method in social network key user mining.

Key Words： social network; super adjacency matrix; ranking aggregation; key user identification

0 引言

動態社交網絡考慮了用戶之間交互的時間、先后順序和頻率，能夠更準確地刻畫用戶的交互關系 [1-5]。傳統靜態社交網絡關鍵用戶識別方法很多，如度中心性、介數中心性、緊密度中心性、特征向量中心性等[6-8]。劉建國等[6]從網絡結構和傳播動力學角度，對現有網絡中的節點重要性排序方法進行了系統歸納和總結;Liu等[9]綜合網絡結構和傳播動力學特征進行耦合分析，利用差分方程評估傳播過程，對節點重要性進行排序;王亮亮等[10]討論一種能夠有效表示社交網絡中用戶關系的數據結構，介紹了用戶關系識別的有關方法;陳志揚[11]挖掘當前社交網絡中具有相同內在因素、特定組織結構的群體，提出一種基于特定用戶群體關系的挖掘與分析方法;仇麗青等[12]考慮微博網絡中的粉絲關注和轉發，同時引入用戶關系權重，提出加權網絡下基于微博轉發關系的FW-Rank算法，用來識別重要用戶。然而動態社交網絡不同于傳統的靜態網絡，由于考慮了時間因素，動態社交網絡中節點的交互會隨時間的推移產生和消失[5，13]。近年來，有關動態社交網絡節點重要性的研究越來越多，動態社交網絡通常用時序網絡表征進行分析和研究。 Kim[14]在構建網絡時對時間切片引入時序最短路徑，定義了時序網絡中的時序介數中心性、時序接近度中心性等中心性指標;樓鳳丹等[15]從時序網絡建模方法、時效網絡結構特性、時序網絡與人類行為結合的統計特性及處理時序網絡的理論方法等方面，對時序網絡當前的研究進展進行了總結和歸納;Yang[16]考慮不同節點層間關系的不同，引入鄰居拓撲重疊系數，提出了基于節點層間相似性的時序網絡節點重要性方法，進一步完善了時序網絡節點重要性研究。

但從時間切片內部和外部連接關系角度出發，楊劍楠[16]的研究僅得出了各時間切片的節點重要性排序，并不能給出整個時序網絡節點重要性的綜合評價;Anjela等[17]提出了排名聚合方法，該模型根據節點之間的排名先后關系建立評分矩陣來評價節點。因此，本文在楊劍楠等[13]研究基礎上，綜合用戶的交互順序與時間影響，采用超鄰接矩陣描述動態網絡，并用排名聚合理論對用戶影響力綜合排名，提出一種基于排名聚合的社交網絡關鍵用戶識別方法。本文以刪除節點后的節點對網絡連通力影響大小作為評判節點重要性基準，采用動態社交網絡中的時序中心度、時序介數中心性、時序接近度中心性3種節點重要性方法作對比。利用Workspace實證數據集對比其它3種方法進行實驗，顯示本方法在準確率對比結果中，Spearman相關系數最高提高了13.14%，實驗證明了該方法在社交網絡關鍵用戶挖掘中的適用性和有效性。

1 模型與方法

1.1 基于排名聚合的社交網絡關鍵用戶識別方法

動態社交網絡是一個包含個體與其他個體相互關系隨時間變化而變化的系統，其中用戶可以表示為節點，用戶間的相互關系可以表示為連邊。社交網絡可以用[G=（V，E（i，j））]表示，其中節點為[V={v1，v2，？，vN}]，[E（i，j）]表示節點在[[i，j]]時間段內的連邊，即用戶間的交互關系。這里將動態社交網絡分成[T]個時間切片進行分析。本文所介紹的基于排名聚合的社交網絡關鍵用戶識別方法考慮了動態社交網絡層內、層間和時間因素，其思想是根據層內和層間關系，建立基于層間相似性的鄰接矩陣（SSAM，similarity-based supra-adjacency matrix），并利用特征向量中心性計算各時間切片網絡的節點重要性排序，按照時間切片內層的節點排序進行排名聚合，最后由聚合結果評價整個動態社交網絡中用戶的影響力，從而挖掘出關鍵用戶。

1.1.1 基于層間相似性的超鄰接矩陣動態社交網絡模型

為了考慮同一節點與其它節點在相鄰時間切片的連接關系和持續連接度，文獻[16]提出基于層間相似性的超鄰接矩陣（SSAM，similarity-based supra-adjacency matrix）時序網絡模型。SSAM為[NT×NT]的分塊矩陣，對于一個給定節點數為[N]的動態社交網絡[G]，其切分的有序時間切片網絡集合為[G={G1，G2，？GT}]，[T]為切分的時間切片總數，其基于層間相似性的超鄰接矩陣（SSAM）表示如下：

其中，[Α]為基于節點層間相似性的超鄰接矩陣SSAM，[A（t）]表示[t（1tT）]時刻對應的時間切片內連接關系，這里用[N×N]的鄰接矩陣表示，[C（t-1，t）]表示兩個相鄰時間切片的連接關系，這里用[N×N]的對角陣表示， 即[C（t-1，t）=][diag（c（t-1，t）1，c（t-1，t）2，？，c（t-1，t）N）]，其中[C（t-1，t）i]為節點的鄰居拓撲重疊系數[14]，即節點在[Gt-1]時間切片網絡上與[Gt]時間切片網絡的共同鄰居數所占的比例。

1.1.2 基于排名聚合的社交網絡關鍵用戶識別方法

特征向量中心性是網絡節點重要性評估指標[6]，該指標在對動態社交網絡節點重要性度量時，同時考慮鄰居節點數量和鄰居節點的重要程度。因此，采用特征向量中心性這指標對超鄰接矩陣SSAM求解，得到最大特征值對應的特征向量[ν={ν1，ν2，？，νT}]，則集合[ν]中的[ν1，ν2，？，][νT]向量分別代表[T]個時間片段上各時間切片的節點重要性得分，向量長度為[N]。

由特征向量中心性計算出各時間切片網絡的節點排名，無法綜合得出整個動態的節點排名。為了綜合不同的排序結果，得出整個動態網絡節點的排名，文獻[14]提出一種排名聚合方法。本文基于上述思想，對各時間切片網絡的建立評分矩陣進行聚和，通過計算最終聚和矩陣中節點的得分來評價節點。若采用時序網絡有[T]個時間切片網絡，[N]個節點，[Gt] 表示第[t（1tT）]時間對應的網絡，則該方法步驟如下：

（1）建立各時間切片網絡的得分矩陣[Χt]。得分矩陣[Χt]指節點之間根據排名確定節點之間比較關系的矩陣，該矩陣為[N×N]型的非對稱矩陣。影響力得分矩陣[Χt]當中的[xt（v，u）]由節點[av]和節點[au]在第[t（1tT）]個時間切片排序順序決定，其規則如下：

（2）聚合各時間切片網絡的得分矩陣[X]。為了綜合各時間切片節點的排名情況，本方法對各時間切片網絡建立的評分矩陣求和，最終得出總影響力得分矩陣[X]，表示如下：

（3）計算動態社交網絡中節點[v]的影響力得分[gv]。該方法考慮節點排名順序，利用影響力得分矩陣計算節點總得分[gv]，[gv]表示如下：

[g（v，u）]表示節點[v]與節點[u∈V＼v]的總影響力得分，這里用節點[v]與節點[u∈V＼v]計算得出，具體計算方法為：[g（v，u）=x（v，u）-x（u，v）]。

1.2 對比方法

為了比較本文提出方法的有效性，采用3種動態社交網絡中中常用的時序中心度、時序接近中心性、時序介數中心性的中心性度量指標[11]作對比分析。

（1）時序中心度。節點中心度表示一個節點的鄰居節點數量，對于一個包含節點[v∈V]的時序網絡，在[[i，j]]個時間段的時序中心度[Di，j（v）]表示為在時間間隔[[i，j]]內標準化后的節點出度和入度的總數量，具體表示如下：

其中，[Dt（v）]是[v]節點在[Gt]上的度，[V]為節點集合[V]的節點數量。

（2）時序接近中心性。節點接近度中心性為這個節點到其它節點的平均距離，對于一個包含節點[v∈V]的時序網絡，在[[i，j]]時間段內時序接近中心度[Ci，j（v）]表示為：

其中，[Δt，j（v，μ）]表示時間間隔[[t，j]] [（it

（3）時序介數中心性。節點介數中心性為通過這個節點的最短路徑所占比例，對于一個包含節點[v∈V]的時序網絡，在[[i，j]]時間段內時序介數中心性[Bi，j（v）]表示為：

其中，[σt，j（s，d）]表示在節點[s]到節點[d]路徑當中所有的最短路徑數量，[σt，j（s，d，v）]表示在節點[s]到節點[d]路徑中，通過[v]節點的最短路徑數量。

1.3 評價方法

通常認為，節點重要性可以兩方面評價[18]：①計算節點在網絡中的信息傳播能力;②計算移除節點對網絡連通性的影響力[8]。本文采用移除節點后網絡連通性的影響力變化評價節點重要性。通常認為，移除節點后網絡的連通性變化越大，該節點的影響力越大;反之，該節點的影響力越小。

動態社交網絡效率是評判社交網絡連通性的一個重要指標，其時序全局效率[19]形式如下：

這里考慮刪除節點后對網絡連通性的影響，用[E'i]表示。

其中，[ei]表示刪除節點后網絡的時序全局效率，[e]表示未刪除節點時網絡的全局效率。

2 實驗分析

2.1 數據描述

本文采用一組實證數據進行試驗，檢驗本文所提方法對動態社交網絡關鍵用戶識別的效果。Workspace數據集是法國一家公司內部員工通過移動射頻設備進行交互的數據，交互日期為2013年6月24日至2013年7月3日，共10個工作日，員工數為92名，交互次數為9 827次。

2.2 結果分析

對于Workspace數據集，基于排名聚合的社交網絡度量方法計算關鍵用戶排序與基準排序，計算Spearman相關系數，同時與其它方法進行比較，結果如表1所示。

從表1可以看出，本文方法與基準的Spearman相關性為0.832 1，表明本文所用方法的排序準確率高于其它3種常用的動態社交網絡度量方法，說明該方法在動態社交網絡關鍵用戶識別中具有適用性和有效性。

3 結語

近年來，帶有時間屬性的動態社交網絡成為社交網絡研究的熱點。本文通過研究動態社交網絡表征模型，提出了基于排名聚合的關鍵用戶識別方法。經Workspace數據實驗，基于排名聚合的社交網絡關鍵用戶識別方法優于其它3種度量指標，證明了該方法的有效性，同時為動態社交網絡關鍵用戶的挖掘研究提供了思路。

但本文提出的方法是基于兩個小規模網絡的，后續將考慮在大規模網絡中應用該方法進行研究。

參考文獻：

[1]HOLME P，SARAM？KI J. Temporal networks as a modeling framework[J]. Understanding Complex Systems， 2013（9）：1-14.

[2]HOLME P，SARAM？KI J. Temporal networks[J]. Physics Reports， 2012， 519（3）：97-125.

[3]PETTER HOLME. Modern temporal network theory： a colloquium[J]. The European Physical Journal B， 2015，88（9）：1-30.

[4]LIU J G， REN Z M， GUO Q. Ranking the spreading influence in complex networks[J]. Physica A Statistical Mechanics & Its Applications， 2013， 392（18）：4154-4159.

[5]REN Z M， ZENG A， CHEN D B， et al. Iterative resource allocation for ranking spreaders in complex networks[J]. Europhysics Letters， 2014， 106（4）：48-55.

[6]劉建國， 任卓明， 郭強，等. 復雜網絡中節點重要性排序的研究進展[J]. 物理學報， 2013，62，（17）： 178-901.

[7]Lü L， CHEN D， REN X L， et al. Vital nodes identification in complex networks[J]. Physics Reports， 2016（650）：1-63.

[8]任卓明， 邵鳳， 劉建國，等. 基于度與集聚系數的網絡節點重要性度量方法研究[J]. 物理學報， 2013， 62（12）：522-526.

[9]LIU J G， LIN J H， GUO Q， et al. Locating influential nodes via dynamics-sensitive centrality[J]. Scientific Reports，2016，6（3）：32-81.

[10]王亮亮，李小聰. 社交網絡用戶關系分析[J]. 軟件導刊， 2017（5）：156-158.

[11]陳志揚，曹金璇，聶世民. 特定用戶群體關系挖掘與分析研究[J]. 軟件導刊，2019（9）：92-97.

[12]仇麗青， 范鑫. 基于加權轉發關系的社交網絡意見領袖識別算法[J]. 軟件導刊， 2018（7）：115-119.

[13]ZHANG Y Q， CUI J， ZHANG S M， et al. Modelling temporal networks of human face-to-face contacts with public activity and individual reachability[J]. European Physical Journal B， 2016， 89（2）：1-8.

[14]KIM H， ANDERSON R. Temporal node centrality in complex networks[J]. Physical Review E， 2012， 85（2）：26-107.

[15]樓鳳丹， 周銀座， 莊曉丹，等. 時效網絡結構及動力學研究進展綜述[J]. 電子科技大學學報， 2017，46（1）：109-125.

[16]楊劍楠， 劉建國， 郭強. 基于層間相似性的時序網絡節點重要性研究[J]. 物理學報， 2018， 67（4）：350-361.

[17]GOVAN A Y， LANGVILLE A N， MEYER C D. Offense-defense approach to ranking team sports[J]. Journal of Quantitative Analysis in Sports， 2009， 5（1）：4-10.

[18]ZHANG Z K， LIU C， ZHAN X X， et al. Dynamics of information diffusion and its applications on complex networks[J]. Physics Reports， 2016（651）：1470-1485.

[19]朱義鑫，張鳳荔，秦志光，等. 時序網絡上的隨機游走免疫策略研究[J].計算機應用 ，2014，34（11）： 318-329.

（責任編輯：杜能鋼）

收稿日期：2019-11-06

基金項目：國家自然科學基金項目（71771152，61773248）

作者簡介：梁耀洲（1994-），男，上海理工大學復雜系統科學研究中心碩士研究生，研究方向為數據挖掘、社會網絡分析;郭強（1975-），女，博士，上海理工大學復雜系統科學研究中心教授，研究方向為復雜網絡;劉建國（1979-），男，上海財經大學金融科技研究院教授，研究方向為在線社會網絡分析。