英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

大型网络社团检测

我们研究出了一种算法来识别复杂网络中的社团结构，这种算法是基于光谱的模式并且考虑到解释链接的复杂性和方向性，自从这种算法有效的识别了复杂网络中成群的节点，即使不能明确的划分，这依然非常适合用来分析社会和信息网络。我们通过心理学方面大型的单词链接实验来测试这个算法，在这个试验中，将单词聚合成为社团和找出关于精神方面链接的社团都十分成功。

网络聚类模式的测量和精确结果，主要关注的是事件发生的经常性[1-4]和它们的相关性[5-7]。然而，许多社会和信息网络，如万维网，可以划分为不规则形状的社团，比如主题相同的网页有较强联系而与其他部分有着较弱的联系。这种将一个部分划分成若干有意义的高度链接的社团的模式已经成为可以应用于生物，社会和信息网络的成熟理论[8–11]。

信息网络中的社团结构检测需要一个更有效率的方式：缩小网络的探索，比如将万维网（大约10⁹个节点）缩小到一定的范围。当将其用在大型协作网的分析时，比如公司或者大学，社团通过整个系统揭示了非正式组织和信息流的性质[12,13]。

有几个通过经验来检测社团的方法，其中最成功的一种方法，近期由格文和纽曼提出[10] (NG-algorithm)，基于边界数，这是衡量一个给定的链接的所有最短路径的分数，或者说这是在网络上随机游走的概率。通过消除高介链接，将一个完整的网络逐步分解成断开连接的组件，直到网络被分解成一个个单一节点组成的社团。该算法的结果是由一个树状图表示，树状图的每个分支对应一个分裂事件。当我们有一定有关被分析社团的信息时，这种方式是十分强大的，这种方法有两个主要缺点：第一，它不能给出指示网络分裂成社团何时该停止的信号，所以它需要额外的信息作为输入（比如预期社团的数量）。第二，这种算法不能将其分割成明确独立的社团。出于同样的目的卡斯特利亚诺等人 [14]提出了一种基于边界数的类似算法，它拥有更快的运行速度，但是和NG -算法有一样的缺点。

我们追求的解决这个问题的另一种方法，是基于谱分析。以前用方法图划分的频谱分析，在计算机科学界的主要目的是基于迭代分割找到处理器上最佳分配的并行计算机的进程。当这些方法应用到检测社团结构的时候一般都有一个缺点：有重复的二分法不能保证达到最佳或最自然的划分，此外他们受到基于边界数算法同样的限制，因为他们不会在平分应该终止时给出信号，所以他们需要额外的社团预期分割数量的信息。

在本文中，我们的目标是开发一些基于频谱的算法用来揭示复杂网络的结构，这是为了克服偏差迭代二分法的限制。当其应用在现实网络中时，这种算法应该结合光谱的能量以揭示一个网络潜在的结构有没有明确的分割。

光谱算法是基于分析邻接矩阵A[ 15，17 ]，如果i=j其元素a_ij等于1，否则a_ij=0。尤其是用这个方法分析矩阵A的简单功能时：假设拉普拉斯矩阵L=K-A，普通矩阵N =K ^-1 A，公式中K是对角矩阵的元素K_ii=sum;^S_j=1a_ij，S是网络中节点的数量，在大多数方法中，代指的是无向网络，假设矩阵A是对称的。

由于行正规化，关联到一个不变平凡特征向量，矩阵的最大特征值始终是1。在网络中有一个明显的社团结构的时候，矩阵N有m-1个特征值接近1，定义M是明确划分的社团的数量，剩余的特征值与1有很大的距离。这些m-1个相关的特征向量，一个非平凡特征向量，也有一个特征结构：对应的节点在同一社团中的组件有非常相近的值x_i ,所以只要每个社团的划分足够明确，每个特征向量的数据，按特征值排序是一个接一个的队列。在配置文件中的步骤数M就是对应社区的数量。类似的算法是非负的拉普拉斯矩阵编码，在特征值接近零时社团相关。

通过对特征向量的研究发现这种算法的实际使用只适合当一个网络存在明确的分区的情况，这是很少见的。在大多数情况下，节点的数目非常大，而不同社区之间的分割是比较模糊的。因此，不能从第一个平凡特征向量检测到社团结构。我们解决这个问题，通过从最初的几个特征向量结合信息，并从不同的特征向量在相同的社团之间的相关性提取社团结构。详细地描述该方法，并理解它为什么工作，这有利于将特征值问题转化为一个更优化的问题。在我们心中最实用的应用程序，不是邻接矩阵A，而是权重矩阵W，其元素w_ij指定链接的强度（I；J）。我们首先考虑无向图，然后我们扩展到最一般的定向的情况下。考虑以下约束优化问题：定义Z(X)为

（1）

X_i用来分配节点的值，向量方面的关系用X表示为

