当前位置:首页 >> IT/计算机 >>

二部图模拟对比和无标度二元网模型


第 25卷第 6期 2010年 12月

系 统 工 程 学 报 JOURNAL OF SYSTEM S ENG I EER ING N

V o.l 25 N o 6 . Dec 2010 .

无标度二元网模型
李小强, 张 宁
( 上海理工大学管理学院, 上海 200093)
摘要: 由两类不同主体构成的复杂系统 , 若同类主体间、 异类主体间都存在着相互作用关系, 则该系统可 以用 二元网来抽象描述. 无标度二元 网的网络整体度分布及两类节点 各自的度 分布都服从 幂律分布. 通过构 建无 标度二元网模型, 尝试解释无标 度二元网的 形成机 制. 研 究无标 度二元 网的拓 扑结构 性质发现 , 模 型的不 同 类节点规模比参数及连接概率参数对 网络的平 均最短 路径和 群聚系 数有着 重要影 响. 无 标度二 元网模型 的 最短路径长度较小, 其幂指数变 化范围在 2. 5到 3. 5之间. 关键词: 复杂网络; 无标度; 二元网 中图分类号: N 94; O414. 2 文献标识码: A 文章编号: 1000- 5781( 2010) 06- 0847- 06

Scale free bielem en tal netw ork m odel
LI X iao q iang ZHANG N ing , ( M anage ent Schoo,l University o f Shanghai o f Sc ience and T echno logy Shangha i 200093 Ch in a) m , , A bstract Com plex syste consisted o f t o different type agents for wh ich re latio ns bet een sam e : m w w type agents and betw een different type agents can be describ ed by b ielem ental netw ork T he degree . d istribution of sca le free b ielem enta l ne t ork fo llow s a pow er law distribu tio n and the degree d istri w , bution o f the tw o subnetw ork a lso follow a pow er la d istribut ion respectively To exp la in th e genera w . tion m echan ism o f sca le free b ie le enta l netw ork a m odel is constructed Through stu dy ing the to m . po logy feature it is found that the rat io n o f one type to the other type and the link probab ility of dif , ferent type agen ts have i portant affect io n on the average path leng th and c lu stering coeff icient of m scale free b ielem enta l net ork T he average path le ngth o f scale free b ielem ental netw ork is shorter w . than that of one m ode random net ork and the pow er law ind ices range from 2 5 to 3 5 w , . . . K ey words com plex netw o rks sca le free bie le ental netw ork : ; ; m

0 引



络的出现不仅顺应了现代科技的发展趋势, 而且 反映了在以信息科学为支柱的新世纪中, 各学科 理论及应用交叉、 渗透和融合的发展趋势. 在复杂网络研究中, 人们研究由同质节点构 成的单元网, 还研究由两类不同质节点构成的二 分网. 二分网中同质节点之间没有直接连边, 但通

现实世界中的许多网 络既非完全 随机的网 络, 也非完全规则的网络, 而是具有小世界特性和 无标度特性的网络, 科学家们称具有这些特点的 网络为复杂网络 ( com plex netw orks)
[ 1- 2]

. 复杂网

收稿日期: 2010- 04 - 30; 修订日期: 2010- 09 - 21. 基金项目: 国家自然科 学 基金 资 助项 目 ( 70971089 ) ; 上 海 市 重点 学 科 建设 资 助项 目 ( S30501 ); 上 海市 研 究 生创 新 基金 资 助 项目 ( J CX SL0902 ) . W

#

848 #













第 25卷

过不同方向的投影, 可获得两个由同质节点构成 的单元网络
[ 3]

2) 每个时刻都有 1个新节点随机添加到网络 中, 该节点是 x 类节点的概率为 p x , 带有 m (m n 0 ) 条边, 是 y类节点的概率为 1- p x , 带有 n ( n m 0 ) 条边; 3) 择优连接. 设网络中已存在的 x 类节点集 合为 Vx , y 类节点集合为 Vy , 则新添加到网络中的 x 类节点或按照择优概率 xy ( k i ) 在 Vy 中选择 y 类节点 i与之连接, 或按照择优概率 xx ( k i ) 在 Vx 中选择 x 类节点 i与之相连. 新增加到网络中的 y 类节点或按照择优概率
yx

