基于复杂网络特征的角色发现算法研究综述

魏旭光，郝晓倩，毕雪燕

（河北工业大学经济管理学院，天津 300400）

0 引言

复杂网络节点数量的激增与其复杂性的逐步升级，使角色发现研究的现实需求逐步增强。角色指具有相同结构特征的节点在网络中承担相似职能，角色发现通过量化节点结构，判定节点在网络中的角色，对分析网络结构、研究节点间关系具有重要意义。

角色发现最初用于识别个体在社交网络中承担的角色及其特征。近年来，角色发现研究逐渐深入到在线社交网络［1］、通信网络［2］、合著网络［3］、生物网络［4］等诸多领域。研究者针对复杂网络拓扑结构特征，从网络整体对网络中的各类角色进行分析，或识别影响者、意见领袖等重要节点［5］，以便进行网络管理。

角色发现作为重要的复杂网络分析工具，通对网络节点进行识别、分类及深入分析，应用领域不断拓展。本文在归纳已有角色发现概念和方法基础上，区分基于图的角色发现和基于特征的角色发现两种研究范式，梳理研究逻辑，解析各方法特点和适用条件，继而对角色发现的动态研究方法进行梳理与说明。研究结果完善了对角色发现已有研究的系统认识，区分了角色发现方法的适用性，有助于拓展角色发现应用领域的新边界。

1 基于图的角色发现

基于图的角色发现是早期角色研究的主要方法，以图论为基础，研究者根据结构等价性划分角色。研究基于自同构等价、正则等价及随机等价等等价标准及多种相似性度量方法，如结构相似性或社会距离等。基于图的角色发现衍生出块模型、概率图模型及邻接矩阵相似性3 种主要方法。

（1）块模型方法。块模型方法基于随机等价理论，通过建立交互图表现网络角色关系，后续研究者提出了随机块模型（SBM）、广义块模型及混合隶属度随机块模型（MMSB）等。其中，随机块模型得到了广泛应用与改进；Edoardo 等［6］针对算法只支持单一角色的不足，提出快速嵌套变分推理算法用于多重角色发现；Fu 等［7］基于MMSB考虑节点角色的动态变化，建立动态混合隶属度随机块模型（dMMSB）；徐建民等［8］基于在线社交网络具体特征对分类混合隶属度随机块模型模型（aMMSB）进行改进，加入节点间单向关系，改进节点隶属度评价指标。

（2）概率图模型。概率图模型以图为依托表现变量概率的依赖关系，是近年来不确定性推理的研究热点。基本的概率图模型分为贝叶斯网络和马尔可夫网络两大类。早期的角色发现研究基于贝叶斯网络模拟人类推理过程中因果关系的不确定性，以马尔可夫链蒙特卡洛方法（MCMC）为主要方法进行节点的角色归类。Aaron 等［9］在此基础上利用先验概率加快学习速度，以多智能体（Multi-Agents）强化学习并对MCMC 模型进行改进。此外，也有研究采用DP（Dirichlet Process）［10］确定角色数量并进行参数优化。

（3）邻接矩阵的行/列相似性。此类方法以节点邻接矩阵为基础，以矩阵行/列之间的相似性度量划分角色。首先，以相似性度量指标（如闵可夫斯基距离、欧氏距离、余弦相似度等）计算邻接矩阵相似性；然后，对相似度矩阵进行处理，例如采用CONCOR 算法对相似度矩阵进行相似性计算，迭代至形成一个仅包含1 和-1 的系数矩阵即进行二分，通过不断对子群进行二分实现角色分类［11］。此外，也有其他聚类方法实现类似处理过程，代表性算法有Sim-Rank、RoleSim 等。

综上，基于图的角色发现方法以等价概念为理论基础，结合概率论及矩阵论等，以网络整体为分析视角对网络图进行分割，在网络整体层面的角色发掘任务中表现较好。但此类方法仅基于节点的结构相似性进行角色发现，计算复杂度较高。因此，基于图的角色发现方法更适用于复杂度较低、网络规模较小的研究。现实背景下，企业网络、在线社交网络及通信网络等典型网络的规模不断扩大，实时分析需求不断提升，其计算复杂度方面的劣势愈发明显。

2 基于特征的角色发现

基于特征的角色发现算法以复杂网络理论为基础［12］，选取具有代表性的度量指标对节点进行描述与分类。根据划分粒度不同，本文将建立在特征基础上的角色研究分为基于二维度量的角色发现和基于多维特征的角色发现。

2.1 基于二维度量的角色发现

