Blog
About

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

      On local weak limit and subgraph counts for sparse random graphs

      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 use an inequality of Sidorenko to show a general relation between local and global subgraph counts and degree moments for locally weakly convergent sequences of sparse random graphs. This yields an optimal criterion to check when the asymptotic behaviour of graph statistics such as the clustering coefficient and assortativity is determined by the local weak limit. As an application we obtain new facts for several common models of sparse random intersection graphs where the local weak limit, as we see here, is a simple random clique tree corresponding to a certain two-type Galton-Watson branching process.

          Related collections

          Most cited references 13

          • 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: not found
            • Article: not found

            Processes on Unimodular Random Networks

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

              The phase transition in inhomogeneous random graphs

              We introduce a very general model of an inhomogenous random graph with independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p=c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied. We show that under one very weak assumption (that the expected number of edges is `what it should be'), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is `stable': for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n).
                Bookmark

                Author and article information

                Journal
                2015-04-30
                2015-06-02
                Article
                1504.08103

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

                Custom metadata
                math.PR math.CO

                Combinatorics, Probability

                Comments

                Comment on this article