反向连边在大型分层网络中的影响

Haosen Cao, Bin-Bin Hu, Xiaoyu Mo, Duxin Chen, Jianxi Gao, Ye Yuan, Guanrong Chen, Tamás Vicsek, Xiaohong Guan, Hai-Tao Zhang

工程(英文) ›› 2024, Vol. 36 ›› Issue (5) : 240-249.

PDF(2608 KB)
PDF(2608 KB)
工程(英文) ›› 2024, Vol. 36 ›› Issue (5) : 240-249. DOI: 10.1016/j.eng.2023.06.011
研究论文
Article

反向连边在大型分层网络中的影响

作者信息 +

The Immense Impact of Reverse Edges on Large Hierarchical Networks

Author information +
History +

Highlight

● Propose an efficient algorithm to screen out active reverse edges.

● Quantitively analyze the impact of reverse edge on network synchronization

● A physical model is given to explain the impact machanism

● The algorithm and mechanism are verified by experiments of USVs groups.

Abstract

Hierarchical networks are frequently encountered in animal groups, gene networks, and artificial engineering systems such as multiple robots, unmanned vehicle systems, smart grids, wind farm networks, and so forth. The structure of a large directed hierarchical network is often strongly influenced by reverse edges from lower- to higher-level nodes, such as lagging birds’ howl in a flock or the opinions of lower-level individuals feeding back to higher-level ones in a social group. This study reveals that, for most large-scale real hierarchical networks, the majority of the reverse edges do not affect the synchronization process of the entire network; the synchronization process is influenced only by a small part of these reverse edges along specific paths. More surprisingly, a single effective reverse edge can slow down the synchronization of a huge hierarchical network by over 60%. The effect of such edges depends not on the network size but only on the average in-degree of the involved subnetwork. The overwhelming majority of active reverse edges turn out to have some kind of “bunching” effect on the information flows of hierarchical networks, which slows down synchronization processes. This finding refines the current understanding of the role of reverse edges in many natural, social, and engineering hierarchical networks, which might be beneficial for precisely tuning the synchronization rhythms of these networks. Our study also proposes an effective way to attack a hierarchical network by adding a malicious reverse edge to it and provides some guidance for protecting a network by screening out the specific small proportion of vulnerable nodes.

关键词

同步性 / 大型分层网络 / 反向连边 / 信息流 / 复杂网络

Keywords

Synchronizability / Large hierarchical networks / Reverse edges / Information flows / Complex networks

引用本文

导出引用
Haosen Cao, Bin-Bin Hu, Xiaoyu Mo. 反向连边在大型分层网络中的影响. Engineering. 2024, 36(5): 240-249 https://doi.org/10.1016/j.eng.2023.06.011

参考文献

