针对检测网络社区的一种高效、规则化方法(论文翻译).docx

针对检测网络社区的一种高效、规则化方法Brian Ball,1 Brian Karrer,1 and M. E. J. Newman1, 21Department of Physics, University of Michigan, Ann Arbor, MI 48109, U.S.A.2Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109, U.S.A.在对网络数据进行分析时面临的一个基本问题便是如何完成对由高密度互联结点（这些结点可能重叠或相交）组成的网络社区的检测。在这里我们描述了一种基于使用生成网络模型的规则化统计方法来寻找重叠社区的方法。我们将展现这个方法是如何通过使用一种快速的、封闭形式的最大值期望算法来实现网络分析的，这种方法使得我们能够在合理的运行时间内完成对于含有百万数量级结点的网络进行分析。这种方法已经在现实世界存在的网络和虚拟的基准测试网络中进行了实验，得出的结论是这种方法对于这两种类型的网络都是适用的。并且利用松弛策略，该算法还可以用来进行非重叠的社区分割，结果表明这种算法对于解决无重叠网络社区问题也是相对快速和精确的。I引言研究表明，很多网络系统（包括生物网络和社交网络）被自然地划分为若干模块（或称社区），这些模块由一组结点构成并且模块内的结点联系紧密而模块间的联系则相对较少。根据上下文可以判断出这些结点或无交集，或相互重叠。在最近的十年里，在网络理论研究领域，如何在实验网络数据中检测发现这样的结点信息则成为了一项亟待解决的问题，这个问题也引起了很多研究者的研究热情。一个优良的社区检测方案应该具有某些理想的性能。首先，它必须是高效的，要能够精确地分析出社区结构。例如，社区结构应该能够广泛适用于自然存在的和虚拟合成的种种网络，并且在其中分析得出适用的结构。其次，基于严格的理论原则依据的方法要优先于那些没有使用该原则的方法。相比于可通过证明得出或是具有基本数学原理的方法相比，那些仅仅依靠纯粹直觉去研究事物可能的发展走向的方法显然难以让人信服。最后，这个方法还应该具有快速和规模适中的特点。当前科学研究中的很多网络都非常庞大，它们包含百万甚至千百万数量级的结点。所以我们要优先考虑的应该是随网络扩张运行时间呈线性增长的网络算法而非那些呈平方级或立方级增长的算法。本文中我们推导出一个可以找出重叠及非重叠社区的社区检测算法并且证明出其满足上述所有要求。此算法在标准基准测试中对于已知社区结构的检测上表现出与最佳前向算法相似的性能。此算法是基于已有方法的统计推断得出的，也就是说它是一个追求极大似然和最大期望并且高效的算法。在其最简单的表现形式中它仅包含两组方程的迭代，每种迭代所需时间仅随系统规模增大而呈线性增长。在实际应用中，此算法能够在一台普通的台式电脑上并且在合理的运行时间里处理拥有百万级结点和边的网络。我们已经完成分析的最大网络拥有400万结点和4000万条边。我们将寻找重叠社区作为网络检测问题的出发点。在社区检测问题上最早的努力可以追溯到上个世纪70年代，当时假定社区是无重叠的或者无交集的。但正如很多研究人员最近这些年争论的那样，在实际情形中社区重叠是普遍存在的。例如在社交网络中，一个人常会拥有不止一个熟人圈，诸如家庭，朋友，同事等等。很明显在这些圈子中存在着至少一个共同成员（也即其本人），也就是说存在着重叠。在生物网络中很多结点可以从属于不止一个群体。在一个新陈代谢网络系统中，一个物种的代谢产物可以在不止一个代谢过程或循环系统中起作用。在食物链中一些物种可以落入两个毫无交集的子社区的边界并且在这两个子社区中都起作用。因此解决网络社区检测问题的一般性方法应当允许结点重叠。我们的研究将首先提出一个对于这种一般问题的解决方案，接着我们将展现此方法的一个变体是如何被应用到无重叠结点社区中的。我们通过将一个随机生成的网络结构模型应用到实际测得的网络数据中来处理重叠社区的检测。这种将统计推断方法应用到网络中的方法已经被一批学者探索应用于无重叠结点的网络研究中（其中也包含一些数十年前的工作）。然而将同样的方法拓展到有重叠的情形则并不容易。一个关键步骤就是发明一种可以产生与现实中存在网络相似的拥有重叠社区结构网络的生成模型。以前被使用的大多数是一种称为“混合成员”的模型，这种模型中结点可以隶属于多个群组并且拥有超过一个共同群组的两个结点更容易产生联系。然而这也就意味着两个社区的重叠区要比那些仅落入一个单一社区的区域拥有更高平均密度的边。我们并不清楚这样的模型是否能够准确反映出现实世界中存在的网络，但可以肯定的是我们能够构造出这种网络结构之外的网络。理想情况下，我们更倾向于一种限制少且对于重叠社区结构少做假设的模型。另一组检测重叠社区的方法是基于本地社区结构的，这些方法在网络中根据对于本地联系模式的分析并且忽略全局网络结构来寻找本地群组，而不是一次性将整个网络分割成不同社区。当在整个网络中生成大量这样的独立本地社区的时候，这样的方法自然会产生重叠社区。并且，这样的社区更趋向于成为紧缩和互联的子图结构，这种需求并不总是适用于其他方法。与之相对的全局检测方法则能够更好地捕捉到大型网络结构并且当为其加上特别的必须满足的限制（如必须满足对于社区数量的限制）时更为精确。本文中我们找到一种全局统计的方法用来检测重叠社区。这种方法是基于一种已经被一批研究物理文学及机器学习的学者在各自研究领域独立提出的连接网络的思想。此观点认为在一个网络中当出现不同类型的边时社区就会产生。例如，在社交网络中，我们用连接来代表家庭联系，友情关联，工作关系等等。如果我们可以识别出边的不同类型，我们就能够识别出上述种种关系。如果在网络中我们不仅将结点聚集，并且也将边聚集的话，我们就能够根据连接结点的边的类型推导出由结点组成的社区。在以自然方式（如果一个结点拥有不止一种类型的边则其属于不止一个社区）产生重叠社区的时候这种方法表现出与我们关于社区结构的起源和本质的感性认识上很好的一致性。先前发现连接社区的方法使用的是一种通过对网络中边的可能划分进行优化的启发式特征函数。这样的特征函数，尤其是其中的模块函数，在过去被用于无重叠社区的研究中。虽然在实际应用中这些函数往往能够给出合理的结果，它们仍然存在着一些缺陷：例如，模块不能用于发现那些很小的社区，可能产生不唯一的优化，从某种形式观点看有一些不尽如意的地方等等。比尔克和陈（音译）最近的研究结果表明这些缺陷可以通过摒弃使用特征函数方法，取而代之，采用将一个生产模式加入到数据中的方法而得以纠正。这也是我们采取的方法，只是对于一个适用于连接社区的模型的定义需要稍作改动。在结点社区的生成模型中可以先将结点指派群组然后根据这样的指派为其分配边。但是在根据边而进行划分的连接社区的模型中，除非边已存在，否则我们不可以为群组指派边。因此边和它们的群组信息要同时生成。下文中我们将详述此目标是如何实现的。一旦我们获得这样的模型，接下的目标就将是确定模型中的与观测到的网络最佳匹配的参数的权值，并且根据这些值来确定重叠结点社区。本文的结构大致如下：首先我们将定义我们使用的模型然后说明各参数的最适取值是如何通过使用一个极大似然算法而计算出来的。这个算法在其最简形式中只是适中快速的，但我们可以证明得出此模型的大量参数会迅速收敛到平均值，因此可以进行剪枝计算。我们为这种剪枝提供了一种解决方案，得出一种适用于特大规模网络的快速算法。我们为大量的现实世界网络以及虚拟构造网络都提供了应用程序示例以证明此算法可以从这些网络中发现已知的重叠社区。最后，我们通过使用在重叠社区划分中为各个节点仅指定一个其依赖性最强的社区的技术来展示这种方法是如何被应用于探测无重叠社区的。我们证明得出对于无连接的社区而言，这种直觉式启发算法可以通过将连接社区模型看成是一种随机障碍模型的松弛这样的方法得以严格修正。之前提出的适用这种障碍模型的各种算法因它们的运行时间与结点规模呈至少平方级增长而只能局限于在一些规模较小的网络上进行使用。本文中提出的算法其速度有了显著提升因此可以用于超大规模网络中无连接社区的检测。II一种适用于连接社区的生成模型首先我们将定义我们即将使用的生成网络模型。此模型通过给定结点数n、社区数以及连接这些社区的无向边来生成网络。为方便起见，我们用种不同的颜色代表不同的社区，并且为属于每个社区的边着上各自的颜色，则这个模型就可用一系列的参数iz，表示结点i拥有颜色为z的边的比例。特别的，izjz表示在结点i和j之间颜色为z的边的期望值，其平均值服从泊松分布。这意味着技术上这是一种多重图（一对结点之间可以拥有不止一条边）。而大多数现实存在的网络只拥有单边，因此从这个角度看这个模型并不现实。然而允许多重边的存在使得此模型变得极为简单，在实际运用中iz的值很小因此多重边的数量以及引入的误差都是小规模的。在大多数其他随机网络图模型（例如，广泛研究的配置模型）中也进行同样的近似。我们的模型同样允许自联边，即两端为同一结点的边，其期望值为12iziz，之所以乘以二分之一是为了和之后的结果保持一致。同样自联边的出现极大地简化了逻辑上的拓展并且对于包括配置模型在内的随机图模型都具有代表性，尽管在某些情况下这并不现实。正如之前引言中所介绍的那样，在此定义的模型中连接社区是随着网络的生成而默认生成的，而非显示定义的。对于一些z拥有较大值iz和jz的两个结点i和j，它们被颜色为z的边连接的可能性也较大，因此包含这样结点的群组将被着色为z的边连接而形成相对稠密的网络，而这样的结构正是我们在一个连接社区的网络中希望看到的。III检测重叠社区根据上述定义的模型，我们可以直接得到生成任意特定网络的所应用的概率。因为对于两个相互独立的泊松分布而言，其参数之和也服从泊松分布，因此两结点i和j之间所有颜色的边的总数为zizjz(对于自联边为12Ziziz),，通过此方法得出实际的值是泊松分布的。因而通过一个邻接矩阵Aij的元素生成图G的概率是 PG= ijZizjzAijAij!exp-zizjzi12ZizizAii2Aii!exp-12ziziz. 1（对于邻接矩阵的元素Aij，一般来说，如果i和j之间有一条边的话取值为1，对于一个自联边而言其值为2，以和上述公式中的12对应）我们通过极大化这种可能性（考虑参数iz或同等地扩大它的对数）而使得这种模型符合已观测到的网络。对公式1取对数，重新排列，去除附加的和乘倍数的常量（这些对于最大化的位置没有影响），我们推出下列对数概率公式： log PG = ijAijlogzizjz -ijzizjz 2通过对一系列关于iz非线性隐含方程我们直接最大化这个表达式，一种简单的方法如下：首先我们将应用以下形式的詹森不等式logzxzzqzlogxzqz (3)xz是任意一组正数，qz表示概率且满足zqz=1，注意到存在等式qz= xz/zxz，将公式3带入到公式2得到log PG ijzAijqijzlogizjzqijz-izjz, 4这里的概率qijz可以任意指定，只要它们满足zqijz=1。注意到qijz只对网络中实际相连的两结点i和j有定义（依此有Aij=1），因此它们与测得的边数数量相同。因此，等式可通过选择一组适当的qijz而成立，最大化等式4右边的qijz和iz等效于最大化原始的线性概率，公式2则仅与iz有关。似乎这并没有使得最优解问题得以简化，我们仅仅是把一个单点优化变成双点优化而已，反而让人感觉问题变得更加复杂了。然而值得庆幸的是，事实并不是这样。这里的双点优化实际上很简单。根据iz的值，qijz的最佳值可通过公式qijz=izjzzizjz (5)得到因为这些值使得不等式实际上成为一个等式。当给出qijz的最佳值，iz的最佳值可通过区分公式4得到公式iz=jAijqijziiz 6 在i上对这个表达式求和并且重新整理的公式iiz2=ijAijqijz (7)然后再与公式(6)结合得到公式iz=jAijqijzijAijqijz (8)这样极大化对数概率就就可简化为同时求解公式5和8，可以通过选择一组随机的初始值在这两个公式中反复迭代来完成。这种方法就是所谓的最大期望算法并且可以证明得出对数概率在迭代过程中单调增长，尽管其并不一定会收敛到全域最大值。为预防其陷入进一个局部最大值上，我们将重复整个计算过程若干次，每次过程的起始条件都是随机给定的，我们取这些计算中得出的最大值作为最终的对数概率。公式5中的qijz的一个物理意义在于，它代表在结点i和j之间着颜色为z的边的概率，这也正是我们考量网络连接社区所需的量。注意到qijz对于结点i和j是对称的，因此我们多讨论的应该是一个无向网络。这里展示的计算与机器学习中分析文本的方法相近。具体来说，我们可以把这里的模型看成是概率潜在语义分析（一种能在文本资料库中自动检测主题的技术）模型中的一个变体。文本分析和社区检测之间的联系也曾经被一些学者研究过。其中不可不提的当属Psorakis等人所作的工作。尽管它并不是把连接网络作为研究重点，但它应用了概率潜在语义分析的另一个变体，同时还使用了一个名为非负矩阵因子的迭代适应算法来寻找有向网络中的重叠社区。同样值得一提的是Parkinnen等人所作的研究。他们与我们采取同样的观点来对待连接社区，所不同的是他们采取的是一种基于贝叶斯生成模型和马尔科夫链的采用蒙特卡洛技术的比较算法。有关文本处理和网络分析之间联系的详细介绍我们在附录A中给以呈现，在此不再赘述。IV实现上述算法可以作为一个寻找重叠社区的计算机算法得以直接实现，并且对于中等规模大小（拥有成千上万结点）的网络此算法运行情况良好。对于大型网络则将占用大量内存，并且运行时间也将变得很长，但这些问题都可以通过使用一种更加精致的实现得以解决，并且使其对于百万级结点级别的网络的分析成为可能。此算法内存的使用主要是用来存储参数：参数iz需要空间n，qijz需要空间m，此处的n和m分别代表网络中结点和边的数量。由于通常情况下m要远大于n，这意味着内存的使用主要由qijz决定。我们可以通过重新构造这个算法，使得qijz不需要被存储，以此来减少内存的使用。我们定义平均值kiZ为连接结点i着颜色为 z的边的端点数。kiZ=jAijqijz (9)在此算法的一个给定迭代过程中指定这些量的值，则计算下一次迭代的值的过程如下。首先我们重新定义一组量kiZ用来存储kiZ的新值，开始我们将这组量都置为0。用kZ来表示所有着颜色为z的结点的和kiZ=ikiZ (10)则iz可以表示为iz=kiZkZ (11)接着我们遍历网络中的每条边i,j 计算公式(5)中的分母得到：D=zizjz=zkiZkjZkZ (12)这样之后将其代入公式(5)我们就将得到qijz=izjzzizjz=kiZkjZDkZ (13)此时我们将它的值代入到量kiZ和kjZ 中，丢弃D和qijz的值，并且对于网络中的下一条边重复此过程。当我们依照这种方法遍历所有边后，变量kiZ的值将等价于公式(9)中的值，并将称为新的kiZ。这种方法只需要存储kiZ的旧值与新值两个量，总共有2nK个量，而不是qijz个。因此节省了大量的内存空间。至于运行时间，此算法对每次迭代过程拥有m的计算复杂度，这里的m仍然是网络中边的数目。总运行时间的主要决定因素是收敛到kiZ的迭代次数。实际中，我们发现在很多例子中需要大量的迭代过程，因此影响了此方法的性能。但速度可以通过下述方法得到提高。在这个算法对于网络的一个典型运用中，最终结果是每个结点仅仅属于个社区中的一个子集。换句话说，就是我们期望一大部分参数kiZ能够在EM迭代过程中趋于零。从上述方程中可以清楚看到如果某特定kiZ一旦变为零，则其在接下来的迭代中都将保持这个值，这也就意味着它不再需要被更新，我们可以通过将其排除出计算过程而节省时间。删减一组变量有两种策略。一种策略是当kiZ低于某个预定阀值时我们就将其设置为零，一旦kiZ被设置为零后，与其相对应所有相邻边上的qijz也都将被设置为零，因此也可以不用再计算。因此对于每条边，我们只需要对于着色为Z的不为零的kiZ和kjZ计算qijz的值。这种策略将带来速度上的明显提升。对于较小的网络直接计算所有的qijz则更为高效。但是如果kiZ低于预定阀值我们仍然将其设置为零，因为这将使得第二次剪枝称为可能。另一种策略可以与上一种串联使用并且对于所有类型的值都将有速度上的显著提升。其原理是由观察得出如果对于某特定结点除一个以外的所有kiZ都被设置为零的话，则这个结点的颜色将被设置为单一值并且不会再改变。如果边i,j的两个端点都具有这个性质，都收敛到一种单一颜色并且不会改变，则连接它们的边将不会对于计算有任何影响并且可以将其删除出网络。通过使用这两种策略我们计算的速度得到可观的提高。我们发现在实际计算过程中参数kiZ的值和边都将快速收缩，因此主要的迭代仅包含一个子集，通常是那些与社区属性不太清楚的结点连接的边。如果将阀值设置为零，则剪枝算法将与原始的EM算法等效。但是即使如此我们也会发现速度有很大程度的提高。如果设置为一个很小但非零的值，则我们将在计算中引入一种近似，意味着结果可能会与原始算法有所不同。然而实际中，这种差别很小，并且非零值会让性能又有所提升。关于不同版本算法的运行结果和运行时间的详细比较在附录B中给出。接下来的计算都使用更快版本的算法，除非特别说明。V结果我们通过系统生成网络和一组现实世界存在的网络来测试此算法的性能。系统生成网络允许我们在可控条件下测试已知被设定的社区结构，而现实世界网络则允许我们在实际现实世界的条件下观测性能。A系统合成网络在系统合成网络的例子中，我们采用一种经典的一致性测试形式。我们通过此算法使用的统一的随机模型生成网络并且测试其对于不同参数的值恢复已知社区划分的能力。可以通过改变变量的值通过单纯社区结构来创建网络，或是根本不使用社区结构。这样我们可以区分出此算法带来的难度上的挑战。我们测试的网络拥有结点数n=1000，被分割成两个重叠社区。我们将x个结点仅置于第一个社区中，表示其只和此社区中的其他结点有关联。将y个结点仅置于第二个社区中，剩下的z=n-x-y个结点可置于两个社区中。对于各群组中的结点有相同数量的连接。我们设置所有结点的期望度为k。我们执行三组测试。第一组中设置z=500，x=y=4750，并且通过改变K的值观察此算法的表现。当k0时，网络中没有边，也就没有社区结构，因此此算法会失效。另一方面，当k是一个比较大的值时，它应该能够直接得出社区所在位置。第二个测试我们仍设置z=500，但这次我们将k设置为10，改变x和y之间结点的平衡。第三个测试中将k设置为10，并且限定x和y相等，但允许z值变动。图1注1），上述三种实验的结果。每个数据点都是超过100个网络的平均值。每个网络使用20个随机初始变量。每个表中黑色曲线表示结点分数，它与此算法正确的社区数对应，而红色曲线代表重叠区结点的Jaccard指数。在图表1中我们用黑色曲线表示每个实验中测量结点部分，每个点都为100个网络的平均值。为了正确考虑划分，在群组中的一个结点成员必须通过算法准确报告。并且对于任一结点如果当最大相似适应过程结束时一个结点平均至少拥有一条相近颜色的边则此算法将其当做是一个群组的成员。用数学术语表示就是，如果一个结点对于颜色z的期望度jAijqijz大于一的话，则其属于社区z。正如图表显示的那样，对于这三种测试参数变量在很大范围内变动都可以得到正确的结果，能够正确划分网络中的大多数结点。正如期望的那样，第一个测试中精确度随着K的增加而增加。当k大于10时，此算法将快速地识别出已知社区结构。在另两个实验中，实验精确度随着两组的不对称增强或重叠部分的增加而下降，但当二者之一很小时却能接近100%。为了探测得到算法识别重叠社区的更多细节，对于同样的实验我们还测量了Jaccard指数：如果用S表示在重叠区中一组结点，V代表算法识别的在重叠区的结点。则可定义Jaccard指数 J=SVSV。此指数的值在图表1中用红色曲线表示。可以看出其大致的走向与正确识别的结点综合分数相同。特别地，我们注意到拥有较高平均度K的网络J的值趋于1，表示重叠区可以被较快识别出。B实际网络我们同样也在大量现实世界网络中进行了测试。这部分我们给出三个具体例子的详细结果。在附录B中我们给出了一些附加例子的概要结果。第一个例子是毫无疑问是测试社区检测的。由观测研究得出的表示全球体育俱乐部成员间友好关系模型的扎卡伊的“空手道俱乐部”网络，因在其研究中俱乐部一分为二会造成兄弟阋墙而引起关注。已经证实，可以仅仅通过网络结构的知识就能推断出其分割线。图2注2），为“空手道网络”中的重叠社区，(b)为悲惨世界中的人物角色网络。对于给定边，边的颜色与qijz值最大的z对应。对于属于不止一个社区的结点为了清晰表示其在所属社区的划分我们用较大的点表示。图表2a展示了通过我们的算法得出空手道俱乐部网络的两个重叠群组的分解。图表中的颜色代表结点和边的划分。俱乐部中两组间的分割在结果中泾渭分明地得以表示，并且与实际情况向对应。但此算法指定了一些同属于两个群组的结点。通过这些重叠结点表示的个体在两个俱乐部都有朋友，当面对指责时有可能会产生立场不明的困惑。实际上在对于扎卡伊模型的讨论上确实存在这样的问题。同样得指出的是，除了确认重叠结点外，我们采用的方法还可以通过饼图上颜色的多少指明某个结点属于一个或另一个社区的多大部分。通过结点上每种颜色边的期望部分可以计算出此分数。第二个例子是另一个社交网络，并且其社区结构之前也被研究过。这个由克努斯编制的网络，代表维多克雨果所著小说悲惨世界中那些虚构的人物之间的关系模型。如果两个人物同时出现在小说的一个章节中，则就用一条边将他们连接。图表2b展示了运用我们的算法将此网络划分为六个重叠社区的划分结果，并且此种划分大致符合其社会划分及小说的剧情结构。但此例中最引人入胜的则是那些网络核心部分所扮演的角色（那些拥有特别高度数的结点所代表的主要人物）。那些拥有如此多联系的结点与网络中各个部分都有关联，它们的存在给应用传统的、无重叠社区检测的方案带来困难，因为它们并不是简单地属于某一社区：不管我们如何设置这些核心，它都将与很多其他社区的结点有联系。重叠社区为此种问题提供了一个优雅的解决方案，我们可将核心置于重叠区。正如图表2b所示，我们的算法确实是这样做的。它将网络中很多核心人物都放置在两个以上的社区中。这样的指派从小说剧情的角度看来也具有现实意义：核心所代表的主要人物正是那些不止一次出现在小说分剧情中的人物。图3注3），美国航空乘客网络的重叠社区。这三个社区大致可分为东海岸、西海岸和阿拉斯加州。在我们的第三个试验中同样可看出与上面相似的表现行为。这是一个描述美国各机场之间航线联系的运输网络。在此网络中，结点代表机场而边则代表一个定期航班。在此空间网络中，有优越地理位置的结点往往与其他与其相近结点产生联系的可能性更大。这也表明如果存在社区的话，它们将是区域性的，主要由一些相近结点的块组成。在航空网络中通过此算法检测到的社区遵循这个模式。如图表3所示，网络中所示的三向划分将此网络划分为东海岸、西海岸和阿拉斯加州。重叠区部分是由各组间的地理边界上的结点组成。但同样拥有核心结点。这样的核心结点是航空网络的经纪人，它们将不同社区连接，因为它们正是连接两个远距离地点的航班所必经的地方。因此将它们看成是多个群组的成员是合适的。在大多数例子中这些核心结点更多地属于它们所在位置的社区，而非其他社区。VI无重叠社区正如我们描述的那样，我们的算法也可以用来寻找网络中无重叠社区。正如之前一些学者指出的那样，一切计算结点在社区中所占比例的算法都可以通过将每个结点指派给它依赖性最强的那个社区这样的方法加以改造，用来适应无重叠社区的情况。在我们的例子中，这意味着将指定结点给拥有最大iz的社区。通过严格证明得出可以将连接社区模型看成是一个无重叠度数校正的随机模型的一种松弛表示。和有重叠的情况一样，我们同样在系统生成网络和现实网络中加以测试。对于生成的无权值的无向网络我们使用标准LFR基准测试。为方便期间。我们采用与Ref31中同样的参数表示。将K的值设为基准测试网络中社区的数目。为了量化表示检测基准测试网络中的已知社区，我们使用Ref31中测量的不同标准化互信息。我们注意到这个测量方法并不唯一，并且通常会返回不同的结果。传统的方法通常用来估计社区结构，使用这种方法同样使得我们能够与Ref31中给出的其他算法所得结果做直接比较。在基准测试中，我们发现通过选择拥有最大iz值的社区这种过分简单化四舍五入式的算法与Ref31中提到的其他算法相比只是取得平均表现性能。然而，对于算法的一个简单的修改就将产生极大的性能上的提高。首先通过采用四舍五入方法生成一个社区的候选划分。接着我们将采用更进一步的优化措施，我们将在随机模型划分下最大化增加对数概率的单一结点从一个社区转移到另一个社区。重复这个过程指导这样的移动不复存在。这个过程容易被实现并且与初始划分相比只需很少的计算开销，这大大改善了我们的结果。图4注4），使用Lancichinetti等人的LFR基准测试模型生成的网络中无重叠社区算法的测试结果。上下两表分别代表不使用和使用后置处理优化对数概率的结果。对于每个网络都使用10个随机初始化变量，每个点都是由超过100个网络所得的平均值。我们实验的结果在图表4中得以展示。上面的表显示的是没有采取附加优化步骤的算法的性能，下面的表展示的是采用附加优化步骤算法的性能。仔细检查这些社区可以发现这种方法偶尔会产生社区分割或是合并。可以通过一个稍微复杂的后置处理步骤来优化可能性，这也使得更进一步提高算法性能成为可能。图5注5），在美国大学足球网络中得出的无重叠社区。结点的聚簇代表由算法得出的社区，结点颜色代表大学被划分进的联盟。可以看出，此例中的算法将联盟结构完美呈现出来（深紫色结点代表不属于任何联盟的大学）。对于现实世界网络，在图表5中我们也给出了其测试结果。这个例子中我们讨论的是Ref1中的大学足球网络。在这个网络中结点代表美国足球中的各大学球队，边代表2000年赛季的比赛时间表，两队如果有比赛则用一条边将其对应结点连接。经反复分析得出这个网络的一个聚簇形成的社区可还原出美国大学运动的组织单元（即联盟），联盟中大学是为了竞赛而划分的。在2000年共有11个联盟I-A组成这个网络。并且有8支队伍独立于任一联盟。如图表5所示，每个单独属于一个联盟的队伍被正确的显示出来。VII结论本文中我们讨论了在无向网络中检测社区（有重叠和无重叠的）的一种方法。这种方法拥有严格的数学基础作保证。它基于一种连接网络的概率模型，容易实现，对于拥有百万数量级结点的网络也有极快的速度。并且能够得到可以与其他算法相媲美的结果。然而，这种方法并不完美。当前其主要的缺陷在于它没有提供任何准则以决定我们称为K的表示网络社区数的值。这是在各种社区检测方法中都普遍存在的问题。一些方法，如模块最大化方法也提供了解决方案，但是会得出偏颇的答案或者是在一些情形下不连续的结论。像贝氏讯息准则和赤池讯息准则这样更严格的方法却不能在这里运用，这是因为很多模型参数的值为零，这也就将它们置于参数空间的边界上，这将使得源于这些准则的假设失效。另一种方法是使用一个较大的K值进行计算并且通过一种方法来规范参数，如果一些社区消失则意味着没有边与这些社区相连。例如，Psorakis等人在研究中使用矩阵分解算法，因为包含很多非零参数它使用前向模型以建立不同社区间的平衡和网络数据的拟合优度。然而问题在于这种预先处理本身包含一些未知参数，它们的值会影响到社区数量，因此上面的问题通过这种方法并不能完全得到解决。我们相信应用于生成模型的统计模型选择方法应该大体上能够以一种一致且令人满意的方式来寻找出社区的数量。我们应用此方法也进行了一些初步试验，其结果充满前景。但是这些方法因为需要大量的计算过程以致于只能在较小的网络中加以应用。对于当今科学家而言，是否能找出一种可靠稳定的方法能够在合理的运行时间内解决大规模网络中的此类问题已成为一类开放问题，并引起他们极大的研究兴趣（我们期待着会有更好的研究成果来解决此类问题）。致谢在此衷心感谢Qiaozhu Mei，Cris Moore和Lenka Zdeborova等提出的的宝贵意见。此项工作得到NSA的基金支持，在此一并感谢！参考文献1 M. Girvan and M. E. J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99, 78217826 (2002).2 S. Fortunato, Community detection in graphs. Phys. Rep.486, 75174 (2010).3 L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, Comparing community structure identification. J. Stat. Mech. P09008 (2005).4 P. W. Holland, K. B. Laskey, and S. Leinhardt, Stochastic blockmodels: Some first steps. Social Networks 5,109137 (1983).5 Y. J. Wang and G. Y. Wong, Stochastic blockmodels for directed graphs. Journal of American Statistical Association 82, 819 (1987).6 T. A. Snijders and K. Nowicki, Estimation and prediction for stochastic blockmodels for graphs with latent block structure. Journal of Classification 14, 75100 (1997).7 A. Clauset, C. Moore, andM. E. J. Newman, Hierarchical structure and the prediction of missing links in networks. Nature 453, 98101 (2008).8 E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, Mixed membership stochastic blockmodels. J. Mach. Learn. Res. 9, 19812014 (2008).9 Y.-Y. Ahn, J. P. Bagrow, and S. Lehmann, Link communities reveal multi-scale complexity in networks. Nature 466, 761764 (2010).10 T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities. Phys. Rev. E 80, 016105 (2009).11 J. Parkinnen, A. Gyenge, J. Sinkkoken, and S. Kaski, A block model suitable for sparse graphs. In Proceedings of the 7th International Workshop on Mining and Learning with Graphs, Association of Computing Machinery, New York (2009).12 A. Gyenge, J. Sinkkonen, and A. A. Benczur, An efficient block model for clustering sparse graphs. In Proceedings of the 8th International Workshop on Mining and Learning with Graphs, pp. 6269, Association of Computing Machinery, New York (2010).13 M. E. J. Newman and M. Girvan, Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004).14 S. Fortunato and M. Barthelemy, Resolution limit in community detection. Proc. Natl. Acad. Sci. USA 104, 3641 (2007).15 B. H. Good, Y.-A. de Montjoye, and A. Clauset, Performance of modularity maximization in practical contexts. Phys. Rev. E 81, 046106 (2010).16 X. S. Zhang, R. S. Wang, Y. Wang, J. Wang, Y. Qiu, L. Wang, and L. Chen, Modularity optimization in community detection of complex networks. Europhys. Lett. 87, 38002 (2009).17 P. J. Bickel and A. Chen, A nonparametric view of network models and NewmanGirvan and other modularities. Proc. Natl. Acad. Sci. USA 106, 2106821073 (2009).18 B. Karrer and M. E. J. Newman, Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).19 M. Molloy and B. Reed, A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 6, 161179 (1995).20 M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 026118 (2001).21 This is a special case of the general observation that the log of the average of any set of numbers is never less than the average of the log, since the logarithm is concave down. If the numbers in question are xz/qz and the average is taken with weights qz this observation leads immediately to the inequality given.22 I. Psorakis, S. Roberts, and B. Sheldon, Soft partitioning in networks via Bayesian non-negative matrix factorization. In 24th Annual Conference on Neural InformationProcessing Systems, Workshop on Networks Across Disciplines: Theory and Applications (2010).23 If the value of _ is greater than 1/K, then it is possible inadvertently to prune all of the colors from a vertex, leaving it in no community at all. To avoid this, we mustchoose _ 1/K, which we have done in all the calculations presented here. 24 W. W. Zachary, An information flow model for conflict and fission in small groups. Journal of Anthropological Research 33, 452473 (1977).25 D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing. AddisonWesley, Reading, MA (1993).26 M. T. Gastner and M. E. J. Newman, The spatial structure of networks. Eur. Phys. J. B 49, 247252 (2006).27 M. Barthelemy, Spatial networks. Physics Reports 499, 1101 (2011).28 M. Zarei, D. Izadi, and K. A. Samani, Detecting overlapping community structure of networks based on vertexvertex correlations. J. Stat. Mech. P11013 (2009).29 F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding, Community discovery using nonnegative matrix factorization. Data Mining and Knowledge Discovery 22, 493521 (2011).30 A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78, 046110 (2008).31 A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis. Phys. Rev. E 80, 056117 (2009).32 T. Hofmann, Probabilistic latent semantic indexing. In Proceedings of the 22nd Annual International ACM Conference on Research and Development in Information Retrieval, pp. 5057, Association of Computing Machinery, New York (1999).33 T. Hofmann, Unsupervised learning by probabilistic latent semantic analysis. Mach. Learn. 42, 177196 (2001).34 T. Hofmann, Latent semantic models for collaborative filtering. ACM Trans. Inf. Syst. 22, 89115 (2004).35 D. D. Lee and H. S. Seung, Learning the parts of objects by nonnegative matrix factorization. Nature 401, 788791 (1999).36 C. Ding, T. Li, andW. Peng, On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing. Comput. Stat. Data Anal. 52, 39133927 (2008).37 D. M. Blei, A. Y. Ng, and M. I. Jordan, Latent Dirichlet allocation.