一种基于信息中心度的社团结构查找方法外文翻译资料

 2022-09-02 08:09

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

一种基于信息中心度的社团结构查找方法

社团结构是许多社会、生物、技术网络的重要特征。在这里，我们研究一种检测社团的方法的演变，这个方法是由Girvan和Newman提出的基于用中心度来界定社团边界的构想。( M. Girvan and M. E. J. Newman, Community structure in social and biological networks Proc.Natl.Acad. Sci. USA 99, 7821-7826 (2002)) 我们开发了一种分层聚类的算法，这个算法包括不断地寻找和删除信息中心度最高的边。我们在在计算机生成的网络和现实世界网络中对这个算法进行检测，这些网络的社团结构已经被大家所知道或者通过其他方法已经被研究出来了。我们表明，虽然我们的算法需要O(n4)的时间来运行完成，但它是非常有效的，特别是当这个社团是非常混杂并且几乎没有其他方法可以检测到的时候。

一、引言

在社会，生物和技术系统[ 1，2，3，4，5 ]中网络分析是一个用来理解复杂现象和组织的强大方法。在网络分析的框架中，一个给定的系统被建模为一个图，其中的节点是系统的元素，例如在一个社会系统的个人，大脑中的神经元和网络中的路由器。边代表的是一对元素的相互作用，社会联系，就像突触和电气线路一样。人们对网络[1, 2, 3, 4, 5]中的各种结构和区位特性的描述方法一直有着大量兴趣。其中，在许多网络中都有的共同特性是亚群或者社团结构的存在。

例如，在社交网络中，一些个人可以是一个紧密连接的群体或封闭的社会精英，其他人可以完全隔离，而其他一些人可能作为群体之间的桥梁。个人被嵌入在网络结构中的方式的差异，对他们很可能会实践的行为有重要的后果。社会网络的个体划分是社会制度的一个基本方面。事实上，社会系统中的子群往往有自己的规范、取向和亚文化，有时与官方文化背道而驰，是一个人身份的最重要来源[ 2 ]。自社会网络分析之初，对于这个原因的主要关注点之一，一直是一个网络中的个体群的定义和识别。在社会网络分析中，提出了第一个找到社团结构的算法。

子群对其他网络也很重要。存在于生物技术网络中的子群可能会阻碍对系统运行的重要信息，并且与了解这种网络的增长机制有关。事实上，在万维网中的社团可能代表网页上的共同主题，而在蜂窝[ 6 ]和遗传网络[ 7 ]中的社团可能代表的是功能模块[ 8 ]。因为这个原因，对于找到一个网络里的子结构的技术，能提供一种有力的工具来理解网络的结构和功能。

在本文中，我们提出了一种新的方法来发现社团结构，使用最近推出的信息中心度来测量[ 10，9 ]，基于网络的全球效率的概念[ 11，12 ]。信息中心度在这里被用来确定网络中各边的相关性。该方法包括寻找并删除中心度最高的边，直到网络分解成组件。

论文组织如下。在第二节中，我们复习派系和凝聚子群的定义和在网络中寻找社团结构的标准方法。在第三节中，我们提出了新的方法，并描述其具体过程。在第四节中，我们讨论这个算法在计算机网络中对已有的现有子群的知识与控制的应用。我们表明，该算法，虽然速度慢于市场上的最好的方法，但是能非常有效的发现社团结构，特别是当社团结构是非常混合而且几乎难以检测到的时候。最后，在第五节中，我们讨论了一些对现实世界的网络的应用。在第六节中，我们提出我们的结论。

二、凝聚子群的定义

社会分析家是第一个将社团观念正式化的人，并制定数学方法来测量社团的数量与凝聚力。在这里，我们回顾了最重要的定义为社会系统的发展。由于这个原因，本节的讨论将主要是在社会网络中，虽然，正如我们在下面的章节中所看到的，社团结构的理念同样适用于其他网络。社团，或集群，或有凝聚力的亚群是个人的一个子集，其中有比较强的，直接的，紧张的关系。所有的定义和措施的出发点是子图的概念。一个子图包括从整个图的节点中选择的任何节点集，以及连接这些节点的边。在一个代表社会系统的图中的点的随机样本是一个子图的例子，但它不可能对应于任何有意义的社会群体。一个有意义的社团的概念是基于该子图中的各成员之间的衔接性。然而，一个子图的凝聚力可以通过使用子集的节点之间的各种不同性质来量化。选择一个特定的属性，而不是其他的，这取决于研究人员的决定，一个特定的数学标准，可以给出一个有意义的和有用的社会学解释。总的目标是通过研究整个图的结构性质并寻找一个可以划分为社会网络的自然存在的社团来定义一个有意义的社会范畴。