. 在现实世界中二分网有很多实际
[ 1]

例子和应用, 典型的如 演员合作网络 、 人类性 [ 4] [ 5] [ 6] 关系网络 、 群体兴趣网络 、 图书借阅网络 、 公司董事会成员网络
[ 7- 9]

、 科学家合作网络

[ 10- 13]

等. 事实上, 现实世界中还存在着这样一类网络, 其节点可以划分成两类, 同类节点间也存在着连 接, 比如歌手与听众网络
[ 14- 15]

, 歌手也听其他歌

手的歌, 因此除了大量歌手与听众之间的连接, 歌 手之间也有少量连接; 又比如师生关系网络, 师生 之间有连接, 青年教师读博士, 与导师之间形成教 师与教师之间的连接; 还有在博客网中, 博主与看 客构成的网络也是如此. H ol e等 m
[ 3]

( kj ) 在 Vx 中选择 x 类

节点 j与之连接, 或按照择优概率 yy ( k j ) 在 Vy 中 选择 y 类节点 j与之连接. 择优概率由公式 ( 1) ( 4) 确定
xy

提出了这类网络二分性 ( net ork w

b ip artiv ity) 的概念 ( 网络在多大 程度上近似于二 [ 16 ] 分网 ) , 同时提出了两种计算公式. Gyori等 研 究了网络中奇圈长度, 以及网络最小度与网络二 分性的关 系. Estrada 等 则 运用谱方 法来研究 [ 18] 网络的二分性. 陈宏斌等 将这类网络称为二元 网, 并构建了二元随机网模型. 该模型具有小世界 效应, 却不具备无标度特性, 而现实生活中很多二 元网是具有无标度特性的. 本文利用增长择优机制构建了无标度二元网 模型. 仿真实验表明使用该模型生成的网络具有 幂律度分布, 幂指数变化范围在 2 5到 3 5之间. . . 并发现网络中两类节点规模比及连接概率这两个 参数对网络平均最短路径长度和群聚系数有着重 要影响.
[ 17]

( ki ) =

( 1 - p ) ki
i? V y

!

ki

( 1)

xx

( ki ) =

p ki
i? V x

!k !
pk j

( 2)
i

yx

( kj ) =

( 1 - p ) kj kj
j? Vx

( 3)

yy

( kj ) =

j? Vy

!k

( 4)

j

