一种基于排名聚合的社交网络关键用户挖掘方法

来源:用户上传      作者:

　　摘 要：带有时间属性的动态社交网络逐步成为社交网络研究热点。相比静态网络，动态网络考虑用户交互发生的先后顺序，能够更直接地描述用户的交互关系和顺序。传统社交网络挖掘方法往往从用户交互路径进行评估，忽略了动态社交网络中交互时间片段的相互影响。综合考虑用户的交互顺序与时间影响，采用超邻接矩阵描述动态网络，并用排名聚合理论对用户影响力进行综合排名，提出了一种基于排名聚合的社交网络关键用户识别方法。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<j）]内节点v与其它节点[μ∈V/v]之间的时序距离。
　　（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-），男，上海财经大学金融科技研究院教授，研究方向为在线社会网络分析。
转载注明来源:https://www.xzbu.com/8/view-15217626.htm