【复杂网络】社区结构

文章导航

× 文章目录

1. 1. 图社区
   1. 1.1. 定义
   2. 1.2. 谱聚类
   3. 1.3. GN算法
   4. 1.4. 基准
      1. 1.4.1. 种植-分区模型
      2. 1.4.2. LFR模型
   5. 1.5. 模块度
   6. 1.6. 算法
2. 2. 图分区的比较（指标）
   1. 2.1. 图聚类
   2. 2.2. 相似性
   3. 2.3. 二元划分
   4. 2.4. 图感知度量
   5. 2.5. 拓扑特征
   6. 2.6. 结论
3. 3. 图的集成聚类（ECG）
   1. 3.1. ECG
   2. 3.2. 分辨率和稳定性
   3. 3.3. LFR 图上的比较研究
   4. 3.4. 真实网络
   5. 3.5. 权重
   6. 3.6. 异常检测

菲尔兹数学科学研究所 复杂网络2019夏令营课程 学习笔记

社区结构

• 图划分（graph partitions）算法比较
• 图聚类算法
• 图上的集成聚类（ECG）

图社区

1. 定义
2. 谱分割
3. Girvan-Newman聚类
4. 基准：种植分区，LFR
5. 模块度
6. 算法

定义

两个基本假设：[Barabasi,Network Science]

1. 一个网络的社区结构在其布局图中是唯一的。
2. 一个社区是网络中的一个局部密集连接子图。

模型：

• 对于一个图，考虑由一个节点的子集诱导的连接子图C（C中的节点满足）。

内部外部度：

• 定义节点的内部度（其在子图C内的度）：

• 节点i的外部度是：

  其中是节点i在G中的总度

强弱社区：

• 如果对每个节点 ， ，则C是一个强社区（strong community）
• 如果对每个节点 ， ，则C是一个弱社区（weak community）

集团和核：

• 集团（clique）是G的一个完全连接的子图。
• k核（k-core）是G的一个最大连接子图，其中所有节点的度数至少为k
  • 我们可以通过反复删除所有度数小于k的节点来找到k-cores
  • 如果一个节点属于k-core但不属于(k+1)-core，那么这个节点的核心度（coreness）为k

簇（聚类）：

• 大小为k的图的聚类（clustering）是一个节点的分区，其中：
  • 所有
  • 对于每个部分（或集群），其诱导子图是连通的

谱聚类

谱聚类（Spectral clustering）是一个庞大的话题，本课程只介绍明谱分割（spectral bisection）

参考：

https://blog.csdn.net/weixin_45591044/article/details/122747024

https://blog.csdn.net/SL_World/article/details/104423536

模型：

• 考虑未加权的无向图，邻接矩阵为A

• D是节点度组成的对角矩阵

• 是G的（未归一化的）拉普拉斯系数矩阵

• G中的社群结构与L的特征分解之间关系紧密

• 对于所有的： 因此，当时，使上述表达式最小化相当于使

求解：

• 考虑比率切分法 ratio-cut ：

  与之对应的还有normalized-cut（将拉普拉斯矩阵归一化）

  这可以近似求解为： 其中，结果是对应于L的第二个最小特征值的特征向量——结论推导见参考博客

讨论：

• L是对称的和半正定的，所以所有的特征值都是实数和非负数。

• L有最小的特征值0；这个特征值的倍数对应于G中连接组件的数量。

• 因此，我们可以对这些特征值进行排序，同时对它们各自的特征向量进行排序。

非连通图情况：

• 有至少两个0特征值
• 按照第二小特征值对应的特征向量，有0和非0两种情况，按这个分类即可。

连通图情况：

• 考虑一个连通图G。它只有一个0特征值。

• 在一个连通图中，特征向量对应于费德勒向量中的。

• 谱分割是基于费德勒向量（第二小的特征向量）中条目的符号。——正为一类，负为另一类

多个社区：

• 如果有2个以上的聚类，这样的过程可以被递归应用
• 这是一个分裂性层次聚类的例子
• 然而，它可能表现得很糟糕，可能会分割本来存在的社区
• 所以我们去，再利用k-means等算法对得到的特征向量进行聚类

总结：

一般适用于分组数量已知的情况，核心是最小化割边总和并最大化每个簇的节点数

GN算法

Girvan-Newman算法

步骤：

• 计算每个 的边介数，并删除具有最高值的边
• 将生成的图按连通分支拆分（簇）并递归地应用该方法
• 这会产生一个聚类层次结构，我们可以将其表示为树状图

