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.
|
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
|
No Suggested Reading articles found! |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
Altmetric
|
blogs
Facebook pages
Wikipedia page
Google+ users
|
Online attention
Altmetric calculates a score based on the online attention an article receives. Each coloured thread in the circle represents a different type of online attention. The number in the centre is the Altmetric score. Social media and mainstream news media are the main sources that calculate the score. Reference managers such as Mendeley are also tracked but do not contribute to the score. Older articles often score higher because they have had more time to get noticed. To account for this, Altmetric has included the context data for other articles of a similar age.
View more on Altmetrics
|
|
|