Feedback arcs and node hierarchy in directed networks

doi:10.1088/1674-1056/26/7/078901

中国物理B ›› 2017, Vol. 26 ›› Issue (7): 78901-078901.doi: 10.1088/1674-1056/26/7/078901

• INTERDISCIPLINARY PHYSICS AND RELATED AREAS OF SCIENCE AND TECHNOLOGY • 上一篇下一篇

Feedback arcs and node hierarchy in directed networks

Jin-Hua Zhao(赵金华), Hai-Jun Zhou(周海军)

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

收稿日期:2017-05-11 修回日期:2017-05-27 出版日期:2017-07-05 发布日期:2017-07-05
通讯作者: Hai-Jun Zhou E-mail:zhouhj@itp.ac.cn
基金资助:
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".

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

Received:2017-05-11 Revised:2017-05-27 Online:2017-07-05 Published:2017-07-05
Contact: Hai-Jun Zhou E-mail:zhouhj@itp.ac.cn
Supported by:
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".

摘要/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.

关键词: directed graph, feedback arc, hierarchy, message-passing algorithm

Abstract:

Key words: directed graph, feedback arc, hierarchy, message-passing algorithm

中图分类号: (Structures and organization in complex systems)

89.75.Fb

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)

赵金华, 周海军. Feedback arcs and node hierarchy in directed networks[J]. 中国物理B, 2017, 26(7): 78901-078901.

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

参考文献 38

[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

Feedback arcs and node hierarchy in directed networks

Feedback arcs and node hierarchy in directed networks

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

参考文献 38

相关文章 15

Metrics

本文评价

推荐阅读 0

[1]	Yu-Qiang Yuan(袁玉强), Xiao-Yu Wu(武晓昱), and Zhong Du(杜仲). Rogue waves of a (3+1)-dimensional BKP equation[J]. 中国物理B, 2022, 31(12): 120202-120202.
[2]	徐西祥, 郭敏. A note on “Lattice soliton equation hierarchy and associated properties”[J]. 中国物理B, 2019, 28(1): 10202-010202.
[3]	胡晓瑞, 陈勇. Nonlocal symmetries and negative hierarchies related to bilinear Bäcklund transformation[J]. 中国物理B, 2015, 24(3): 30201-030201.
[4]	于发军 . A nonlinear discrete integrable coupling system and its infinite conservation laws[J]. 中国物理B, 2012, 21(11): 110202-110202.
[5]	魏含玉, 夏铁成 . A new generalized fractional Dirac soliton hierarchy and its fractional Hamiltonian structure[J]. 中国物理B, 2012, 21(11): 110203-110203.
[6]	杨红卫, 董焕河, 尹宝树. Nonlinear integrable couplings of a nonlinear Schrödinger–modified Korteweg de Vries hierarchy with self-consistent sources[J]. 中国物理B, 2012, 21(10): 100204-100204.
[7]	于发军. Prolongation structure for nonlinear integrable couplings of a KdV soliton hierarchy[J]. 中国物理B, 2012, 21(1): 10201-010201.
[8]	陶司兴, 王惠, 史会. Binary nonlinearization of the super classical-Boussinesq hierarchy[J]. 中国物理B, 2011, 20(7): 70201-070201.
[9]	李建祯. Reference model based consensus control of second-order multi-agent systems[J]. 中国物理B, 2011, 20(2): 20512-020512.
[10]	李夏苗, 曾明华, 周进, 李科赞. Hierarchy property of traffic networks[J]. 中国物理B, 2010, 19(9): 90510-090510.
[11]	夏铁成. Two new integrable couplings of the soliton hierarchies with self-consistent sources[J]. 中国物理B, 2010, 19(10): 100303-100303.
[12]	杨红卫, 董焕河. Multi-component Harry--Dym hierarchy and its integrable couplings as well as their Hamiltonian structures[J]. 中国物理B, 2009, 18(3): 845-849.
[13]	于发军, 张鸿庆. The multicomponent (2+1)-dimensional Glachette--Johnson (GJ) equation hierarchy and its super-integrable coupling system[J]. 中国物理B, 2008, 17(5): 1574-1580.
[14]	于发军, 李丽. Non-isospectral integrable couplings of Ablowitz--Kaup--Newell--Segur (AKNS) hierarchy with self-consistent sources[J]. 中国物理B, 2008, 17(11): 3965-3973.
[15]	岳超, 张玉峰, 魏媛. Two types of loop algebras and their expanding Lax integrable models[J]. 中国物理B, 2007, 16(3): 588-594.