Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInput graph: the hidden geometry in controlling complex networks
150
0
0.0
(
0
)
Added by
Xizhe Zhang
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The ability to control a complex network towards a desired behavior relies on our understanding of the complex nature of these social and technological networks. The existence of numerous control schemes in a network promotes us to wonder: what is the underlying relationship of all possible input nodes? Here we introduce input graph, a simple geometry that reveals the complex relationship between all control schemes and input nodes. We prove that the node adjacent to an input node in the input graph will appear in another control scheme, and the connected nodes in input graph have the same type in control, which they are either all possible input nodes or not. Furthermore, we find that the giant components emerge in the input graphs of many real networks, which provides a clear topological explanation of bifurcation phenomenon emerging in dense networks and promotes us to design an efficient method to alter the node type in control. The findings provide an insight into control principles of complex networks and offer a general mechanism to design a suitable control scheme for different purposes.
rate research
Read More
Understanding structural controllability of a complex network requires to identify a Minimum Input nodes Set (MIS) of the network. It has been suggested that finding an MIS is equivalent to computing a maximum matching of the network, where the unmatched nodes constitute an MIS. However, maximum matching of a network is often not unique, and finding all MISs may provide deep insights to the controllability of the network. Finding all possible input nodes, which form the union of all MISs, is computationally challenging for large networks. Here we present an efficient enumerative algorithm for the problem. The main idea is to modify a maximum matching algorithm to make it efficient for finding all possible input nodes by computing only one MIS. We rigorously proved the correctness of the new algorithm and evaluated its performance on synthetic and large real networks. The experimental results showed that the new algorithm ran several orders of magnitude faster than the existing method on large real networks.
The sensitivity (i.e. dynamic response) of complex networked systems has not been well understood, making difficult to predict whether new macroscopic dynamic behavior will emerge even if we know exactly how individual nodes behave and how they are coupled. Here we build a framework to quantify the sensitivity of complex networked system of coupled dynamic units. We characterize necessary and sufficient conditions for the emergence of new macroscopic dynamic behavior in the thermodynamic limit. We prove that these conditions are satisfied only for architectures with power-law degree distributions. Surprisingly, we find that highly connected nodes (i.e. hubs) only dominate the sensitivity of the network up to certain critical frequency.
In this paper, we investigate the linear controllability framework for complex networks from a physical point of view. There are three main results. (1) If one applies control signals as determined from the structural controllability theory, there is a high probability that the control energy will diverge. Especially, if a network is deemed controllable using a single driving signal, then most likely the energy will diverge. (2) The energy required for control exhibits a power-law scaling behavior. (3) Applying additional control signals at proper nodes in the network can reduce and optimize the energy cost. We identify the fundamental structures embedded in the network, the longest control chains, which determine the control energy and give rise to the power-scaling behavior. (To our knowledge, this was not reported in any previous work on control of complex networks.) In addition, the issue of control precision is addressed. These results are supported by extensive simulations from model and real networks, physical reasoning, and mathematical analyses. Notes on the submission history of this work: This work started in late 2012. The phenomena of power-law energy scaling and energy divergence with a single controller were discovered in 2013. Strategies to reduce and optimize control energy was articulated and tested in 2013. The senior co-author (YCL) gave talks about these results at several conferences, including the NETSCI 2014 Satellite entitled Controlling Complex Networks on June 2, 2014. The paper was submitted to PNAS in September 2014 and was turned down. It was revised and submitted to PRX in early 2015 and was rejected. After that it was revised and submitted to Nature Communications in May 2015 and again was turned down.
Metabolism is a fascinating cell machinery underlying life and disease and genome-scale reconstructions provide us with a captivating view of its complexity. However, deciphering the relationship between metabolic structure and function remains a major challenge. In particular, turning observed structural regularities into organizing principles underlying systemic functions is a crucial task that can be significantly addressed after endowing complex network representations of metabolism with the notion of geometric distance. Here, we design a cartographic map of metabolic networks by embedding them into a simple geometry that provides a natural explanation for their observed network topology and that codifies node proximity as a measure of hidden structural similarities. We assume a simple and general connectivity law that gives more probability of interaction to metabolite/reaction pairs which are closer in the hidden space. Remarkably, we find an astonishing congruency between the architecture of E. coli and human cell metabolisms and the underlying geometry. In addition, the formalism unveils a backbone-like structure of connected biochemical pathways on the basis of a quantitative cross-talk. Pathways thus acquire a new perspective which challenges their classical view as self-contained functional units.
The fundamental idea of embedding a network in a metric space is rooted in the principle of proximity preservation. Nodes are mapped into points of the space with pairwise distance that reflects their proximity in the network. Popular methods employed in network embedding either rely on implicit approximations of the principle of proximity preservation or implement it by enforcing the geometry of the embedding space, thus hindering geometric properties that networks may spontaneously exhibit. Here, we take advantage of a model-free embedding method explicitly devised for preserving pairwise proximity, and characterize the geometry emerging from the mapping of several networks, both real and synthetic. We show that the learned embedding has simple and intuitive interpretations: the distance of a node from the geometric center is representative for its closeness centrality, and the relative positions of nodes reflect the community structure of the network. Proximity can be preserved in relatively low-dimensional embedding spaces, and the hidden geometry displays optimal performance in guiding greedy navigation regardless of the specific network topology. We finally show that the mapping provides a natural description of contagion processes on networks, with complex spatiotemporal patterns represented by waves propagating from the geometric center to the periphery. The findings deepen our understanding of the model-free hidden geometry of complex networks.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
