一种基于局部与全局结构特征的网络节点角色发现算法

唐诗琦 怀 念 陈 军 胡俊勇

(武汉大学计算机学院国家多媒体软件工程技术研究中心 湖北 武汉 430072)(国网湖北省电力公司江陵县供电公司 湖北 荆州 434000)

0 引 言

基于节点结构特征的角色发现在复杂网络研究中成为一个越来越受关注的问题。具有相似的结构特征(例如度中心性、聚类系数和介数中心性等)的节点被划分为同一角色，例如中心节点、桥梁节点、边缘节点等。节点的角色发现问题在许多领域都有重要的应用，例如：角色可用于IP-traces等技术网络的异常检测[1-2]；可用于在线社交网络中基于用户的角色向用户定制化地投放广告[3]。此外，角色发现在许多社会网络研究应用中也成为了一个重要的工具，例如分类[4-5]、主动学习、网络采样[6]和匿名化[7]等。

近年来，国内外对于角色发现的研究主要基于节点的结构特征。文献[8]根据近年来的研究提出了基于节点结构特征的角色发现方法框架，主要分为两步：(1) 构建角色特征，将图转换为一系列的图的特征。(2) 角色分配，将拥有相似特征向量的节点分配为同一角色。文献[9]提出了RolX算法[9]，该算法是一个可拓展的，无监督学习方法。文献[10]根据Henderson提出的算法，将RolX算法扩展到了动态网络中，提出了动态行为混合成员模型DBMM(Dynamic Behavioral Mixed-membership Model)。文献[11]将RolX算法通过添加稀疏以及多样性约束拓展为半监督的学习算法GLRD。文献[12]则结合了基于图和基于特征的角色发现算法，同时考虑了在网络整体中角色间的连接模式与节点局部特征的连接模式，提出了RIDεRs(Role Identification and Discovery using ε-equitable Refinements)算法。

目前，对于角色发现的研究大多数还是基于网络的拓扑结构，应用节点的局部结构特征[9-11]。本文同时考虑了的节点的全局以及区域特征，递归地生成节点结构特征矩阵，使用非负矩阵分解NMF(Non-negative Matrix Factorization)发现角色。将算法应用于Facebook以及Email-Enron社会网络数据集[13]，并与其他角色发现算法进行评估对比。实验表明，本文所提出算法在局部以及全局评价指标上，相较其他算法具有更高的准确性。

1 节点结构特征矩阵构建

一个网络的拓扑结构记为G(V,E)，其中V={v1,v2,…,vn}是网络中节点的集合，而E={e1,e2,…,em}是网络中边的集合，n和m分别为节点数和边数。一个图的邻接矩阵被记为An×n=(aij)，在无向网络中，若节点vi和节点vj之间存在连边，则aij=1，否则aij=0。

本文综合节点的局部以及全局特征作为原始特征，递归地计算节点特征的总和以及平均值，得到节点的区域特征。在递归过程中若新特征与原特征十分相近时，则认为新产生的特征对网络结构不再提供新的信息，停止递归，由此得到节点的结构特征矩阵。

1.1 节点结构特征

1.1.1 局部指标

在社会网络中，节点的度作为节点的局部特征之一，是一个简单但十分重要的概念。节点Vi的度ki被定义为与节点Vi直接相连的节点的数目。本文使用节点的度中心性作局部指标，构建节点的结构特征矩阵。度中心性表示为：

(1)

1.1.2 全局指标

节点的全局属性具有许多的度量值，为了平衡算法时间复杂度以及准确性，本文选择了基于特征向量的全局属性。基于特征向量的属性，不仅考虑了节点的邻居节点数量，还考虑了其邻居节点的质量对该节点重要性的影响，同时与其他全局属性相比，具有更低的时间复杂度[14]。

(2)

PageRank的时间复杂度为O(n+m)，其中n和m分别为网络中的节点数和边数。另外由于PageRank的算法是用于有向图的，在本文的实验中，无向图的计算将自动将两个节点间的边转换为两个有向边。

1.2 递归特征

本文参考文献[16]在2011年所提出的ReFeX特征提取方法，将度中心性和PageRank作为原始的特征值，然后递归计算当前节点个体网络的特征值和以及平均值，并对相似特征值进行分箱处理。若递归产生的特征值向量与原特征值向量的方差小于相似度阈值，则终止递归。为控制生成递归特征的数量，减少算法复杂度，经过多次实验，设置初始相似度阈值为0，并在每一次递归结束后增加3。递归特征的生成流程见图1。

图1 递归特征生成流程图

算法伪代码如算法1所示。

算法1生成节点递归特征矩阵

输入：网络G

输出：包含原始特征和递归特征的特征矩阵V

1 计算网络G中节点的PageRank和度中心性，获得原始特征矩阵F

2 设置相似度阈值threshold=0

3 while(true){

4 计算每个节点自网络中的所有节点在F中的特征值之和与平均值得到Fnew

5Fall=F+Fnew

6 设置BinFraction=0.5

7 for eachfiinFall{

8fsorted=fi.sort()

9 设置BinValue=0，NumNodes=网络G中的节点数，NumAssigned=0

10 NumToAssign= ceil(BinFraction *(NumNodes - NumAssigned ) )

11 for j in NumToAssign do {

12fsorted(j)=BinValue

13 }

14Fbin+=fsorted

15 NumAssigned+=NumToAssign

16 ++BinValue

17 }

18 创建新的网络Gwcc，以Fbin中每个特征fi作为节点i

19 对于每对节点，如果|fi-fi+1|>threshold，则在点i与点i+1间添加边

20 得到网络Gwcc的连通组件，取每个联通组件中的第一个节点k所对应的特征fk添加到特征矩阵Fretain中

21ifFretain.length==0 {break;}

22 else {

23F+=Fretain

24 threshold+=3

25 }

26 }