公式 ( 1)、 2)、 3)、 4) 中, ki 是节点 i 的度数. k j ( ( ( 是节点 j的度数; 分母求和是对有新节点添加的集 合中的所有节点度进行求和.

2

数值实验

1 无标度二元网模型
定义 1 若图 G 的节点集 V ( G ) 可以分成两

根据第 1 节给出的二元 无标度模 型构造算 法, 将模型参数设定 为初始网络为完全二分图, m 0 = 2 n0 = 3 m = n = 2 p x = 0 5 p = 0 4 网 , , , . , . , 络节点总数 N = 100 000 网络演化得到的 x 类子 . 网络节点总数为 50 182, y 类子网络节点总数为 49 818 网络度分布如图 1和图 2所示. 表明两种 , 类型节点各自构成的子网络度分布都服从幂律分 布, 且整个二元网络的度分布也服从幂律分布. 采 用 C lause t等
[ 19]

个非空子集 V1 和 V2, 并且满足 G的边 xy关联的两 个节点 x、 分别 属于这两 个子集, 则图 G 为二 y 分图. 定义 2 由两类不同节点组成的网络 N, 若 其中同类节点间连接概率, 不同于异类节点间的 连接概率, 则称网络 N 为二元网. 无标度二元网的构造算法如下. 1) 初始网络由给定 m 0 个 x 类节点, n 0 个 y类 节点构成, 其中, 异类节点连接概率为 p, 同类节 点连接概率为 1 - p;

提出的幂律拟合的极大似然估计

方法, 计算得到 x 类节点子网络度分布幂指数为 2 92 y 类节点子网络度分布幂指数为 2 86 二元 . 、 . , 网络整体度分布的幂指数为 2 89 所得到的网络 . , 模型是典型的二元无标度网络.

第 6期

李小强等: 无标度二元网模型

#

849 #

100次取平均值, 得到 x 类节点概率度分布的幂指 数 rx , y 类节点概率度分布的幂指数 ry 及网络整体 概率度分布的幂指数 r 实验发现网络整体概率度 . 分布取值在 [ 2 48 3 50] 内变化. 在两类节点规 . , . 模相差大, 而异类连接概率 p 又较大时, 由节点总 数少的一类节点构成的子网络的幂指数较小, 而另 一类节点构成的子网络的幂指数较大, 即 rx 与 ry 的 值差异较大, 最大差异为 1 8左右. 在其他情况下 rx . 与 ry 的值差别不大, 取值范围在 [ 2 0 3 50] 内. . , 3 2 .
( a) x 类节点子网度分布图 ( a) D egree d ist ribu t ion o f vertex set x 图 1 ( b) y类节点子网度分布图 ( b) D eg ree d is tribu t ion of vertex set y

平均最短路径长度及群聚系数

平均最短路径可以对网络的连通性进行很好 的描述. 设网络中两个节点 i 和 j 之间的距离 d ij 为连接这两个节点的最短路径上的边数. 网络中 的平均路径长度 l 定义为任意两个节点之间的距 离的平均值 l=
[ 20]

两个子网络度分布图

F ig. 1 D egree d ist ribu t ion o f th e tw o sub netw ork resp ect ively m 0 = 2 n0 = 2 m = n = 2, p x = 0 5 p = 0. 4 , , . , F ig. 1 D egree d istribut ion of the t o su b n et ork w w m 0 = 2 n0 = 2 m = n = 2, p x = 0 5 p = 0. 4 , , . ,

,即 ( 5)

2 d ij n ( n + 1) !j i?

其中 n为网络的节点数. 群聚系数用来描述网络中节点的群聚情况, 即网络有多紧密. 比如节点 A和节点 B连接, 节点 B与节点 C连接, 那么 A与 C相连的可能性很大. 换一种说法, 如果 B有两个邻接节点 A和 C, 那么 A和 C 很可能彼此相连接. 因为它们都与 B相连. 用拓扑学术语表示就是 ABC 在网络中形成高密 度的三角形, 节点 i 的群聚系数为 Ci = 与点 i相连的三角形的数量 与点 i相连的三元组的数量
[ 20] n i

( 6)

网络的群聚系数 C 定义为所有节点的群聚系
图 2 二元网络整体度分布

数的平均值 C = 1 n

.即
i

F ig. 2 D egree d istribut ion of b ielem en tal n etw ork .

!C

( 7)

3
3 1 .

二元网的结构性质
幂指数

设定网络规模为 200 其他参数分别为 m 0 = , 1 n0 = 3 m = n = 2 初始网络为完全连接网络. , , , 当新增节点为 x 类节点的概率 px 取不同值时, 分 别进行 100 次独立实验, 对获得的平均最短路径 长度和群聚系数取平均值, 得到平均最短路径长 度 d 和群聚系数随异类节点连接概率 p 的变化曲 线如图 3所示. 同样当异类节点连接概率 p取不同 值时, 分别进行 100次独立实验, 对获得的平均最 短路径长度和群聚系数取平均值, 得到平均最短 路径长度和群聚系数随新增节点为 x 类节点的概 率 p x 的变化曲线如图 4所示. 因为平均最短路径

幂律分布始终都是复杂系统研究的重要性质 之一. 自复杂网络无标度特性发现以来, 对于幂律 拟合的问题一直都存在着很多不同的方法. 本节 采用 C lauset等
[ 19 ]

提出的幂律拟合的极大似然估

计方法, 估计不同参数下的网络幂指数. 设定网络规模为 200 其他参数分别为 m 0 = 2 , , n0 = 3 m = n = 2 初始网络为完全连接网络. 在 , , px , p 取不同值时, 分别用极大似然法计算各幂指数

#

850 #













第 25卷

长度和群聚系数都是相对于整个网络而言的, 所 以只要研究 px 在 [ 0 0 5] 内的平均最短路径长 , . 度和群聚系数变化情况, 在 [ 0 5 1] 内平均最短 . , 路径长度和群聚系数的变化情况与 [ 0 0 5] 内 , . 的变化情况是对称的. 有意思的是两个图中的所 有曲线在不同条件下变化很不相同. 因为当模型生成的网络只含一类节点时, 模 型等价于 BA 型, 所以这里不考虑这种情形. 当网 络中只存在一个 x类节点时, 即 m 0 = 1 p x = 0时, , 随着异类节点连接概率 p 的增加, 平均最短路径 长度和群聚系数的变化情况如图 3( a) 所示. 平均 最短路径长度先衰减得较快, 当 p > 0 6后衰减速 . 度较平缓, 最终收敛于 2 其变化范围在 [ 2 0 3 5] , . , 内; 群聚系数是先增长得较快, 当 p > 0 4后增长 . 较平缓, 其 变 化范 围 在 [ 0 024 0 028] 内. 当 . , . px = 0 1时, 平均最短路径长度和群聚系数随 p的 . 增大而减小, 不过减小速度不一样, 如图 3( b ) 所 示. 当 px 较大时, 平均最短路径长度和群聚系数 随 p 的变化而变化的情况如图 3( c)、 d) 所示. 3( 平均最短路径长度随着 p 的增加, 先是减小而后 增加, 转折点大概在 p = 0 7处, 平均最短路径长 . 度取值范围为 [ 3 3 3 8] ; 群聚系数变化趋势呈 . , .

竖 S曲线形式下降, 取值范围为 [ 0 005, 0 050]. . . 图 4给出了在不同的异类节点连接概率 p下, 网 络的平均最短路径长度和群聚系数随 x 类节点产生 概率 px 的变化曲线. 可以看出, 网络的平均最短路径 长度和群聚系数随 p x 的变化并不是单调的. 并且, 在 不同的 p 下有不同的变化规律. 当 p 取值较小时, 网 络的平均最短路径长度和群聚系数随 p x 的增加而增 加; 当 p 取值较大时, 网络的平均最短路径长度依旧 随 px 的增加而增加, 而群聚系数先是急剧减小, 而后 再增加, 其转折点大概在 p x = 0 05处. . 总之, 在图 3中, 当网络中存在两个以上 x 类 节点时, 无论 p x 怎么取值, 群聚系数基本上都是 随着异类节点连接概率 p 的增加而减小; 网络的 平均最短路径长则是在 px 较小时随异类节点连 接概率 p 的增加而单调减小, p 较大时, 先是减小 而后增加. 在图 4中, 无论异类节点连接概率取何 值, 网络的平均 最短路径长度 都是随 px 单调增 加, 而群聚系数随 p x 先单调减小, 之后单调增加. 从这两个图中可以看出, 用无标度二元网络模型 演化生成的网络, 其平均最短路径长度较短, 其值 不超过 3 8 遗憾的是网络的群聚系数却很小, 其 . . 取值大约在 [ 0. 005 0 050] 内. , .

( a) 只有一个 x 类节点 ( a) V ertexset x h as on ly one node

( b) p x = 0 1 . ( b) The gen erate probab il ity of x typ enod e px = 0 1 :

( c) p x = 0 4 . ( c) Th e generat e p robab ility of x typen ode: p x = 0 4 图 3 群聚系数, 其纵坐标在右边 )

( d) p x = 0 5 . ( d) Th e generate p robab i lity of x typen ode: p x = 0 5

网络平均最短路径长度 d和群聚系数 C 随异类节点连接概率 p的变化情况图

( 网络规模为 200 所有曲线都是在 100次实验下取平均值得到的, 实心钻石形曲线为平均最短路径长度, 其纵坐标在左边, 空心圆曲线为 , F ig 3 A verage shortest p ath length d and cluster coefficien t C of the s cale free b ie lem en t netw ork m od e, versus fou r . l d if feren t values of the l ink probab ility p of t o d ifferen t typ es of n odes w

第 6期

李小强等: 无标度二元网模型

#

851 #

( a) p = 0. 2

( b) p = 0 4 .

( c) p = 0 8 . 图 4 群聚系数, 其纵坐标在右边 )

( d) p = 1

网络平均最短路径长度 d 和群聚系数 C 随 x 类节点产生概率 p x 的变化情况图

( 网络规模为 200 所有曲线都是在 100次实验下取平均值得到的, 实心钻石形曲线为平均最短路径长度, 其纵坐标在左边, 空心圆曲线为 ,

F ig 4 A verage shortest p ath length d and clust er coeff icien t C of the scale free b ielem en t netw ork m od e, l versu s fou r d ifferent va lu es of th e generat ion probab il ity p x o f x type n ode.

4

结束语

产生的网络的平均最短路径长度和群聚系数随异 类节点连接概率 p 及 x 类节点产生概率的变化情 况. 发现网络的平均最短路径长度较短, 其值不超 过 3 8 遗憾的是网络的群聚系数却很小, 其取值 . ; 大概在 [ 0 005 0 050] 内. 希望以后能有方法改 . , . 进模型得到平均最短路径长度短, 而群聚系数较 高的网络, 即具有小世界效应的网络.

二元网普遍存在于真实世界当中, 对二元网 的研究有助于更好地理解真实世界网络. 本文构 建了无标度二元网络模型, 并通过仿真实验验证 其确实具有无标度特性. 同时, 文章分析了该模型 参考文献:

[ 1]W atts D J, Strogatz S H. Co llective dynam ics o f % sm a ll wo rld& netwo rks[ J]. N ature 1998, 393( 6684): 440- 442. , [ 2] Ba rab siA L, A lbert R. Em ergence o f sca ling in rando networks[ J]. Sc ience 1999 286( 5439): 509- 512. m , , [ 3]H o l e P, L iljeros F, Edling C R, et a.l N etwo rk b ipartiv ity[ J]. Phys ica R ev iew E, 2003, 68( 5): 056107. m [ 4] L iljeros F Ed ling C R, Am aral L A N, et a. T he web o f hum an sexual contacts[ J]. N a ture 2001, 411( 6840 ): 907 , l , - 908. [ 5]张 宁. 群体兴趣网的 统计特性研究 [ J]. 上海理工大 学学报, 2008, 30( 3): 243- 248 . Z hang N ing S tatistica l character istics study on the g roup interest netwo rks[ J]. Journal of U niversity o f Shangha i fo r Science . and T echno logy 2008, 30( 3): 243- 248. ( in Ch inese) , [ 6]李楠楠, 张 宁. 图书馆借阅网的二部图研究 [ J]. 复杂系统与复杂性科学, 2009, 6( 2): 33- 39. L iN annan Zhang N ing The study o f the bipa rtite g raph about the library lending ne t ork[ J]. Co plex Syste s and Com , . w m m plex ity Sc ience 2009, 6( 2): 33- 39. ( in Chinese) , [ 7]M ar io lis P Interlock ing directorates and contro l o f co rporations[ J]. Soc ia l Sc ience Q uarter ly 1975, 56( 1): 425- 439. . , [ 8] D av is G F. The sign ificance of board inter locks for co rporate governance [ J] . Corpo rate G overnance , 154- 159. [ 9] D av is G F, G reve H R. Corporate e lite netw orks and governance changes in the 1980s[ J]. Am erican Journa l o f Soc io logy , 1997 103( 1): 1- 37 , . 1996, 4 ( 3):

#

852 #













第 25卷

[ 10] G ross an JW, Ion P D F On a portion of the w e ll known co llaboration g raph[ J]. Cong ressus, Nume rantium, 1995, 108 m . ( 1): 129- 131. [ 11] Castro R D, G rossm an JW. F a ous tra ils to Paul E rd s[ J]. M athem atica l Inte lligence 1999 21( 3) : 51- 63. m , , [ 12] BatageljV, M rvar A. So e ana ly ses o f E rd s co llaboration graph[ J]. Soc ial N etwo rks 2000, 22( 2): 173- 186. m , [ 13] N ewm an M E J The struc ture of sc ientific co llaboration ne t orks[ J]. P roceedings o f the N ationa l A cade y of Sc iences o f . w m the U SA, 2001 98( 2) : 404- 409 , . [ 14] Lamb io tte R, A usloos M. U ncov ering co llective listen ing hab its and music genres in b ipartite netwo rks[ J]. Phy sica l R e v ie E, 2005 72( 6) : 066107 w , . [ 15] Cano P , Ce l a O, K oppenberge r M, m et a. T opo logy o f m usic recomm enda tion netw orks [ J ]. l Chaos , 2006, 16 ( 1): 013107. [ 16] G y r i E, N ik iforov V, Sche lp R H. N ea rly b ipartite graphs[ J]. D iscre teM athema tics 2003 272( 2): 187- 196. , , [ 17] Estrada E, R odrguez V e lquez JA. Spectralm easures of bipartiv ity in co plex netwo rks[ J]. Physical R ev ie E, 2005, 72 m w ( 4): 046105. [ 18]陈宏斌, 樊 瑛, 方锦清, 等. 二元随机网 [ J]. 物理学报, 2009, 58( 3): 1383- 1390. Chen H ongbin, F an Y ing F ang Jinqing et a.l B ie le enta l rando netw orks[ J]. A cta Physica S inica 2009 58 ( 3): , , m m , , 1383- 1390. ( in Ch inese) [ 19] C lauset A, ShaliziC R, N ewm an M E J P o er law d istr ibu tions in emp irical data[ J] . S I . w AM R ev ie 2009, 51( 4) : 661 w, - 703 . [ 20] N ewm an M E J The struc ture and function o f comp lex netwo rks[ J]. S I . AM R ev iew, 2003 45( 2) : 167- 256 , .

作者简介:
李小强 ( 1985# ), 男, 江西萍乡人, 硕士生, 研究方向: 复杂网络, E ma i: allei1234 163 co l @ . m; 张 宁 ( 1956# ), 女, 江苏 武进 人, 硕 士, 教授, 通讯 作 者, 研 究方 向: 系 统 分析 与 集 成、复杂 网 络 等. Em ai:l zhangning usst edu. @ .


赞助商链接
相关文章:
模块化无标度网络模型的建立与仿真分析毕业设计(论文)
17 3.2.1 模块结构的定义 17 18 20 3.2.2 模块结构的定量描述---Q 函数 3.2.3 模块化无标度网络模型的算法 第四章 BA 模型模块化无标度网络模型...
无标度网络SIS模型传播代码
SIS模型无标度网络的传播matlab代码,包括无标度网络的生成代码;不同传播率得到的最终感染率。(有图有注释) %网络版 function Spreading_in__Networks_SIS2() ...
无标度网络matlab建模
关键词:无标度网络,幂律特性,模型建立 1 引言任何...的随机网络钟形图,但结果出乎他们的意外:万维网基本...但无标 度网络经过模拟,情况却和随机网络截然不同,...
【最新修订版】模块化无标度网络模型的建立与仿真分析...
【最新修订版】模块化无标度网络模型的建立仿真分析毕业论文设计40论文41_工学_高等教育_教育专区。毕业设计,毕业论文,毕业论文设计,硕士论文,研究生论文,单片机...
模块化无标度网络模型的建立与仿真分析毕业论文设计40...
网页 新闻 贴吧 知道 音乐 图片 视频 地图 文库 |...模块化无标度网络模型的建立仿真分析毕业论文设计...17 3.2.1 模块结构的定义 17 18 21 3.2.2 ...
模块化无标度网络模型的建立与仿真分析毕业论文设计40...
模块化无标度网络模型的建立仿真分析毕业论文设计40论文41_工学_高等教育_教育专区。单片机论文,毕业设计,毕业论文,单片机设计,硕士论文,研究生论文,单片机研究论文...
具有高对称性但非小世界的无标度网络
1、引言 在过去的二十年里,特别是小世界和无标度网络,已经被深入调查为复杂的网 络,这期间,巴拉布曼阿尔贝广管局的模型优惠附件已成为标准的机制用来解释出...
复杂网络建模与控制研究报告——BA无标度网络的牵制控制
新闻 网页 贴吧 知道 音乐 图片 视频 地图 百科文库 搜试试 3 帮助 全部 ...5 1.2.4 无标度网络模型......
第五章 图与网络模型及方法
第五章 图与网络模型及方法§1 概论 图论起源于 ...的无序对集合 E (G ) 构成的二元组,记为 G =...2.5 顶点的度 设 v ∈ V (G ) , G 中 v...
无标度网络及MATLAB建模
新闻网页贴吧知道音乐图片视频地图百科文库 ...简介传统的随机网络(如 ER 模型),尽管连接是随机...2.BA无标度网络构成原则 ( 1) 增长: 网络开始于...
更多相关标签: