文章导航
菲尔兹数学科学研究所 复杂网络2019夏令营课程 学习笔记
社区结构
- 图划分(graph partitions)算法比较
- 图聚类算法
- 图上的集成聚类(ECG)
图社区
- 定义
- 谱分割
- Girvan-Newman聚类
- 基准:种植分区,LFR
- 模块度
- 算法
定义
两个基本假设:[Barabasi,Network Science]
- 一个网络的社区结构在其布局图中是唯一的。
- 一个社区是网络中的一个局部密集连接子图。
模型:
- 对于一个图
,考虑由一个节点 的子集诱导的连接子图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的特征分解之间关系紧密
对于所有的
: 因此,当 时,使上述表达式最小化相当于使
求解:
讨论:
L是对称的和半正定的,所以所有的特征值都是实数和非负数。
L有最小的特征值0;这个特征值的倍数对应于G中连接组件的数量。
因此,我们可以对这些特征值进行排序,同时对它们各自的特征向量进行排序。
非连通图情况:
- 有至少两个0特征值
- 按照第二小特征值对应的特征向量,有0和非0两种情况,按这个分类即可。
连通图情况:
考虑一个连通图G。它只有一个0特征值。
在一个连通图中,特征向量
对应于费德勒向量中的 。 谱分割是基于费德勒向量(第二小的特征向量)中条目的符号。——正为一类,负为另一类
多个社区:
- 如果有2个以上的聚类,这样的过程可以被递归应用
- 这是一个分裂性层次聚类的例子
- 然而,它可能表现得很糟糕,可能会分割本来存在的社区
- 所以我们去
,再利用k-means等算法对得到的特征向量进行聚类
总结:
一般适用于分组数量已知的情况,核心是最小化割边总和并最大化每个簇的节点数
GN算法
Girvan-Newman算法
步骤:
- 计算每个
的边介数,并删除具有最高值的边 - 将生成的图按连通分支拆分(簇)并递归地应用该方法
- 这会产生一个聚类层次结构,我们可以将其表示为树状图
——根据一些标准选择最好的分区,比如模块度(modularity)、或指定集群数量
问题:
- 该算法的一个问题是它的时间复杂度:
- 对于非常稀疏的图,也有
,仍然很高 - 其他算法可以达到
或
基准
为什么要有社区基准模型?
- 测试和比较算法
- 控制噪音水平、社区规模等
- 真实图数据很少有真实值(ground-truth)
- 有ground-truth,但可能与基本假设不一致
种植-分区模型
Planted partitions model
- 固定节点数 n 和社区数 k,对于社区,我们:
平均分配节点到每个社区
或将每个节点独立分配给社区 i,概率为
,
- 对于分别在社区i和社区j中的节点对
,我们按照概率 添加边 - 可以指定
、
- 可以指定
LFR模型
Lancichinetti-Fortunato-Radicchi model
- 固定节点数 n
设定三个主要参数:
:节点度服从 的幂律分布;推荐值为 。 :社区规模服从 的幂律分布;推荐值为 。 :对于每个节点,这是连接到其他社区的边的预期比例,而 是其自己社区内的比例。
——
称为噪声水平或混合参数 - 把每个节点都分配到社区
- 存在允许重叠社区的变体
- 可以提供额外参数来限制度分布(平均和最大度)和社区大小(最小和最大)
- 从配置模型开始,重新连接节点以逼近目标分布
- 初始阶段可以使用BA等其他模型
基准代码生成 3 个文件:
- 包含节点标记为 1 的边列表的文件
- 包含节点列表及其社区成员的文件,社区也被标记为 1
- 具有度分布、社区大小分布和混合参数等统计信息的文件
讨论:
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)组成的环,
- 当
时,对相邻的集团进行分组,模块度高于每个集团自己形成集群 - 正如我们将说明的那样,一些基于模块化的算法因此倾向于对已有社区进行组合
- 考虑l个大小为m的集团(m-clique)组成的环,
![分辨率限制](/2023/02/03/%E5%9B%BE%E4%B8%8E%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C-3%E7%A4%BE%E5%8C%BA%E7%BB%93%E6%9E%84/image-20230208002239680.png)
算法
CNM:
CNM算法(Clauset、Newman、Moore),也称为快速贪心算法(Fast Greedy)
- 开始,每个顶点作为一个单独集群
- 选择最能提高模块度的一对集群(如果有的话),然后合并它们
- 当没有办法提高模块度的时候停止
- 复杂度:
,稀疏图更少
Louvain:
也称为多级算法(Multilevel algorithm)或快速折叠算法(fast unfolding)
- 开始,每个顶点作为一个单独集群
- 循环遍历每个顶点,将其移动到模块度增加最多(如果有的话)的邻居社区
- 重复以上步骤,直到没有任何提升空间为止
- 将每个社区折叠成一个节点并重新运行上述步骤——另一个层级
- 当图折叠到单个节点(或者当最后一级没有移动)时停止
- 复杂度:
![louvain](/2023/02/03/%E5%9B%BE%E4%B8%8E%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C-3%E7%A4%BE%E5%8C%BA%E7%BB%93%E6%9E%84/image-20230208173034683.png)
Infomap:
- Infomap基于信息论:使用概率随机游走和压缩算法来实现
- 给定 G 和一个初始化分区方案,尽可能高效地编码随机游走
- 利用随机游走往往在同一社区中停留更长时间的性质
- 优化图方程:社区间游走的平均位数+社区内游走的平均位数
- 复杂度:
标签传播:
- 开始,每个顶点作为一个单独集群,有自己的簇标签
- 循环遍历每个顶点,每个顶点都采用其邻居中最流行的标签(使用随机来打破死锁)
- 当每个顶点具有与其邻域中最频繁出现的标签相同的簇标签时,算法停止
- 复杂度:
——注意:此算法速度很快,但并不总能收敛到一个解。
其他:
- WalkTrap:一种基于短距离随机游走的分层算法。它的复杂度是
。 - Leading eigenvector(前导特征向量):基于模块化矩阵的谱分解。对于每个双分区,其复杂度为
Louvain和Infomap的算法目前被认为是最先进的。
2023年评论:应该是Leiden算法
图分区的比较(指标)
- 介绍:图聚类
- 常见的相似性测度量
- 与二元分类的联系
- 图感知度量 (Graph-aware measures)
- 拓扑学特征
图聚类
符号描述:
- A,邻接矩阵:
:顶点i的程度
术语解释:
- 图聚类/分割(clustering/partitioning):将顶点分割成相连的子图
- 社区发现(Community finding):并非所有的顶点都需要被分配到一个群组中去
- 模糊聚类(Fuzzy clustering):节点不属于、属于一个或多个群组
图划分:
- 每个
诱导出一个连通子图 - 是连通分支的泛化
- 集群内的边密度大;集群间的边密度小
应用:
- 图聚类是关系型EDA(互联网数据分析)的一个重要工具
- 图尺寸缩减
- 社区检测
- 异常检测
- ……
- 如何挑选聚类算法?
- 集群的质量
- 稳定性
- 效率(时间空间)
- 其他:不需要指定聚类的数量(k)、集群的层次结构等
优化目标:
这是无监督学习,所以没有明确的目标函数
不同算法使用不同的目标函数:
- 模块度:
- N-cut
不同分割方法对比:
- 质量的衡量标准:
- 稳定性的衡量标准:同一算法的运行多次比较
- 比较算法之间的结果:
相似性
总体分类:
基于成对计数(Pairwise-counting)
基于信息论
基于卡方分布(
)
基于成对计数:
考虑对图节点的两个划分:
度量指标基于A和B里面各个集群中的成对元素
关键值为:
示例:
Jaccard 指数:
兰德指数
基于信息论:
基于 A 和 B 之间的互信息
关键值为:
示例:归一化互信息 (NMI):
基于卡方分布:
关键值为:
示例:Cramer 的 V指标 和 Tschurprow 的 T指标
测量指标vs.大小分布:
问题:比较不同大小的分区时,这些度量指标表现怎么样?
实验(多次重复):
:节点V的划分 ,V 的随机分区 ,、 、 、 、 、 、 、 - 测量
和所有分区 之间的相似性——期望所有相似度都很低
——结果:只有兰德系数变得接近1,其他都随着t的增大减小或趋向0
按概率进行调整:
实现 “在聚类结果随机产生的情况下,指标应该接近零”
成对计数指标的调整:
Jaccard 没有已知的调整形式
调整兰德指数定义为:
- 基于信息论和基于
的也可以针对机会进行调整 - 最常用的有:
- ARI:调整兰德系数
- AMI:调整互信息
——调整后的指标在随机下都趋近于0
二元划分
我们已经有了对比划分的指标,但我们根本没有考虑图拓扑。
测量相似性时应该考虑边吗?
这就引出了下面要讲的图感知测量,在这之前,要先讲下二元划分
边分类:
图分区可以由节点 V 上的集合分区表示
我们还可以考虑二元边分类(顶点是否在同一簇中)
——两端节点在同一簇的边 ——两端节点在不同簇的边更正式地说,对于顶点分区 A,我们定义长度为 m 的二元向量
,其中,对于每条边 :更进一步地,可以利用此方法对类别1边子集的边进行搜寻。
二元分类器的评估:
考虑
和 ,两个二元边分类器。用于比较二元分类器的四个基本计数是:
对应的各种度量指标如下:
准 确 性 分 数 余 弦 相 似 度
图感知度量
(调整)图感知度量:
上一节的指标可以用二元分类向量的乘积表示:
我们提出一系列成对计数的图感知度量指标:(一个是普通、另一个是调整后的)
实验:
- 在LFR模型构建的社区中,调整图感知度量的性能指标都很好
- 不同种类的度量指标的度量效果不同(引子)
补充:
——图感知和图无关度量在解决问题方面具有相反的行为
图无关度量即前面说的普通相似性指标ARI等
- 设 G 的真实社区情况为 A, 并设 B1 和 B2 分别是 A 的粗化和细化
- 在某些情况下,在图无关度量下A更接近B2(细化);在图感知度量下A更接近B1(粗化)
- 当使用图无关的度量时,集群的数量更多
- 图感知度量生成的集群的数量更少
- 这两种指标都获得高值是我们做图聚类所希望的
定理的公式化描述:
- 考虑Girvan 和 Newman 模型的变体 G(n, p, q, A),用于研究具有社区结构的图族
- 图有 n 个顶点,A为分区结果
- p为随机选择两个节点,其中的边在同一分区内的比例;
- q为随机选择两个节点,其中的边在不同分区内的比例。
![定理](/2023/02/03/%E5%9B%BE%E4%B8%8E%E5%A4%8D%E6%9D%82%E7%BD%91%E7%BB%9C-3%E7%A4%BE%E5%8C%BA%E7%BB%93%E6%9E%84/image-20230210231034533.png)
拓扑特征
验证集群的另一种方法是比较集群的拓扑特征:参考Orman et al.,arXiv:1206.4987
示例:对于具有
个节点和 个边的社区 ——缩放密度(scaled density):
内部传递性(internal transitivity):
其中
是 c 中 i 的邻居之间的边数, 是 c 中 i 的度数。
可以将特征作为簇大小的函数进行比较——比较聚类算法结果和ground truth的图形相似度
结论
- 使用调整后的基于集合的相似性度量,可以减少度量对分区粒度的偏差,消除随机性
- 图无关(ARI,AMI)和图感知(AGRI)度量是互补的:在评估算法的优越性时应同时使用它们
图的集成聚类(ECG)
- 共识聚类和 ECG
- 分辨率和稳定性
- LFR 图上的研究
- 一些真实的图示例
- ECG 权重
- 在异常检测中的应用
ECG
符号说明:
- 令图 G = (V , E), V = {1, 2, . . . , n}, 为无向图
- 对于每个 e ∈ E,边可以具有权重 w(e) > 0,或者考虑所有 w(e) = 1
- 令
是大小为 的 V 的一个分区 - 定义指示函数
,表示
图聚类的目标:好的、可扩展的、通用的——注意这是无监督学习
- 关联强度的度量
- 聚类的层次结构
- 不需要或尽量少调整参数
——使用集成学习(Ensemble learning)来实现这些目标:利用生成的多个分区来集成——如何合并多个图分区?
ECG算法:
ECG算法是图的共识聚类算法。步骤是:
- 生成步骤:来自 Louvain (ML) 算法的 k 个随机的 1级别(level-1) 分区:
。 - 集成步骤:在初始图 G = (V, E) 的重新加权版本上运行 ML。 ECG权重是通过联合获得的。
边
是人工定义的最小权重 表示是否在 的簇中共现。
通过示例可以看到,一个社区内的节点间的边在集成后权重变大,集团(clique)内的边尤其明显,而社区间的边集成后权重减小,变得很容易区分
分辨率和稳定性
分辨率:
- 基于模块化的算法存在分辨率限制问题:举例集团组成的环,相邻两个组合后模块度更大
- w* 值较小的 ECG 算法缓解了这个问题
- 使用 level-1的Louvain 作为弱学习器是关键——第一层louvain不会聚合那些环上的边
实验:
- 在广义集团环上ECG算法表现也很好:将ECG和louvain、InfoMap比较,分别考察环上连接集团边数从1增加到5时的表现
- 即使噪音很大,权重仍然很显著:当噪声很大时,同一集团中的边权重仍然显著
- 在LFR生成的社区发现上,ECG算法能够很好地保留原始数量:level1的louvain数量过多,最终的louvain数量过少
- 在上一章的图感知与图无关度量上表现也很好
稳定性:
- Louvain 和其他算法的已知问题:多次重新运行同一个算法会得到不同的结果
- 我们通过运行每个算法两次并应用一些比较措施(例如 ARI)来量化稳定性
实验:
- ECG相比louvain在稳定性方面有了很大的改善
- 实证研究表明,结果对参数的选择不是很敏感(低级聚类次数k和最小权重W*)——不过一般情况下k越大、W*越小效果越好。
LFR 图上的比较研究
- 论文在数千个 LFR 图上比较 8 种算法
- 各种指标水平都是ECG较好
- 本研究只考虑γ1 = 2, γ2 = 1,在不同参数的LFR模型下,ECG大部分情况下都比较好
一些观察结论:
- InfoMap 在大小相同的小型社区上提供最佳结果
- ECG 在其他情况下提供最佳结果
- ECG 的效果始终优于单个 Louvain (ML)
真实网络
- 足球俱乐部网络
- ECG和InfoMap都取得了最佳结果
- YouTube网络
- 1,134,890 个节点(用户)和 2,987,624 条边(好友关系)
- 2-core 仅覆盖 41.1% 的顶点
- 8,385 个社区被声明为用户组,这些社区从拓扑角度来看非常薄弱
- 只有 12 个合格作为弱社区,外部度与总度的比率低于 0.5 我们将此比率扩展到 0.75(类似于 LFR 图中的 µ)
- 在图感知度量上ECG比InfoMap略胜一筹
权重
ECG 重新加权有助于提升聚类准确性和稳定性
我们讨论了计算的 ECG 权重的其他一些应用
- 我们定义了一个新的社区强度指数 (CSI)
- 我们展示了如何使用权重来放大种子顶点
社区强度指数CSI:
- 边界(0 和 1)附近的 ECG 权重的双峰分布(bi-modal distribution)表明了强大的社区结构
- 我们提出了一个基于点质量 Wasserstein 距离(推土机距离(Earth Mover's distance))的简单社区强度指标 (CSI)
定义:
- 对于所有边
,以及来自 ECG 的 ,我们定义: 使得
关联强度:
- 从图上直观看出高 ECG 权重表示强关联
- 从经验上比较 ECG 权重和三角形出现次数:正相关关系
我们可以使用 ECG 权重作为自我网络的替代方案来放大种子节点
给定一个种子节点 v:
- 确定它所属的集群
- 删除所有 ECG 权重低于某个阈值 τ 的边
- 放大包含 v 的连通分量
- 增加 τ 可以对其进一步放大
——使用此方法可以很好地保留ground truth里面的真实同社区节点
异常检测
最近提出了CADA(community-aware anomaly detection社团感知异常检测)
CADA:
对于每个节点
:v 的邻居数。 : v 属于出现次数最多社区的邻居数(通过图聚类)。
——
实验: