Renormalization flows in complex networks

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

Complex networks have acquired a great popularity in recent years, since the graph representation of many natural, social and technological systems is often very helpful to characterize and model their phenomenology. Additionally, the mathematical tools of statistical physics have proven to be particularly suitable for studying and understanding complex networks. Nevertheless, an important obstacle to this theoretical approach is still represented by the difficulties to draw parallelisms between network science and more traditional aspects of statistical physics. In this paper, we explore the relation between complex networks and a well known topic of statistical physics: renormalization. A general method to analyze renormalization flows of complex networks is introduced. The method can be applied to study any suitable renormalization transformation. Finite-size scaling can be performed on computer-generated networks in order to classify them in universality classes. We also present applications of the method on real networks.

Related collections

Most cited references 6

Record: found
Abstract: found
Article: found

Is Open Access

Self-similarity of complex networks

Chaoming Song, Shlomo Havlin, Hernán Makse (2005)

Complex networks have been studied extensively due to their relevance to many real systems as diverse as the World-Wide-Web (WWW), the Internet, energy landscapes, biological and social networks \cite{ab-review,mendes,vespignani,newman,amaral}. A large number of real networks are called ``scale-free'' because they show a power-law distribution of the number of links per node \cite{ab-review,barabasi1999,faloutsos}. However, it is widely believed that complex networks are not {\it length-scale} invariant or self-similar. This conclusion originates from the ``small-world'' property of these networks, which implies that the number of nodes increases exponentially with the ``diameter'' of the network \cite{erdos,bollobas,milgram,watts}, rather than the power-law relation expected for a self-similar structure. Nevertheless, here we present a novel approach to the analysis of such networks, revealing that their structure is indeed self-similar. This result is achieved by the application of a renormalization procedure which coarse-grains the system into boxes containing nodes within a given "size". Concurrently, we identify a power-law relation between the number of boxes needed to cover the network and the size of the box defining a finite self-similar exponent. These fundamental properties, which are shown for the WWW, social, cellular and protein-protein interaction networks, help to understand the emergence of the scale-free property in complex networks. They suggest a common self-organization dynamics of diverse networks at different scales into a critical state and in turn bring together previously unrelated fields: the statistical physics of complex networks with renormalization group, fractals and critical phenomena.

0 comments Cited 243 times – based on 0 reviews

Preprint

     Review now

Bookmark

Record: found
Abstract: found
Article: found

Is Open Access

Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model

A Samukhin, S. Dorogovtsev, J. Mendes (2000)

We generalize the Barab\'{a}si--Albert's model of growing networks accounting for initial properties of sites and find exactly the distribution of connectivities of the network \(P(q)\) and the averaged connectivity \(\bar{q}(s,t)\) of a site \(s\) in the instant \(t\) (one site is added per unit of time). At long times \(P(q) \sim q^{-\gamma}\) at \(q \to \infty\) and \(\bar{q}(s,t) \sim (s/t)^{-\beta}\) at \(s/t \to 0\), where the exponent \(\gamma\) varies from 2 to \(\infty\) depending on the initial attractiveness of sites. We show that the relation \(\beta(\gamma-1)=1\) between the exponents is universal.

0 comments Cited 169 times – based on 0 reviews

Preprint

     Review now

Bookmark

Record: found
Abstract: found
Article: found

Is Open Access

Skeleton and fractal scaling in complex networks

K. Goh, D. Kim, B. Kahng … (2005)

We find that the fractal scaling in a class of scale-free networks originates from the underlying tree structure called skeleton, a special type of spanning tree based on the edge betweenness centrality. The fractal skeleton has the property of the critical branching tree. The original fractal networks are viewed as a fractal skeleton dressed with local shortcuts. An in-silico model with both the fractal scaling and the scale-invariance properties is also constructed. The framework of fractal networks is useful in understanding the utility and the redundancy in networked systems.