该方法选取两种特征建立坐标系，将所有节点按照两个指标的表现强弱划分为4 种或以上的角色类别。一类研究单纯基于节点指标进行角色划分：Burt［13］基于表现突出程度及其与结构等价节点的交互程度，将节点归类为4个经典角色；李婉钰［12］根据出拓扑势值及入拓扑势值定义4 种经典角色，计算节点与4 种角色向量的欧氏距离以确定节点角色。第二类研究将角色发现与社团发现相结合，基于社团发现结果定义节点角色。Zhu 等［14］在社团划分基础上定义inner rank 和outter rank 指标，分别表示节点与社团内节点的连接强度及节点与社团外节点的连接强度，将节点区分为4 类角色。Jerry 等［15］依据模块度函数Q 测定链结构与社团间的关联程度，根据社团聚类结果与社团间的连接度定性地分配为4种角色。

综上，基于二维度量的角色发现方法多结合应用场景改进其度量指标及角色划分原则。该方法适用于较少节点的粗粒度分类，但利用指标数量有限，且角色的表达能力存在局限，对多重特征及其动态变化灵敏度低，不便于对复杂网络进行动态研究与角色预测。其局限性无法支撑其成为研究的主要发展方向。

2.2 基于多维特征的角色发现

基于多维特征的角色发现方法对大规模复杂网络研究更加灵活，是角色发现的研究热点。此类方法考虑角色发现研究需要和无监督学习算法优势，将聚类算法如Kmeans 聚类、DBSCAN 聚类及降维分析算法如非负矩阵分解（Nonnegative Matrix Factorization，NMF）及Trucker 分解等应用于角色发现，推动了角色发现在各研究领域的发展。本文依据所用算法类别差异，将基于多维特征的角色发现归纳为朴素聚类和矩阵分解两个主要类别以及张量分解等其他研究方法。

2.2.1 朴素聚类

朴素聚类算法根据聚类原理可分为分块聚类算法、层次聚类算法、密度聚类算法、网格聚类算法等。研究者使用聚类算法对节点特征进行聚类，将特征相似或特征距离接近的节点归类为一种角色，已有文献中的代表性聚类算法有K-means 聚类和DBSCAN 聚类等。

K-means 聚类是一种基于划分的聚类算法，根据节点特征计算，首先需指定质心初始值，初始划分后再为每一类重新计算质心，如此迭代，以质心体现某类型节点的平均特性，作为此类节点的角色。Yu 等［16］将K-means 应用于社会网络角色分析，定义了基本群体描述、社会行为及结构洞等11 项特征并进行角色聚类。针对经典K-means需指定角色数量等不足，部分文献采用贝叶斯信息准则（BIC）作为最佳聚类数量选择依据。

DBSCAN 聚类是基于密度的有噪声应用空间聚类，通过对特征空间密度检测对节点进行聚类，密度大的区域为节点类内部，密度小的区域为类的界限。Xiao 等［17］借助二维网格空间图对算法的角色检测原理进行说明，并首次将算法置于并行分布式计算环境下，进行在线社交网络的角色分析。

朴素聚类算法相对灵活，但该方法只能将节点划分至单个角色，难以通过角色的软分配对节点角色演化趋势作进一步分析。此外，该方法仅体现节点的最终分类结果，结果准确性受研究者先验知识影响，这是朴素聚类算法进行角色发现面临的主要挑战。

2.2.2 矩阵分解

以矩阵分解进行节点角色发现的步骤包含特征选择、特征处理及非负矩阵分解，详细过程如下：

（1）特征选择。节点基本特征包括局部特征、全局特征、位置特征及随机游走等。局部特征考虑节点本身及邻居节点信息，计算复杂度低。全局特征反映节点的全局性结构特征，有助于把握节点的整体性特征，但计算复杂度较高。位置属性是对节点网络位置的刻画，最常用的K-壳分解法可确定节点的网络位置，该方法对于节点重要性研究具有重要意义。随机游走特征则指在随机游走前提下确定节点影响力的方法，例如PageRank、LeaderRank 等。4 种特征可灵活结合，也有部分研究将基于图的节点分类结果作为特征之一，有助于提升节点特征的全面性，可挖掘出更有意义的潜在角色［18］。

以上文献均基于低阶特征进行角色发现。低阶网络特征指仅表示节点两两交互连接的相关属性，如度、介数等；而网络中的诸多高阶属性，如模体（motifs）、最大派系、三角形数等，可发掘网络中更高阶的连接关系。Nesreen等［19］首次利用模体（motifs）进行特征提取，通过迭代运算将特征进行深度筛选，使特征矩阵构建更具有深度与代表性。Pei 等［20］使用包含3 节点的模体类作为网络特征对Zachary 网络及悲惨世界人物关系网络进行潜在角色挖掘，与MMSB、MMTM 等已有算法相比，其对角色的定位更加准确高效。

