一種基于排名聚合的社交網(wǎng)絡(luò)關(guān)鍵用戶挖掘方法

梁耀洲　郭強　劉建國

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

關(guān)鍵詞：社交網(wǎng)絡(luò);超鄰接矩陣;排名聚合;關(guān)鍵用戶挖掘

DOI：10. 11907/rjdk. 192562

中圖分類號：TP391 ? 文獻標(biāo)識碼：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 引言

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

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

1 模型與方法

1.1 基于排名聚合的社交網(wǎng)絡(luò)關(guān)鍵用戶識別方法

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

1.1.1 基于層間相似性的超鄰接矩陣動態(tài)社交網(wǎng)絡(luò)模型

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

其中，[Α]為基于節(jié)點層間相似性的超鄰接矩陣SSAM，[A（t）]表示[t（1tT）]時刻對應(yīng)的時間切片內(nèi)連接關(guān)系，這里用[N×N]的鄰接矩陣表示，[C（t-1，t）]表示兩個相鄰時間切片的連接關(guān)系，這里用[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]為節(jié)點的鄰居拓撲重疊系數(shù)[14]，即節(jié)點在[Gt-1]時間切片網(wǎng)絡(luò)上與[Gt]時間切片網(wǎng)絡(luò)的共同鄰居數(shù)所占的比例。

1.1.2 基于排名聚合的社交網(wǎng)絡(luò)關(guān)鍵用戶識別方法

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

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

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

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

（3）計算動態(tài)社交網(wǎng)絡(luò)中節(jié)點[v]的影響力得分[gv]。該方法考慮節(jié)點排名順序，利用影響力得分矩陣計算節(jié)點總得分[gv]，[gv]表示如下：

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

1.2 對比方法

為了比較本文提出方法的有效性，采用3種動態(tài)社交網(wǎng)絡(luò)中中常用的時序中心度、時序接近中心性、時序介數(shù)中心性的中心性度量指標(biāo)[11]作對比分析。

（1）時序中心度。節(jié)點中心度表示一個節(jié)點的鄰居節(jié)點數(shù)量，對于一個包含節(jié)點[v∈V]的時序網(wǎng)絡(luò)，在[[i，j]]個時間段的時序中心度[Di，j（v）]表示為在時間間隔[[i，j]]內(nèi)標(biāo)準(zhǔn)化后的節(jié)點出度和入度的總數(shù)量，具體表示如下：

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

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

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

（3）時序介數(shù)中心性。節(jié)點介數(shù)中心性為通過這個節(jié)點的最短路徑所占比例，對于一個包含節(jié)點[v∈V]的時序網(wǎng)絡(luò)，在[[i，j]]時間段內(nèi)時序介數(shù)中心性[Bi，j（v）]表示為：

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

1.3 評價方法

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

動態(tài)社交網(wǎng)絡(luò)效率是評判社交網(wǎng)絡(luò)連通性的一個重要指標(biāo)，其時序全局效率[19]形式如下：

這里考慮刪除節(jié)點后對網(wǎng)絡(luò)連通性的影響，用[E'i]表示。

其中，[ei]表示刪除節(jié)點后網(wǎng)絡(luò)的時序全局效率，[e]表示未刪除節(jié)點時網(wǎng)絡(luò)的全局效率。

2 實驗分析

2.1 數(shù)據(jù)描述

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

2.2 結(jié)果分析

對于Workspace數(shù)據(jù)集，基于排名聚合的社交網(wǎng)絡(luò)度量方法計算關(guān)鍵用戶排序與基準(zhǔn)排序，計算Spearman相關(guān)系數(shù)，同時與其它方法進行比較，結(jié)果如表1所示。

從表1可以看出，本文方法與基準(zhǔn)的Spearman相關(guān)性為0.832 1，表明本文所用方法的排序準(zhǔn)確率高于其它3種常用的動態(tài)社交網(wǎng)絡(luò)度量方法，說明該方法在動態(tài)社交網(wǎng)絡(luò)關(guān)鍵用戶識別中具有適用性和有效性。

3 結(jié)語

近年來，帶有時間屬性的動態(tài)社交網(wǎng)絡(luò)成為社交網(wǎng)絡(luò)研究的熱點。本文通過研究動態(tài)社交網(wǎng)絡(luò)表征模型，提出了基于排名聚合的關(guān)鍵用戶識別方法。經(jīng)Workspace數(shù)據(jù)實驗，基于排名聚合的社交網(wǎng)絡(luò)關(guān)鍵用戶識別方法優(yōu)于其它3種度量指標(biāo)，證明了該方法的有效性，同時為動態(tài)社交網(wǎng)絡(luò)關(guān)鍵用戶的挖掘研究提供了思路。

但本文提出的方法是基于兩個小規(guī)模網(wǎng)絡(luò)的，后續(xù)將考慮在大規(guī)模網(wǎng)絡(luò)中應(yīng)用該方法進行研究。

參考文獻：

[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]劉建國， 任卓明， 郭強，等. 復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究進展[J]. 物理學(xué)報， 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]任卓明， 邵鳳， 劉建國，等. 基于度與集聚系數(shù)的網(wǎng)絡(luò)節(jié)點重要性度量方法研究[J]. 物理學(xué)報， 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]王亮亮，李小聰. 社交網(wǎng)絡(luò)用戶關(guān)系分析[J]. 軟件導(dǎo)刊， 2017（5）：156-158.

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

[12]仇麗青， 范鑫. 基于加權(quán)轉(zhuǎn)發(fā)關(guān)系的社交網(wǎng)絡(luò)意見領(lǐng)袖識別算法[J]. 軟件導(dǎo)刊， 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]樓鳳丹， 周銀座， 莊曉丹，等. 時效網(wǎng)絡(luò)結(jié)構(gòu)及動力學(xué)研究進展綜述[J]. 電子科技大學(xué)學(xué)報， 2017，46（1）：109-125.

[16]楊劍楠， 劉建國， 郭強. 基于層間相似性的時序網(wǎng)絡(luò)節(jié)點重要性研究[J]. 物理學(xué)報， 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]朱義鑫，張鳳荔，秦志光，等. 時序網(wǎng)絡(luò)上的隨機游走免疫策略研究[J].計算機應(yīng)用 ，2014，34（11）： 318-329.

（責(zé)任編輯：杜能鋼）

收稿日期：2019-11-06

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

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