Search

In this review we establish various connections between complex networks and symmetry. While special types of symmetries (e.g., automorphisms) are studied in detail within discrete mathematics for particular classes of deterministic graphs, the analysis of more general symmetries in real complex networks is far less developed. We argue that real networks, as any entity characterized by imperfections or errors, necessarily require a stochastic notion of invariance. We therefore propose a definition of stochastic symmetry based on graph ensembles and use it to review the main results of network theory from an unusual perspective. The results discussed here and in a companion paper show that stochastic symmetry highlights the most informative topological properties of real networks, even in noisy situations unaccessible to exact techniques. [ABSTRACT FROM AUTHOR]

The interplay between topology and dynamics in complex networks is a fundamental but widely unexplored problem. Here, we study this phenomenon on a prototype model in which the network is shaped by a dynamical variable. We couple the dynamics of the Bak–Sneppen evolution model with the rules of the so-called fitness network model for establishing the topology of a network; each vertex is assigned a ‘fitness’, and the vertex with minimum fitness and its neighbours are updated in each iteration. At the same time, the links between the updated vertices and all other vertices are drawn anew with a fitness-dependent connection probability. We show analytically and numerically that the system self-organizes to a non-trivial state that differs from what is obtained when the two processes are decoupled. A power-law decay of dynamical and topological quantities above a threshold emerges spontaneously, as well as a feedback between different dynamical regimes and the underlying correlation and percolation properties of the network. [ABSTRACT FROM AUTHOR]