Session D54: Focus Session: Complex and co-evolving networks - Foundations in Complex Networks

Dynamics of Random Graphs with Bounded Degrees

We investigate the dynamic formation of regular random graphs. In our model, we pick a pair of nodes at random and connect them with a link if both of their degrees are smaller than $d$. Starting with a set of isolated nodes, we repeat this linking step until a regular random graph, where all nodes have degree $d$, forms. We view this process as a multivariate aggregation process, and formally solve the evolution equations using the Hamilton-Jacobi formalism. We calculate the nontrivial percolation thresholds for the emergence of the giant component when $d\geq 3$. Also, we estimate the number of steps until the giant component spans the entire system and the total number of steps until the regular random graph forms. These quantities are non self-averaging, namely, they fluctuate from realization to realization even in the thermodynamic limit.   

Influence of Boundary Conditions on Metastable Lifetimes for The Ising Model on the Hyperbolic Plane

Some corals grow in shapes that resemble 3D models of the hyperbolic plane, since this allows them to have greater area for a given growth radius. Each polyp could be represented by an Ising site, with ``feeding'' = ``up'' and ``retracted'' = ``down''. The mechanisms of metastable decay could be interpreted as how the coral as a whole reacts to changing conditions of food availability or predation. Previous studies have shown that there is a spinodal field for the Ising model on a regular lattice in the hyperbolic plane if it is infinite or has periodic or mean-field boundary conditions. This happens because the size of the boundary grows asymptotically at the same rate as the droplet volume, in clear contrast with droplets in the Euclidean plane. Our simulations show, however, that the spinodal field disappears if more physically relevant open boundary conditions are used instead.   

Quantifying the complexity of random Boolean networks

We study two measures of the complexity of spatially extended systems in the context of random Boolean networks. A measure defined by Shalizi et al. for cellular automata, based on a criterion for optimal statistical prediction [1], does not distinguish between the spatial inhomogeneity of the ordered phase and the dynamical inhomogeneity of the disordered phase. A modification in which complexities of individual nodes are calculated yields vanishing complexity values for networks in the ordered and critical regimes and for highly disordered networks, peaking somewhere in the disordered regime. Individual nodes with high complexity are the ones that pass the most information from the past to the future, a quantity that depends in a nontrivial way on both its own Boolean function and the location of the node within the network. \\[4pt] [1] C. R. Shalizi, K. L. Shalizi, and R. Haslinger, Phys. Rev. Lett. 93, 118701 (2004).   

Synchronization in Noisy Networks with Multiple Time Delays

We expand our previous work of uniform time delays in stochastic, linearly-coupled synchronization problems\footnote{D. Hunt, G. Korniss, B.K. Szymanski, Phys. Rev. Lett. \textbf{105}, 068701 (2010)} by including descriptions of networks with multiple delays. Non-uniform time delays can arise when there are multiple sources of delay, e.g. the time to transmit and the time to process information. In this particular two-delay case\footnote{D. Hunt, G. Korniss, B.K. Szymanski, Phys. Lett. A \textbf{375}, 880 (2011)}, the primary limitation on the network to synchronize without any centralized direction does not come from restrictions in the transmission of a node's state to its neighbors; rather it depends on the ability for each node to process and respond to the information about itself in the context of its local environment. Furthermore, given a network's structure, there are optimal transmission delays for which the network remains synchronizable for longer processing delays. As a result, synchronization is not always improved--and in some cases it can be totally destroyed--by minimizing the transmission delays. For special cases we also study the scaling function that quantifies the synchronization of the system. This shows the limitation of synchronization in a noisy network   

Continuous Percolation by Discontinuities

In the very recent article [Science {\bf 333}, 322 (2011)], O. Riordan and L. Warnke, state that (i) {\em any rule based on picking a fixed number of random vertices gives a continuous transition}, and (ii) that therefore {\em explosive percolation is continuous}. It is equally true that certain percolation processes based on picking a fixed number of random vertices are discontinuous. Here we resolve this seeming paradox. We exemplify this by studying an extremal case of a process that is continuous in the sense of Riordan and Warnke but still exhibits infinitely many discontinuous jumps in arbitrary vicinity of the onset of the continuous phase transition. Moreover, we demonstrate analytically that continuity at the phase transition and discontinuity of the percolation process are compatible and generic for certain competitive percolation systems.   

