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

Brian Ball,1 Brian Karrer,1 and M. E. J. Newman1, 2 1Department 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年代，当时假定社区是无重叠的或者无交集的。但正如很多研究人员最近这些年争论的那样，在实际情形中社区重叠是普遍存在的。例如在社交网络中，一个人常会拥有不止一个熟人圈，诸如家庭，朋友，同事等等。很明显在这些圈子中存在着至少一个共同成员（也即其本人），也就是说存在着重叠。在生物网络中很多结点可以从属于不止一个群体。在一个新陈代谢网络系统中，一个物种的代谢产物可以在不止一个代谢过程或循环系统中起作用。在食物链中一些物种可以落入两个毫无交集的子社区的边界并且在这两个子社区中都起作用。因此解决网络社区检测问题的一般性方法应当允许结点重叠。我们的研究将首先提出一个对于这种一般问题的解决方案，接着我们将展现此方法的一个变体是如何被应用到无重叠结点社区中的。 我们通过将一个随机生成的网络结构模型应用到实际测得的网络数据中来处理重叠社区的检测。这种将统计推断方法应用到网络中的方法已经被一批学者探索应用于无重叠结点的网络研究中（其中也包含一些数十年前的工作）。然而将同样的方法拓展到有重叠的情形则并不容易。一个关键步骤就是发明一种可以产生与现实中存在网络相似的拥有重叠社区结构网络的生成模型。以前被使用的大多数是一种称为“混合成员”的模型，这种模型中结点可以隶属于多个群组并且拥有超过一个共同群组的两个结点更容易产生联系。然而这也就意味着两个社区的重叠区要比那些仅落入一个单一社区的区域拥有更高平均密度的边。我们并不清楚这样的模型是否能够准确反映出现实世界中存在的网络，但可以肯定的是我们能够构造出这种网络结构之外的网络。理想情况下，我们更倾向于一种限制少且对于重叠社区结构少做假设的模型。 另一组检测