社区结构

• 图划分（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 的二元向量 ，其中，对于每条边 ：