AI内参_53_051_社区检测算法之模块最大化_

你好，我是洪亮杰。

今天我和你分享的主题是社区检测算法之模块最大化。

一起来回顾一下本周的内容。

周一我们介绍了用图来表达网页与网页之间的关系，并计算网页的重要性。

意是经典的配置rank算法。

周三我们介绍了配置rank的一个姊妹算法，HITS算法，并且分析了这两种算法的内在联系。

这两类算法都希望给网页赋予一个权重来表达网页的重要性。

今天呢我们来看一类完全不一样的网页分析工具，那就是希望把网页所代表的图分割成小块的图，或者叫图聚类。

每个小聚类代表一个社区这类分析。

有时候被称作图上面的社区检测，意思就是从一个图上挖掘出潜在的社区结系。

我先来简单说说社区检测的历史。

提到社区检测，就不得不提到这么一位学者，他与我们今天要介绍的算法有非常紧密的联系。

而且他的研究在二零零零年到二零一零年间成了社区检测研究的标杆，影响了后续的大量研究工作。

这位学者是密歇根大学的物理学教授，马克纽曼，一九九一年，纽曼从牛津大学获得理论物理博士学位。

在接下来的十年里，他在康奈尔大学和圣塔菲学院分别担任博士后研究员和研究研授。

二零零二年，纽曼来到密歇根大学物理系担任教授，并且一直在这里进行网络科学的基础研究。

二零零六年，纽曼在物理评论杂志上发表了一个叫模块最大化的社区检测算法。

从某种程度上来说，这个算法很快就成了社区检测的标准。

算法吸引了研究领域的广泛关注，激发了大量的针对这个算法的分析和研究。

今天我们就来讲一讲这个模块最大化算法的基本原理。

在我们讲解模块最大化算法之前，并们先来看一看社区的含义。

在图分析以及网络科学中，社区定义为一组节点，他们互相之间的联系比他们跟社区之外节点的联系要更加紧密。

你可以注意到，在这个定义中，什么叫紧密，怎么来衡量更紧密，这个关系都是没有说明的这就为各类社区检测算法或模型带来了很大的发挥空间。

社区检测算法的核心就是要根据给定的一组节点和它们之间的关系，直到社区的情况，找到这些社区并分配哪些节点不再发生。

社区最终先来谈一谈模块最大化的一个整体函路。

最终我们讨论一种简化的情况，那就是如何把一个网络分割成两个社区。

首先，算法按照某种随机的初始化条件，把网络分成两个社区，然后算法逐一检查。

每一个节点看，如果把这个点划归到另外一个社区的话，会不会增加模块化这个目标函数？最终，算法决定改变那些能够最大化模块化目标的节点的社区赋值。

然后整个算法不断重复这个过程，直到社区的赋值不再发生变化。

现在我们来讨论一下模块化这个目标函数。

我据上面提到的社区含义，我们希望社区里节点之间的联系紧密，在模块化目标函数里就表达为两个节点的连接数目。

减去这两个节点之间的期望。

连接数模块化最大化。

说的就是对于同一个社区中的所有节点，我们希望这个差值的和最大化。

什么意思呢？就是说如果我们把两个节点放到一个社区中，那它们的连接数要足够大于它们之间的连接数的期望值。

这就解决了我们刚才所说的如何来衡量更加紧密的难题。

那么怎么来定义两个节点之间的期望连接数呢？最初纽曼在介绍模块最大化的时候，它给出了了两个一个计算方法。

那就是用两个节点各自的连接，接数相乘。

针对整个网络的总连接数的两倍。

直观上说，这在在量量这两节点之之出现任何连接的可能性。

那么整个模块最大化的目标函数就是针对现在网络中间的所节点点，根据们们是否在同个个接数，那就是它它们两两之间的模块化数值，也就是它们之间的连接减去期望连接数。

最后对所有的两两对进行加和，我们希望这个目标函数最大化。

这个目标函数中的未知数就是社区的分配，也就是哪个节点属于哪个社区。

一旦社区的分配，已知整个模块最大化。

这个目标函数的数值就可以很容易的计算出来。

那么如何得到这些社区的分配呢？和我们之前介绍的配置rank以及HITS的思路类似，纽曼使用了矩阵的表达方法，对整个模块最大化进行了一个重构。

经过一系列代数变形之后，纽曼得到了一个新的目标函数，那就是一个向量s的转置乘以一个矩阵b然后再乘以向量s最后除以四倍的网络连接总数。

这里向量s代表了一个节点是否属于两个社区中的一个矩阵。

B中的每一个元素表示了横纵坐标所代表的两个结点的模块化值问题，就是求解s的值。

请注意，s中的值是离散的，要么是正一，要么是负一。

很明显这是一个困难的离散优化出来。

纽曼对这个复杂的离散优化问题进行了近似处理的方法。

具体来说，那就是允许s的值，不仅仅是正负一，而是实数。

这样就大大简化了优化问题的难度。

在设置好最优化这个新的目标函数之后，经过代数变形，我们得知了一个惊人的结论，那就是最优情况下的s实际就是矩阵b最大的特征值所对应的特征向量。

这又和配置rank以及HITS又着极其相似的最优结构。

在找最大特征向量的过程中，找到s以后，我们就根据s里元素的正负号正的属于一个社区，负的属于另外一个社区，来对整个网络中的结点进行划分。

当然我们这里讲的仅仅是把整个网络进行二分的情况。

在实际应用中，我们往往需要把整个网络划分成多个社区。

纽曼在论文中也讲解了如何把二分法推广到多个社区的情景。

具体来说就是先把一个网络分成两份，然后再不断的二分下去。

不过每次进行二分的时候，我们都需要检查值否对模块化目标函数起了正向的帮助，而不只是机械的进行二分。

今天我为你讲了社区检测中一个有代表性的算法模块最大化。

一起来回顾一下要点。

第一，我们讲了什么是社区检测以及社区检测的一些简明历史。

第二，我们讲了模块最大化的基本思想，比如模块最大化是如何定义的，又是如何把一个困难的离散优化问题转换成类似HITS和配置rank的寻找最大特征向量的问题。

最后给你留一个思考题，如何把网页的社区信息利用到学习网页的相关度里面去呢？欢迎你给我留言，和我一起讨论。