——根据一些标准选择最好的分区，比如模块度（modularity）、或指定集群数量

问题：

• 该算法的一个问题是它的时间复杂度：
• 对于非常稀疏的图，也有 ，仍然很高
• 其他算法可以达到 或

基准

为什么要有社区基准模型？

• 测试和比较算法
• 控制噪音水平、社区规模等
• 真实图数据很少有真实值（ground-truth）
• 有ground-truth，但可能与基本假设不一致

种植-分区模型

Planted partitions model

1. 固定节点数 n 和社区数 k，对于社区，我们：

• 平均分配节点到每个社区

• 或将每个节点独立分配给社区 i，概率为 ，

2. 对于分别在社区i和社区j中的节点对，我们按照概率添加边
   • 可以指定、

LFR模型

Lancichinetti-Fortunato-Radicchi model

1. 固定节点数 n

2. 设定三个主要参数：

   1. ：节点度服从 的幂律分布；推荐值为 。
   2. ：社区规模服从 的幂律分布；推荐值为 。
   3. ：对于每个节点，这是连接到其他社区的边的预期比例，而 是其自己社区内的比例。

   —— 称为噪声水平或混合参数

3. 把每个节点都分配到社区
   • 存在允许重叠社区的变体
   • 可以提供额外参数来限制度分布（平均和最大度）和社区大小（最小和最大）
   • 从配置模型开始，重新连接节点以逼近目标分布
   • 初始阶段可以使用BA等其他模型

基准代码生成 3 个文件：

1. 包含节点标记为 1 的边列表的文件
2. 包含节点列表及其社区成员的文件，社区也被标记为 1
3. 具有度分布、社区大小分布和混合参数等统计信息的文件

讨论：

• LFR 的可扩展性有些受限，一些可扩展的基准模型有：

  • RMAT ，生成具有幂律度数分布的图；在 Graph-500 中使用

  • BTER (Block Two-level ER)，生成服从幂律度分布以及社区结构的图

  • SBM（Stochastic Block Model），它也生成具有社区结构的图。

    ——它最简单的定义是种植分区模型的变体。

模块度

引言：

• Barabasi 的第三个基本假设：随机连线的网络缺乏固有的社区结构
• 模块度使用随机连接作为空模型来量化某些图分区的社区结构

模型：

• 考虑无向图

• 令, , 为节点 i 的度数

• 设 当且仅当 ，否则为 0；设当且仅当

• 当我们随机连线时，节点 i 和 j 之间的预期边数（概率）为：

• 令 ，将图划分为 k 个簇。对于某些簇 ，定义： 展开为： 令：

  代入可得：

• 模块度最终定义为：

  我们将上面的第一项称为边缘贡献（edge contribution），将第二项称为度税（degree tax）

• 图的模块度 有时被定义为所有可能分区中上述指标所取的最大值

讨论（局限）：

• Barabasi 的第四个基本假设：对于一个给定的网络，具有最大模块化的分区对应于最佳社区结构。

• 然而，模块化有一些已知的问题——"最佳 "可能并不总是转化为 "直观"。

  基于模块化的算法受到分辨率限制问题的影响：

  • 考虑l个大小为m的集团（m-clique）组成的环，
  • 当时，对相邻的集团进行分组，模块度高于每个集团自己形成集群
  • 正如我们将说明的那样，一些基于模块化的算法因此倾向于对已有社区进行组合

算法

CNM：

CNM算法（Clauset、Newman、Moore），也称为快速贪心算法（Fast Greedy）

• 开始，每个顶点作为一个单独集群
• 选择最能提高模块度的一对集群（如果有的话），然后合并它们
• 当没有办法提高模块度的时候停止
• 复杂度：，稀疏图更少

Louvain：

也称为多级算法（Multilevel algorithm）或快速折叠算法（fast unfolding）

• 开始，每个顶点作为一个单独集群
• 循环遍历每个顶点，将其移动到模块度增加最多（如果有的话）的邻居社区
• 重复以上步骤，直到没有任何提升空间为止
• 将每个社区折叠成一个节点并重新运行上述步骤——另一个层级
• 当图折叠到单个节点（或者当最后一级没有移动）时停止
• 复杂度：

Infomap：

