同样来自【斯坦福CS224W 图与机器学习 3】：Motifs and Structural Roles in Networks http://web.stanford.edu/class/cs224w/slides/03-motifs.pdf 

该部分内容值得去深入探索，尤其是节点特征表示的部分。

Structural roles in networks

Role: 角色， 是对节点在网络中功能的描述， 是有相同结构特征的点，相同角色的节点并不一定直接相连，而Group/Communities(社群)， 是彼此相互密集连接的节点群；

视频中举了个例子，假定一个计算机系构建一个社交网络，其中：

• 角色指： 教职、职员、学生；

• 社群指： AILab、Info Lab、 Theory Lab等；

• 
  

如果节点u和节点v和所有其他节点有相同的关系，则说明节点u和节点v在结构上等同， 如下图中u和v完全相同；

Discovering Structural Roles in Networks

为什么要研究图当中的role ？如下图：

RoIX: AutoMatic Discovery of nodes' structural roles in network

RoIX特点如下：

• 非监督学习方法；

• 无需先验知识；

• 支持多种角色分类；

• 按边数线性扩展；

RoIX过程如下图， 其中最重要的Recursive Feature Extraction.

Recursive Feature Extraction是基于图的结构详细，从某一节点出发，聚合该节点的特征，如有向图中，该特征未出度、入度、度等等，其次基于该node的邻居、包含该节点的可导出子图，这称之为Egonet，也会提取Egonet中节点的特征。以此类推，用这种方法提取到的特征，是指数级增长，后续会使用裁剪技术将部分特征裁剪掉；

最终，每一个节点会由如下图的向量表示， 然后采用non negative matrix factorization（KL离散度距离来评估似然度） 即可完成流程图中node * role matrix与role * feature matrix的生成：

local features：节点度的度量。若为有向图，包含出度，入度，总度；若为带权重的图，则包含权重向量

egonet features：计算节点的egonet（自我网络？）

    egonet包含：节点，邻居，边

此外，还增加平均和最大这两个统计特征

RoIx：使用 non negative matrix factorization 用于聚类，MDL（最小描述长度？）用于模型选择，KL散度用于相似度衡量

应用：结构相似度

将节点基于他们的结构相似度进行聚类：

  通过RoIx获取节点的向量

  向量进行聚类

下图是co-authorship的例子

蓝色：连接紧密

红色：桥梁节点，连接两个group

灰色：大部分节点，不属于团，也不属于链

绿色：细长的聚类

购买网络：红色节点——中心，蓝色——外围