Fastunfoldingofcommunitiesinlargenetworks
JournalofStatisticalMechanicsTheoryandExperiment2008(10)·April2008
vincent.blondel@uclouvain.bejean-loup.guillaume@lip6.frr.lambiotte@imperial.ac.uk
摘要Abstract
1.介绍Introduction
社区检测的问题需要将网络划分为密集连接的节点的社区，属于不同社区的节点仅稀疏地连接。已知该优化问题的精确公式在计算上是难以处理的。因此，已经提出了几种算法以合理快速的方式找到相当好的分区。近年来，由于大型网络数据集的可用性增加以及网络对日常生活的影响，这种对快速算法的搜索引起了人们的极大兴趣。可以区分几种类型的社区检测算法：分裂算法检测社区间链接并将其从网络中删除[4,5,6]，凝聚算法递归地合并类似的节点/社区[7]，优化方法基于最大化目标函数[8,9,10]。
由这些方法产生的分区的质量，通常通过所谓的分区模块度/模块性/模块化（modularity）来测量。分区的模块度是-1和1之间的标量值，它测量社区内链接的密度，与社区之间的链接相比[4,11]。在有权重的网络中，可以定义如下：
其中:
Aij表示顶点i和顶点j之间相连的边的权重值(representstheweightoftheedgebetweeniandj)。即顶点i指向顶点j的边的权重值，当网络不带权时，此权重可以看做是1；
ki=Sigma(j)Aij表示附加到顶点i的边的权重之和(isthesumoftheweightsoftheedgesattachedtovertexi)。即所有指向顶点i的边的权重之和，kj同理，当图不带权时，即为顶点i的入度数；
ci表示顶点i所在的社区编号(isthecommunitytowhichvertexiisassigned)；
Funcd(u,v)函数表示当u等于v时为1，否则为0(is1ifu=vand0otherwise)。即若顶点i和顶点j在同一个社区内，则返回1，否则返回0；
m=1/2SigmaAij表示所有边的权重之和。当图不带权时表示边的总数，充当归一化的作用。
注意：模块度的概念不是Louvain算法/本文首次提出发表，Louvain算法是以优化图模块度Q为目标的一种策略优化实现。
modularityQ的计算公式背后体现了这种思想：社区内部边的边权重总和，减去所有与社区顶点相连的边的权重和；对无向图更好理解，即社区内部边的度数之和，减去社区内节点的总度数。
模块度已被用于比较通过不同方法获得的社区的质量，但也作为优化的目标函数。不幸的是，精确的模块度优化的计算很难，因此在处理大规模图时需要近似算法。
（1）Clauset等人提出了用于优化大型网络模块化的最快近似算法。该方法包括反复合并优化模块度生产的社区。不幸的是，这种贪婪算法可能产生的模块度值明显低于使用例如模拟退火所能找到的值（虽然快速但是可能不够准确）。
到目前为止，文献中处理的最大图是30739个顶点的蛋白质间相互作用网络[17]；一个大型在线零售商网站上出售的约40万个物品的网络[8]；日本的一个社交网络系统约有550万用户[16]。这些规模仍然留有相当大的改进空间[18]，考虑到截至今日，社交网络服务Facebook拥有约6400万活跃用户，移动网络运营商Vodaphone拥有约2亿客户，谷歌索引数十亿网页。让我们也注意到，在上面列出的大多数大型网络中，有几个自然组织层次-社区将自己划分为子社区-因此需要获得揭示这种层次结构的社区检测方法[19]。
2.方法Method
（1）首先，我们为网络的每个顶点分配一个不同的社区编号。因此，在这个初始分区中，存在与顶点数一样多的社区。
（2）然后，对于每个顶点i，我们考虑i的邻居顶点j（0或多个），并且我们通过将i从其社区中移除并将其放置在j的社区中来评估将发生的模块度的增益。
（3）接着，仅当该增益为正时，将顶点i放置在增益最大的顶点j所在的社区中（如果有多个j的社区的增益都相等，我们使用破坏规则）；如果没有可能获得正收益，顶点i会留在原来的社区。
（4）对所有节点重复并顺序地应用该过程（2）和（3），直到不能实现进一步改进，然后完成第一阶段。
算法效率的一部分源于这样的事实：通过将孤立顶点i移动到社区C中获得的模块度增益？DQ可以通过以下方式轻松计算：
Sigma(in)表示社区C内部的边的权重之和。(isthesumoftheweightsofthelinksinsideC)
Sigma(tot)表示与社区C内的顶点相连的边的权重之和。(isthesumoftheweightsofthelinksincidenttonodesinC)
ki=Sigma(j)Aij表示附加到顶点i的边的权重之和(isthesumoftheweightsofthelinksincidenttonodei)。即所有指向顶点i的边的权重之和，当图不带权时，即为顶点i的入度数；
ki,in表示社区C内顶点与顶点i的边的权重之和(isthesumoftheweightsofthelinksfromitonodesinC)；
m表示图中所有边的权重之和(isthesumoftheweightsofallthelinksinthenetwork)；
当我从社区中移除顶点i时，使用类似的表达式来评估模块度的变化。因此，在实践中，算法通过将i从其社区中移除，然后将其移动到邻近社区来评估模块度的变化。
3应用于大规模网络Applicationtolargenetworks
Inordertoverifythevalidityofouralgorithm,wehaveapplieditonanumberoftestcasenetworksthatarecommonlyusedforefficiencycomparisonandwehavecompareditwiththreeothercommunitydetectionalgorithms(seeTable1).
Wehavealsotestedthesensitivityofouralgorithmbyapplyingitonad-hocnetworksthathaveaknowncommunitystructure.
TovalidatethecommunitiesobtainedwehavealsoappliedouralgorithmtoalargenetworkconstructedfromtherecordsofaBelgianmobilephonecompany.