Core percolation and the controllability of complex networks

Held by Márton Pósfai (Eötvös University, Budapest)
19.03.2013, 16:00
EW 731

Abstract:
Network science has emerged as a prominent field in complex system research, showing that complexity may arise from the connectivity patterns that underline a system. Structural transitions in networks were extensively studied due to their impact on numerous dynamical processes. Here we study such a transition, the core percolation on complex networks.
The core of a network is defined as a spanned subgraph which remains in the network after the following greedy leaf removal procedure: As long as the network has leaves, i.e. nodes of degree 1, choose an arbitrary leaf and its neighbour, and remove them together with all the adjacent links. Finally, we remove all isolated nodes. For low mean degree the core is small (zero asymptotically), whereas for mean degree larger than a critical value the core covers a finite fraction of all the nodes. We analytically solve the core percolation problem for networks with arbitrary degree distributions. We show that for undirected networks the transition is continuous while for directed networks it is discontinuous (and hybrid) if the in- and out-degree distributions differ.
As an application we use core percolation to explain phenomena related to the controllability of networks. Recent advances in applying control theory to complex networks have o?ered the tools to identify the driver nodes, through which we can achieve full control of a system. These tools predict the existence of multiple control configurations, prompting us to classify each node in a network based on their role in control: a node is critical if a system cannot be controlled without it; intermittent if it acts as a driver node only in some con?gurations; and redundant if it does not play a role in control. We find that above the core percolation threshold networks fall into two classes: (i) either they are in a centralized control mode, being driven by only a tiny fraction of nodes, (ii) or a distributed control mode, when most nodes play some role in controlling the system. We show that the control mode of a network depends on the structure of the emerging core.