第六届全国网络科学论坛与第二届全国混沌应用研讨会

Presentation on theme: "第六届全国网络科学论坛与第二届全国混沌应用研讨会"— Presentation transcript:

1 第六届全国网络科学论坛与第二届全国混沌应用研讨会
网络特征值谱与 网络拓扑及同步的关系 陆君安 陈 娟 School of Mathematics and statistics Wuhan University 第六届全国网络科学论坛与第二届全国混沌应用研讨会 北京，2010.7

2 Acknowledgements 感谢香港城市大学陈关荣教授的帮助和支持
感谢国家自然科学基金项目《基于耦合矩阵特征值谱分布的网络拓扑结构与同步动力学关系研究 》（ ）和国家973项目《需求工程—对复杂系统的软件工程的基础研究》（2007CB310800）的资助

3 Abstract 在研究网络拓扑和同步能力时，网络耦合矩阵的特征值谱起到决定性作用。通过对网络特征值谱分布与网络拓扑及同步关系的研究，总结和发现 （1）随机网络和小世界网络的特征值谱分布比较集中，而无标度网络的分布相对较广，社团网络的分布呈现出跳跃 （2）随机、小世界和无标度网络特征值谱与度序列有很高的相关性，可以从度序列入手研究特征值谱，提出基于度序列的特征值谱的局部预估－校正算法

4 Abstract （3）网络中尺度层次的研究有利于揭示同步过程，同步从度大区域开始，不同拓扑结构同步过程是不一样的
（4）不同时间尺度下网络的社团结构是不一样的;社团网络同步过程为：部分同步－聚类同步－完全同步；基于演化过程存在的时间尺度，可以通过同步过程识别网络的社团结构

5 提 纲 1. 网络耦合矩阵特征值谱的几个理论结果 2. 几种典型网络的特征值谱分布 3. 特征值谱与度序列的相关性
提 纲 1. 网络耦合矩阵特征值谱的几个理论结果 2. 几种典型网络的特征值谱分布 3. 特征值谱与度序列的相关性 4. 同步过程与度分布的关系 5. 社团网络特征值谱及其同步过程 6. 结束语

6 Introduction 复杂网络的统计性质已经有许多研究，它们对于认识和刻画网络的特征有着重要的意义。最近文献指出网络局部子图的变化会造成特征值谱和同步性质的很大变化，仅仅利用网络的统计量推断网络动力学性质经常会得到错误的结论，起到决定性的因素是网络耦合矩阵的特征值，但目前研究较少。本文研究几种典型网络的特征值谱分布，特征值谱与度序列相关性，同步演化过程时间尺度和网络拓扑尺度的关系，不同网络特别是社团网络同步过程及与特征值谱的关系

7 1. 网络耦合矩阵的特征值谱的 几个理论结果

8 考虑一个具有N个节点和m条边的图G(V,E).
如果D表示对角元为度其它为0，A表示邻接矩阵，则 图G的Laplacian 矩阵 L=D-A 的元素为 （1） 其中 是节点v的度。当L是对称时，L为半正定，特征值非负， 由于L的行和为0，所以最小特征值 ，对应的特征向量为（1,1,…,1）.当网络是连通的(L不可约)，则

9 注：一些文献定义Normalized Laplacian matrix
这种定义比较复杂，好处：与谱几何、随机过程中的定义一致。 参考：Fan R K Chung, Lectures on Spectral Graph Theory, CHAPTER 1: Eigenvalues and the Laplacian of a graph

10 讨论耗散耦合的连续动力网络 A是负的Laplacian 矩阵，为方便起见都按Laplacian 矩阵特征值讨论 由主稳定函数方法 ，当动力学和内连函数给定，同步化区域分为 类型1网络：同步化区域是半无界的，同步能力由A第二特征值 刻画，它越远离0，其同步能力越强 类型2网络：同步化区域是有界的，同步能力由A的特征值比率 来刻画，它越靠近1，其同步化能力越强 类型3网络：同步化区域为空集

