有向社团网络的Laplace特征值谱和同步能力的分析研究.pdf

H J S F X Y X B1 3有有向社团网络的L a p l a c e特征值谱和同步能力的分析研究涂 壕1,黄金珠2,赵雪漪1,黄苗苗1(1.汉江师范学院 数学与计算机科学学院,湖北 十堰 4 4 2 0 0 0;2.十堰市郧阳中学,湖北 十堰 4 4 2 0 0 0)摘 要 网络的L a p l a c e矩阵的特征值谱中包含了网络拓扑结构的丰富信息,在研究网络动力学行为上发挥着重要的作用.现实中网络很多都具有社团结构,甚至还是有向的.以两种典型的有向环状相连的社团网络为例,旨在研究社团个数和社团内节点数的增加对单边和两边相连的有向社团网络的L a p l a c e特征值谱、同步能力和社团显著度的影响.并且,基于主稳定函数方法讨论两种不同的环状有向社团网络的同步能力随着网络规模增大时的变化趋势.关键词 有向社团网络;L a p l a c e特征值;社团结构;同步能力 d o i1 0.1 9 5 7 5/j.c n k i.c n 4 2-1 8 9 2/g 4.2 0 2 3.0 3.0 0 3 中图分类号O 2 3 3,;O 1 5 7.5 文献标识码A 文章编号2 0 9 63 7 3 4(2 0 2 3)0 30 0 1 30 5 复杂网络在我们的日常生活中扮演着很重要的角色,像交通运输网络,电话网、万维网和电力网.1 9 9 8年W a t t s和S t r o g a-t z提出了小世界网络模型1,是一种具有很小的平均路径长度但具有较大的聚类系数网络模型,在现代网络研究中发挥了重要的作用,是现代复杂网络研究理论的基础.随着后来无标度网络模型2,3的提出,更加促进了复杂网络科学的研究进程.自此,复杂网络的理论研究引起了人们的广泛兴趣4,5,6,7,其中一个热点就是对复杂网络的拓扑结构进行刻画.从图 论 角 度 来 看,复 杂 网 络L a p l a c e的谱包含了丰富的网络结构信息,能够帮助我们更加深入理解网络的内在本质属性7.一个典型的例子就是网络的同步能力关键取决于L a p l a c e矩阵的最小非零特征值 及 其 与 最 大 特 征 值 之 比8,9.并 且,L a p l a c e矩阵的特征向量有助于网络社团结构 的 发 现.虽 然 现 在 对 复 杂 网 络 的L a p l a c e矩阵的谱分析有很多,但是大多数都停留在对规则网络或者无向网络.现实世界中很多网络都是没有规则和有向的,甚至呈 现 出 社 团 结 构,对 有 向 社 团 网 络L a p l a c e谱和同步能力的研究是很有必要的.在有向社团网络中,连接的方向包含了很多重要信息,像非对称影响或者信息流动.因此,研究有向社团网络的L a p l a c e特征值谱、同步能力和社团显著度之间的相互影响成为了一项重要的课题.1 网络模型 两种典型的有向环状社团网络5.设网络中有M个社团,每个社团分别有N个节点,社团和社团之间有L条边相连.其中N3,L0是 网 络 的 耦 合 强 度,耦 合 矩 阵L=li()jNN是满足条件jli j=0的拉普拉斯矩阵.H:RnRn为个节点状态变量之间的内部耦合函数(简称内连函数).假设网络中各节点之间的内部耦合关系H(x)完全相同,s(t)为孤立节点的动力学方程s=f(s)的解,基于P e c o r a和C a r r o l l于1 9 9 8年提出的主稳定函数方法的文章6,可以得到当耦合矩阵L为不对称矩阵时,i=-1,主稳定方程为:y=D f()s-+i()()DH s y同样,在无向网络中,主稳定方程可以写为:y=D f()s-DH(s)y值得注意的是,主稳定函数方法是基于节点动力学完全相同的完全同步的线性稳定性分析,但在实际的系统中,网络的节点动力学不一定是完全相同的,达不到理想化的完全同步,更不用说达到严格的完全同步情况.3 有向社团网络的L a p l a c e特征值谱 这里我们给出L a p l a c e矩阵的定义.给定一个有N个顶点m条边的有向图G,假设 网 络 不 存 在 自 环 和 重 边.图G的L a p l a c e矩阵可以定义为:L=-1,(vj,vi)E0,e l s eNj=1jiLi j,j=i这里研究的都是有向网络,因此L(G)可能不对称,并且会存在复数的特征值.因此,我们研究的是特征值谱的实部.将L(G)的所有特征值按照实部由小到大的顺序排列为0=R e()1R e()2 R e(N).3.1单边相连,增加社团内部的节点 考虑到环状节点奇偶性对图1中的单边相连有向网络特征值谱的影响,绘制不同奇数和偶数网络结构的特征值谱图,如图2所示.然后,为了研究网络的同步能力,做 了 网 络 节 点 数 从1到1 0 0过 程 中R e()2和R e()2/R e()N的变化情况,如图3所示.最后,为了研究社团的聚类程度,绘制了有向网络的社团显著度Q5的变化图,如图4所示.在图2a)和图2c)中,随着社团内节点数的偶数增加,最大特征值实部的数值减小,使得社团网络的特征值谱分布的范围逐渐缩小.在图2b)和图2d)中,随着社团内节点数的奇数增加,最大特征值实部减 小 的 先 快 后 慢.在 图3中,网 络 的R e()2和R e()2/R e()N会随着网络内部网络节点数的增大而逐渐减小,最终逼近于0.综合两个特征值的指标,社团个数固定内部节点增加时,网络的同步能力在下降.同时在图4中,社团显著度随社团内部节点数的增加而增加,也就是说社团结构的明显程度随社团内部节点数的增加而逐渐显著.涂 壕,黄金珠,赵雪漪,黄苗苗:有向社团网络的L a p l a c e特征值谱和同步能力的分析研究H J S F X Y X B1 5图2特征值谱和最大特征值的变化趋势图3同步能力的变化图4社团显著度变化3.2 两边相连,增加社团内部的节点 对于图1中两条边相连的有向网络,绘制类似的变化图,如图5,图6,图7.可以得到两条边相连的有向网络的特征值谱和同步能力的边和单边相连的情况有着一样的结论.图5特征值谱和最大特征值的变化趋势图6同步能力的变化图7社团显著度的变化3.3 单边相连,增加社团的个数 研究单边相连有向网络图1的社团个数对特征值谱的影响,绘制L a p l a c e特征值谱及最大特征值的变化趋势图,如图8所示.然后,为了研究网络的同步能力,做了社团个数 从3到4 0过 程 中R e()2和R e()2/R e()N的变化图,如图9所示.最后,为了探究社团的聚类程度,绘制了社团显著度Q的变化图,如图1 0所示.在图8a)中,随着社团个数的增加,特征值谱的总体变化趋势随着节点数m的增加而逐渐平缓.但是,在图8b)中,随着社团个数的增加,最大特征值实部的数值基本上保持不变.在图9中,社团内部的节点数保持不变,增加网络社团数量,网络的R e()2和R e()2/R e()N的值都是随着社团个数的增大而逐渐减小最后趋于0;综合这两个特征值的指标,社团内部节点数固定,增加网络社团个数网络的同步能力下降.同时在图1 0中,社团显著度随社团个数的增加而增加.涂 壕,黄金珠,赵雪漪,黄苗苗:有向社团网络的L a p l a c e特征值谱和同步能力的分析研究H J S F X Y X B1 6图8特征值谱和最大特征值的变化趋势图9同步能力的变化图1 0社团显著度的变化3.4 两边相连,增加社团的个数 对于图1中两条边相连的有向网络,绘制类似的变化图,如图1 1,图1 2,图1 3.可以得到两条边相连的有向网络的特征值谱和同步能力与单边相连的情况有着一样的结论.图1 1特征值谱和最大特征值的变化趋势图1 2同步能力的变化图1 3社团显著度的变化4 两种方式增加相同规模时同步能力比较4.1 单边相连 单边相连的有向网络图1,比较网络规模增大时,两种不同增长方式下的网络同步能力变化趋势.图1 4显示了当网络规模从4 0 0增大到2 0 0 0时,R e()2和R e()2/R e()N的值都迅速变小.固定网络内部节点时,社团个数从2 0增大至1 0 0,以及固定社团个数,社团内部节点数从2 0增大至1 0 0时,两种不同增长方式下的网络同步能力的都在急剧下降.但是固定社团内节点数,增加社团个数时R e()2和R e()2/R e()N的下降趋势比固定社团个数增加社团内部节点数时的R e()2和R e()2/R e()N的下降趋势更快,说明网络的同步能力下降得更快.图1 5显示了当网络规模从4 0 0增大到2 0 0 0时,社团显著度的变化,对于单边相连的有向网络两种增加的方式都会使社团显著度增加,但是增加社团个数m时的社团显著度Q要比增加社团内节点个数n时的社团显著度Q的增加的更快一些.涂 壕,黄金珠,赵雪漪,黄苗苗:有向社团网络的L a p l a c e特征值谱和同步能力的分析研究H J S F X Y X B1 7图1 4同步能力的变化图1 5社团显著度4.2 两边相连情形 对图1中两条边相连的有向网络,作与单边相连的类似变化.图1 6明显发现两变相连的有向网络中两种增长方式的同步能力变化和单边相连时有着同样的结果.图1 6同步能力变化5 小 结 深入的研究有向社团网络L a p l a c e的特征值谱和同步能力,有助于提高对有向社团网络的认识.结果显示,无论是单边相连还是两边相连的有向社团网络,网络的同步能力都是随着网络规模的增加而减小,而且,增加社团的个数对同步能力的影响比增加社团内的节点数的影响更加显著.另外,L a p l a c e特征值谱的分布范围主要受社团的节点个数的影响,基本上不受社团个数的影响.参考文献1W a t t s,D.J.a n dS t r o g a t z,S.H.C o l l e c t i v ed y n a m i c so f“s m a l l-w o r l d”n e t w o r k sJ.N a t u r e,1 9 9 8,3 9 3(6 6 8 4).2B a r a b a s iA L,A l b e r tR:E m e r g e n c eo fS c a l i n gi nR a n d o m N e t w o r k sJ.S c i e n c e,1 9 9 9,2 8 6(5 4 3 9).3B a r a b s iA L,A l b e r tR,J e o n g H.M e a n-f i e l dt h e o r yf o r s c a l e-f r e er a n d o mn e t w o r k sJ.P h y s i c aA,1 9 9 9,2 7 2(1-2).4 郭崇慧,张亮.基于P C A的复杂网络社区结构分析方法J.运筹与管理,2 0 0 8,1 7(0 6).5L a iD,L uH,N a r d i n iC.F i n d i n gc o mm u n i t i e s i nd i r e c t e dn e t w o r k sb yP a g e R a n kr a n d o m w a l ki n d u c e dn e t w o r k e m b e d d i n gJ.P h y s i c a A:S t a t i s t i c a lM e c h a n i c sa n d i t sA p p l i c a t i o n s,2 0 1 0,3 8 9(1 2).6C h e nJ,L uJA.S y n c h r o n i z a t i o np r o c e s s e si nc o m p l e xn e t w o r k sJ.J o u Rna lo ft h e U n i v e r s i t yo fE l e c t r o n i cS c i e n c e a n dT e c h n o l o g yo fC h i n a,2 0 1 2,4 1(1).7 丁连红,孙 斌,时 鹏.知识图谱复杂网络特性的实证研究与分析J.物理学报,2 0 1 9,6 8(1 2).8B r e d e M.N e t w o r k s:A nI n t r o d u c t i o nJ.A r t i f i c i a lL i f e,2 0 1 2,1 8(2).9C h e nG,D u a nZ.N e t w o r ks y n c h r o n i z a b i l i t ya n a l y s i s:Ag r a p h-t h e o r e t i c a p p r o a c hJ.C h a o sA nI n t e r d i s c i p l i n a r yJ o u Rna l o fN o n l i n e a rS c i e n c e,2 0 0 8,1 8(3).【编校:胡军福】O nL apl a c eSpe c t r aa n dSyn c h r o n i z a b i l i tyo fD i r e c t e dC o mm u n i tyN e t w o r k sTU-H a o1,HUANGJ i n-z h u2,Z HAOX u e-y i1,HUANG M i a o-m i a o1(1.S c h o o l o fM a t h sa n dC o m p u t e rS c i e n c e,H a n j i a n gN o r m a lU n i v e r s i t y,S h i y a n4 4 2 0 0 0,C h i n a;2.Y u n y a n gM i d d l eS c h o o l,S h i y a n4 4 2 0 0 0,C h i n a)A b s t r a c t:T h es p e c t r u mo fL a p l a c em a t r i xo f aw o r kc o n t a i n s ag r e a t d e a l o f i n f o r m a t i o na b o u t t h en e t w o r ks t r u c t u r ea n dp l a y sa f u n d a m e n t a l r o l e i nt h ed y n a m i c a l b e h a v i o ro f t h en e t w o r k.T h e r ea r e l o t so f r e a l n e t w o r k s t h a th a v ed i r e c t e dc o mm u n i t ys t r u c t u r e.T h i sp a p e r i n v e s t i g a t e st h eL a p l a c es p e c t r a,s y n c h r o n i z a b i l i t ya n dc o mm u n i t ym o d u l a r i t yo ft w ot y p i c a l d i r e c t e dr i n gc o mm u n i t yn e t w o r k sa n de x p l o r e s t h ee f f e c t o f t h e mi n i n c r e a s i n gt h en u m b e ro f c o mm u n i t i e so r t h en u m b e ro fn o d e si ne a c hc o mm u n i t y.B a s e do nt h e m a s t e rs t a b i l i t yf u n c t i o na p p r o a c h,t h es y n c h r o n i z a b i l i t yo ft w od i f f e r e n t c i r c u l a rd i r e c t e dc o mm u n i t yn e t w o r k s i sd i s c u s s e dw i t ht h e i n c r e a s eo fn e t w o r ks i z e.K eyw o r d s:d i r e c t e dc o mm u n i t yn e t w o r k s;L a p l a c es p e c t r a;c o mm u n i t ym o d u l a r i t y;s y n c h r o n i z a b i l i t y涂 壕,黄金珠,赵雪漪,黄苗苗:有向社团网络的L a p l a c e特征值谱和同步能力的分析研究