Feedback arcs and node hierarchy in directed networks |
| |
Institution: | 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 |
本文献已被 CNKI 等数据库收录! |
| 点击此处可从《中国物理 B》浏览原始摘要信息 |
| 点击此处可从《中国物理 B》下载免费的PDF全文 |
|