9
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Random Sequential Renormalization of Networks I: Application to Critical Trees

      Preprint
      , , ,

      Read this article at

      Bookmark
          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

          We introduce the concept of Random Sequential Renormalization (RSR) for arbitrary networks. RSR is a graph renormalization procedure that locally aggregates nodes to produce a coarse grained network. It is analogous to the (quasi-)parallel renormalization schemes introduced by C. Song {\it et al.} (Nature {\bf 433}, 392 (2005)) and studied more recently by F. Radicchi {\it et al.} (Phys. Rev. Lett. {\bf 101}, 148701 (2008)), but much simpler and easier to implement. In this first paper we apply RSR to critical trees and derive analytical results consistent with numerical simulations. Critical trees exhibit three regimes in their evolution under RSR: (i) An initial regime \(N_0^{\nu}\lesssim N<N_0\), where \(N\) is the number of nodes at some step in the renormalization and \(N_0\) is the initial size. RSR in this regime is described by a mean field theory and fluctuations from one realization to another are small. The exponent \(\nu=1/2\) is derived using random walk arguments. The degree distribution becomes broader under successive renormalization -- reaching a power law, \(p_k\sim 1/k^{\gamma}\) with \(\gamma=2\) and a variance that diverges as \(N_0^{1/2}\) at the end of this regime. Both of these results are derived based on a scaling theory. (ii) An intermediate regime for \(N_0^{1/4}\lesssim N \lesssim N_0^{1/2}\), in which hubs develop, and fluctuations between different realizations of the RSR are large. Crossover functions exhibiting finite size scaling, in the critical region \(N\sim N_0^{1/2} \to \infty\), connect the behaviors in the first two regimes. (iii) The last regime, for \(1 \ll N\lesssim N_0^{1/4}\), is characterized by the appearance of star configurations with a central hub surrounded by many leaves. The distribution of sizes where stars first form is found numerically to be a power law up to a cutoff that scales as \(N_0^{\nu_{star}}\) with \(\nu_{star}\approx 1/4\).

          Related collections

          Most cited references7

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          The structure and function of complex networks

          M. Newman (2003)
          Inspired by empirical studies of networked systems such as the Internet, social networks, and biological networks, researchers have in recent years developed a variety of techniques and models to help us understand or predict the behavior of these systems. Here we review developments in this field, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Random graphs with arbitrary degree distributions and their applications

            Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: found
              Is Open Access

              The spread of epidemic disease on networks

              M. Newman (2002)
              The study of social networks, and in particular the spread of disease on networks, has attracted considerable recent attention in the physics community. In this paper, we show that a large class of standard epidemiological models, the so-called susceptible/infective/removed (SIR) models can be solved exactly on a wide variety of networks. In addition to the standard but unrealistic case of fixed infectiveness time and fixed and uncorrelated probability of transmission between all pairs of individuals, we solve cases in which times and probabilities are non-uniform and correlated. We also consider one simple case of an epidemic in a structured population, that of a sexually transmitted disease in a population divided into men and women. We confirm the correctness of our exact solutions with numerical simulations of SIR epidemics on networks.
                Bookmark

                Author and article information

                Journal
                20 September 2010
                2011-03-23
                Article
                10.1103/PhysRevE.83.036110
                1009.3955
                7aa4fe9e-08d6-4897-a0ea-a25cfd6235f4

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                Phys. Rev. E 83, 036110 (2011)
                cond-mat.stat-mech cs.SI physics.soc-ph

                Comments

                Comment on this article