角色（Roles）

role指的是节点的角色或功能（function），我们可以把角色相近的节点归类为同一种role，比如度很小的节点可以归类为边缘节点。

注意，role只要求角色相近，这种相近往往只需要参考节点所在的子图来判断即可，如果要在全图上判断两个节点是否是结构等同（structural equivalence），就需要判断图中所有其他节点与这两个节点的关系是否完全相同。很显然，角色相同的节点未必是结构等同的，比如下图中，红色节点的角色都是星型结构的中心节点，但是它们与其他节点的结构关系几乎各不相同。

角色发现算法

我们可以利用一些模型来找到角色相近的节点，RolX（Role eXtraction）是一个常用的角色发现方法（Role Discovery Method）。RolX 的输入数据是图的邻接矩阵，首先进行特征提取（Feature Extraction），得到每个节点的特征向量（Feature Vector），然后进行角色提取（Role Extraction），得到节点 角色矩阵和角色 特征矩阵。

特征提取是第一个关键步骤，这里所指的特征是针对每个节点来计算的，常见特征分三类——Local、Egonet和Recursive。

• Local Feature是针对节点本身的特征，比如度、集群系数等；
• Egonet是由节点及节点的邻居节点构成的子图，可以针对这个子图计算各种特征，比如子图的节点数和边数、节点的平均度数、节点的平均集群系数等；
• Recursive Feature是针对已经计算出的特征进行二次加工，得到特征的特征，比如邻居节点的特征的平均值（类似GCN的思路），或者当前节点某些特征的统计量（均值、求和等）。

Role Extraction是第二个关键步骤，它的思路是在Node Feature Matrix 的基础上进行无监督建模，把节点划分到不同集合中，每个集合代表一种角色。最直接的方法是进行 NMF（non-negative matrix factorization，非负因式分解），直接把Node Feature Matrix分解成 Node Role Matrix 和 Role Feature Matrix两个矩阵，关于这个方法的细节可以参考RoIX Paper。