x

## 留言板

A spectral coarse graining algorithm based on relative distance

## A spectral coarse graining algorithm based on relative distance

Yang Qing-Lin, Wang Li-Fu, Li Huan, Yu Mu-Zhou
PDF
HTML
• #### Abstract

As a key approach to understanding complex systems (e.g. biological, physical, technological and social systems), the complex networks are ubiquitous in the whole world. Synchronization in complex networks is significant for a more in-depth understanding of the dynamic characteristics of the networks, where tremendous efforts have been devoted to their mechanism and applications in the last two decades. However, many real-world networks consist of hundreds of millions of nodes. Studying the synchronization of such large-scale complex networks often requires solving a huge number of coupled differential equations, which brings great difficulties to both computation and simulation. Recently, a spectral coarse graining approach was proposed to reduce the large-scale network into a smaller one while maintaining the synchronizability of the original network. The absolute distance between the eigenvector components corresponding to the minimum non-zero eigenvalues of the Laplacian matrix is used as a criterion for classifying the nodes without considering the influence of the relative distance between eigenvector components in an original spectral coarse graining method. By analyzing the mechanism of the spectral coarse graining procedure in preserving the synchronizability of complex networks, we prove that the ability of spectral coarse graining to preserve the network synchronizability is related to the relative distance of the eigenvector components corresponding to the merged nodes. Therefore, the original spectral coarse graining algorithm is not satisfactory enough in node clustering. In this paper, we propose an improved spectral coarse graining algorithm based on the relative distance between eigenvector components, in which we consider the relative distance between the components of eigenvectors for the eigenvalues of network coupling matrix while clustering the same or similar nodes in the network, thereby improving the clustering accuracy and maintaining the better synchronizability of the original network. Finally, numerical experiments on networks of ER random, BA scale-free, WS small-world and 27 different types of real-world networks are provided to demonstrate that the proposed algorithm can significantly improve the coarse graining effect of the network compared with the original algorithm. Furthermore, it is found that the networks with obvious clustering structure such as internet, biological, social and cooperative networks have better ability to maintain synchronization after reducing scale by spectral coarse-grained algorithm than the networks of fuzzy clustering structure such as power and chemical networks.

#### References

 [1] Watts D J 2004 Annu. Rev. Sociol. 30 243 [2] Pecora L M, Carroll Y L 1998 Phys. Rev. Lett. 80 2109 [3] Fink K S, Johnson G, Carroll T, Mar D, Pecora L 2000 Phys. Rev. E 61 5080 [4] Wang X F, Chen G R 2002 Int. J. Bifurcat. Chaos 12 187 [5] Belykh I V, Belykh V N 2004 Physica D 195 159 [6] Motter A E, Zhou C S, Kurths J 2005 Phys. Rev. E 71 016116 [7] Nishikawa T, Motter A E 2006 Physica D 224 77 [8] Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93 [9] 朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502 Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502 [10] 孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨 2017 物理学报 66 188901 Sun J, Li X X, Zhang J H, Shen Y Z, Li Y Y 2017 Acta Phys. Sin. 66 188901 [11] Wei J, Wu X Q, Lu J A, Wei X 2017 Europhys. Lett. 120 20005 [12] Chen C, Liu S, Shi X Q, Chaté H, Wu Y L 2017 Nature 542 210 [13] 王宇娟, 涂俐兰, 宋帅, 李宽洋 2018 物理学报 67 050504 Wang Y J, Xu L L, Song S, Li K Y 2018 Acta Phys. Sin. 67 050504 [14] 郑广超, 刘崇新, 王琰 2018 物理学报 67 050502 Zheng G C, Liu C X, Wang Y 2018 Acta Phys. Sin. 67 050502 [15] Shen J, Tang L K 2018 Chin. Phys. B 27 100503 [16] Ma X J, Huang L, Lai Y C, Wang Y, Zheng Z 2008 Chaos 18 043109 [17] Gfeller D, Rios P D L 2007 Phys. Rev. Lett. 99 038701 [18] Gfeller D, Rios P D L 2008 Phys. Rev. Lett. 100 174104 [19] 周建, 贾贞, 李科赞 2017 物理学报 66 060502 Zhou J, Jia Z, Li K Z 2017 Acta Phys. Sin. 66 060502 [20] Chen J, Lu J A, Lu X F, Wu X Q, Chen G R 2013 Commun. Nonlinear Sci. 18 3036 [21] Wang P, Xu S 2017 Physica A 478 168 [22] 郭世泽, 陆哲明 2012 复杂网络基础理论(北京: 科学出版社)第183—187页 Guo S Z, Lu Z M 2012 Complex Network Basic Theory (Beijing: Science Press) pp183-187 (in Chinese) [23] Barabási A L, Albert R 1999 Science 286 509 [24] Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17 [25] Watts D J, Strogatz S H 1998 Nature 393 440 [26] Newman M E J, Watts D J 1999 Phys. Lett. A 263 341 [27] Ahmed N, Rossi R A, Zhou R http://networkrepository.com/index.php [2018-9-14] [28] Kunegis J http://konect.uni-koblenz.de/ [2018-9-14] [29] 罗筱如 2012 硕士学位论文 (重庆: 西南大学) Luo X R 2012 M.S. Thesis (Chongqing:Southwest University) (in Chinese) [30] Ai J, Zhao H, Kathleen M C, Su Z, Li H 2013 Chin. Phys. B 22 078902 [31] Ravasz E, Somera A L, Mongru D A, Oltvai Z N, Barabási A L 2002 Science 297 1551 [32] Xiong F, Wang X M, Cheng J J 2016 Chin. Phys. B 25 108904