（2）特征处理。特征处理对模型准确度具有重要作用。配合后续矩阵分解实施要求，对单一特征值作归一化、标准化等预处理，可使数据实现无量纲化或缩小数据波动范围。对多维特征进行降维，通过Filter、Wrapper 或Embedded 方法进行特征筛选，可使特征表征能力得到提升。已有研究大多延续ReFex 算法［21］的特征处理方法：通过递归法对特征进行交互，并通过垂直对数分箱法及特征关联图对递归特征进行筛选（如算法1 所示）。角色发现算法构建具有灵活性，研究者可使用其他特征处理方式进行特征矩阵构建［2］。

算法1Refex 特征递归

（3）非负矩阵分解。给定非负矩阵Gn×m，将该矩阵分解为两个非负矩阵Wn×r及Hr×m，使Gn×m≈Wn×rHr×m；其中，Gn×m为节点—特征矩阵，n 为节点数量，m 为特征数量；Wn×r与Hr×m分别为节点—角色矩阵与角色—特征矩阵，r为角色数量。

研究者就角色数量选择、分解约束条件等不断作出改进，并就分解结果的解释与评价提出了诸多经典模型。利用矩阵分解算法进行角色发现的研究多基于RolX 算法［2］，该算法以F 范数最小化为目标函数对特征矩阵进行非负矩阵分解，通过最小描述长度方法（MDL）进行角色数量选择，实现基于特征的自动角色识别。将角色发现应用于图的去匿名化、迁移学习及相似度评估等多个数据挖掘任务中，拓展了角色发现与其他领域的关联研究。

Gilpin 等［22］针对算法的无监督性提出基于约束引导的角色发现算法GLRD，将分解过程视为每行每列对应处理的子问题，使矩阵分解转化为凸优化问题，且分别将稀疏性约束、多样性约束与可选择性约束加入矩阵分解过程，用于发现更具有可解释性、创新性的潜在角色集合。

RIDεRs 算法［23］是εER 准则下基于图与基于特征的角色发现算法的结合，εER 准则是一个基于图的等价概念。设置ε 为节点间的平均度松弛值进行节点的块划分，将划分结果作为节点特征之一，并提出基于零模型的角色评价方法。

2.2.3 张量分解

张量指代三阶及以上的高阶张量，张量可以包含更广维度的节点特征，包括时间维度、网络层级关系等，研究者可基于核心张量开展角色演化分析。

于兴隆［24］结合节点角色的现实意义选择平行因子分解，以误差平方和及核一致性诊断确定角色数量，将三维特征矩阵分解为角色—时间映射关系及节点—角色映射关系，实现了时间维度下角色的演化研究。段松青等［25］类似地采用CP 分解将节点映射为权威性角色及枢纽性角色。Gilpin 等［26］基于多重关系图指出已有研究仅对节点关系进行单一层次划分的不足，建立节点、特征及关系层面的三维张量模型，采用Trucker 分解获得核张量，发掘节点在不同关系层面下的角色。

综上，张量模型相较矩阵具有更高的特征容纳及分析能力，在动态数据分析、复杂关系分析等任务中也较矩阵分析更高效，在节点特征复杂度或数据分析实时性要求较高的网络角色分析中优势更显著，但模型构建复杂度较高。

相较于朴素聚类算法，矩阵分解方法及张量分解方法通过隶属度评分为节点分配不同角色，对角色分配更加灵活。研究者将矩阵分解方法所得的角色—特征矩阵可直观展示各角色特征及角色间的相似度，也可通过意义构建对角色的现实意义进行解析，提升角色发现在各研究领域的可解释性与适用性。

3 基于特征的角色发现动态研究

动态角色分析通过对网络中节点角色随时间变化的演变规律挖掘演化过程中网络的结构性及功能性变化。动态网络的时序演化过程增加了其量化表示与研究的难度，动态网络的角色发现研究仍处于起步阶段。

动态网络的角色发现包括历史快照及张量模型两种方法。快照研究将动态网络分割为快照子图，分别在各快照中进行角色识别，最终对各节点的角色演化过程进行分析。Rossi 等［27］利用历史快照方法进行网络角色的一系列研究：首先基于网络动力学提出混合隶属度动态模型DBMM，并将核函数模式与时间权重衰减法结合进行角色预测。此外，李川等［28］针对TM 模型中矩阵转移方法只考虑前一时刻角色的不足，构建二阶训练模型MTR-RP 进行角色的动态研究及预测。冯冰清等［29］基于向量自回归（VAR）方法进行角色的动态分析与预测。

