051 | 社区检测算法之“模块最大化 ”
洪亮劼
该思维导图由 AI 生成，仅供参考
一起来回顾下本周的内容。周一我们介绍了用图（Graph）来表达网页与网页之间的关系并计算网页的重要性，就是经典的 PageRank 算法。周三我们介绍了 PageRank 的一个姊妹算法，HITS 算法，并且分析了这两种算法的内在联系，这两类算法都希望给网页赋予一个权重来表达网页的重要性。
今天，我们来看一类完全不一样的网页分析工具，那就是希望把网页所代表的图分割成小块的图，或者叫图聚类，每个小聚类代表一个“社区”。这类分析有时候被称作图上面的“社区检测”（Community Detection），意思就是从一个图上挖掘出潜在的社区结构。
社区检测的简要历史
提到社区检测就不得不提到这么一位学者，他与我们今天要介绍的算法有非常紧密的联系，而且他的研究在 2000 年~2010 年间成了社区检测研究的标杆，影响了后续的大量研究工作。这位学者就是密歇根大学（University of Michigan）的物理学教授马克·纽曼（Mark Newman）。
1991 年，纽曼从牛津大学获得理论物理博士学位。在接下来的 10 年里，他在康奈尔大学和圣塔菲学院（Santa Fe Institute）分别担任博士后研究员和研究教授。2002 年，纽曼来到密歇根大学物理系担任教授，并且一直在这里进行网络科学（Network Science）的基础研究。
2006 年，纽曼在《物理评论》杂志上发表了一个叫“模块最大化”（Modularity Maximization）的社区检测算法。从某种程度上来说，这个算法很快就成了社区检测的标准算法，吸引了研究领域的广泛关注，激发了大量的针对这个算法的分析和研究。对这个算法的最原始论述，请参阅参考文献[1]和[2]。
今天我们就来讲一讲这个“模块最大化”算法的基本原理。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
模块最大化算法是一种用于社区检测的重要算法。该算法的基本思想是将网络分割成紧密连接的社区，以便更好地理解网络结构和关系。该算法的核心是通过最大化模块化目标函数来确定节点的社区分配，从而实现社区的划分。模块化目标函数衡量了节点之间的连接数与期望连接数之间的差异，以此来评估社区的紧密程度。为了解决这一离散优化问题，研究者使用了矩阵表达和特征向量的方法，类似于PageRank和HITS算法。通过对网络进行二分或多次二分，模块最大化算法可以应用于划分多个社区。最后，文章提出了一个思考题，即如何将网页的社区信息应用于学习网页的相关度。这篇文章深入浅出地介绍了模块最大化算法的基本原理和应用，对于对网络科学和社区检测感兴趣的读者具有很高的参考价值。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《AI 技术内参》，新⼈⾸单¥98
《AI 技术内参》，新⼈⾸单¥98
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(1)
- 最新
- 精选
韩 * *同个社区只输出少量枢纽节点，提高topk结果多样性2019-08-03
收起评论