11 因此 和 在刻画同步能力中十分重要。 我们的问题是： 1）如何利用度值对这两个特征值作估计？ 2）除了这两个特征值外，整个特征值谱与网络同步过程有什么关系？ 3）整个特征值谱在刻画网络拓扑结构和动力学过程中起到什么作用？

12 对于无向网络（L对称），假设 和 是L的最大和最小度，则特征值可以由网络节点的度估计[6]
（2） 这是一个著名的估计式，但是比较保守，即使最小度 ，也只能得到 另外 是点的连通度, 是边的连通度

13 [21]给出了网络有环、链等作为子图的特征值估计
注: 有许多估计： 如[16] [17] 其中 表示节点u的所有邻居的平均度 [18] 其中 表示u和v相互是邻居的数目 [19] 其中等号当且仅当 成立 [20] 其中G为二分图或度为（N/2,N/2,1,…,1）的 树时等号成立 [21]给出了网络有环、链等作为子图的特征值估计

14 的下界估计较少 如 其中e是边的连通度, 对于链e=1, 其中D是图的直径

15 邻接矩阵A的谱半径 与平均度的关系[10,14] (3)

16 由（2）得到 （4） 注：由（4）并不能得到度分布比较均匀一定有好的同步性。因为度分布均匀只是统计意义的性质，并不能保证最大和最小度的差很小，只要有一个节点的度很大或者很小，都会使得（4）的右边发生很大变化。一般实际网络， , 很大，所以 很小。 说明：网络局部的度的变化会造成同步性质的很大变化，但是它几乎不影响网络的统计性质（如度分布、平均距离）

17 [6]指出,设无向网络G的节点集V, S V是子集 , V − S是余集，|S| 是S的节点数目
记 表示S和它的余集V − S之间边的权值和. G 的等周数（isoperimetric number） i (G)为 （5） 表示S中每一个节点与它的余集平均边数

18 图论的一个重要结果是i (G) 作为 上界估计
但是计算i (G) 是一个 NP-hard problem .利用这个式子和（5）得到 的重要估计 （6） 其中 ,S可以是任意一个子集。 (6)比 精确 （6）的重要意义： 的界经常由某个子图S的性质所确定，而改变子图对网络的统计性质影响不大，因此仅仅利用网络的统计性质估计 常常失效

19 [6]给出的例子 G的统计量主要依赖H，而第2特征值却依赖S

20 (ii)有小社团：p增加时 保持在 0.021附近 ,而最大特征值有所增加,导致 有所下降。表明尽管长程边在增加,但网络同步能力不会提高
例子 (i)没有小社团：p增加时 也增加 (ii)有小社团：p增加时 保持在 0.021附近 ,而最大特征值有所增加,导致 有所下降。表明尽管长程边在增加,但网络同步能力不会提高 (iV)有小社团时, 利用（6）计算得出 说明估计式(6)并非很保守 (iii)小社团的存在是阻碍同步的 500个节点 小世界NW模型 50个节点 全连接

21 [6]给出的例子 切换前是连通的，切换后不连通 ，不能同步，但是切换前后度分布不变。所以度分布不能确定 和同步性质。

22 小结 分析网络的同步能力时，起到决定性的因素是网络耦合矩阵的特征值谱。
在研究复杂动力网络的控制和同步性质的时候，仅仅利用网络的统计量（度分布和平均距离）不但不能充分刻画网络的动力学性质，而且经常会得到相反的结论。 网络局部子图的变化会造成同步性质的很大变化，但是它几乎不影响网络的统计性质。

23 2. 几种典型网络的特征值谱分布

24 规则网络 全连接网络的特征值，除一个为0外其余均为N 2K(K＝1)规则环状无向网络的特征值： 0， N偶数时最大和最小非零特征值分别为4和
0, 链状无向网络的特征值： 星形无向网络的特征值： 0, 1,…,1, 和 N.

25 随机网络 Fig 1. 不同p的特征值分布（N=1000,50次平均） 表明：随机网络随p的增加，特征值分布的范围迅速缩小（注：全连接网络的特征值，除一个为0外其余均为N）