（2）

其中M_ij是给定对称矩阵M的元素，在所有约束条件下的固定点，公式（2）是下式的结果

（3）

公式中D是对角矩阵的元素，u是拉格朗日乘子。

对矩阵M不同的约束，会导致不同的特征值选择问题。比如选择M=D会导致特征值问题当M=1时会导致

因此，对于M=D或1，对应的特征值分别为（广义）平凡矩阵和拉普拉斯矩阵。

因此，求解特征值问题等价于最小化功能（1）与约束（2），其中X_i是特征向量的分量，最小绝对值对应于特征向量，是个常数。其他的固定点对应的特征向量，以及相关联的节点承担类似的值。

方法如二分法或边界数的检测都不能在适合的时间停止网络分割成社团。为了计算社团的大小和分布，我们的方法，不是立即从特征向量中检测到网络应该被分割成社团的数量。

图2是一个典型的例子，根据D^-1W的第二特征向量可以分割成图1所示的简单图，网络节点数S=19，将1和10之间的随机权重分配给链接（图1和图2）属于同一社区的节点对应的特征向量的组成部分代表恒定的值。因此，社区的数量自然出现，这是不需要作为输入。

不过，如上所述，当处理大网络没有明确的分区，该特征向量分量的精确值能发挥的作用非常小。在这种情况下，典型的特征向量不是一个阶梯状分布，但看起来像连续的曲线。不过，我们的方法依然能使用，并且能有效检测到连接良好的节点。事实上，对应节点属于同一社团的链接仍然是强相关性的，在每个特征向量之间他们的值是相似的。因此，一个非常实用的方法来确定社团结构是衡量相关性。

其中，lt;.gt;表示对若干第一平凡特征向量中相应的元素取平均值，r_ij的大小可以用来衡量节点i和节点j之间的连接度，显然，对越多的特征向量求平均值效果就越好，随着计算量的增加，我们发现，即使是大型的复杂网络，只要对少量的特征向量求平均值就能取得很好的效果。

图1 ：由19个节点组成的三社团网络

网络中的每条边都被随机赋予一个1到10之间的权值，该网络明显的分为三个社团，其中节点0到6,7到12,13到18分别构成这三个社团。

图2 ：图1所示网络的D^-1W矩阵的第二向量中各元素的分布情况

在处理一个有向网络时，链接不对应任何等价关系。相反，拥有共同指向的相邻节点是一个重要的关系，在一些社会学的文献中将其称为节点结构等价[18]。因此，在一个有向网络中，社团应该是由大量指向公共相邻节点的节点组成的，而不管他们的直接联系。在有向网络中，我们修改我们的方法，简化命中算法[17]。提出了在基于经验的基础上，从大型网络中寻找主流群体的命中算法。它假定的最大组成部分（在绝对值）的矩阵的特征向量，而不是一个对应的高度聚集的节点属于一个单一的社团。这样的算法能有效地检测到主要社团，即使这些社团结构都没有明确界定。然而，一个小社团对应于较小的特征值，它的计算变得十分繁琐。在无向的情况下，我们解决这个问题，通过从最初的几个特征向量的平凡矩阵和相同的节点在不同的特征向量之间的相关性结合信息提取社团结构。

为了在一个有向网络中检测到社团结构，我们将采用新的方法：矩阵W和矩阵Y=WW^T。这相当于取代定向网络的无向加权网络，节点指向的共同节点通过链接项链，其强度是成正比的权重的链接指向从原来的节点指向共同的相邻节点的总和。然后我们将用前面提出的方法来检测无向网络。在这种情况下，最小化的功能是：

（5）

Q是对角矩阵，其元素，广义平凡矩阵的特征值问题（6）

相当在约束条件下，于最大限度地减少函数（5）

在简单的有向网络中，算法通过Y的最小值得出的结果优于通过Z的最小值得到的结果。

为了检验这一光谱相关的社团检测方法在真实复杂的网络的应用，我们将算法应用于一个心理实验报告的参考数据[19]。志愿者在该实验中快速自由地将一个词（响应）和另一个词作为输入（刺激）联系，由一个固定子集提取。科学家进行研究记录了所有的刺激和相关的反应，随着每个关联的发生。对于这份参考数据 [20]，我们构建了一个用单词作为节点组成的网络，并根据每个刺激的响应的加入相应的链接，假设每个链接都是面向刺激做出的响应。由此产生的网络包括S=10616个节点，平均路径长度约为7。考虑到给定的刺激引起响应的频率，我们构造了加权邻接矩阵W。在这种情况下，信号传递到矩阵Y的意思是，我们研究的刺激与引起的反应是相关的。

大型语义属性[19,21,22 ]和句法网络[ 23 ]在过去的许多不同国家的文献中，主要是基于字典和文本，已经发现一个强大的相似性：统计特征必须是指一个共同的基本结构，而不是个别特征。有趣的是，迄今为止的字图网络也是复杂网络的一种，其与小世界有共同的特征并通过幂律度分布具体定义的网络[24]。

