September 2020
Intermediate to advanced
213 pages
5h 25m
Chinese
Content preview from 数据分析之图算法: 基于Spark和Neo4j
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
92
第 6 章
社团发现算法
社团的形成在所有类型的网络中都很常见，识别社团对于评价群体行为和突发现象不可或
缺。发现社团的一般性原则是，社团成员在群组内部的关系要多于其与群组外部节点的关
系。识别这些有关联关系的集合揭示了节点簇、孤立群组和网络结构。这些信息有助于推
断同类群组的相似行为或偏好，评估弹性，查找嵌套关系，并为其他分析准备数据。社团
发现算法也常用于实现面向常规检测的网络可视化。
本章将详细介绍几种最具代表性的社团发现算法。
•
面向整体关系稠密度的三角形计数和聚类系数。
•
用于发现连通簇的强连通分量算法和连通分量算法。
•
标签传播算法，可基于节点标签快速推断群组。
• Louvain
模块度算法，用于研究分组的质量和层级结构。
本章将解释这些算法的工作原理，并给出相应的
Spark
示例和
Neo4j
示例。当算法仅适用
于一种平台时，仅提供一个示例。本章还会用到加权关系，这是因为权重通常用于表示不
同关系的重要程度。
图
6-1
展示了各种社团发现算法之间的差异，表
6-1
是每种算法及其示范用例的速查表。
社团发现算法
｜
93
度量算法 分量算法
标签传播算法
连通分量算法
不考虑方向，集合中的所
有节点都能到达集合中其
他节点
图中由虚线圈出的两个集
合：{A, B, C, D, E}和{F, G}
强连通分量算法