26 随机网络 Fig 2. 近似地线性依赖于p （N=1000,50次平均）
当 p = 0.005， p < pc. 这时第2特征值＝0（有孤立块）。当p = 0.01,第2特征值=1.4512,特征值比为0.0610,当p= 0.1,第2特征值= ,特征值比为 当p 接近1时, 网络几乎是全连通,特征值比几乎为1.因此从统计角度看,当p增加时同步能力是提高的

27 随机网络第2特征值的一个算法：由于 近似地线性依赖p。当固定N时，如果已知 ,可估计
Fig 3.计算随机网络第2特征值的相对误差 随机网络第2特征值的一个算法：由于 近似地线性依赖p。当固定N时，如果已知 ,可估计 只要选 ,例如 ,能保证连通性.从Fig 3可见,在 时相对误差非常小

28 小世界网络 Fig 4. N=500，p=0.005的特征值谱的分布 表明：小世界网络的特征值谱分布跨度较小，比较均匀，谱密度较一致。
（NW小世界网络模型） Fig 4. N=500，p=0.005的特征值谱的分布 表明：小世界网络的特征值谱分布跨度较小，比较均匀，谱密度较一致。

29 小世界网络 Fig 5. 随p的增加特征值的分布（N=1000） 表明：小世界网络接近随机网络，随p的增加，特征值分布的范围缩小

30 小世界网络 Fig 6. 随p的增加 及 的变化规律图（21次平均） 表明：随着p的增大，小世界网络的同步能力从统计角度看是增强的。

31 无标度网络 Fig 7.无标度网络特征值分布(N=1000, 3次平均) 无标度网络的特征值分布极不均匀, 谱密度不一致。
( N=1000, m0=5, m=3) Fig 7.无标度网络特征值分布(N=1000, 3次平均) 无标度网络的特征值分布极不均匀, 谱密度不一致。 特征值谱 后面大的特征值表明hubs的存在

32 小世界与无标度网络特征值分布比较 Fig 8. 小世界网络与无标度网络特征值谱的对比图 ( N=500)
表明：小世界网络特征值分布跨度小，比较集中，谱密度较一致；而无标度网络特征值分布跨度大，大多数较小的特征值比较集中，同时有一些很大的特征值存在，谱密度很不均匀。

33 小世界网络与随机网络的比较 Fig 9.小世界网络与随机网络的特征值谱的对比图
( N=500，p＝0.005 的NW模型;p=0.005的ER随机模型) 随机网络特征值分布跨度比小世界网络更小，更集中， 谱密度更一致

34 小结 随机网络谱分布跨度最小, 小世界网络其次, 无标度网络谱分布跨度大, 而且大多数较小的特征值比较集中, 也存在一些很大的特征值. 造成上述差异的原因: 度分布的差异,而度分布与谱分布相关(第3节) 随机网络和小世界网络随p的增加特征值分布范围迅速缩小，从统计角度看，当p增加时同步能力是提高的 少量的长程连接对2K规则网络的Laplace矩阵的结构改变很小，但是对矩阵的特征值谱影响很大，长程连接有利于同步能力提高

35 3. 特征值谱与度序列的相关性

36 最近文献【13】研究了Laplace耦合矩阵特征值谱与度序列的关系，给出一个很有用的估计式：特征值谱关于度序列的相对误差为
其中 按非降排序。 意义：对于一般的网络，由于度的差异性， 是很小的。特别对于无标度网络，由于Hubs的存在， 是非常小的（尤其在N非常大时）

37 [13]BA网络 [13]ER网络 上面：N,mo和m给定,2000次的相对误差 上面：N和p给定,2000次的相对误差
下面：特征值与度的相对误差 [13]ER网络 上面：N和p给定,2000次的相对误差 下面：特征值与度的相对误差

38 [13]WS网络 [13]NW网络 上面：N,mo和p给定,2000次的相对误差 下面两幅：特征值与度的相对误差

39 特征值谱与度序列具有很强的相关性 下面定义相对谱和相对度

40 Fig 1. 随机网络（N＝1000，50次平均） （a）相对谱和相对度分布 (b)相对谱和相对度的相关性 表明：相对谱和相对度有很高的相关性