[1]
S.H. Strogatz. Exploring complex networks. Nature, 410 (6825) ( 2001), pp. 268-276
[2]
E. Schöll. Chaos control sets the pace. Nat Phys, 6 (3) ( 2010), pp. 161-162
[3]
R. Albert, A.L. Barabási. Statistical mechanics of complex networks. Rev Mod Phys, 74 (1) ( 2002), pp. 47-97
[4]
M.E.J. Newman. The structure and function of complex networks. SIAM Rev, 45 (2) ( 2003), pp. 167-256
[5]
J.K. Parrish,L. Edelstein-Keshet. Complexity, pattern, and evolutionary trade-offs in animal aggregation. Science, 284 (5411) ( 1999), pp. 99-101
[6]
T. Vicsek, A. Zafeiris. Collective motion. Phys Rep, 517 (3-4) ( 2012), pp. 71-140
[7]
C.C. Ioannou, V. Guttal, I.D. Couzin. Predatory fish select for coordinated collective motion in virtual prey. Science, 337 (6099) ( 2012), pp. 1212-1215
[8]
H. Weimerskirch, J. Martin, Y. Clerquin, P. Alexandre, S. Jiraskova. Energy saving in flight formation. Nature, 413 (6857) ( 2001), pp. 697-698
[9]
J. Sawicki, I. Omelchenko, A. Zakharova, E. Schöll. Chimera states in complex networks: interplay of fractal topology and delay. Eur Phys J Spec Top, 226 ( 2017), pp. 1883-1892
[10]
T. Nishikawa, A.E. Motter.Synchronization is optimal in nondiagonalizable networks. Phys Rev E, 73 (6) ( 2006), p. 065106
[11]
T. Nishikawa, A.E. Motter. Maximum performance at minimum cost in network synchronization. Physica D, 224 (1-2) ( 2006), pp. 77-89
[12]
F. Sorrentino. Effects of the network structural properties on its controllability. Chaos, 17 (3) ( 2007), p. 033101
[13]
L. Li, Q.S. Jia, H. Wang, R. Yuan, X. Guan. A systematic method for network topology reconfiguration with limited link additions. J Netw Comput Appl, 35 (6) ( 2012), pp. 1979-1989
[14]
A. Pokhilko, A.P. Fernández, K.D. Edwards, M.M. Southern, K.J. Halliday, A.J. Millar.The clock gene circuit in Arabidopsis includes a repressilator with additional feedback loops. Mol Syst Biol, 8 (1) ( 2012), p. 574
[15]
Verma R.Aanalysis of 1996 western American electric blackouts. In: Proceedingsof Bulk Power System Dynamics and Control-VI; 2004 Aug 22-27 ; Cortina d’Ampezzo, Italy; 2004.
[16]
Berizzi A. The Italian 2003 blackout. In: Proceedings of IEEE Power Engineering Society General Meeting; 2004 Jun 6-10 ; Denver, CO, USA; 2004.
[17]
G. Andersson, P. Donalek, R. Farmer, N. Hatziargyriou, I. Kamwa, P. Kundur, et al.. Causes of the 2003 major grid blackouts in North America and Europe, and recommended means to improve system dynamic performance. IEEE Trans Power Syst, 20 (4) ( 2005), pp. 1922-1928
[18]
Y.Y. Liu, J.J. Slotine, A.L. Barabási. Control centrality and hierarchical structure in complex networks. PLoS ONE, 7 (9) ( 2012), p. e44459
[19]
F.L. Iudice, F. Garofalo, P. De Lellis. Bounded partial pinning control of network dynamical systems. IEEE Trans Control Netw Syst, 10 (1) ( 2023), pp. 238-248
[20]
A.K. Das, R. Fierro, V. Kumar, J.P. Ostrowski, J. Spletzer, C.J. Taylor. A vision-based formation control framework. IEEE Trans Robot Autom, 18 (5) ( 2002), pp. 813-825
[21]
H.G. Tanner, G.J. Pappas, V. Kumar. Leader-to-formation stability. IEEE Trans Robot Autom, 20 (3) ( 2004), pp. 443-455
[22]
M. Nagy, Z. Ákos, D. Biro, T. Vicsek. Hierarchical group dynamics in pigeon flocks. Nature, 464 (7290) ( 2010), pp. 890-893
[23]
W. Ding, G. Yan, Z. Lin. Collective motions and formations under pursuit strategies on directed acyclic graphs. Automatica, 46 (1) ( 2010), pp. 174-181
[24]
P. Torres, J.W. van Wingerden, M. Verhaegen. PO-MOESP subspace identification of directed acyclic graphs with unknown topology. Automatica, 53 ( 2015), pp. 60-71
[25]
A.J. King,C. Sueur. Where next? Group coordination and collective decision making by primates. Int J Primatol, 32 ( 2011), pp. 1245-1267
[26]
M. Ashburner, C.A. Ball, J.A. Blake, D. Botstein, H. Butler, J.M. Cherry, et al.. Gene Ontology: tool for the unification of biology. Nat Genet, 25 (1) ( 2000), pp. 25-29
[27]
The Gene Ontology Consortium. Expansion of the Gene Ontology knowledgebase and resources. Nucleic Acids Res, 45 (D1) ( 2017), pp. D331-D338
[28]
M. Cantoni, E. Weyer, Y. Li, S.K. Ooi, I. Mareels, M. Ryan. Control of large-scale irrigation networks. Proc IEEE, 95 (1) ( 2007), pp. 75-91
[29]
Gebraad PMO, van Dam FC, A model-free distributed approach for wind plant control. In: Proceedingsof American Control Conference; Jun 17-19 2013 ; Washington, DC, USA; 2013.
[30]
Yang F, Kang P, Guan X.Distributed economic dispatch for cyber attacked smart grid based on resilient event-triggered consensus. In:Proceedings of 59th IEEE Conference on Decision and Control (CDC); 2020 Dec 14- 18; Jeju, Republic of Korea; 2020.
[31]
Smotherman M, Krishnamurthy S, Aravind PS, Hunnicutt D.Efficient DAG construction and heuristic calculation for instruction scheduling. In:Proceedings of the 24th Annual International Symposium on Microarchitecture; 1991 Nov 18- 20; Albuquerque, NM, USA; 1991.
[32]
R. Horowitz, P. Varaiya. Control design of an automated highway system. Proc IEEE, 88 (7) ( 2000), pp. 913-925
[33]
P.R. Montague, P. Dayan, C. Person, T.J. Sejnowski. Bee foraging in uncertain environments using predictive hebbian learning. Nature, 377 (6551) ( 1995), pp. 725-728
[34]
L. Huelsbergen. Dynamic resolution: a runtime technique for the parallelization of modifications to directed acyclic graphs. Int J Parallel Program, 25 ( 1997), pp. 385-417
[35]
W.M. Johnston, J.R.P. Hanna, R.J. Millar. Advances in dataflow programming languages. ACM Comput Surv, 36 (1) ( 2004), pp. 1-34
[36]
J. Bang-Jensen, G.Z. Gutin. Digraphs: theory, algorithms and applications. Springer, London ( 2009)
[37]
N. Friedman. Inferring cellular networks using probabilistic graphical models. Science, 303 (5659) ( 2004), pp. 799-805
[38]
D. Husmeier, R. Dybowski, S. Roberts. Probabilistic modeling in bioinformatics and medical informatics. Springer, London ( 2005)
[39]
B.M.E. Moret, L. Nakhleh, T. Warnow, C.R. Linder, A. Tholse, A. Padolina, et al.. Phylogenetic networks: modeling, reconstructibility, and accuracy. IEEE/ACM Trans Comput Biol Bioinformatics, 1 (1) ( 2004), pp. 13-23
[40]
C.J. Quinn, T.P. Coleman, N. Kiyavash, N.G. Hatsopoulos. Estimating the directed information to infer causal relationships in ensemble neural spike train recordings. J Comput Neurosci, 30 ( 2011), pp. 17-44
[41]
M.B. Eisen, P.T. Spellman, P.O. Brown, D. Botstein. Cluster analysis and display of genome-wide expression patterns. Proc Natl Acad Sci USA, 95 (25) ( 1998), pp. 14863-14868
[42]
C.W. Granger. Investigating causal relations by econometric models and cross-spectral methods. Econometrica, 37 (3) ( 1969), pp. 424-438
[43]
D. Witthaut, M. Timme.Braess’s paradox in oscillator networks, desynchronization and power outage. New J Phys, 14 (8) ( 2012), p. 083036
[44]
J.E. Cohen, P. Horowitz. Paradoxical behaviour of mechanical and electrical networks. Nature, 352 (6337) ( 1991), pp. 699-701
[45]
K. Ozogány, T. Vicsek. Modeling the emergence of modular leadership hierarchy during the collective motion of herds made of harems. J Stat Phys, 158 (3) ( 2015), pp. 628-646
[46]
I.A. Seres, L. Gulyás, D.A. Nagy, P. Burcsi. Topological analysis of Bitcoin’s lightning network. P. Pardalos, I. Kotsireas, Y. Guo, W. Knottenbelt (Eds.), Mathematical research for blockchain economy, Springer, Cham ( 2020), pp. 1-12
[47]
B. Liu, Z. Chen, H.T. Zhang, X. Wang, T. Geng, H. Su, et al.. Collective dynamics and control for multiple unmanned surface vessels. IEEE Trans Control Syst Technol, 28 (6) ( 2020), pp. 2540-2547
[48]
J.W. Demmel. Applied numerical linear algebra. SIAM, Philadelphia ( 1997)
[49]
J.D. Gibbons, S. Chakraborti. Nonparametric statistical inference. M. Lovric ( Ed.), International encyclopedia of statistical science, Springer, Berlin ( 2014)
[50]
C.J. Calleman. The purposeful universe:how quantum theory and Mayan cosmology explain the origin and evolution of life. Simon and Schuster, New York City ( 2009)
[51]
X. Mo, Z. Chen, H.T. Zhang. Effects of adding a reverse edge across a stem in a directed acyclic graph. Automatica, 103 ( 2019), pp. 254-260
PDF(2608 KB)

Accesses

Citation

Detail

段落导航
相关文章

/