COMP5313 Week 04 社区检测讲课总结
COMP5313 Week 04 讲课总结：Community Detection
1. 本讲主题
本讲讨论如何在图中发现社区。核心问题是：
哪些节点内部连接密集，对外连接稀疏？
老师强调 community 没有唯一严格定义，所以算法和评价指标很重要。
2. 社区的直觉定义
一个社区通常满足：
- 社区内部边多。
- 社区之间边少。
- 社区结构能解释网络中的群体或功能模块。
例子：
- 社交网络中的朋友圈。
- 合作网络中的研究领域。
- Web graph 中相互引用的一组页面。
3. 两类方法
Divisive 方法
自顶向下：
- 从整张图开始。
- 找到连接不同社区的关键边。
- 删除这些边。
- 图逐渐分裂成社区。
Girvan-Newman 是典型 divisive 方法。
Agglomerative 方法
自底向上：
- 每个节点先是一个社区。
- 按相似度逐步合并社区。
- 最后形成层次结构。
两类方法通常都会产生 dendrogram，可以在不同层切割得到不同社区数。
4. Edge Betweenness
边中介性衡量一条边出现在多少最短路径上：
[ b(e)=_{st} ]
- \(\sigma_{st}\)：\(s\) 到 \(t\) 的最短路径数量。
- \(\sigma_{st}(e)\)：这些最短路径中经过边 \(e\) 的数量。
直觉：社区之间的桥接边会出现在很多跨社区最短路径上，所以 edge betweenness 高。
5. Edge Betweenness 手算流程
老师讲的 BFS 计算法很重要：
- 选一个起点 \(s\) 做 BFS，得到层次结构。
- 记录从 \(s\) 到每个节点的最短路径数。
- 从底层往上回传 flow。
- 每个节点自带 1 单位流量，下层传来的流量按最短路径数量比例分配给上一层边。
- 对每个起点重复。
- 无向图最后除以 2，因为每对节点被算了两次。
这是计算题重点。
6. Girvan-Newman 算法
算法流程：
- 计算所有边的 edge betweenness。
- 删除 betweenness 最大的边。
- 重新计算所有边的 betweenness。
- 如果图分裂成更多 connected components，就记录当前划分。
- 重复直到边被删完。
老师强调：每删一次边后必须重新计算 betweenness，因为最短路径结构会变化。
复杂度：
- 一次所有边 betweenness 计算约为 \(O(nm)\)。
- 完整 Girvan-Newman 约为 \(O(nm^2)\)。
- 所以它适合理解和小图手算，不适合超大图。
7. Modularity 模块度
Modularity 衡量一个划分比随机图更像社区结构的程度：
[ Q=_{sS}]
其中：
- \(m_s\)：社区 \(s\) 内部边数。
- \(D_s\)：社区 \(s\) 内所有节点度数之和。
- \(m\)：全图边数。
直觉：
- 第一项是社区内部真实边比例。
- 第二项是随机情况下期望内部边比例。
- \(Q\) 越大，社区划分越好。
常见性质：
- 所有节点放在一个社区，\(Q=0\)。
- 每个节点单独成社区，通常 \(Q<0\)。
- \(Q\) 范围大致在 \([-1,1]\)，实际越大越好。
8. Louvain 算法
老师把 Louvain 作为常用的 modularity 优化方法介绍。
核心思想：
- 直接贪心优化 modularity。
- 先局部移动节点提高 \(Q\)。
- 再把社区压缩成 supernodes，重复优化。
重点知道它是 scalable heuristic，不需要掌握完整实现细节。
9. 其他方法
老师提到但不作为主要计算重点：
- Agglomerative clustering：基于相似度合并。
- Clique percolation：用相邻 clique 找重叠社区。
需要知道它们是社区发现思路，不需要像 Girvan-Newman 那样手算。
10. 考点重点
- 会解释社区：内部密集、外部稀疏。
- 会区分 divisive 和 agglomerative。
- 必会 edge betweenness 的直觉和手算 BFS flow 方法。
- 必会 Girvan-Newman 流程，特别是每删边后重新计算。
- 会用 modularity 公式计算 \(Q\)。
- 知道 Louvain 是贪心最大化 modularity 的 scalable 方法。
- 知道 Girvan-Newman 复杂度高，不适合大图。