关于凝聚子群的文献包含各种方式使社会网络中的亚群思想有概念。特别是，有四种考虑到四个不同的结构特性[ 1 ]的主要想法。由此产生的四类凝聚子群以我们弱化从第一个到最后一个亚群必须满足的性质这样的方式来排序。我们简要地提出关于单模、非定向、非价值的图表的这些想法。

  1. 结点的相关性。基于结点的相关性的凝聚子群要求所有分组成员选择彼此。这种想法在集团的定义中是正式的。一个集团就是一个最大的包含三个或多个节点的完整子图，也就是一个子集所有的节点都是彼此相邻的并且没有节点相邻与集团内的所有成员。
  2. 亚群成员的封闭性或可达性。由于集团的定义是相当强大的和对现实社会网络的限制，一些扩展的基本思想已经提出。基于可达性的凝聚子群，要求所有的成员都可以互相联系。用n-cliques延长了集团的概念，弱化所有亚组成员之间的邻接的要求。一个n-clique是任意两个节点之间测地线的最大距离不大于N的最大的子图。当n=1时我们回到“集团”的概念。2-cliques表示一种子图，在这种子图中，所有的节点不需要相邻，但是必须能通过最多一个中介。在3-cliques中所有节点能通过最多两个中介，等等。

一个定义，将在下文中是重要的组成部分。一个组件是最大的连通子图，即图中所有节点对之间的路径都存在，而在子图中节点之间没有路径，任何节点都没有。

  1. 成员之间的联系频率。这个凝聚子群的概念是基于对一个子群中相邻演员的最小数目的限制。而n-clique概念包括增加允许的路径长度，另一种放松的派系强假设方法包括减少其他节点数，每个节点必须连接。一个k-plex是一个最大的子图,包含n个节点，其中每个节点与不少n-k个节点相邻。相比于对n-cliques的分析，对k-plex的分析倾向于寻找一个比较大的小团体。
  2. 亚组成员之间的相对频率与非亚组成员之间的频率比较。这个凝聚子群的概念与前三个是不同的，因为它是基于子群内关系和子群外关系的比较[ 14 ]。在这种方式中，凝聚子群被视为在图中相对高密度的地区，局部密度大于整个域的部分。在这一类里，LS集合是一个亚群的最简单的形式定义。一个LS集合就是一个节点组S，它的任何一个适当的子集（即可以从节点中选择的任何可能的子集）有更多的关系到它的补充，而不是外部的[ 15 ]。LS集合是与遏制有关的事实意味图中有一个集合的层次结构。lambda;集的定义是LS集合定义的延伸，并基于边连通度的概念。对于一对节点i和j的边连通度相当于最小的边数必须从图形中删除，为了不在两个节点之间留下路径。如果节点组S中任何一对节点都比另一对既包含S中的节点又包含S外节点具有较大的边连通性，一个节点组S是一个lambda;集。lambda;集是基于这样一种观念，凝聚子群是相对稳定的，即很难断开相连的边。另一种方法是基于同样的想法，就是是否在图中存在这样一条边，如果被删除，会造成一个断开连接的结构。这种方法是很容易实现的算法程序，并允许开发分层聚类方法。这样的方法根据网络的边的重要性将它们排列并移除，其中边的重要性可以用不同的方式定义，因为它很快会很清楚。通过反复地这样做，网络分解成更小和更小的组件直到它分解成一个单一的非连接的节点的集合。由此产生的分层结构的集群可以表示为树状图，或分层的树，作为一个报告图，显示在每一步的细分产生的集群。

最近，格文和纽曼已经考虑了两种形式的边介数测量边缘的重要性：最短路径介数和随机游走介数[ 17，18，19 ]。边介数的最短路径延伸到弗里曼提出的边缘节点介数[ 20 ]作为节点的中心性度量，被定义为通过该边缘运行的节点之间的最短路径的数目[ 17 ]。随机游走介数考虑随机游动的连接所有节点的节点而不是最短路径（随机游动也被用来量化最近邻节点之间相似的异同在寻找社团的其他算法中[ 21 ]）。格文和纽曼提出的算法在每一步识别和删除是最对节点之间的边，在这个意义上，他们是负责连接多对节点。在本文中我们提出的寻找社团结构的算法是在格纹和纽曼的基础上改进的。在我们的方法中，我们建议直接识别那些边，在移除了大多数后会破坏网络在节点间交换信息的能力。事实上，代替边介数，我们采用测量中心，信息中心度CI[ 9，10 ]，基于有效传播信息的网络概念[ 11，12 ]。信息中心度作为表征一个网络的中心节点是一个有趣的数量从中介中心性给出不同的结果[ 9 ]。因此，我们认为，它可能会对开发一种基于边的信息中心度的分层聚类算法有所用处。