词联想网络是一个理想的网络来测试我们的算法，尽管在大尺寸的网络中，社团的质量可以通过直接检查评估是否符合。在类似这样的大数据库中，社团中的一个分区没有以自然的方式定义，也没有明确的答案，最好的分区是什么。相反，我们十分感兴趣的是寻找一组高度相关的节点或一个高度连接到给定节点的组。表一列出了三组测试单词中相关度最高的单词。通过平均超过10个特征向量的矩阵Q^-1Y计算的相关性：仅计算少量特征向量得到的结果似乎是相当令人满意的。

除了寻找相关节点社团的表现，我们的结果有多重标准：由于该实验中的词语有许多相近的词汇。我们观察到，自由联想是通过同义词或反义词、句法角色甚至类似的感觉产生的。

总之，我们已经介绍了一种新的方法来检测网络中的高度连接的节点的社团。该方法是基于频谱分析，并考虑到节点之间的加权链路的存在。不同于以往的谱方法，我们的方法不是基于迭代分割。我们在一个真实的网络实例测试了我们的算法：建立一个心理实验的记录。该算法被证明能够成功的检测到社团结构（在这种情况下）根据合理的标准，并提供了一种自动的方法来提取最高连接度的节点集到一个给定的10⁴组中的一组。鉴于广泛的适用性，这种算法给出一个可靠的方法来检测大型网络社团，在许多的领域都适用，包括生物学，计算机科学和社会学。

我十分高兴能与雷蒙费勒坎乔和米格尔安吉拉一起进行愉快的讨论。

我们十分感谢FET Open Project COSIN 和 IP project DELIS的特别帮助。

人们感兴趣的许多网络，包括社会网络，计算机网络，和代谢和调控网络，被发现自然分成社团或模块。该社团结构的检测与特征问题是网络化系统研究中的一个突出问题。一个非常有效的能将网络最优化分解的办法是称为“模块化算法”的网络优化分裂。我在这里表明，模块化可以把一个特征矩阵的特征向量表示为矩阵，我称之为模块化矩阵，这种表达导致光谱算法在检测社团结构时比其他算法运行时间更短结果更好。本文说明了该方法与应用该程序的几个已发表的网络文献。

许多系统可以科学的被表示为网络，通过线或边连接的节点或顶点的集合。包括互联网和万维网，代谢网络，食物网，神经网络，通信和分销网络，和社会网络。网络系统的研究历史追溯了几个世纪，但它在过去的十年中飞速发展，特别是在数学科学方面的研究，部分原因是由于越来越多的具有准确可用性的大规模描述网络的拓扑结构数据出现在现实世界中。这些数据的统计分析，揭示了一些意想不到的结构特征，如高网络传递，幂律分布，和重复的社团存在模式。

一个问题已经得到了相当多的关注，在网络和社区结构特征检测，在密集连接组的顶点出现只有稀疏连接的组。检测到这样的社团可能有显著的实际意义。例如，在全球范围内的组可能对应于相关主题的网页；社会网络中的群体可以对应于社会单位或社团。仅仅是发现一个网络中包含着紧密联系的群体，在所有能传递有用信息的信息：如果一个新陈代谢网络被分成了这样的群体，例如，它可以提供一个模块化的视图的网络的动态，具有不同的组的节点进行不同的功能，具有一定程度的独立性的证据。

过去在网络中发现社团的工作主要分为两个主要的研究路线，都有很长的历史。首先，这是由图形分区的分类方法，一直追求特别是在计算机科学和相关领域，并行计算和集成电路设计和其他领域中的应用。其次，有确定分区的方法，如块建模，层次聚类，或社区结构检测，一直研究的社会学家和最近的物理学家，生物学家和应用数学家，非常注重社会和生物网络的应用。

这是很有价值的建议，这两行的研究真的解决了同样的问题，尽管有点不同的手段。然而，有重要的相同目标之间不同的阵营，使不同的技术方法可取。在图形划分的一个典型问题是划分一组并行计算机的处理器之间的任务，以减少处理器间通信的必要量。在这样的应用中，处理器的数目通常是预先知道的，并且每个处理器可以处理的任务的数量至少是一个大概已知的数字。因此，我们知道，网络将被拆分成的数量和具体多大规模的网络将被拆分。此外，目标通常是要找到最佳的网络分区，即使是一个不好的分工，甚至存在的一个算法或方法，在某些情况下都可能导致失败的网络划分。

相反，社团结构检测，作为一个数据分析技术，也许是最好的方法用于揭示大型网络数据集的结构，如社会网络，互联网和网络数据，

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[147522]，资料为PDF文档或Word文档，PDF文档可免费转换为Word