#### Cited By

• 图 1  合并节点的过程

Figure 1.  The processing of merging nodes.

图 2  15个节点并为14个节点的两种方案

Figure 2.  Two schemes of merging 15 nodes into 14 nodes.

图 3  采用ISCG与ISCGR算法获得谱粗粒化网络对${\lambda _2}$的保持情况　(a) BA无标度网络; (b) ER随机网络; (c) NW小世界网络

Figure 3.  The maintaining of ${\lambda _2}$ obtained by using ISCG and ISCGR algorithms in coarse graining metwork: (a) BA network; (b) ER network; (c) NW network.

图 4  采用ISCG算法与ISCGR算法获得谱粗粒化网络对${{{\lambda _N}} /{{\lambda _2}}}$的保持情况 (a) BA无标度网络; (b) ER随机网络; (c) NW小世界网络

Figure 4.  The maintaining of ${{{\lambda _N}} /{{\lambda _2}}}$ obtained by using ISCG and ISCGR algorithms in coarse graining metwork: (a) BA network; (b) ER network; (c) NW network.

图 5  分别采用ISCG与ISCGR算法对实际网络进行粗粒化后保持${\lambda _2}$情况的对比图

Figure 5.  The maintaining of ${\lambda _2}$ obtained by using ISCG and ISCGR algorithms for real-world networks in coarse graining network.