41 Fig 2. 小世界网络（N＝1000，50次平均，p=0.0218） 表明：相对谱和相对度有比较高的相关性 （a）相对谱和相对度分布
(b)相对谱和相对度的相关性 表明：相对谱和相对度有比较高的相关性

42 注：无标度网络相关谱的分布与随机网络和小世界网络的区别,后者几乎线性
Fig 3. 无标度网络（N＝1000，50次平均，m0=m=13） 相对谱和相对度分布 表明：相对谱和相对度的相关性达0.9992 注：无标度网络相关谱的分布与随机网络和小世界网络的区别,后者几乎线性

43 在相对谱和相对度的相关性基础上，建立特征值谱的局部预估－校正算法：
预估：已知 以及度序列，计算 校正：已知 ，计算 的近似值

44 Fig 4.局部预估－校正算法的精度（N＝1000，50次平均）
相对误差0.3263％ 不足：局部性，只能已知 计算

45 小结 随机网络、小世界网络和无标度网络特征值谱与度序列有很强的相关性，特别是无标度网络 提出特征值谱的局部预估－校正算法，由于实际网络很大，特征值计算非常困难，而网络的度序列是容易得到的，因此算法是有意义的

46 4. 同步过程与度分布的关系

47 复杂网络可以在不同层次用不同尺度去刻画 目前小尺度层次和大尺度层次研究得比较清楚， 可是中尺度层次的属性，很多都还没有搞清楚， 存在着巨大的挑战 目前主要集中在给定拓扑结构和动力学后判断 网络能否达到同步，至于同步过程的很少研究。 事实上，从中尺度层次看不同的拓扑结构同步 过程是不一样的。 网络中尺度层次的研究有利于揭示同步过程

48 有关工作 [1] A Arenas, A Diaz-Guilera, C J. Perez-Vicente， Synchronization processes in complex networks，Physica D 224 (2006) 27–34 [2] J Gomez-Gardenes, Y Moreno, and A Arenas，Paths to Synchronization on Complex Networks，PRL 98, (2007) [3] S G Guan, X G Wang, X F Gong，K Li and C.-H. Lai，The development of generalized synchronization on complex networks， Chaos 19, （2009） [4] J Chen, J A Lu, X Q Wu, and W X Zheng, Generalized synchronization of complex dynamical networks via impulsive control, CHAOS 19, (2009) [5] H Liu , J Chen, J A Lu, M Cao，Generalized synchronization in complex dynamical networks via adaptive couplings ,Physica A ,2010,389 :

49 振子模型 全局序参数r刻画同步程度 局部序参数刻画同步边所占比例
注：这两个序参数和后面的GC和 Nc的引入是网络中尺度层次研究的关键 ※ J Gomez-Gardenes, Y Moreno, and A Arenas，Paths to Synchronization on Complex Networks，PRL 98, (2007)

50 Fig 1. ER和SF网络的同步与耦合强度 的关系

51 Fig 2. ER和SF网络的同步与耦合强度 的关系
GC：最大同步块包含的节点数目 Nc:同步块的数目

52 ER: 多块小团－相互连接 ，完全同步所需时间比SF短 SF: 以Hubs为中心凝聚，边缘点影响同步时间
Fig 3.不同耦合强度的同步结构 ER: 多块小团－相互连接 ，完全同步所需时间比SF短 SF: 以Hubs为中心凝聚，边缘点影响同步时间

53 Pgc(k)表示度为k的节点属于最大同步块的概率 左上角：即使耦合强度小，度大的节点Pgc(k)仍然大
Fig 4.SF网络同步从度大的区域开始 Pgc(k)表示度为k的节点属于最大同步块的概率 左上角：即使耦合强度小，度大的节点Pgc(k)仍然大 右下角：度小的节点即使耦合强度大Pgc(k)仍然小

54 理论分析：同步是从度大的节点开始 振子方程 线性化（误差方程） 对角化 由于度序列与谱序列的强相关性，所以同步是度大的节点开始