Random Transverse Ising Model on Annealed Complex Networks

In order to shed light on critical phenomena on cuprates, here we propose a stylized model capturing the essential characteristics of the superconducting-insulator transition of a highly dynamical, heterogenous granular material: the Disordered Quantum Tranverse Ising Model (DQTIM) on Annealed Complex Network. We show that when the networks encode for high heterogeneity of the expected degrees described by a power law distribution, the critical temperature for the onset of the supercoducting phase diverges to infinity as the power-law exponent $\gamma$ of the expected degree distribution is less than 3, i.e. $\gamma < 3$. Moreover we investigate the case in which the critical state of the electronic background is triggered by an external parameter $g$ that determines an exponential cutoff in the power law expected degree distribution characterized by an exponent $\gamma$. We find that for $g = g_c$ the critical temperature for the supercondutor-insulator transition has a maximum if $\gamma > 3$ and diverges if $\gamma<3$.   

Dynamical Instability in Boolean Networks as a Percolation Problem

Boolean networks, a widely used model of gene regulatory networks, exhibit a phase transition between a stable regime, in which small perturbations die out, and an unstable regime, in which small perturbations grow exponentially. We show that this phase transition can be mapped onto a static percolation problem which predicts the critical point and the long-time Hamming distance between perturbed and unperturbed systems. The results, which apply to Boolean networks with a broad class of topologies and update functions, are confirmed by numerical simulations.   

Critical Behavior of the Ising Model on Small-world Hanoi Networks

The addition of small-world bonds on hierarchical lattices changes a typical Ising model ferromagnetic phase transition to one of infinite order, referred to as the inverted-Berezinski-Kosterlitz-Thouless transition. We study this shift in phase behavior on Hanoi networks, which are one-dimensional Ising chains connected by small-world bonds that are self-similar and hierarchical in structure [1]. The phase behavior of the Ising model near T$_{c}$ on Hanoi networks is studied using an exact renormalization group and Monte Carlo techniques. We show that compared to the Migdal-Kadanoff hierarchical lattice, Hanoi networks possess characteristics in their thermodynamic densities that are more physical. These densities are studied in detail and the behavior of their critical exponents near T$_{c}$ is described. By introducing a continuous parameter which regulates the strength of small-world bonds in the Hanoi networks, we begin to uncover the essential small-world properties that dictate this change in phase behavior from second- to infinite-order. \\[4pt] [1] S. Boettcher and C.T. Brunson, Phys. Rev. E, \textbf{83}, 021103 (2011)   

Popularity versus similarity in growing networks

Preferential attachment is a powerful mechanism explaining the emergence of scaling in growing networks. If new connections are established preferentially to more popular nodes in a network, then the network is scale-free. Here we show that not only popularity but also similarity is a strong force shaping the network structure and dynamics. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework admits a geometric interpretation, in which preferential attachment emerges from local optimization processes. As opposed to preferential attachment, the optimization framework accurately describes large-scale evolution of technological (Internet), social (web of trust), and biological (E.coli metabolic) networks, predicting the probability of new links in them with a remarkable precision. The developed framework can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.   

Is it really a small world after all

One of the most intriguing revelations in the study of complex networks is the ubiquitous appearance of small worlds, that is networks exhibiting a small, and sometimes even ultra-small, average path length. This suggests that these networks feature globally connected dynamics, where all nodes are affected by all other nodes, given the short distance between them. Nevertheless, empirical data on the dynamics of such networks shows that in practice, such global connectedness is rarely observed. To address this gap between the topology and the observed dynamics of networks we developed the network correlation function method, a framework in which we obtain the patterns of influence between nodes in the network. In simple words we complement the topological description of {\it who is connected to whom}, by the dynamical description of {\it who is affected by whom}. Strikingly, using this method, we find that small world topology tends to avoid global dynamics, while non-small worlds could potentially support it. We test our results on a set of networks from various fields, ranging from social to biological networks, and discuss the implications on the dynamical stability of these systems.   