•  [1] Watts D J 2004 Annu. Rev. Sociol. 30 243 [2] Pecora L M, Carroll Y L 1998 Phys. Rev. Lett. 80 2109 [3] Fink K S, Johnson G, Carroll T, Mar D, Pecora L 2000 Phys. Rev. E 61 5080 [4] Wang X F, Chen G R 2002 Int. J. Bifurcat. Chaos 12 187 [5] Belykh I V, Belykh V N 2004 Physica D 195 159 [6] Motter A E, Zhou C S, Kurths J 2005 Phys. Rev. E 71 016116 [7] Nishikawa T, Motter A E 2006 Physica D 224 77 [8] Arenas A, Díaz-Guilera A, Kurths J, Moreno Y, Zhou C S 2008 Phys. Rep. 469 93 [9] 朱廷祥, 吴晔, 肖井华 2012 物理学报 61 040502 Zhu T X, Wu Y, Xiao J H 2012 Acta Phys. Sin. 61 040502 [10] 孙娟, 李晓霞, 张金浩, 申玉卓, 李艳雨 2017 物理学报 66 188901 Sun J, Li X X, Zhang J H, Shen Y Z, Li Y Y 2017 Acta Phys. Sin. 66 188901 [11] Wei J, Wu X Q, Lu J A, Wei X 2017 Europhys. Lett. 120 20005 [12] Chen C, Liu S, Shi X Q, Chaté H, Wu Y L 2017 Nature 542 210 [13] 王宇娟, 涂俐兰, 宋帅, 李宽洋 2018 物理学报 67 050504 Wang Y J, Xu L L, Song S, Li K Y 2018 Acta Phys. Sin. 67 050504 [14] 郑广超, 刘崇新, 王琰 2018 物理学报 67 050502 Zheng G C, Liu C X, Wang Y 2018 Acta Phys. Sin. 67 050502 [15] Shen J, Tang L K 2018 Chin. Phys. B 27 100503 [16] Ma X J, Huang L, Lai Y C, Wang Y, Zheng Z 2008 Chaos 18 043109 [17] Gfeller D, Rios P D L 2007 Phys. Rev. Lett. 99 038701 [18] Gfeller D, Rios P D L 2008 Phys. Rev. Lett. 100 174104 [19] 周建, 贾贞, 李科赞 2017 物理学报 66 060502 Zhou J, Jia Z, Li K Z 2017 Acta Phys. Sin. 66 060502 [20] Chen J, Lu J A, Lu X F, Wu X Q, Chen G R 2013 Commun. Nonlinear Sci. 18 3036 [21] Wang P, Xu S 2017 Physica A 478 168 [22] 郭世泽, 陆哲明 2012 复杂网络基础理论(北京: 科学出版社)第183—187页 Guo S Z, Lu Z M 2012 Complex Network Basic Theory (Beijing: Science Press) pp183-187 (in Chinese) [23] Barabási A L, Albert R 1999 Science 286 509 [24] Erdös P, Rényi A 1960 Publ. Math. Inst. Hung. Acad. Sci. 5 17 [25] Watts D J, Strogatz S H 1998 Nature 393 440 [26] Newman M E J, Watts D J 1999 Phys. Lett. A 263 341 [27] Ahmed N, Rossi R A, Zhou R http://networkrepository.com/index.php [2018-9-14] [28] Kunegis J http://konect.uni-koblenz.de/ [2018-9-14] [29] 罗筱如 2012 硕士学位论文 (重庆: 西南大学) Luo X R 2012 M.S. Thesis (Chongqing:Southwest University) (in Chinese) [30] Ai J, Zhao H, Kathleen M C, Su Z, Li H 2013 Chin. Phys. B 22 078902 [31] Ravasz E, Somera A L, Mongru D A, Oltvai Z N, Barabási A L 2002 Science 297 1551 [32] Xiong F, Wang X M, Cheng J J 2016 Chin. Phys. B 25 108904
•  [1] Zhou Jian, Jia Zhen, Li Ke-Zan. Improved algorithm of spectral coarse graining method of complex network. Acta Physica Sinica, 2017, 66(6): 060502. doi: 10.7498/aps.66.060502 [2] Sun Juan, Li Xiao-Xia, Zhang Jin-Hao, Shen Yu-Zhuo, Li Yan-Yu. Synchronizability and eigenvalues of multilayer star networks through unidirectionally coupling. Acta Physica Sinica, 2017, 66(18): 188901. doi: 10.7498/aps.66.188901 [3] Ma Xiao-Juan, Wang Yan, Zheng Zhi-Gang. Effect of leaf nodes on synchronizability of complex networks. Acta Physica Sinica, 2009, 58(7): 4426-4430. doi: 10.7498/aps.58.4426 [4] Wang Dan, Jing Yuan-Wei, Hao Bin-Bin. Effect of weighted scheme on synchronizability based on different network structures. Acta Physica Sinica, 2012, 61(17): 170513. doi: 10.7498/aps.61.170513 [5] Wang Dan, Hao Bin-Bin. A weighted scale-free network model with high clustering and its synchronizability. Acta Physica Sinica, 2013, 62(22): 220506. doi: 10.7498/aps.62.220506 [6] Wang Dan, Jing Yuan-Wei, Hao Bin-Bin. Extended Holme-Kim network model and synchronizability. Acta Physica Sinica, 2012, 61(22): 220511. doi: 10.7498/aps.61.220511 [7] Feng Cong, Zou Yan-Li, Wei Fang-Qiong. Synchronization processes in clustered networks with different inter-cluster couplings. Acta Physica Sinica, 2013, 62(7): 070506. doi: 10.7498/aps.62.070506 [8] Wang Zhen-Hua, Liu Zong-Hua. Partial synchronization in complex networks: Chimera state, remote synchronization, and cluster synchronization. Acta Physica Sinica, 2020, 69(8): 088902. doi: 10.7498/aps.69.20191973 [9] Li Yu-Shan, Lü Ling, Liu Ye, Liu Shuo, Yan Bing-Bing, Chang Huan, Zhou Jia-Nan. Spatiotemporal chaos synchronization of complex networks by Backstepping design. Acta Physica Sinica, 2013, 62(2): 020513. doi: 10.7498/aps.62.020513 [10] Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462 [11] LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504 [12] Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503 [13] Ren Zhuo-Ming, Liu Jian-Guo, Shao Feng, Hu Zhao-Long, Guo Qiang. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Physica Sinica, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902 [14] Zeng Chang-Yan, Sun Mei, Tian Li-Xin. Adaptive-impulsive control for projective synchronization in the drive-response complex network with time-varying coupling. Acta Physica Sinica, 2010, 59(8): 5288-5292. doi: 10.7498/aps.59.5288 [15] Wang Jian-An. Adaptive generalized synchronization between two different complex networks with time-varying delay coupling. Acta Physica Sinica, 2012, 61(2): 020509. doi: 10.7498/aps.61.020509 [16] Yang Pu, Zheng Zhi-Gang. Analysis the convergency speed of estimating the network topology based on the dynamical synchronization. Acta Physica Sinica, 2012, 61(12): 120508. doi: 10.7498/aps.61.120508 [17] Liu Shuang, Lü Ling, Li Gang. Sliding mode tracking synchronization of an uncertain complex network. Acta Physica Sinica, 2012, 61(16): 160507. doi: 10.7498/aps.61.160507 [18] Tan Suo-Yi, Qi Ming-Ze, Wu Jun, Lu Xin. Link predictability of complex network from spectrum perspective. Acta Physica Sinica, 2020, 69(8): 088901. doi: 10.7498/aps.69.20191817 [19] Liang Yi, Wang Xing-Yuan. Pinning chaotic synchronization in complex networks on maximum eigenvalue of low order matrix. Acta Physica Sinica, 2012, 61(3): 038901. doi: 10.7498/aps.61.038901 [20] Liang Yi, Wang Xing-Yuan. Chaotic synchronization in complex networks with delay nodes by non-delay and delay couplings. Acta Physica Sinica, 2013, 62(1): 018901. doi: 10.7498/aps.62.018901
•  Citation:
##### Metrics
• Abstract views:  1013
• Cited By: 0
##### Publishing process
• Received Date:  15 October 2018
• Accepted Date:  14 March 2019
• Available Online:  01 May 2019
• Published Online:  20 May 2019

