复杂网络中分析社团结构算法研究概述
复杂网络及其在国内研究进展的综述
第17卷第4期2009年10月 系统科学学报 JOURNAL OF SYSTEMS SCIENCE Vo1.17No.4 oct ，2009 复杂网络及其在国内研究进展的综述 刘建香 （华东理工大学商学院上海200237） 摘要：从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内关于复杂网络理论及其应用的研究现状从两方面进行综述：一是对国外复杂网络理论及应用研究的介绍，包括复杂网络理论研究进展的总体概括、复杂网络动力学行为以及基于复杂网络理论的应用研究介绍；二是国内根植于本土的复杂网络的研究，包括复杂网络的演化模型，复杂网络拓扑性质、动力学行为，以及复杂网络理论的应用研究等。并结合复杂网络的主要研究内容,对今后的研究重点进行了分析。 关键词：复杂网络；演化；拓扑；动力学行为中图分类号：N941 文献标识码：A 文章编号：1005-6408（2009）04-0031-07 收稿日期：2009-01-05 作者简介：刘建香（1974—），女，华东理工大学商学院讲师，研究方向：系统工程。E-mail ：jxliu@https://www.docsj.com/doc/7a5644002.html, 0引言 系统是由相互作用和相互依赖的若干组成部分结合的具有特定功能的有机整体[1]。而网络是由节点和连线所组成的。如果用节点表示系统的各个组成部分即系统的元素，两节点之间的连线表示系统元素之间的相互作用，那么网络就为研究系统提供了一种新 的描述方式[2、3] 。复杂网络作为大量真实复杂系统的高度抽象[4、5]，近年来成为国际学术界一个新兴的研究热 点，随着复杂网络逐渐引起国内学术界的关注，国内已有学者开始这方面的研究，其中有学者对国外的研究进展情况给出了有价值的文献综述，而方锦清[6]也从局域小世界模型、含权网络与交通流驱动的机制、混合择优模型、动力学行为的同步与控制、广义的同步等方面对国内的研究进展进行了简要概括，但是到目前为止还没有系统介绍国内关于复杂网络理论及应用研究现状的综述文献。本文从复杂网络模型的演化入手，在简要介绍复杂网络统计特征的基础上，对国内研究现状进行综述，希望对国内关于复杂网络的研究起到进一步的推动作用。 1.复杂网络模型的发展演化 网络的一种最简单的情况就是规则网络 [7] ，它 是指系统各元素之间的关系可以用一些规则的结构来表示，也就是说网络中任意两个节点之间的联系遵循既定的规则。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。20世纪50年代末，Erdos 和Renyi 提出了一种完全随机的网络模型———随机网络（ER 随机网络），它指在由N 个节点构成的图中以概率p 随机连接任意两个节点而成的网络，即两个节点之间连边与否不再是确定的事，而是由概率p 决定。或简单地说，在由N 个节点构成的图中，可以存在条边，从中随机连接M 条边所构成的网络就叫随机网络。如果选择M =p ，这两种构造随机网络模型的方法就可以联系起来。规则网络和随机网络是两种极端的情况，对于大量真实的网络系统而言，它们既不是规则网络也不是随机网络，而是介于两者之间。1998年，Watts 和Strogatz [8]提出了WS 网络模型，通过以概率p 切断规则网络中原始的边并选择新的端点重新连接 31--
复杂网络研究概述,入门介绍
复杂网络研究概述 周涛柏文洁汪秉宏刘之景严钢 中国科学技术大学，近代物理系，安徽合肥：230026 摘要：近年来，真实网络中小世界效应和无标度特性的发现激起了物理学界对复杂网路的研究热潮。复杂网络区别于以前广泛研究的规则网络和随机网络最重要的统计特征是什么？物理学家研究复杂网络的终极问题是什么？物理过程以及相关的物理现象对拓扑结构是否敏感？物理学家进入这一研究领域的原因和意义何在？复杂网络研究领域将来可能会向着什么方向发展?本文将围绕上述问题，从整体上概述复杂网络的研究进展。 关键词：复杂网络小世界无标度拓扑性质 A short review of complex networks Zhou Tao Bai Wen-Jie Wang Bing-Hong? Liu Zhi-Jing Yan Gang Department of Modern Physics, University of Science and Technology of China, Hefei, 230026 Abstract: In recent years, the discoveries of small-world effect and scale-free property in real-life networks have attracted a lot of interest of physicists. Which are the most important statistical characteristics for complex networks that known from regular networks and random networks? What is the ultimate goal of the study of complex networks? Are physical processes sensitive to the topological structure of networks? What are the reason and meaning that physicist come into the research field on complex networks? What are the directions for future research? In the present paper, we concentrate on those questions above and give a general review about complex networks. Keyword: complex networks, small-world, scale-free, topological characters 1 引言 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述。一个典型的网络是由许多节点与连接两个节点之间的一些边组成的，其中节点用来代表真实系统中不同的个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条边，反之则不连边，有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作大量神经细胞通过神经纤维相互连接形成的网络[1]；计算机网络可以看作是自主工作的计算机通过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络[2]。类似的还有电力网络[1]、社会关系网络[1,3-4]、交通网络[5]等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来描述真实的系统呢？两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里，科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又或者最近邻环网，它总是会让你想到一群手牵着手围着篝火跳圆圈舞的姑娘。到了二十世纪五十年代末，数学家们想出了一种新的构造网
基于复杂网络的社团结构分析_以四川大学蓝色星空为例
技术与市场 第16卷第12期2009年 1.引言 目前，国内对虚拟论坛的社区结构有一定的研究，张瑜通过实证分析证实了公社社会类型、科层社会类型和广场社会类型这三种类型的交往场域在BBS网络空间中的存在性，并分析了各类交往场域的特点,探讨了不同类型交往场域的形成机制。宫辉和徐渝利用社会网络矩阵分析法对网络虚拟社区中信息传播模式进行分析，概括出网络虚拟社区群体的基本特征。余兰则对大学生在BBS交往中的网络角色进行了研究。彭小川和毛晓丹运用社群图和矩阵法对网络社会群体进行了分析，概括出BBS群体的基本特征，并对群体中成员地位的形成、意见领袖的特点和群体内部人际交往的特征进行了探讨。王海明和韩瑞霞则在2004年发表了对国内BBS研究现状的述评文章。 从目前国内研究的情况看来，许多的研究已经开始使用社会网络的方法对论坛数据进行分析。尽管国内外学者作了大量研究，但是大部分都是从传播学、社会学以及心理学的某一角度进行研究，分析手段的限制使得大部分研究仍停留在定性阶段，所得到的结论说服力不强。因此，我们将采用复杂网络的方法，通过对蓝色星空数据进行研究和分析，包括两个阶段：1)建立复杂网络模型；2)对该模型进行分析，找出该网络的基本统计数据，包括度分布、聚集系数和平均路径长度等。 2.复杂网络 2.1网络定义 网络已成为各学科领域重要的分析工具和研究手段。网络是由许多节点与连接节点的边组成，其中节点代表系统中不同的个体，边则表示个体间的关系；两个节点之间具有特定的关系则连一条边，有边相连的两个节点被看作是相邻的。比如计算机网络可以看作是自主工作的计算机通过各种物理介质与通信协议相互连接得到的网络。 2.2复杂网络 网络模型包括规则网络、随机网络和复杂网络。随机网络首先由Erdos和Rényi引入，是概率方法与传统图论相结合的网络，着重于网络的随机性。而科学家们发现大量的真实系统的网络模型既不是随机网络，也不是规则网络，却是介于随机网络和规则网络之间的复杂网络。1998年Watts和Strogatz表明大量真实网络都具有小世界效应；1999年Barabasi和Albert指出许多现实世界中的大量网络具有无标度网络(scale-free)的特性—— —无尺度特征、脆弱性和抗毁性。无尺度特性刻画了复杂网络的不均匀复杂性，即大部分结点只有少数连接，少数结点拥有大量连接。脆弱性与抗毁性并存从另一方面反映无尺度特性。Albert等人的研究表明，无标度网络比随机网络具有更强的抗毁性，但是对于选择性攻击抗攻击能力较差，5%的核心结点被攻击，网络就基本瘫痪。 复杂网络的研究可以简单概括为三方面密切相关却又依次深入的内容：通过实证方法度量网络的统计性质；构建相应的网络模型来理解这些统计性质何以如此；在已知网络结构特征及其形成规则的基础上，预测网络系统的行为。 2.3复杂网络的主要统计参数 2.3.1度和度的分布 一个节点与其它节点相连的边数称为该节点的度,度是描述网络局部特性的基本参数。节点度分布是指网络中度为k的节点的概率p(k)随节点度k的变化规律。节点度的分布函数反映了网络系统的宏观统计特征,理论上利用度的分布可以计算出其它表征全局特征参数的量化行为。 2.3.2平均路径长度 网络中两个节点i和j之间的距离dij定义为连接这两个节点的最短路径上的边数。网络中任意两个节点之间的距离的最大值称为网络的直径，记为D，即 D=max i,j d ij 网络的平均路径长度L定义为任意两个节点之间的距离的平均值，即 L=1 1 2 N(N-1) ∑i≥j d ij其中，N为网络节点数。 2.3.3聚集系数C 在有N个节点的网络中,若第i个节点的度为k i ,由这k i个邻 基于复杂网络的社团结构分析 —— —以四川大学蓝色星空为例 陈志翔 四川大学计算机学院成都610041 摘要：随着我国计算机和网络的普及，网络社团、尤其是BBS，在人们日常生活中发挥着巨大的作用，国内目前对BBS 的社团结构进行定量分析的研究不多。本文通过对基于四川大学蓝色星空ID间相互回帖关系所构建的复杂网络模型的 研究，构造仿真实验，找出该网络的基本统计数据。 关键词：复杂网络社团结构BBS网络建模 doi:10.3969/j.issn.1006-8554.2009.12.029 专题研究 41
基于信号传递与层次聚类的社团发现算法
ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用２０１０，４６（９）５１ 基于信号传递与层次聚类的社团发现算法 黄浩英，马英红 ＨＵＡＮＧＨａｏ－ｙｉｎｇ，ＭＡＹｉｎｇ－ｈｏｎｇ 山东师范大学管理与经济学院，济南２５００１４ ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ＆Ｅｃｏｎｏｍｙ，ＳｈａｎｄｏｎｇＮｏｒｍａｌＵｌｌｉｖｅ玛ｉｔｙ，Ｊｉｎａｎ２５００１４，Ｃｈｉｎａ Ｅ—ｍａｉｌ：ｈｕａｎｇｈａｏｙｉｎ９２０００＠１２６．ｃｏｍ ＨＵＡＮＧＨａｏ－ｙｉｎｇ。ＭＡＹｉｎｇ－ｈｏｎｇ．ＤｅｔｅｃｔｉｎｇｃｏｍｍｕｎｉｔｙａｌｇｏｒｔｔｌｕｎｂａｓｅｄＯｎａｇｕａｌｐｒｏｃｅｓｓａｎｄｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ．ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｔｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ．２０１０。４６（９）：５１－５４． Ａｂｓｔｒａｃｔ：Ｃｏｍｍｕｎｉｔｙｉｓｏｎｅｏｆｉｍｐｏｒｔａｎｔｃｈａｒａｃｔｅｒｓｉｎｓｏｃｉａｌｎｅｔｗｏｒｋｓａｎｄｃｏｍｍｕｎｉｔｙｄｅｔｅｃｔｉｎｇｉｓａｌｓｏａｆａｓｈｉｏｎａｂｌｅｓｔａｔｅｍｅｎｔｒｅｃｅｎｔｌｙ．Ｉｎｔｈｉｓｐａｐｅｒ，ｂａｓｅｄｏｎｓｉｇｎａｌｉｎｇｐｒｏｃｅｓｓｏｎｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ，ｉｎｆｌｕｅｎｃｅｖｅｃｔｏｒｓｏｆｅａｃｈｎｏｄｅａｔｅｇｏｔ，ｔｏｐｏｌｏｇｉｃａｌＳｔｌｔｌｌＣ－－ｔｕｒｅｏｆｅａｃｈｎｏｄｅｉｓｔｒａｎｓｌａｔｅｄｉｎｔｏｇｅｏｍｅｔｒｉｃａｌｒｅｌａｔｉｏｎｓｈｉｐｓｏｆｖｅｃｔｏｒ８ｉｎａｌｇｅｂｒａｓｐａｃｅｓ．ａｎｄｂｙｔｈｅａｉｄｏｆｈｉｅｒａｒｃｈｉｃａｌｃｈ吼ｅ卜ｉｎｇｍｏｄｕｌａｒｉｔｙｈｉｅｔｌＩｏｄ，ｃｏｍｍｕｎｉｔｉｅｓａｒｅｄｅｔｅｃｔｅｄｅｆｆｅｃｔｉｖｅｌｙ．ＷｉｔｈｄａｔａｓｉｍｕｌａｔｉｏｎｓｏｎｔｈｅＺａｃｈａｒｙＫａｒａｔｅＣｌｕｂｎｅｔｗｏｒｋ，ＣｏＨｅｇｅＦｏｏｔｂａｌｌｎｅｔｗｏｒｋａｎｄＤｏｌｐｈｉｎｓｏｃｉａｌｎｅｔｗｏｒｋ，ｉｔｓｈｏｗｓｔｈａｔｔｈｅｐｒｏｐｏ窨ｅｄａｌｇｏｒｉｔｈｍｉｎｔｈｉｓｔｏｐｉｃｉｓｍｏｌｅａｃｃｕｒａｔｅｔｈａｎＮｅｗｍａｎ’８．Ｋｅｙｗｏｒｄｓ：ｃｏｍｍｕｎｉｔｙｓｔｒｕｃｔｕｒｅ；ｓｉｇｎａｌｐｒｏｃｅｓｓ；ｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇ；ｍｏｄｕｌａｒｉｔｙ 摘要：社团是社会网络的一个重要特征，社团发现是近年来研究的热点问题之一。通过在复杂网络上传递信号，获得各节点对网络的影响向量，从而把网络中节点的拓扑性质转化为代数空间上向量的几何关系，然后用结合模块度的层次聚类挖掘社会网络中的社团结构。该算法优点是不需要预先知道社团的数量或社团内节点的数量，用Ｚａｃｈａｒｙ空手道俱乐部网络、大学足球赛网络以及海豚关系网络的数据进行验证，该算法划分的社团准确性超过了Ｎｅｗｍａｎ的结论。 关键词：社团结构；信号传递；层次聚类；模块度 Ｉ）ＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２－８３３１．２０１０．０９．０１６文章编号：ｌ００２＿８３３ｌ（２０ｌＯ）０９－００５ｌ—０４文献标识码：Ａ中图分类号：Ｎ９４；ＴＰ３９３ １引言 复杂网络是复杂系统的抽象，网络中的节点代表复杂系统中的个体，节点之间的边则代表系统中个体之问某一种关系。现实世界中复杂网络无处不在，如人际关系网、科学家合作网络、万维网、食物链网络等等。大量的研究表明，许多实际网络都呈现具有社团的性质，即整个网络是由若干个社团构成，在每个社团内部节点之间的连接相对紧密，而在各个社团之间却相对稀疏１１１。例如，在以人为主体的社交网络模型中，网络中的连线是根据兴趣或某种关系而形成的，—个人连接线越多，则表示他拥有的关系越多、影响也越大，并且可以控制的资源也越多，此时他与所连接的人就构成了—个社团。在科学引文网络中的社团代表针对同一主题的相关论文，而生物化学网络中的社团则代表具有相近功能的单元嘲，发现网络中的社团有助于更加有效地理解网络结构以及网络特性。 社团的研究中—个重要的课题是网络社团的划分，与此相关的理论包括图论以及模式识别等。社团的发现最早起源于社会学研究工作，较早的算法是在社会学研究中的分级聚类算法，它与计算机科学中的图形分割研究有着密切的关系嗍，其中分级聚类中最著名的是ＧＮ算ｉ去ｆｕ，Ｋｅｍｉｇｈａｒｔ—Ｌｉｎ算法哪谱平分嗣法是图形分割在处理社团划分中最具代表性的方法。此外，还有许多有效的算法如Ｒａｄｉｃｃｈｉ算法、极值优化算法、Ｎｅｗｍａｎ快速算法等Ｍ。在所有的社团的搜索算法中时间复杂度和查找的准确性是最为关键的两个问题。 基于上述问题，用在复杂网络传递信号的方法，得到网络中每个节点对网络的影响向量，通过每个节点的影响向量把网络的拓扑关系转换到ｎ维代数空问上，将ＧＮ算法中提出的模块度函数与层次聚类方法结合进行社团结构的探测，用Ｚａｃｈａｒｙ空手道俱乐部网络、大学足球赛网络以及海豚关系网络的数据进行验证，该算法划分的社团准确性超过了Ｎｅｗｍａｎ的结论研。该算法优点是不需要预先知道社团的数量或社团内节点的数量，算法较好地改善了运行时间，提高了社团搜索的准确率。 ２算法准备 ＨｕＹａｎｑｉｎｇ等人提出了在复杂网络中传递信号的方ｊ去Ｉ嘲，是将—个具有ｎ个节点的网络视为—个系统，系统中的每个节点被认为具有发送、接受和记录信号的功能。信号传递基本思 基金项目：国家自然科学基金（ｔｈｅＮａｔｉｏｎａｌＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＣｈｉｎａｕｎｄｅｒＧｒａｎｔＮｏ．６０６７３０４７）；山东省自然科学基金（ｔｈｅＮａｔｕｒａｌＳｃｉｅｎｃｅＦｏｕｎｄａｔｉｏｎｏｆＳｈａｎｄｏｎｇＰｒｏｖｉｎｃｅｏｆＣｈｉｎａ）；山东省教育厅科技项目（ＮｏＪ０７ＹＪ０２）。 作者筒介：黄浩英（１９８３一）。女。研究生。主要研究方向：复杂网络与复杂系统；马英红（１９７１一），女，副教授，主要研究方向：复杂网络与复杂系统，图论，粗糙集应用等。 收稽日期：２００９一ｌｏ－１２修回日期：２０１０－０１－０８ 万方数据
复杂网络的局部社团结构挖掘算法
第40卷第5期自动化学报Vol.40,No.5 2014年5月ACTA AUTOMATICA SINICA May,2014 复杂网络的局部社团结构挖掘算法 袁超1柴毅1,2 摘要挖掘复杂网络的社团结构对研究复杂系统具有重要的理论和实践意义.其中,相较于全局社团,局部社团的挖掘难度更大,相关文献更少.现有的局部社团挖掘算法大都精度较低、稳定性较差.本文提出了一个有效的局部社团挖掘算法,称为内外夹推法(Shell interception and core expansion,SICE).算法有两个创新之处:1)将节点相似度模型引入到局部社团挖掘算法中(节点相似度模型在局部社团挖掘中较难应用),并提出了“一次一个子图”的社团扩展模式;2)提出了一种“内外夹推”的思想.这两个创新使SICE算法摆脱了缺乏网络全局信息的困扰,并解决了以往算法的一个致命缺陷,从而使算法具有很高的精度和稳定性.通过理论分析和实验比较,证明SICE算法要远好于当前的同类算法,甚至不逊色于性能较好的全局社团挖掘算法. 关键词复杂网络,局部社团,数据挖掘,聚类 引用格式袁超,柴毅.复杂网络的局部社团结构挖掘算法.自动化学报,2014,40(5):921?934 DOI10.3724/SP.J.1004.2014.00921 Method for Local Community Mining in the Complex Networks YUAN Chao1CHAI Yi1,2 Abstract Community structure detection bears both theoretical and practical signi?cance for the study of complex sys-tems.Generally speaking,the local community detection is relatively a more di?cult problem than the global community detection.So up to now,the related researches are still slow progress.And there are many defects existing in the previous local community detection algorithms,such as low precision and poor stability.In this paper,a local community detection algorithm,which is called shell interception and core expansion(SICE),has been proposed.There are two innovations in this algorithm:1)A node similarity model is introduced into this algorithm,and a community expansion mode“one sub-graph at a time”is proposed;2)An e?ective method which is named“shell interception and core expansion”is proposed. By these two innovations,the SICE algorithm has solved the problem of missing global network information,and avoided a fatal weakness of the previous algorithms.Theoretical analysis and experiments all illustrate that the SICE algorithm has high precision and stability,and it outperforms the previous algorithms. Key words Complex network,local community structure,data mining,clustering Citation Yuan Chao,Chai Yi.Method for local community mining in the complex networks.Acta Automatica Sinica, 2014,40(5):921?934 复杂网络分析是当前最重要的多学科交叉研究领域之一[1].社团结构挖掘则是复杂网络研究中的重要内容,对网络的结构特性和动力学特性分析具有重要帮助.此外,社团结构挖掘在许多工程领域中也有重要的应用,如图像分割领域[2?3]、互联网领域[4]等.近年来,不同领域的学者提出了许多有效的社团挖掘算法.如传统的全局社团挖掘算法 收稿日期2013-03-26录用日期2013-08-13 Manuscript received March26,2013;accepted August13,2013国家自然科学基金(61374135)资助 Supported by National Natural Science Foundation of China (61374135) 本文责任编委吕金虎 Recommended by Associate Editor LV Jin-Hu 1.重庆大学自动化学院重庆400044 2.重庆大学输配电装备及系统安全与新技术国家重点实验室重庆400044 1.School of Automation,Chongqing University,Chongqing 400044 2.State Key Laboratory of Power Transmission Equip-ment and System Security and New Technology,Chongqing Uni-versity,Chongqing400044(包括非重叠社团挖掘算法[5?9]和重叠社团挖掘算法[10?11])、演化网络的社团挖掘算法[12?13]以及局部社团挖掘算法[14?18]等. 现实世界中,对于像互联网这样的大规模复杂网络,通常只能获取其局部信息,很难获取其全局信息.这样,许多传统的全局社团挖掘算法就很难在这些网络上应用.另外,许多情况下我们也只需要挖掘某个或者某些节点所属的社团结构,并不需要探测整个网络的社团结构.因此,有必要设计出高效的局部社团挖掘算法.然而,由于只能得到网络的局部信息,局部社团的挖掘难度比全局社团的挖掘难度更大.目前,这方面的典型算法并不是很多.其中,Clauset提出了一个基于R值的局部社团挖掘算法[14].该算法首先定义了一个局部模块度R,然后,采用贪婪算法的思想,迭代地添加使R值增加最大的邻居节点,直到局部社团达到预先定义的规模.其中,局部模块度R值的定义如下:
社团算法总结
社团发现的算法 1.非重叠社团发现算法 1.1基于模块度优化的社团发现算法 （1）Newman M E J. Fast Algorithm for Detecting Community Structure in Networks[J]. Phys Rev E, 2004, 69(6): 066133. （2）Clauset A. Finding Local Community Structure in Networks[J].Phys Rev E, 2005, 72(2): 026132 （3）SchuetzP,CaflischA.MultistepGreedyAlgorithmIdentifiesCommunity Structure in Real-world and Computer-generatedNetworks[J]. PhysRev E, 2008, 78(2): 026112. 1.2基于谱分析的社团发现算法 （1）Donetti L, Munoz M. Detecting Network Communities: A New Systematic and Efficient Algorithm[J]. Journal of Statistical Mechanics, 2004, P10012 （2）Capocci A, Servedio V D P, Caldarelli G, et al. Detecting Communities in Large Networks [J]. Physica A: Statistical Mechanics and Its Applications, 2005, 352(2-4): 669-676. 1.3 基于信息论的社团发现算法 （1）Rosvall M, Bergstrom C T. An Information-theoretic Framework for Resolving Community Structure in Complex Networks[J]. P Natl Acad Sci USA, 2007, 104(18): 7327-7331. 1.4 基于标号传播的社团发现算法 Raghavan UN, Albert R, Kumara S. NearLinearTime Algorithmto Detect CommunityStructures inLarge-scaleNetworks[J]. Phys RevE, 2007, 76(3): 036106. 1.5 迭代层次社团发现算法 一种新的复杂网络层次社团发现算法 2．重叠社团发现算法 2.1 基于团渗透改进的重叠社团发现算法 Palla G, Derenyi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society [J]. Nature, 2005, 435(7043): 814-818. 2.2 基于模糊聚类的重叠社团发现算法 Zhang S, Wang R, Zhang X. Identification of Overlapping Community Structure in Complex Networks Using Fuzzy C-means Clustering [ J]. Physica A: Statistical Mechanics and its Applications, 2007, 374(1): 483-490. 2.3 基于非负矩阵分解的重叠社团发现算法 Zhang S, Wang R S, Zhang X S. Uncovering Fuzzy Community Structure in Complex Networks[J]. Phys Rev E, 2007, 76(4):046103. 2.4 基于种子扩展思想的重叠社团发现算法 Lancichinetti A, Fortunato S, Kertesz J. Detecting the Overlapping andHierarchical Community Structure in Complex Networks[J]. New Journal of Physics, 2009, 11:033015. 2.5 基于混合概率模型的重叠社团发现 NewmanME, Leicht EA. MixtureModels and ExploratoryAnalysis in Networks[J]. Proc Natl Acad Sci USA, 2007, 104(23): 9564-9569. 2.6 基于边聚类的重叠社团发现 （1）EvansT,Lambiotte R.Line Graphs,LinkPartitions, and Overlapping Communities[J]. Physical Review E, 2009, 80(1): 16105. （2）Ahn Y Y, Bagrow J P, Lehmann S. Link Communities Reveal Multiscale Complexity in Networks[J]. Nature, 2010, 466: 761-764. CNM算法
复杂网络理论研究状况综述
■现代管理科学■2010年第9期 一、复杂网络概述 1.复杂网络演化过程。用网络的观点描述客观世界起源于1736年德国数学家欧拉Eular使用图论解决哥尼斯堡七桥问题。数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的欧几里德格网，它看起来像是格子体恤衫上的花纹；又如最近邻环网，它总是会让你想到一群手牵着手、围着篝火跳圆圈舞的姑娘。也就是说网络中任意两个节点之间的联系遵循既定的规则。用得最多的规则网络是由N个节点组成的环状网络，网络中每个节点只与它最近的K个节点连接。规则网络的特点就是：每个节点的近邻数目都相同。但是对于大规模网络而言由于其复杂性并不能完全用规则网络来表示。 到了20世纪50年代末，Erdos&Renyi想出了一种新的构造网络的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决定。这是一种完全随机的网络模型，数学家把这样生成的网络叫做随机网络。随机网络ER模型的描述如下：给定网络节点总数N，网络中任意两个节点以概率P连接，生成的网络全体记为G（N，P），构成一个概率空间。由于网络中连线数目是一个随机变量X，取值可以从0到N（N-1）/2。随机网络在接下来的40年里一直被很多科学家认为是描述真实系统最适宜的网络。 规则网络和随机网络是两种极端的情况，随着信息技术的飞速发展，科学家们发现对于大量真实的网络系统而言，他们既不是规则网络，也不是随机网络，而是介于两者之间，具有与前两者皆不同的统计特征的一种复杂网络。1998年，Watts&Strogatz提出了W-S网络模型，通过以概率p切断规则网络中原始的边并随机选择新的端点重新连接，构造出一种介于规则网络和随机网络之间的网络—— —小世界网络（Small-world Networks）。显然，当p=0时，相当于各边未动，还是规则网络；当p=1时就成了随机网络。1999年，Barabasi&Albert在Science上发表文章指出，许多实际的复杂网络的连接度分布具有幂律函数形式，由于幂律分布没有明显的可度量特征，该类网络又被称为无标度网络。 2.复杂网络的统计性质。复杂网络的不同的统计性质决定了不同的网络内部结构，而结构又决定了系统的功能。所以，我们先了解一下复杂网络的相关统计性质。 （1）度及度分布。在网络中，节点的度是与目标节点相连的边的条数。即与该节点相邻的节点的数目，朋友的个数。而网络的度