2 角色发现

2.1 矩阵分解

通过节点特征矩阵构建步骤，得到了节点-特征矩阵Vn×f，其中n为节点个数，f为对应的特征个数。使用非负矩阵分解NMF，对于给定的矩阵Vn×f，存在正整数r<

(3)

s.t.G≥0F≥0

式中：Gn×r的每一行代表了该节点属于每个角色概率分布；Fr×f的每一列指定了特定角色的成员关系如何有助于评估特征值。

在执行矩阵分解时，需要确定整数r(即节点被分配的角色)的数目。对于该问题，本文选用了最小描述长度MDL标准来选择角色分配数量的最佳估计值r。

对于给定的模型，可以通过计算两个部分来得到所需的描述长度r：(1) 描述模型本身所需要的比特数M；(2) 描述V-GF的重构误差(实现无损压缩)的代价ε。最终得到的最优的r值，即最小化描述长度L的值，即L=M+ε。

假定G和F不是稀疏矩阵，则描述该模型的成本被定义为：

M=br(n+f)

(4)

式中：b的值取log2(n)，则弥补V-GF重构误差的代价为：

(5)

这里使用到了KL散度来进行计算。

为确定算法所发现角色的数量r，首先使用不同r值进行非负矩阵分解，得到不同的矩阵G与矩阵F，再使用最小描述长度方法进行计算。当计算得到的L值最小时，即得到了当前网络的划分角色数量r。

2.2 意义建构

由文献[9]中提出的NodeSense意义建构方法可以很好地应用于大型网络中。由于大型网络不易于图形化，使用相应的度量指标对角色进行评估，可以更加直观地分析得出该节点角色在网络中的作用。

对于评价指标，本文选用了全局属性介数中心性，接近中心性，局部属性聚类系数以及邻居属性节点个体网络中的各个节点度之和共m个评价指标。

在NodeSense方法中，给定网络G、n个节点、r个角色以及m个评价指标。对于网络G中的每个节点，计算其在m个评价指标中的得分，从而得到对应的节点评价矩阵Mn×m。在角色发现算法中，通过矩阵分解步骤，得到了节点角色矩阵Gn×r。NodeSense方法将矩阵Mn×m和矩阵Gn×r作为输入，计算得到一个非负的角色评价矩阵Er×m，其中M≈GE，对于minE‖M-GE‖2，满足E≥0。再根据角色评价矩阵E，计算对应的NodeSense矩阵N：

(6)

式中：Ed为1×m维非负矩阵，代表了单个角色在M个评价指标中的得分；N为r×m维矩阵。

3 实验与结果分析

本文实验使用斯坦福大学SNAP项目中的Facebook及Email-Enron数据集[13]进行实验，数据集的具体信息见表1。

表1数据集

数据集节点数边数平均度网络直径FaceBook4 03988 23421.9468Email-Enron36 692183 8315.01011

在以往的工作中，往往将角色发现作为辅助手段应用于如链路预测和异常检测等研究中。因此，目前角色发现领域并未发展出权威的、公认的评价体系。为将本文算法与其他的角色发现算法进行对比，评估各个算法的性能，本文参考文献[12]中提出的评价方法。该方法引入了复杂网络中社区划分评价标准模块度[17]的思想，对实验中的每个网络中的节点随机分配角色，得到对应的零模型。计算节点所分配角色的NodeSense值与对应零模型的NodeSense值的平均绝对误差，评估该角色发现算法的性能。平均绝对误差的数值越高，表明该方法的性能越好。

对于给定的网络G、n个节点以及相应的角色发现算法所得到的r个角色，对该网络中的每个节点随机分配一个角色，由此得到随机分配的节点角色矩阵Gr。由式(6)计算得到该随机分配的节点角色矩阵对应的NodeSense矩阵Nr。计算该角色发现算法的NodeSense矩阵N与对应的随机分配NodeSense矩阵Nr的绝对误差：

(7)

同时由式(7)可计算得到平均绝对误差：

(8)

本文将实验结果与RolX算法和GLRD算法进行对比，其中GLRD算法由其稀疏性和差异性约束分为GLRD-S和GLRD-D(详情见文献[11])，对比几种算法NS值与零模型NS值的平均绝对误差。实验对比数据如表2-表3所示。

表2 基于FaceBook数据集的算法性能对比

表3 基于Email-Enron数据集的算法性能对比

由表2和表3可知，本文所提出算法在介数中心性、接近中心性、个体网络，以及聚类系数四个评价指标上，均比其他算法具有更高的性能。

4 结 语

本文针对复杂网络中的节点角色发现问题，基于节点的结构特征，在RolX角色发现算法的基础上，引入节点的局部以及全局特征进行特征提取，构建节点结构特征矩阵，使用非负矩阵分解对节点结构特征矩阵进行降维，获得对应的节点角色矩阵。并使用几种不同的节点重要性评价指标对分析所得的角色进行意义建构，同时对比RolX与GLRD角色发现算法。实验结果表明本文提出算法在局部以及全局属性上具有更高的性能。下一步工作将本文提出算法应用于更大规模的数据集中，以满足真实场景中更大规模数据的处理以及分析需求。