• Infomap基于信息论：使用概率随机游走和压缩算法来实现
• 给定 G 和一个初始化分区方案，尽可能高效地编码随机游走
• 利用随机游走往往在同一社区中停留更长时间的性质
• 优化图方程：社区间游走的平均位数+社区内游走的平均位数
• 复杂度：

标签传播：

• 开始，每个顶点作为一个单独集群，有自己的簇标签
• 循环遍历每个顶点，每个顶点都采用其邻居中最流行的标签（使用随机来打破死锁）
• 当每个顶点具有与其邻域中最频繁出现的标签相同的簇标签时，算法停止
• 复杂度：

——注意：此算法速度很快，但并不总能收敛到一个解。

其他：

1. WalkTrap：一种基于短距离随机游走的分层算法。它的复杂度是 。
2. Leading eigenvector（前导特征向量）：基于模块化矩阵的谱分解。对于每个双分区，其复杂度为

Louvain和Infomap的算法目前被认为是最先进的。

2023年评论：应该是Leiden算法

图分区的比较（指标）

1. 介绍：图聚类
2. 常见的相似性测度量
3. 与二元分类的联系
4. 图感知度量 （Graph-aware measures）
5. 拓扑学特征

图聚类

符号描述：

• A，邻接矩阵：
• ：顶点i的程度

术语解释：

• 图聚类/分割（clustering/partitioning）：将顶点分割成相连的子图
• 社区发现（Community finding）：并非所有的顶点都需要被分配到一个群组中去
• 模糊聚类（Fuzzy clustering）：节点不属于、属于一个或多个群组

图划分：，为节点集的一个划分（partition）

• 每个诱导出一个连通子图
• 是连通分支的泛化
  • 集群内的边密度大；集群间的边密度小

应用：

• 图聚类是关系型EDA（互联网数据分析）的一个重要工具
  • 图尺寸缩减
  • 社区检测
  • 异常检测
  • ……
• 如何挑选聚类算法？
  • 集群的质量
  • 稳定性
  • 效率（时间空间）
  • 其他：不需要指定聚类的数量（k）、集群的层次结构等

优化目标：

• 这是无监督学习，所以没有明确的目标函数

• 不同算法使用不同的目标函数：

  1. 模块度：
  2. N-cut

不同分割方法对比：

• 质量的衡量标准：
• 稳定性的衡量标准：同一算法的运行多次比较
• 比较算法之间的结果：

相似性

总体分类：

• 基于成对计数（Pairwise-counting）

• 基于信息论

• 基于卡方分布（）

基于成对计数：

• 考虑对图节点的两个划分：

• 度量指标基于A和B里面各个集群中的成对元素

• 关键值为：

• 示例：

  1. Jaccard 指数：

  2. 兰德指数

基于信息论：

• 基于 A 和 B 之间的互信息

• 关键值为：

• 示例：归一化互信息 (NMI)：

基于卡方分布：

• 关键值为：

• 示例：Cramer 的 V指标 和 Tschurprow 的 T指标

测量指标vs.大小分布：

问题：比较不同大小的分区时，这些度量指标表现怎么样？

实验（多次重复）：

• ：节点V的划分
• ，V 的随机分区 ，
• 测量 和所有分区 之间的相似性——期望所有相似度都很低

——结果：只有兰德系数变得接近1，其他都随着t的增大减小或趋向0

按概率进行调整：

实现 “在聚类结果随机产生的情况下，指标应该接近零”

• 成对计数指标的调整：

• Jaccard 没有已知的调整形式

• 调整兰德指数定义为：

• 基于信息论和基于 的也可以针对机会进行调整
• 最常用的有：
  1. ARI：调整兰德系数
  2. AMI：调整互信息

——调整后的指标在随机下都趋近于0

二元划分

我们已经有了对比划分的指标，但我们根本没有考虑图拓扑。

测量相似性时应该考虑边吗？

这就引出了下面要讲的图感知测量，在这之前，要先讲下二元划分

边分类：

• 图分区可以由节点 V 上的集合分区表示

• 我们还可以考虑二元边分类（顶点是否在同一簇中）

  ——两端节点在同一簇的边 ——两端节点在不同簇的边

• 更正式地说，对于顶点分区 A，我们定义长度为 m 的二元向量 ，其中，对于每条边 ：

• 更进一步地，可以利用此方法对类别1边子集的边进行搜寻。

二元分类器的评估：

• 考虑 和 ，两个二元边分类器。

• 用于比较二元分类器的四个基本计数是：

  

• 对应的各种度量指标如下：