COMP5313 Lecture 04 Summary - Community Detection

Lecture 04 — Community Detection

主题

这节研究如何只根据图结构把网络切成 communities。

1. 什么是 community

community 是一组节点，使得： - 组内连接稠密 - 组间连接稀疏

2. 为什么要找 community

• 识别朋友圈/兴趣群体
• 识别组织内部模块
• 识别蛋白质/疾病相关模块
• 帮助理解大图的宏观结构

3. 两大类思路

Divisive

从大图开始，删掉“跨社区”的边，把图拆开。

Agglomerative

从小块开始，逐步合并相似节点/子群。

4. Girvan-Newman

这是本课程里最重要的方法之一。

核心思想

跨社区边通常具有较高的 edge betweenness，因为很多跨群体最短路径会经过它们。

算法流程

1. 计算所有边的 edge betweenness
2. 删除 betweenness 最大的边
3. 重新计算
4. 重复
5. 形成层次化划分

5. Modularity

modularity 用来评估一个划分是不是“像社区”。

直觉

好的 community partition 应满足： - 社区内部边数比随机期望更多 - 社区之间边数比随机期望更少

含义

modularity 越高，说明划分越符合“社群结构”。

6. 层次聚类结果

community detection 常给出 hierarchical structure： - 顶层：整个图一个 community - 中间层：拆成若干较大群体 - 底层：再细分成小群体

7. 注意点

• 社区不一定唯一
• 不同算法可能给出不同结果
• 评价 community detection 也不是完全容易的问题

takeaway

Community detection 的关键是：找到那些“内部密、外部疏”的群体，而 Girvan-Newman 的核心武器是 edge betweenness。