Subgraphs, Motifs and Graphlets
- 主题(motif)：反复出现的、显著的相互连接的模式
- Pattern：小的生成子图（对于一个结点集合，集合中所有的边与原图中的边完全重合，不多不少）
- Motifs的作用
- 帮助我们理解网络的工作机制
- 帮助我们预测网络产生的效果等
- 例子：
- Motifs
- 生成子图示例：
- 重复出现（Recurrence）：motifs是允许重叠出现的，并不要求完全一致
- 比如下图中motif出现了4次
- 显著性（Significance）：比较子图在真实网络中出现的频率与在随机网络中出现的频率，若真实网络中出现的频率明显较高，则我们认为它是显著的
- Motifs在网络中是被过度表示的
的值表明了motif i的显著程度，它是一个度量标准，不受网络大小等因素的影响：
- Network significance profile (SP)：将所有做了归一化处理，转化为一个向量。SP注重子图之间相对的显著性，这样就可以更好地比较不同大小的网络。一般来说，大的网络Z值也会更高
- Configuration Model（随机构造网络的算法）：根据结点度的序列（使结点数、边数与原图相同）随机生成一张图。非常巧妙、非常简单。首先我们把所有结点想象成一个轮辐，即一个结点拥有与它的度数量相同的触手。之后，我们将序列中的每个结点进行处理，一个结点的度是几，那么给它画出多少小结点。之后，我们将序列中的所有小结点随机地两两相连，汇总连通信息后，我们就得到了最终的图。
- Switching（对图继续进行随机再造）：随机地两两交换边的终端，但这种方法比前者要慢
- 侦测motif的步骤：
- 在真实网络中计算子图i的出现次数
- 在随机生成的网络（通常生成几百几千个）中计算子图i的出现次数（随机网络的结点数、边数、度分布与原始网络完全一致）
- 计算i的Z-score，若得分很高，则子图i是原图的一个motif
Graphlets：Node feature vectors
- Graphlet：连通且不同构的生成子图，用于获取结点级别的子图标准。motif是全图级别的子图标准。
- 在一个图中，结点所处的位置可以是独特的，也可以是多个结点共有的，比如对G1而言，结点在图中的位置只有两个，要么在两边，要么在中间。
- 既然结点的度代表了一个结点与多少条边关联，那么我们也可以类比一下，Graphlet degree vector代表了一个结点与多少graphlets相关联。比方说对G9而言，结点可以接触3个位置。
- Graphlet degree vector（GDV）：一个结点所在位置的频率组成的向量。通过计算一个节点所在的Graphlets中不同的非对称位置，可以对节点附近的局部结构进行衡量。
- 对于下图，我们可以点v对于每个位置的GDV，即多少graphlets可以在v的位置是x时出现。a、b很明显，但c是0，因为graphlet是生成子图，若点v在c的位置，另外两个点是不应该相连的，然而在图G中两个点是连着的。
- 若我们对图中一个结点考虑2-5个结点的graphlet，那么我们可以得到73维度的的一个向量，因为有73个位置。它表示了结点邻居（长度为4的距离内）的拓朴结构。
- GDV给出了一个节点附近的拓扑结构的衡量。
Finding Motifs and Graphlets
- 查找给定网络中大小为k的motifs或graphlets有两个挑战：
- 枚举所有大小为k的连通子图
- 计算每个子图的出现次数（np完全问题）计算时间指数级上升，可行的motif大小通常在3-8之间
- ESU算法
- 建立两个集合：子图结点集合（目前建立的子图）、扩展集合（可扩展motif的候选节点集合）
- 从一个结点v开始，把满足以下两个条件（u结点的id大于v；u只与一些新加入的结点邻接，且它不是任何在子图节点集合的结点）的结点加入扩展集合
- 递归树示例：
- 找出具有一定结点数的子图后，我们对子图进行分类
-
Structral Roles in Networks
Roles是在一个网络中结点起到的作用，例如食物链中的各个种族，公司中的每一个人。
- Roles的定义：具有相似结构属性的节点集合。与组或社区不同，组或社区是通过邻接，可达性定义的。Roles与社区相互补充。
- 例如考虑一个计算机学院的社交网络：
- Roles由教员、工作人员、学生组成
- 社区由AI研究室、信息研究室、理论研究室组成
- 例如考虑一个计算机学院的社交网络：
- 结构等价：若节点 u 和节点 v 与所有其他节点拥有相同的关系，则称节点 u 和节点 v 结构等价。
- 如下图，u和v是结构等价的
Discovering Structrual Roles in Networks
- RoIX：自动检测网络中结点的structural roles。一种无监督学习方法
- 步骤：
- Recursive feature extraction（递归特征抽取）：通过递归特征抽取，将节点转化为特征向量，该特征向量包含了该节点本身、节点的邻居，以及它与什么样的节点向量的信息。
- local特征：有关结点的度，可能包含出度、入度、带权信息
- Egonet（自我中心网络）特征：在自我中心网络上进行计算，包括网络中的边，以及网络与外部相连的边等等
- 递归特征：结点与什么类型的结点相连？
- 算法步骤：
- 以基础特征集作为开始
- 使用当前节点特征集生成新特征：使用mean和sum两种聚类。如计算一个结点周围unweighted dgree的均值，或计算所有现有特征的均值或总和。
- 重复2
- 随着每次递归迭代，生成特征的数量呈指数增长。故可以使用剪枝减少特征数量：
- 寻找高度相关的特征对
- 当两个特征的相关性超过用户定义的阈值时，删除其中一个特征
若有收获，就点个赞吧
0 人点赞
