复杂网络初探.doc

第24卷2010年

第2期5月

五邑大学学报（自然科学版）JOURNALOFWUYIUNIVERSITY(NaturalScienceEdition)

Vol.24No.2May2010

文章编号：1006-7302（2010）02-0012-01
1

复杂网络初探
吴今培
（五邑大学智能技术与系统研究所，广东江门529020）

摘要：讨论了复杂网络的基本概念，重点介绍了小世界网络和无标度网络，提出了一些值得进一步研究的复杂网络问题.关键词：复杂网络；小世界网络；无标度网络中图分类号：TP393文献标志码：A

AnIntroductiontoComplexNetworks
WUJin-pei
(InstituteofIntelligenceTechnologyandSystem,WuyiUniversity,Jiangmen529020,China)Abstract:Inrecentyears,researchoncomplexnetworkshasarousedgreatinterestsamongresearchersfromdifferentdisciplines.Thispaperbrieflyintroducestheconceptsoncomplexnetworks,especiallythefeaturesofsmall-worldandscale-freenetworks,andproposessomekeyproblemsmeritingfurtherresearch.Keywords:complexnetworks;small-worldnetworks;scale-freenetworks

人类从远古走来，很早就构造出林中路，并且把路构造成网络；在农业社会，人又构造出各种水利网络，通过航海网络，资本主义才遍布全世界；在工业社会，普通的小路被公路、铁路所替代，休闲散步的路被高速公路所淹没，公路和铁路之网覆盖大地；在今天的信息时鞲龉抑铝τ?建设自己的信息高速公路，即新型的信息网路，如今，Internet/www网络已经基本覆盖整个世界.与人们生活息息相关的还有通信网络、电力网络、航空网络、银行网络、商业网络等等.人类把自己生存的世界变成了网络世界，网络越发达、越有效，世界就越小，人的社会性就越得到强化.网络如此广泛、如此重要，人类处在网络的丛林中.如何开辟出一条林中路，揭示网络拓扑结构的形成机制，探索网络的演化规律和整体行为，认识网络内部深奥的动力学特性，挖掘网络展现出的广泛、潜在的应用价值等问题，正引起国内外学术界的高度重视，掀起了复杂网络的研究热潮.

1

复杂网络的表述方式和主要特征度量
复杂网络是指由一个节点集V和一个边集E组成的元组(V,E)，中元素称为节点或顶点V（node

，且E中的每条边li有V的一对节点(u,v)与之对或vertex）E中元素称为边或连线（edge或link），
收稿日期：2009-05-14特约稿作者简介：吴今培（1937—），男，江西吉安人，教授，中南大学、北京航空航天大学博士生导师，研究方向：智能信息处理，E-mail:[e-mail].

2

五邑大学学报（自然科学版）

2010年

应，如果E中任意的节点对(u,v)和(v,u)对应同一条边，则该网络称为无向网络，否则为有向网络；如果E中所有边的长度均为1，即li=1，则称网络为无权网络，否则为加权网络.V中元素个数和
E中元素个数分别称网络的阶（order）和边数（size）.阶和边数都有限的网络称为有限网络或有

限图（finitegraph）.边所连接的节点称为端点（end-vertices），两端点相同的边称为环（loop）.有公共起点并且有公共终点的两条边称为平行边（paralleledges）或重边（multi-edge）.复杂网络结构的宏观特性通常由给定网络G=(V,E)微观量的统计分布或统计平均值来刻画，其主要特征量为度分布、集聚系数和平均路径长度[1].1）度分布（DegreeDistribution）网络节点i的度k为与该节点连接的边的总数目.在不同的网络中度代表不同的含义.如在朋友关系网中，每一个人都是一个节点，两个人若是朋友则他们之间就连一条边，一个节点的度也就是一个人的朋友数.网络中节点的度分布用概率分布函数P(k)表示，其含义为一个任意选择的节点2一种是指数度分布P(k)~e?k，恰好有k条边连接的概率.在目前的网络研究中，种度分布较为常见：即P(k)随着k的增大以指数形式衰减；另一种是幂律分布，即P(k)~k?γ，其中γ称为度指数，不同

γ的网络其动力学性质也不同.
2）集聚系数（ClusteringCoefficient）集聚系数C用来描述网