复杂网络社区结构问题综述.pdfVIP

2011年9月 阴山学刊 Sep．2011 第25卷第3期 YINSHANACADEMICJOURNAL V01．25No．3 复杂网络社区结构问题综述 智 源，行 飞 (内蒙古大学数学科学学院，内蒙古呼和浩特010021) 摘 要：本文从社区的定义，社区结构评价指标，社区发现算法几个方面对复杂网络社区结构问题进行了 综述。对现有的几种对社区的定义进行了较详细的阐述，介绍了几种比较有代表性的评价指标，并对复杂网 络社区发现算法进行了分类总结，最后对复杂网络社区结构的发展做出展望。 关键词：复杂网络；社区结构；评价函数；算法 中图分类号：0242．21文献标识码：A文章编号：1004—1869(2011)03—0031一04 社区结构是复杂网络的一种重要的特性，已经成为复杂 最大的连接数为n；(n。一1)／2，子图外部最大连接数为n。(凡 网络研究的一个热点。经过科学家们的大量科研工作，目前 一ni)．定义子图S。的内部链接率： 对于复杂网络社区结构的研究取得了很大的成果，本文将对 这些新的思想进行综述。 。L —l，二 蹦小志／7,ni／ 自然界和人类社会中很多复杂系统可以抽象为复杂网 其中S。。为子图S内部连边的数量． 络，如食物链网络、新陈代谢网、神经网络、万维网、科学家合 外部连接率： 作网、社会关系网等。对于这些复杂系统，我们可以用网络 (1·2) 中的顶点表示系统中的个体，用边来表示个体之间存在的关 允√s)2而尚 系，这样就可以用顶点和边来刻画复杂系统。2002年，New— 其中s。为子图外部边数． man提出了复杂网络的社区结构(CmmunityStructure)的概 网络的平均连接率： 念，社区(Community)就是网络中结点的集合。社区中的结 点之间具有紧密的连接，而社区之间则为松散的连接。例 占(c)2而等沥 (1．3) 如，在社会网络中，社区可能表现为根据兴趣或背景而形成 其中m为网络中总的边数． 的社会团体。在万维网中，社区可能就是讨论相关主题的一 一个网络的合理社区分割要满足社区内的连接率要大 些网站。 于网络的平均连接率，而社区间的连接率要小于平均连接 本文将从以下几个方面来对复杂网络社区划分问题进 室． 行综述：一、社区的定义。二、社区结构划分的评价指标。 1．2 强社区和弱社区的定义 三、现有社区发现算法概述。四、总结和展望。 lqadieehi等人给出了强社区和弱社区的定义，引文[2] 1 社区定义 中，又在强社区和弱社区的基础上定义了最弱社区，并且对 一些科研工作中们又从不同的角度提出了一些社区的 弱社区的概念进行了改进． 概念，主要有以下几种。