唐诗琦 怀 念 陈 军 胡俊勇

(武汉大学计算机学院国家多媒体软件工程技术研究中心 湖北 武汉 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)算法。……