网络集团度的幂律分布
周 涛1
, 肖伟科2
, 任 捷1
,汪秉宏1
(1. 中国科学技术大学近代物理系 ,合肥 230026; 2. 中国科学技术大学天体物理中心 , 合肥 230026)
摘要 :复杂网络的群落结构以及基元 —模块 —网络三级结构对网络的结构和功能
都有重大的影响。本文提出了集团度的概念 ,它是网络节点度的推广 ,可以量化网
络中各阶基元的密度。实证研究显示 ,大量不同领域中抽象出来的网络都具有近
似服从幂律的低阶集团度分布。通过与随机热化后的网络进行比较 ,本文验证了
集团度的幂律分布是独立于幂律度分布之外的真实网络新的统计特性。另外 ,随
着所统计的集团阶数的上升 ,其相应的集团度分布的幂律指数呈现下降的趋势。
关键词 :复杂网络 ;集团度分布 ;无标度特性
中图分类号 : N94
文献标识码 : A
Power2Law Clique2D egree D istr ibution
ZHOU Tao1 , X IAO W ei2ke2 , REN Jie1 , WAN G B ing2hong2
(1. Depeartment ofModern Physics,University of Science and Technology of China, Hefei Anhui 230026, China;
2. Center for A strophysics,University of Science and Technology of China, Hefei Anhui 230026, China)
Abstract: The community and motif2modular2network structures have significant impact on network func2
tion. In this article, we proposed a new measure, namely clique2degree, which is an extension of degree
and can be used to explore the density ofmotifs. The empirical study indicates the extensively existence
of power2law clique2degree distribution, which is an independent character to scale2free p roperty. Moreo2
ver, the power2law exponents decrease with the increasing of clique order.
Key words: complex networks; clique2degree distribution; scale2free property
收稿日期 : 2007 - 05 - 07
基金项目 :国家自然基金重点项目 (10635040) ;中国科学院院长特别基金 ;国家自然基金面上项目 ( 10472116, 70471033)
作者简介 :周涛 (1983 - ) ,男 ,四川成都人 ,中国科学技术大学近代物理系博士研究生。已发表 SC I论文 50余篇 ,他引数百次。主要研究方向
为复杂网络、金融复杂性、时间序列分析、信息系统的集群动力学等。
1 引言
近年来 ,真实网络中小世界效应 [1] 和无标度特性 [2] 的发现激起了物理学界对复杂网络的研究热
潮 [3 - 6] 。在网络中 ,两点间的距离被定义为连接两点的最短路所包含的边的数目 ,把所有节点对的距离求平
均 ,就得到了网络的平均距离 L。另外一个叫做簇系数的参数 ,专门用来衡量网络节点集聚成团的情况。对
于某个节点 ,它的簇系数被定义为它所有相邻节点之间连边的数目占可能的最大连边数目的比例 ,网络的簇
系数 C则是所有节点簇系数的平均值。大量的实证研究表明 ,真实网络几乎都具有小世界效应 [1, 3, 4, 7 ]
,即同
时具备如随机网络般的短的平均距离和如规则网络般的大的簇系数。科学家还发现很多真实网络是无标度
第 4卷第 2期
周 涛 ,等 :网络集团度的幂律分布
的 [2-4 ]
,其节点度分布近似服从幂律 ,即 :
p(k) ～k
-γ
(1)
其中 , k代表节点的度 , p(k)是度为 k的节点数目占网络节点总数的比例。
最近 ,对复杂网络 ,尤其是生物网络深入的实证研究揭示 ,很多真实网络可以看做由密集的功能基元
(motifs)堆砌而成 [8,9] ,这些基元的分布状况可以反映同类网络的整体特征 [ 10 ] ,并且它们的存在对于网络的
功能有不可忽略的影响 [ 11 ] 。通过比较真实网络与随机网络基元的密度可以给出基元的分布状况一个直观
简单的定量化度量 [ 10 ] ,但是这种方法过于粗糙 ,因此仍然受到质疑 [ 12, 13 ] 。本文提出了集团度的概念 ,这个概
念是顶点度概念的推广 ,可以看做量化基元密度的一种尝试。实证研究显示 ,大量真实网络都具有近似幂律
的低阶集团度分布 ,且该特征是独立于网络无标度性的新的统计特性。
2 集团度的基本概念
集团 (clique)这个术语是生物和物理学家讨论网络问题时引入的 [ 11, 14 ] ,其对应的数学概念是完全子图。
也就是说 , m 阶集团是指任意两点都相互连边的 m 个节点构成的子图 ,记做 Km 。显然 , K2 就是一条边 ,而
Km 包含 m (m - 1) /2条边。图 1给出了 K2 到 K5 的示意。节点 x的 m 阶集团度定义为包含 x的不同的 m 阶
集团的数目 ,记做 k
(m )
x
。其中 , k
( 2)
x
与节点 x的度 kx 是等价的 ,因此集团度的概念可以看做节点度的概念的
推广。图 2给出了一个 10个节点的简单网络 ,由于该网络中没有 6阶集团 ,因此所有点的不小于 6阶的集
团度都为零。在表 1中给出了这 10个点的低阶集团度 (2 - 5阶 )的计算结果。
图 1 集团示意图
图 2 网络示例
表 1 图 2所示网络低阶集团度的计算结果
节点号 /集团度
k(2)
k(3)
k(4)
k(5)
1
5
6
4
1
2
4
6
4
1
3
4
6
4
1
4
4
6
4
1
5
7
9
5
1
6
2
0
0
0
7
4
3
1
0
8
3
3
1
0
9
4
3
1
0
10
1
0
0
0
3 真实网络的集团度分布
真实网络按其所代表系统的不同 ,可以粗略
地分为 4类 ,分别是社会网络、技术网络、生物网
络和信息网络 [4] 。本节将选择 4类网络中的典型
代表 ,考察其集团度分布的特征。对于每个网络 ,
我们给出了 2至 5阶的集团度分布 ,其中 2阶集
团度分布就是传统的度分布。图 3～图 8给出了
6个典型的例子 ,它们分别是自主系统层次的计
算机互联网 [ 15 ] ,路由器层次的计算机互联网 [ 16 ] ,
铜绿菌素的新陈代谢网络 [ 17 ] , [ 18 ] ,数学家
合作网 [ 19 ] 和中国科学技术大学朋友关系网络。
其中 , 图 8所示的朋友关系网络是笔者根据中国