在描述了基于相对频率的凝聚子群的形式定义之后，我们需要给出一些方法来评估亚群的凝聚性。在分层聚类方法中，从原始图到极端的情况下，所有的节点都断开，得到一个层次的社团结构是特别重要的，在这种情况中，社团的数量取决于图被分割在哪一个等级，因此我们需要一个标准说在这一点上停止。一个群是如何衔接的第一个措施，是在文献[ 22 ]提出，是联系数的比值（或一个值图的关系强度平均值）在除以从群外群节点数量关系子群。这种方法在文献[ 18 ]中通过模块化的措施延伸了，我们将在第四节中讨论这个，这证明了许多网络社团的凝聚力程度是成功的。这就是它最近在文献[ 23 ]提出了采用模块化本身作为数量最大化，以确定最佳的群落结构的原因。这种最大化的数值实现允许分析非常大的网络，因为它可以在一个时间远远小于所有以前的算法所需的时间中进行。

  1. 我们寻找社团的方法

寻找结构的算法，我们建议使用最近推出的中心性措施[ 10，9 ]，这是基于网络上的信息的有效传播的概念[ 11，12 ]。我们假设我们要分析的网络可以表示为一个连接的，非定向的，非价值的N个节点和K条边的图G.然而，非对称的延伸和值数据不存在任何特别的问题，并将在即将发表的论文[ 13 ]中被考虑。图G被描述为一个邻接矩阵a，一个Ntimes;n矩阵中如果i和j是相邻的，则aij等于1，否则为0。在图中的2个节点表示相邻的，如果它们被边连接。主对角线上的条目是未定义的，为了方便，它们被设置为0。我们现在给出一些定义，将在下文中用到。一步就是节点和边的交替序列，其中每个边都连接前面和后面的节点。连接i和j的路径是从i到j的一步，所有的点和边是不同的，路径的长度是从i到j所经过的边的数目。i和j之间的最短路径或测地线是从i到j的包含最小数量的边的任何一条路径。

为了描述在网络G中的节点如何高效的传递信息，我们用网络使用效率E这个量，在文献[ 11，12 ]中介绍。这个变量是基于这样一个假设，假设网络中的通信信息沿最短路径（测地线）传递，并且在两个节点i和j之间的通信效率eij等于其最短路径长度dij的倒数。网络G的效率是eij的平均值：

（1）

并测量了G以外的信息平均流量。E[G]的数量在[0,1]的范围内的变化，并且在非连通图的情况下也是一种很好的定义。事实上，当i和j之间没有路径时，我们假设dij= infin;，eij=0。这个性质对我们的算法是非常重要的。

关于测量节点的中心度的方法，也就是所谓的信息中心度，基于网络的效率，最近已经在文献[ 9 ]提出。同样的措施可以用来量化组和类的重要性[ 9，10 ]。

在这里，我们使用这样的措施来量化图G中边的重要性。一条边k的信息中心度CIk定义为当从图G中移除这条边后网络效率的相对下降：

k=1，...,K （2）

这里的Gkrsquo;表示为通过移除图G中的边k所得到的包含N个点和K-1条边的一个图。注意当Gkrsquo;是非连通图时，这个方法也是一种很好的定义。在图G中寻找凝聚子群的层次的方法包括不断地去除具有最高信息中心度的边，直到系统分解成组件。我们期望，那些连接各组件之间的边是具有高信息中心度的边，而组建内部的边具有低的信息中心度。算法的大致过程如下：

  1. 计算各边的信息中心度。
  2. 移除信息中心度最高的边。
  3. 对分解的网络组件进行分析。
  4. 回到第一步，直到所有的边都被移除，系统被分解成N个不连接的点。

在Girvan和Newman算法中[ 17，18 ]，对每次移除边后的信息中心度的计算似乎是一个重要的方面。我们将在第五节中讨论这一点。所有的最短路径的计算，必要的网络计算的效率，可以在时间O(KN)中用广度优先搜索算法执行[ 24，25 ]。然后对所有边的信息中心度的计算需要O(K2N)的时间。这个时间与计算所有的随机游走的边介数的时间相媲美[ 18 ]，但是比O(KN)的时间长，它需要计算最短路径的所有边介数，用文献[ 17 ]中的方法。该算法里每次移除一条边都要重复计算一次信息中心度，即k次。总之，基于信息中心度的社团结构识别算法，可以在O(K3N)或O(K4N)的时间内边成一个稀疏图。然而，正如我们即将在第四节中展示的，在某些情况下，这种基于信息中心度的寻找社团结构的算法比基于最短路径边介数的算法要好，因为它的性能差，它只能用于最多一千个节点的图形。对于非常大的网络，最好的算法就是在文献[ 23 ]提出的，基于模块化最大化的算法，它在一个稀疏图中运行只要O(KN)

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

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

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章