张量分解方法凭借其高维特征优势，将时间序列作为张量模型的时间维度，通过张量分解过程直接获得时间—角色序列，对节点角色演化规律进行剖析。于兴隆［24］、段松青等［25］均将时间维度建立在张量模型中进行角色动态分析。

快照分析建模简单且计算复杂度低，适用于数据的时间跨度较小或数据变化较慢的研究领域；张量模型分析建模复杂度较高，但在角色的演化分析任务中更加高效。在动态分析基础上，对节点角色的预测研究也成为近年来的研究重点。目前，对节点角色的预测工作还限于线性模型和向量回归方法。然而，角色发现预测属于时间序列预测问题，诸多时间序列预测方法均可运用于角色发现任务中。

4 研究展望

本文简要归纳了基于图的角色发现研究原理及主要方法，并分静态与动态对基于特征的角色发现研究进行梳理。基于图的角色发现为早期研究的主要方法，但计算复杂度高、灵活性差，在大规模复杂网络中难以扩展。基于二维度量的角色发现方法以便捷性和与社团发现等方法的易结合性在基于特征的角色发现研究初期起到了重要作用。以朴素聚类、矩阵分解等为代表的机器学习方法则使基于特征的角色发现算法以细粒度深入探讨复杂特征，为更多复杂网络研究提供了新视角和有力工具。基于角色发现的理论必要性与需求现实性，以及对角色发现已有文献的梳理与分析，本文从理论与实践角度对未来研究方向进行展望。

4.1 理论延伸方向

4.1.1 基于图与特征混合方法的角色发现

基于图与基于特征的角色发现算法各具优势，研究者通常从中择其一。事实上，两种方法的结合可使研究兼顾网络全局与局部信息，使角色更贴合实际。RIDεRs 算法是对两种方法结合的初次尝试，但该方法仅将基于图的特征利用特征矩阵的方式进行构造，未考虑局部特征，故两种方法的结合仍是后续研究的方向之一。

4.1.2 边角色发现

网络的复杂性不仅源于节点变化，更源于节点间连接关系的变化，如企业规模、中心性及度等特征在较短周期内变动较小。但企业间的合作关系变动速度相对较快，对合作关系的分析更能体现企业在网络中承担的角色等。因此，网络中边角色的分析极其重要。已有文献多以节点为中心展开研究，对网络中边角色的挖掘工作较少，Nesreen 等［19］已在其部分研究中开始了对边角色发现的探索，边角色发现方法在经济、交通及社交网络等领域有很大研究空间。

4.1.3 时序网络

时序网络是复杂网络的扩展，可在网络中记录节点在历史时刻的交互信息和交互次序。传统网络研究基于系统动力学将时间维度编码于动态系统，而时序网络将时间维度提升至网络本身的数学性表征，对节点交互和网络拓扑结构的异构性研究以及大规模动态现象的解释和预测具有重要意义。时序网络与角色发现在大规模网络、动态网络及角色预测方面的理论和实际需求日益突出的现状十分契合，借助时序网络的一般方法可对潜在角色进行更深层次的挖掘与分析。

4.2 实践应用空间

目前，角色发现方法主要应用于社会网络、生物网络及通信网络等。随着角色发现静态方法的不断完善，动态研究依托的理论基础不断丰富，角色发现研究可扩展到更多实践领域。供应链网络是典型的复杂网络之一，网络中的企业具有很强的实体意义，企业角色对于供应链网络的节点研究、演化研究具有重要意义。

企业的角色不仅取决于企业规模，也与交易额、专利数目等各方面特征密切相关，供应链网络显著的层级性也通过影响企业在网络中的位置使企业承担角色各异。在创新网络中进行角色发现研究，能够对创新网络和专利网络中节点角色的识别与演化产生更加清晰的认知与理解，以角色为依托的演化研究也可借助创新主体的合作行为促使网络的良好发展。此外，在典型的病毒网络研究中，由于同构节点传播效果相似，节点的角色识别可用于同构节点的识别与病毒网络的演化研究，拓展病毒网络研究方法与研究视角。

除上述详细说明的3 个理论延伸方向与3 个实践应用延伸外，角色发现还可借助分布式平台、并行式平台实现海量数据处理，借助迁移学习实现跨领域知识的学习与应用，借助分层网络对多种交通方式进行综合研究等。综上所述，角色发现方法的基础研究已经逐渐完善，随着横向研究领域与纵向研究深度的不断发展，角色发现研究依然面临诸多现实问题，因此具有广阔的发展空间。