The landscape of complex networks: Critical nodes and a hierarchical decomposition

Weinan E (School of Mathematical Sciences and BICMR, Peking University, Beijing, China; Department of Mathematics and Program in Applied and Computational Mathematics, Princeton University, Princeton, New Jersey, U.S.A.)

Lu Jianfeng (Department of Mathematics, Physics, and Chemistry, Duke University, Durham, North Carolina, U.S.A.)

Yao Yuan (School of Mathematical Sciences, Peking University, Beijing, China)

Abstract

Networks have recently emerged as a general tool for data representation in various fields. In the analysis of conformation transition networks in biomolecular dynamics (protein, RNA etc.), it is important to discover major transition bottlenecks which provides clues for drug design. Similarly in the analysis of social networks, it is helpful to identify nodes which act as bridges connecting different communities. Although there have been extensive studies on the community structure of networks, much less has been done about the connection between the communities. Inspired by the classical Morse theory, we introduce a new notion, critical nodes of functions on networks, based on the gradient flow of these functions. Critical nodes of different indices, together with their attraction basins, lead to a hierarchical decomposition of networks. This enables us to define a concise topological landscape of functions on networks. The usefulness of this new concept is illustrated by three examples: two social networks and one protein-ligand binding network. For the social networks, the index-0 critical nodes together with their attraction basins represent the different communities on the network; the index-1 and higher critical nodes play the role of bridges or hubs connecting the different communities. For the protein binding network, the index-0 critical nodes together with their basins explain the major metastable bound and misbound macrostates, while the index-1 and higher critical nodes represent the bottleneck between the misbound to the bound states. Computation of such critical nodes can be performed by a polynomial time algorithm based on recent developments in computational topology. In the non-degenerate case an almost linear time algorithm exists which is scalable for large scale network analysis.

Keywords

network, landscape, critical node, gradient flow, attraction basin, saddle, persistent homology, discrete Morse theory

2010 Mathematics Subject Classification

55Uxx, 62-07, 62P35, 68U05

Full Text (PDF format)

Published 16 April 2014