## A spectral coarse graining algorithm based on relative distance

###### Corresponding author: Wang Li-Fu, wlfk@qq.com;
• School of Control Engineering, Northeastern University at Qinhuangdao, Qinhuangdao 066004, China

Abstract: As a key approach to understanding complex systems (e.g. biological, physical, technological and social systems), the complex networks are ubiquitous in the whole world. Synchronization in complex networks is significant for a more in-depth understanding of the dynamic characteristics of the networks, where tremendous efforts have been devoted to their mechanism and applications in the last two decades. However, many real-world networks consist of hundreds of millions of nodes. Studying the synchronization of such large-scale complex networks often requires solving a huge number of coupled differential equations, which brings great difficulties to both computation and simulation. Recently, a spectral coarse graining approach was proposed to reduce the large-scale network into a smaller one while maintaining the synchronizability of the original network. The absolute distance between the eigenvector components corresponding to the minimum non-zero eigenvalues of the Laplacian matrix is used as a criterion for classifying the nodes without considering the influence of the relative distance between eigenvector components in an original spectral coarse graining method. By analyzing the mechanism of the spectral coarse graining procedure in preserving the synchronizability of complex networks, we prove that the ability of spectral coarse graining to preserve the network synchronizability is related to the relative distance of the eigenvector components corresponding to the merged nodes. Therefore, the original spectral coarse graining algorithm is not satisfactory enough in node clustering. In this paper, we propose an improved spectral coarse graining algorithm based on the relative distance between eigenvector components, in which we consider the relative distance between the components of eigenvectors for the eigenvalues of network coupling matrix while clustering the same or similar nodes in the network, thereby improving the clustering accuracy and maintaining the better synchronizability of the original network. Finally, numerical experiments on networks of ER random, BA scale-free, WS small-world and 27 different types of real-world networks are provided to demonstrate that the proposed algorithm can significantly improve the coarse graining effect of the network compared with the original algorithm. Furthermore, it is found that the networks with obvious clustering structure such as internet, biological, social and cooperative networks have better ability to maintain synchronization after reducing scale by spectral coarse-grained algorithm than the networks of fuzzy clustering structure such as power and chemical networks.

Reference (32)

/