Renormalization of Complex Networks with Partition Functions

The inherent properties of specific physical systems can be used as metaphors for investigation of the behavior of complex networks. This insight has already been put into practice in previous work, e.g., studying the network evolution in terms of phase transitions of quantum gases or representing distances among nodes as if they were particle energies. This paper shows that the emergence of different structures in complex networks, such as the scale-free and the winner-takes...

The cornerstone of statistical mechanics of complex networks is the idea that the links, and not the nodes, are the effective particles of the system. Here we formulate a mapping between weighted networks and lattice gasses, making the conceptual step forward of interpreting weighted links as particles with a generalised coordinate. This leads to the definition of the grand canonical ensemble of weighted complex networks. We derive exact expressions for the partition function...

We study the statistical behavior under random sequential renormalization(RSR) of several network models including Erd"os R'enyi (ER) graphs, scale-free networks and an annealed model (AM) related to ER graphs. In RSR the network is locally coarse grained by choosing at each renormalization step a node at random and joining it to all its neighbors. Compared to previous (quasi-)parallel renormalization methods [C.Song et.al], RSR allows a more fine-grained analysis of the reno...

Complex networks as the World Wide Web, the web of human sexual contacts or criminal networks often do not have an engineered architecture but instead are self-organized by the actions of a large number of individuals. From these local interactions non-trivial global phenomena can emerge as small-world properties or scale-free degree distributions. A simple model for the evolution of acquaintance networks highlights the essential dynamical ingredients necessary to obtain such...

At the eight-year anniversary of Watts & Strogatz's work on the collective dynamics of small-world networks and seven years after Barabasi & Albert's discovery of scale-free networks, the area of dynamical processes on complex networks is at the forefront of the current research on nonlinear dynamics and complex systems. This volume brings together a selection of original contributions in complementary topics of statistical physics, nonlinear dynamics and biological sciences,...

Physicists study a wide variety of phenomena creating new interdisciplinary research fields by applying theories and methods originally developed in physics in order to solve problems in economics, social science, biology, medicine, technology, etc. In their turn, these different branches of science inspire the invention of new concepts in physics. A basic tool of analysis, in such a context, is the mathematical theory of complexity concerned with the study of complex systems...

In this paper we describe the emergence of scale-free degree distributions from statistical mechanics principles. We define an energy associated to a degree sequence as the logarithm of the number of indistinguishable simple networks it is possible to draw given the degree sequence. Keeping fixed the total number of nodes and links, we show that the energy of scale-free distribution is much higher than the energy associated to the degree sequence of regular random graphs. Thi...

The return-to-origin probability and the first passage time distribution are essential quantities for understanding transport phenomena in diverse systems. The behaviors of these quantities typically depend on the spectral dimension $d_s$. However, it was recently revealed that in scale-free networks these quantities show a crossover between two power-law regimes characterized by $ d_s $ and the so-called hub spectral dimension $d_s^{\textrm{(hub)}}$ due to the heterogeneity ...

Research on generative models is a central project in the emerging field of network science, and it studies how statistical patterns found in real networks could be generated by formal rules. Output from these generative models is then the basis for designing and evaluating computational methods on networks, and for verification and simulation studies. During the last two decades, a variety of models has been proposed with an ultimate goal of achieving comprehensive realism f...

We perform the renormalization-group-like numerical analysis of geographically embedded complex networks on the two-dimensional square lattice. At each step of coarsegraining procedure, the four vertices on each $2 \times 2$ square box are merged to a single vertex, resulting in the coarsegrained system of the smaller sizes. Repetition of the process leads to the observation that the coarsegraining procedure does not alter the qualitative characteristics of the original scale...