Metric Structure of Bipartite Networks

Many social, biological and technological systems can be conveniently represented as bipartite networks, consisting of two disjoint sets of elements along with edges connecting only elements from different sets. Many of such systems are characterized by high values of bipartite clustering coefficient. We also find that pairs of elements in these bipartite systems tend to have many common neighbors. We present a natural interpretation of these observations. We suggest that elements of the above bipartite systems exist in underlying metric spaces, such that the observed high clustering is a topological reflection of the triangle inequality, the key property of metric space. We propose a simple stochastic mechanism of formation of bipartite networks embedded in metric spaces. We prove that this mechanism is able to reproduce the observed topological properties of bipartite networks. We also discuss the possibility of constructive embedding of real bipartite systems into metric spaces. In my talk I will overview the concept of hidden metric spaces with respect to both unipartite and bipartite networks. I will also discuss existing methods used to infer hidden metric spaces in real networks and possible applications for bipartite networks.   

Topological features of a fractal model for complex networks

We study the construction and topological features of fractal and non-fractal hierarchical tree-like models generated through an inverse-renormalization growth mechanism with various parameters. These complex networks are characterized by scale-free distribution of connections, clustering coefficient, modular structure, degree correlation and a set of fractal dimensions. We compare the results with analytic expressions and show the dependence of topological properties on growing parameters. Networks with different tendency of hub-hub repulsion are produced and classified in terms of degree correlations. Interloops and intraloops are introduced into growing process to test robustness and stability of networks under attack.   

Control Centrality and Hierarchical Structure in Complex Networks

We introduce the concept of control centrality ($C_{\mathrm{c}}$) to quantify the ability of a single node to control a directed weighted network. We map the control centrality into a combinatorial optimization problem. We calculate the distribution of control centrality for several real networks and find that it is mainly determined by the network's degree distribution. We show that the underlying hierarchical structure of a general directed network plays an important role in determining the distribution of control controllability. We rigorously prove that in directed acyclic graphs, i.e. directed networks without loops, a node's control centrality is uniquely determined by its topological position in the underlying hierarchical structure of the network. Our finding on the relation between control centrality and the hierarchical structure inspires us to design an effective random attack strategy against the controllability of malicious networks, without requiring the detailed knowledge of the network structure. We test our random attack strategy on several real networks and find it is indeed effective and even comparable to those targeted attacks which rely on the detailed knowledge of the network structure.   

A community detection approach to image segmentation and its phases

In this talk, I will discuss ``unsupervised'' image segmentation that relies on phase diagram structure of the community detection method. Specifically, we apply a replica-inference-based community detection method. ``Community detection'' describes the general problem of partitioning a complex system involving many elements into optimally decoupled communities of such elements. In our image segmentation analysis, we invoke a multi-resolution community detection variant to ascertain the overall structure of the image at different resolutions. Information based measures (e.g., the normalized mutual information) are used to determine the significant structures at which ``replicas'' of the systems are strongly correlated. We report on the ``easy'', ``hard'', and ``unsolvable'' phases of the corresponding Potts model at both zero and finite temperatures. The optimal image segmentations are obtained by choosing parameters at the easy phase of the Potts model. The determination of the phase diagram in the analysis of the image segmentation is proved to be highly efficient. We demonstrate in a detailed study of various test cases that our method is fast and accurate and to be especially suited to the detection of camouflaged images.   

Ordinary Percolation with Discontinuous Transitions

We study percolation on hierarchical networks using generating functions and renormalization group techniques. Our exact results show the presence of novel features in these networks including the existence of non-trivial critical points, three distinct regimes in the phase diagram and, most importantly, a discontinuity in the formation of the extensive cluster at a critical point $p_{c}<1$ . At $p_{c}$, the order parameter $P_{\infty}$ describing the probability of any node to be a part of the largest cluster, jumps instantly to a finite value. We present simple examples of small-world networks with various hierarchies of long range bonds, indicating that the presence of discontinuous transitions is generic.\\[4pt] [1] S. Boettcher, V. Singh, and R.M. Ziff. Ordinary Percolation with Discontinuous Transitions. Arxiv preprint arXiv:1110.4288 (2):2 5, 2011.