55 (a)按节点度编号（度大编号小）的误差演化图;(b)3个节点的误差演化图 表明：广义同步也是从度大的节点开始。 理论分析：误差方程线性化
Fig 5. BA无标度网络,N＝800,边数为2388 (a)按节点度编号（度大编号小）的误差演化图;(b)3个节点的误差演化图 表明：广义同步也是从度大的节点开始。 理论分析：误差方程线性化 由于 是节点i的度，因此广义同步也是从度大的节点开始 ※Juan Chen, Jun-an Lu, Xiaoqun Wu, and Wei Xing Zheng，Generalized synchronization of complex dynamical networks via impulsive control, CHAOS 19, (2009) ※ Hui Liu , Juan Chen, Jun-an Lu, Ming Cao，Generalized synchronization in complex dynamical networks via adaptive couplings ,Physica A ,2010,389 :

56 Fig 6. NW小世界网络,N＝800,边数为2388 (a)按节点度编号的误差演化图;(b)3个节点的误差演化图 表明：广义同步是从度大的节点开始。 分析原因：同上 比较Fig 5和 Fig 6可见，BA同步的时间长。按照误差小于 0.5分析由于BA网络最大度很大，所以最大度的节点同步时间 只需要0.2，而小的度的节点需要0.9;而NW小世界网络同步时间分别为0.3和0.6，同步时间集中.

57 Fig 7. BA 和NW网络同步过程误差演化图 （a）误差演化图 （b）同步节点的百分比 说明：开始阶段BA同步快，但是达到完全广义同步NW网络所需时间比BA 网络短 原因：度分布的不同，Hubs的作用 与PRL 98, (2007)一致

58 Fig 8. BA网络不同的度脉冲广义同步误差所需时间
表明：度大的节点同步快

59 小结 网络中尺度层次的研究有利于揭示同步过程，同步过程与度分布有关 网络同步从度大的区域开始 ER:多块小团形成－相互连接－完全同步， SF:以Hubs为中心凝聚，边缘点影响同步时间 ER和SF网络的同步与耦合强度的关系 一般ER完全同步所需时间比SF短

60 5. 社团网络特征值谱 及其同步过程

61 Laplace矩阵(行和为0,不可约)最小特征值为0;如果网络具有两个孤立的子图, 则其Laplace矩阵特征值有2个为0, 多个孤立子图情况类推
在实际系统中社团网络是普遍存在的, 所谓社团网络是指网络呈块状结构, 在块的内部连接比较稠密, 块之间连接比较稀疏, 而整个网络是连通的 社团网络是中尺度研究的主要对象 社团网络特征值谱与同步的时间尺度关系 同步过程发现社团结构

62 社团网络特征值谱 Fig 1.两个社团网络特征值谱
（a）两个全连接子图(N＝250)之间随机连接100, 200, 300条边 （b）两个随机子图(N＝250), p＝0.03, 之间随机连接5, 20, 100条边 （c）两个小世界子图(N＝250), p＝0.005, 之间随机连接5, 20, 100条边 （d）两个无标度子图(N＝250, m0=5,m=2), 之间随机连接5, 20, 100条边 谱分布: 第2特征值非0但接近0，第2和第3特征值之间有明显的跳跃,当社团间的边数增加时，跳跃减少

63 社团网络特征值谱 Fig 2. 三个社团网络特征值谱
（a）3个小世界子图(N＝250, p＝0.005), 任意2块之间随机连接5, 20, 80条边 （c）3个无标度子图(N＝250, m0=5,m=2),任意2块之间随机连接5, 20, 80条边 谱分布: 第2和第3特征值非0但接近0，第3和第4特征值之间有明显的跳跃,当社团间的边数增加时，跳跃减少

64 两个社团网络特征值谱 第1特征值0，第2特征值非0但接近0，第2和第3特征值之间有明显的跳跃，而且当社团之间的边数增加时，跳跃减少，社团特征减弱.第二特征向量包含正负两种元素，所有正元素对应的节点属于同一社团，而所有负元素对应的节点则属于另一个社团 由g个社团构成的网络，其第二特征向量中，各个节点对应的元素会属于g个不同的区域

