Please wait a minute...
Chin. Phys. B, 2017, Vol. 26(7): 078901    DOI: 10.1088/1674-1056/26/7/078901
INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY Prev   Next  

Feedback arcs and node hierarchy in directed networks

Jin-Hua Zhao(赵金华)1,3, Hai-Jun Zhou(周海军)1,2
1 Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China;
2 School of Physical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;
3 Department of Applied Science and Technology, Politecnico di Torino, 10129 Torino, Italy
Abstract  

Directed networks such as gene regulation networks and neural networks are connected by arcs (directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which leads to complex information-processing dynamics in the network and makes it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks.

Keywords:  directed graph      feedback arc      hierarchy      message-passing algorithm  
Received:  11 May 2017      Revised:  27 May 2017      Accepted manuscript online: 
PACS:  89.75.Fb (Structures and organization in complex systems)  
  75.10.Nr (Spin-glass and other random models)  
  87.16.Yc (Regulatory genetic and chemical networks)  
  02.70.Uu (Applications of Monte Carlo methods)  
Fund: 

Project by the National Basic Research Program of China (Grant No.2013CB932804) and the National Natural Science Foundations of China (Grant Nos.11121403 and 11225526).J-H Zhao also acknowledges support by Fondazione CRT under project SIBYL,initiative"La Ricerca dei Talenti".

Corresponding Authors:  Hai-Jun Zhou     E-mail:  zhouhj@itp.ac.cn

Cite this article: 

Jin-Hua Zhao(赵金华), Hai-Jun Zhou(周海军) Feedback arcs and node hierarchy in directed networks 2017 Chin. Phys. B 26 078901

[1] White J G, Southgate E, Thomson J N and Brenner S 1986 Phil. Trans. R. Soc. Lond. B 314 1
[2] Li F, Long T, Lu Y, Ouyang Q and Tang C 2004 Proc. Natl. Acad. Sci. USA 101 4781
[3] Oda K, Matsuoka Y, Funahashi A and Kitano H 2005 Mol. Syst. Biol. 1 2005.0010
[4] Alon U 2007 Nature Rev. Genetics 8 450
[5] Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D and Alon U 2002 Science 298 824
[6] Leicht E A and Newman M E J 2008 Phys. Rev. Lett. 100 118703
[7] Fortunato S 2010 Phys. Rep. 486 75
[8] Tarjan R E 1972 SIAM J. Comput. 1 146
[9] Dorogovtsev S N, Mendes J F F and Samukhin A N 2001 Phys. Rev. E 64 025101(R)
[10] Jeong H, Tombor B, Albert R, Oltvai Z N and Barabási A L 2000 Nature 407 651
[11] Ravasz E, Somera A L, Mongru D A, Oltvai Z N and Barabási A L 2002 Science 297 1551
[12] Lan Y and Mezić I 2011 BMC Syst. Biol. 5 37
[13] Corominas-Murtra B, Goñi J, Solé R V and Rodríguez-Caso C 2013 Proc. Natl. Acad. Sci. USA 110 13316
[14] Domínguez-García V, Pigolotti S and Muñoz M A 2014 Sci. Rep. 4 7497
[15] Fiedler B, Mochizuki A, Kurosawa G and Saito D 2013 J. Dynam. Differ. Equat. 25 563
[16] Xu J and Lan Y 2015 PLoS ONE 10 e0125886
[17] Ispolatov I and Maslov S 2008 BMC Bioinformatics 9 424
[18] Gupte M, Shankar P, Li J, Muthukrishnan S and Iftode L 2011 Proceedings of the twentieth International World Wide Web Conference, March 28–April 01, 2011, Hyderabad, India, p. 557
[19] Ulanowicz R E, Bondavalli C and Egnotovich M S 1998 Network analysis of trophic dynamics in south Florida ecosystem, fy 97$:The Florida Bay ecosystem. Technical report, Chesapeake Biological Laboratory, Solomons, 1998
[20] Liu Y Y Barabśi A L 2016 Rev. Mod. Phys. 88 035006
[21] Eades P and Sugiyama K 1990 J. Information Processing 13 424
[22] Garey M and Johnson D S 1979 Computers and Intractability:A Guide to the Theory of NP-Completeness (San Francisco:Freeman)
[23] Mézard M and Montanari A 2009 Information, Physics, and Computation (New York:Oxford Univ. Press)
[24] Mézard M and Parisi G 2001 Eur. Phys. J. B 20 217
[25] Bayati M, Borgs C, Braunstein A, Chayes J, Ramezanpour R and Zecchina R 2008 Phys. Rev. Lett. 101 037208
[26] Altarelli F, Braunstein A, Dall'Asta L and Zecchina R 2013 J. Stat. Mech.:Theor. Exp. 2013 P09011
[27] Guggiola A and Semerjian G 2015 J. Stat. Phys. 158 300
[28] Zhou H J 2016 J. Stat. Mech.:Theor. Exp. 2016 073303
[29] Kirkpatrick S, Gelatt Jr. C D and Vecchi M P 1983 Science 220 671
[30] Galinier P, Lemamou E and Bouzidi M W 2013 J. Heuristics 19 797
[31] Qin S M and Zhou H J 2014 Eur. Phys. J. B 87 273
[32] Dorogovtsev S N and Mendes J F F 2002 Adv. Phys. 51 1079
[33] Goh K I, Kahng B and Kim D 2001 Phys. Rev. Lett. 87 278701
[34] Pardalos P M, Qian T B and Resende M G C 1998 J. Combin. Optim. 2 399
[35] Leskovec J, Huttenlocher D and Kleinberg J 2010 Proceedings of the 19th International Conference on World Wide Web, April 26-30, 2010, Raleigh, NC, USA, p. 641
[36] Ripeanu M, Foster I and Iamnitchi A 2002 IEEE Internet Comput. 6 50
[37] Mugisha S and Zhou H J 2016 Phys. Rev. E 94 012305
[38] Braunstein A, Dall'Asta L, Semerjian G and Zdeborová L 2016 Proc. Natl. Acad. Sci. USA 113 12368
[1] Rogue waves of a (3+1)-dimensional BKP equation
Yu-Qiang Yuan(袁玉强), Xiao-Yu Wu(武晓昱), and Zhong Du(杜仲). Chin. Phys. B, 2022, 31(12): 120202.
[2] A note on “Lattice soliton equation hierarchy and associated properties”
Xi-Xiang Xu(徐西祥), Min Guo(郭敏). Chin. Phys. B, 2019, 28(1): 010202.
[3] Nonlocal symmetries and negative hierarchies related to bilinear Bäcklund transformation
Hu Xiao-Rui (胡晓瑞), Chen Yong (陈勇). Chin. Phys. B, 2015, 24(3): 030201.
[4] A nonlinear discrete integrable coupling system and its infinite conservation laws
Yu Fa-Jun (于发军 ). Chin. Phys. B, 2012, 21(11): 110202.
[5] A new generalized fractional Dirac soliton hierarchy and its fractional Hamiltonian structure
Wei Han-Yu (魏含玉), Xia Tie-Cheng (夏铁成 ). Chin. Phys. B, 2012, 21(11): 110203.
[6] Nonlinear integrable couplings of a nonlinear Schrödinger–modified Korteweg de Vries hierarchy with self-consistent sources
Yang Hong-Wei (杨红卫), Dong Huan-He (董焕河), Yin Bao-Shu (尹宝树). Chin. Phys. B, 2012, 21(10): 100204.
[7] Prolongation structure for nonlinear integrable couplings of a KdV soliton hierarchy
Yu Fa-Jun(于发军) . Chin. Phys. B, 2012, 21(1): 010201.
[8] Binary nonlinearization of the super classical-Boussinesq hierarchy
Tao Si-Xing(陶司兴), Wang Hui(王惠), and Shi Hui(史会). Chin. Phys. B, 2011, 20(7): 070201.
[9] Reference model based consensus control of second-order multi-agent systems
Li Jian-Zhen(李建祯). Chin. Phys. B, 2011, 20(2): 020512.
[10] Hierarchy property of traffic networks
Li Xia-Miao(李夏苗),Zeng Ming-Hua(曾明华), Zhou Jin(周进), and Li Ke-Zan(李科赞). Chin. Phys. B, 2010, 19(9): 090510.
[11] Two new integrable couplings of the soliton hierarchies with self-consistent sources
Xia Tie-Cheng(夏铁成). Chin. Phys. B, 2010, 19(10): 100303.
[12] Multi-component Harry--Dym hierarchy and its integrable couplings as well as their Hamiltonian structures
Yang Hong-Wei(杨红卫) and Dong Huan-He(董焕河). Chin. Phys. B, 2009, 18(3): 845-849.
[13] The multicomponent (2+1)-dimensional Glachette--Johnson (GJ) equation hierarchy and its super-integrable coupling system
Yu Fa-Jun(于发军) and Zhang Hong-Qing(张鸿庆). Chin. Phys. B, 2008, 17(5): 1574-1580.
[14] Non-isospectral integrable couplings of Ablowitz--Kaup--Newell--Segur (AKNS) hierarchy with self-consistent sources
Yu Fa-Jun (于发军), Li Li (李 丽). Chin. Phys. B, 2008, 17(11): 3965-3973.
[15] Two types of loop algebras and their expanding Lax integrable models
Yue Chao(岳超), Zhang Yu-Feng(张玉峰), and Wei Yuan(魏媛). Chin. Phys. B, 2007, 16(3): 588-594.
No Suggested Reading articles found!