kevin64zhang的个人博客分享 http://blog.sciencenet.cn/u/kevin64zhang

博文

[转载]Structural roles in networks

已有 1070 次阅读 2020-12-10 21:05 |个人分类:论文读取与总结|系统分类:科研笔记|文章来源:转载

同样来自【斯坦福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

灰色:大部分节点,不属于团,也不属于链

绿色:细长的聚类

购买网络:红色节点——中心,蓝色——外围




https://m.sciencenet.cn/blog-3413082-1261961.html

上一篇:[转载]subgraph, motif, and graphlet
下一篇:[转载]评估信息物理系统的威胁建模方法

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2023-1-30 09:28

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部