65 例子 假设第二特征向量为 （ ,  , , , ,                            ） 可以看出第二特征向量的元素大致可以分为3块，前 5个为一块，中间7个为另一块，后面7个为第三块，对应网络也可以分为3个社团:节点1－5,节点6－12，节点13-19

66 3个社团网络特征值谱 第2和第3特征值非0但接近0，第3和第4特征值之间有明显的跳跃，而且当社团之间的边数增加时导致第2和第3特征值增加，第3和第4特征值跳跃减少，社团特征减弱. 多个社团网络类似 特征值的跳跃表明网络社团结构的存在 如果有k个社团存在，则有k－1个特征值接近于0，而且第k和k+1个特征值之间有明显的跳跃，以此可以区分社团的个数 社团之间的边数增加时第2特征值提高，同步能力提高

67 社团结构的网络的同步过程 相互联系比较紧密的振子比联系稀疏的振子更容易同步，比较紧密的节点会首先同步，然后依次发生同步，直到最后整个网络达到同步。社团结构的网络过程会在不同的时间段发生。因此，动力学过程就可以揭示网络在不同层次的结构。 为了研究社团网络的同步过程,选Kuramoto 模型

68 当阈值T足够大时，就能够显露出社团结构【7】
振子对之间的相关性的平均值 给定阈值T，定义如下相关性确定是否同步 当阈值T足够大时，就能够显露出社团结构【7】

69 同步过程可以发现网络的社团结构,以及社团的数目
棕色：相关系数1 蓝色：相关系数0 500个节点 小世界NW模型 P=0.01 50个节点 全连接 t=0.025全连接社团内同步 t>0.25秒小世界社团同步,两个社团各自同步 在t>2秒时,整个网络全局同步. 实现全局同步的过程: t<0.02秒 不同步 0.025<t<0.25 部分同步 0.25<t<2 聚类同步(时间尺度造成的，有别于不同节点动力学的聚类同步) t>2 全局同步 Fig 3. 由两个社团组成的网络的同步 演化图 同步过程可以发现网络的社团结构,以及社团的数目

70 Fig 4. 上面两个社团的网络.在同步过程中的社团数目的时间演化图和特征值谱( 分布图)
可以看出: 社团结构在不同的时间尺度下是不一样的. t=0.1时社团数目剧减 从社团数目的时间演化可以发现,这个网络分为两个社团是比较稳定的. 从特征谱可以发现,该网络有一个靠近零的特征值,并且最小非零特征值与次小特征值之间有跳跃,从而有两个社团. 社团数目的演化图和网络的特征值谱在一定程度上一致.

71 Fig 5. 四个社团的网络同步演化图. 由下而上四个社团为:N=30,p=0. 001小世界; N=40, p=0
Fig 5. 四个社团的网络同步演化图.由下而上四个社团为:N=30,p=0.001小世界; N=40, p=0.01小世界;N=80,p=0.1小世界;N=150,p=0.5小世界,每两个社团之间的随机边数为1. 表明（1）p大的社团先同步；（2）部分同步－聚类同步－全局同步；（3）同步过程识别社团结构.

72 利用Kuramoto振子的同步过程发现社团层次
振子对的相关性（同步性） 256个节点分为16块作为第1层次社团，分4块作为第2层次，度为18。 左边13－4 ，右边15－2。13－4是指13条边连接第1层次，4条边连接 第2层次，1条连接网络第2层次外的任意社团。网络13－4表示4个 大的社团容易同步，而15－2表示16个 小的社团容易同步 Alex Arenas, Albert Diaz-Guilera, and Conrad J. Perez-Vicente, Synchronization reveals topological scales in complex network, Phys Rev Lett Mar 24;96(11):

73 利用Kuramoto振子的同步过程发现社团
13-4: 4个社团最稳定,4-5特征值的跳跃最大 15-2: 16个社团最稳定,16-17特征值的跳跃最大

74 利用Kuramoto振子的同步过程发现社团

75 利用Kuramoto振子的同步过程发现社团
Zachary空手道俱乐部网络社团结构的划分

76 社团网络同步过程小结 社团网络是中尺度研究的主要对象 社团结构与同步时间尺度有关,其时间尺度与网络的特征值谱有很大关系 社团网络同步过程：部分同步－聚类同步－完全同步，表示出演化过程的时间尺度 网络的同步过程可以识别社团结构

77 6. 结束语

78 网络科学已经取得丰硕的成果，但是关于网络演化的时间尺度、网络的拓扑尺度以及两者之间的关系方面研究得还很少。整个网络的动力学过程与网络的拓扑尺度有密切的关系，网络同步的时间尺度和稳定性展示了网络的拓扑尺度，而建立这两方面的联系正是网络耦合矩阵特征值谱。 本文从网络耦合矩阵特征值谱入手研究复杂网络，从根本上揭示网络拓扑和动力学的深层次关系。本文的工作还是初步的，还有许多问题有待深入研究。

79 Reference [1] T.Nishikawa.A.E.Motter.Y.-C.Lai,F.C.Hoppensteadt,Heterogeneity in oscillator networks:Are smaller worlds easier to synchronize?,Phys.Rev.Lett.91(2003) [2] H.Hong,B.J.Kim,M.Y.Choi,H.Park,Factors that predict better synchronizability on complex networks,Phys.Rev.E 65(2002)067105 [3] M. di Bernardo, F. Garofalo, F. Sorrentino, Synchronizability of degree correlated networks, cond-mat/ [4] M. Barahona, L.M. Pecora, Synchronization in small-world systems,Phys. Rev. Lett. 89 (5) (2002) [5] H. Hong, M.Y. Choi, B.J. Kim, Synchronization on small-world networks, Phys. Rev. E 69 (2004) [6] F M. Atay, T Biyikoglu, J Jost，Network synchronization: Spectral versus statistical properties ，Physica D 224 (2006) 35–41 [7] A Arenas, A Diaz-Guilera, and C J. Perez-Vicente, Synchronization reveals topological scales in complex network, Phys Rev Lett. 96(11)(2006 ):

80 Reference [8] A Arenas, A Diaz-Guilerab, C J. Perez-Vicente，Synchronization processes in complex networks，Physica D 224 (2006) 27–34 [9] B. Mohar, Graph Laplacians, in: Topics in Algebraic Graph Theory,Cambridge University Press, Cambridge, 2004, pp. 113–136. [10] F.M. Atay, T. Bıyıkoglu, Graph operations and synchronization of complex networks, Phys. Rev. E 72 (2005) [11] T Nishikawaa, A E. Motterb，Maximum performance at minimum cost in network synchronization，Physica D 224 (2006) 77–89 [12] Jesus Gomez-Gardenes,Yamir Moreno,and Alex Arenas，Paths to Synchronization on Complex Networks，Phys.Rev.Lett. 98, (2007) [13] Choujun Zhan, Guanrong Chen, Lam F. Yeung, On the distributions of Laplacian eigenvalues versus node degrees in complex networks,Physica A 389 (2010) [14] Ted G. Lewis,Network Science –Theory and Applications,2009 by John Wiley & Sons

81 Reference [15] Ted M. Fiedler, Algebraic Connectivzty of Graphs, Czechoslovak Mathematical Journal 23 (1973) [16] W. N. Anderson, T. D. Morley, Eigenvalues of the Laplucian of a Graph, Linear and Multilinear Algebra 18 (1985) (Widely circulated in preprint form as University of Maryland technical report TR-71-45, October 1971). [17] R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra and its Applications 285 (1998) [18] O. Rojo, R. Sojo, H. Rojo, An always nontrivial upper bound for Laplacian graph eigenvalues, Linear Algebra and its Applications 312 (2000) [19] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra and its Applications, 197/198 (1994) [20] J. Li, Y. Pan, A note on the second largest eigenvalue of the Laplacian matrix of a graph, Linear and Multilinear Algebra 48 (2000) [21] Z Duan, C Liu, G Chen，Network synchronizability analysis: The theory of subgraphs and complementary graphs, Physica D, 237(7)(2008)

82 欢迎批评指正  Thank You !