PaperlayerView exact revision on arXiv

Source-linked AI summary

Random graphs containing arbitrary distributions of subgraphs

Brian Karrer, M. E. J. Newman

arXiv:1005.1659v1cond-mat.stat-mechcs.DMphysics.soc-ph

TL;DR

Many real networks contain short loops and other subgraphs that locally tree-like random-graph models do not represent well, while practical models incorporating arbitrary motifs have been limited. This paper builds random-graph models from chosen subgraphs and analyzes their properties, including giant-component thresholds and percolation.

  • Problem

    Many real networks contain triangles and other small subgraphs in excess of chance expectations, but practical random-graph models incorporating significant densities of arbitrary subgraphs have been scarce.

    Source: §I · p. 1

  • Method

    The paper constructs random graphs from specified subgraph distributions and exploits tree-like structure at a higher level to analyze them.

    Source: §I · p. 1, §II · pp. 2–3

  • Results

    The framework gives calculations for giant-component size and threshold, and for site and bond percolation properties.

    Source: C. Position of the phase transition · pp. 8–9, D. Percolation · p. 10, §V · p. 11

  • Takeaways & Limitations

    Arbitrary chosen subgraphs can be incorporated while retaining analytical calculations of local and global network properties.

    Source: §I · p. 1, §II · p. 3, §V · p. 11

    In the edge–triangle model, pairs of triangles sharing an edge vanish as network size grows, despite their common occurrence in real networks.

    Source: §III · p. 3

Abstract

from arXiv · show

Traditional random graph models of networks generate networks that are locally tree-like, meaning that all local neighborhoods take the form of trees. In this respect such models are highly unrealistic, most real networks having strongly non-tree-like neighborhoods that contain short loops, cliques, or other biconnected subgraphs. In this paper we propose and analyze a new class of random graph models that incorporates general subgraphs, allowing for non-tree-like neighborhoods while still remaining solvable for many fundamental network properties. Among other things we give solutions for the size of the giant component, the position of the phase transition at which the giant component appears, and percolation properties for both site and bond percolation on networks generated by the model.

I. INTRODUCTION

Many real networks contain small subgraphs more often than chance would predict, yet practical random-graph models incorporating general subgraphs have been scarce. The paper introduces models that include arbitrary subgraphs while remaining exactly solvable for many network properties.

I. INTRODUCTION

  • Observed networks often contain triangles and other small subgraphs in numbers exceeding chance expectations, motivating models that represent them.The passages cite social, technological, and biological examples of why such motifs may occur.Source: §I · p. 1
  • Practical random-graph models incorporating significant densities of arbitrary small subgraphs have been scarce, while exponential random graphs can be difficult to analyze and exhibit pathological behavior.Source: §I · p. 1
  • The proposed models incorporate arbitrary subgraphs and remain exactly solvable in the large-network limit for properties including degree distributions, clustering, component sizes, and percolation.Source: §I · p. 1
  • The paper develops a general formalism from an edge–triangle special case, and notes that several recent models are special cases of that formalism.The edge–triangle model had been described previously in Refs..Source: §I · p. 1

II. A SIMPLE EXAMPLE

The edge–triangle model extends random graphs by specifying single edges and triangles at each vertex and matching their stubs and corners uniformly. Although triangles break ordinary local tree-likeness, the network is tree-like when viewed as a collection of edge and triangle units, enabling calculations such as the giant-component size.

II. A SIMPLE EXAMPLE

  • Unlike ordinary sparse random graphs, the edge–triangle model contains triangles; conventional locally tree-like models have vanishing triangle density as network size grows.Source: §II · pp. 1–2
  • The edge–triangle model specifies each vertex’s counts of single edges and triangles, then uniformly samples compatible matchings of stubs and triangle corners.The total stub count must be divisible by two and the total corner count by three.Source: §II · p. 2
  • The giant component is the extensive set of vertices mutually reachable by paths, and its size is one of the quantities calculated for this model.Source: §II · pp. 2–3
  • The model’s giant-component calculation uses the joint distribution of single edges and triangles and corresponding excess-degree distributions reached through edges or triangles.The passage defines the joint degree distribution; the surrounding supplied passages describe the two types of excess degree.Source: §II · p. 2
  • The giant-component fraction in the edge–triangle model is obtained by iterating its equations to convergence and substituting the resulting probabilities.The equations need not be analytically solvable; the passage describes simple numerical iteration.Source: §II · p. 3
  • Despite triangles breaking naive local tree-likeness, finite neighborhoods are tree-like when each edge or triangle is treated as a unit.In the large-network limit, the largest biconnected component of a finite neighborhood is a triangle.Source: §II · p. 3

III. A GENERAL MODEL

The edge–triangle model cannot represent the common occurrence of triangles sharing an edge, because such pairs vanish asymptotically in that model. The generalization treats the shared-edge pair as a larger network element and allows arbitrary subgraph distributions while retaining exact solvability at a suitable higher level.

III. A GENERAL MODEL

  • In the edge–triangle model, the probability that two triangles attached to the same vertex share an edge vanishes as network size grows, although such pairs are common in real networks.Source: §III · p. 3
  • The model treats two triangles sharing an edge as a four-vertex network element and generalizes this approach to arbitrary chosen subgraphs.Such models can be viewed as tree-like at a suitable higher level and solved exactly for local and global properties in the large-size limit.Source: §III · p. 3, Figure 1 · p. 3

A. Subgraphs and roles

The general model specifies a set of subgraphs and the number of times each vertex participates in them, with roles distinguishing topologically different positions within a subgraph. Role counts form a role sequence, subject to graphicality constraints that ensure compatible subgraph instances can be assembled.

A. Subgraphs and roles

  • The model selects a subgraph set and specifies how many instances of each subgraph attach to each vertex before sampling a compatible network.The edge–triangle model is the special case whose set contains single edges and triangles.Source: A. Subgraphs and roles · p. 3, Figure 2 · p. 4
  • Vertices in the same subgraph type may occupy different roles, so specifying only subgraph membership can be ambiguous.In the diamond, two vertices have three incident edges while the other two have two.Source: A. Subgraphs and roles · p. 3
  • A subgraph’s roles correspond to the orbits of its automorphism group, grouping vertices that are topologically equivalent.The diamond has two such vertex classes.Source: A. Subgraphs and roles · p. 4, Figure 3 · p. 4
  • Finding automorphism-group orbits is computationally hard, so the paper focuses on relatively small subgraphs whose roles can be found by hand.Source: A. Subgraphs and roles · p. 4
  • The role sequence records, for every vertex, how often it plays each role across the chosen subgraph set.The sequence is a vector of non-negative integer counts, analogous to a degree sequence.Source: A. Subgraphs and roles · p. 4
  • A role sequence is graphical only when total counts of each role match the multiplicities of that role within its subgraph and agree across that subgraph’s roles.For the diamond, the two roles each occur twice, so their network-wide counts must be the same multiple of two.Source: A. Subgraphs and roles · p. 4

B. Network creation

The model draws role vectors from a role distribution, enforces graphical consistency, and uniformly matches compatible stubs to create subgraphs. It considers sparse networks and permits self-edges and multiedges, whose densities vanish as network size grows.

B. Network creation

  • Compatible stubs are randomly matched by subgraph type, producing a matching drawn uniformly from all possible such matchings.The procedure repeatedly selects the required combination of stubs for each subgraph type and connects them.Source: B. Network creation · p. 5
  • Self-edges and multiedges are allowed, but their densities vanish as 1/n; generating simple graphs is more complicated.The model’s self-edges and multiedges arise when multiple stubs from one vertex are selected for a subgraph.Source: B. Network creation · p. 5
  • Role vectors are drawn from p(d), and vertices are resampled until the resulting role sequence is graphical before stubs are matched.The role distribution gives the probability, or large-network fraction, of each role vector.Source: B. Network creation · p. 5
  • For every pair of roles in a subgraph, the expected number of stubs must imply the same number of subgraph occurrences.This constraint makes the role distribution graphically consistent.Source: B. Network creation · p. 5
  • The model considers sparse graphs with constant average total degree as network size grows.The passage identifies this as the setting considered, not a strict requirement of the construction.Source: B. Network creation · p. 5

IV. BIPARTITE GRAPH REPRESENTATION

The model represents each original vertex and each subgraph as separate node types in a bipartite graph. Although the original network contains subgraphs, this representation is locally tree-like at large size, enabling standard network calculations.

IV. BIPARTITE GRAPH REPRESENTATION

  • Each original vertex connects to nodes representing its subgraphs, with links labeled by the vertex’s role within each subgraph.The bipartite graph encodes the same network as the original representation.Source: §IV · pp. 5–6, Figure 4 · p. 6
  • Figure 4 contrasts a network containing a square and triangle with its bipartite representation.The figure depicts the equivalence between the two representations.Source: Figure 4 · p. 6, §IV · p. 6
  • The bipartite graph is locally tree-like at large size: the density of loops of any fixed size falls as 1/n.Calculations can use standard techniques for such networks and translate results back to the original model.Source: §IV · p. 6

A. Subgraph counts

Subgraph counts depend on whether motifs are biconnected or singly connected: biconnected motifs can be counted from allowed subgraphs, while general singly connected counts are harder to determine.

A. Subgraph counts

  • In the large-network limit, biconnected subgraphs formed by joining other subgraphs have vanishing density, so counts come from motifs included explicitly or inside larger allowed subgraphs.Joining subgraphs at two vertices would form a bipartite loop of length four, whose density vanishes.Source: A. Subgraph counts · p. 6
  • The clustering coefficient can be calculated from triangle counts in allowed subgraphs and the number of connected triples.Triangles are biconnected; the passage gives the counting procedure for triangles and connected triples.Source: A. Subgraph counts · p. 6
  • Counts of singly connected subgraphs are generally harder because such motifs can form by joining subgraphs at single vertices.The connected triple, or 2-star, is a special case whose count is straightforward to calculate.Source: A. Subgraph counts · p. 6

B. Giant component

The bipartite representation supplies role-based generating functions and fixed-point equations for the giant-component size. The section applies this framework to edge–triangle networks and to an example combining edges, triangles, and diamonds.

B. Giant component

  • Following a role-labeled bipartite edge gives an excess role distribution weighted by the role count in p(d).The framework defines generating functions for role distributions on both the vertex and subgraph sides of the bipartite graph.Source: B. Giant component · p. 7
  • Given the role-distribution generating function G0(z), the conventional degree-distribution generating function H(z) can be calculated using Eq. (11).Each role r contributes kr edges per role instance.Source: B. Giant component · p. 7
  • The giant-component size is determined by fixed-point equations and can be computed by numerical iteration when closed-form solutions are unavailable.The equations jointly provide a complete solution for the giant-component size.Source: B. Giant component · p. 7
  • The probability of avoiding the giant component is tracked separately for participation through a subgraph and through a vertex’s other roles.The resulting probabilities are related by u = F(v) and v = G(u), or a fixed-point equation in u.Source: B. Giant component · p. 7
  • For the edge–triangle model, the general equations reduce to the earlier two equations, and S = 1 − G0(u) gives the giant-component fraction.The model has edge and triangle subgraphs, each with one role.Source: B. Giant component · pp. 7–8
  • In the edge–triangle–diamond example, edge and triangle participation is Poisson distributed, while diamond participation assigns role 3 or 4 with probability a each.Vertices participate in no diamonds with probability 1 − 2a.Source: B. Giant component · p. 8
  • For that role distribution, the giant-component size obeys S = 1 − (1 − 2a)e^−c1S−c2S(2−S) − 2ae^−4c1S−4c2S(2−S).The passage presents this as a nontrivial but relatively simple solution.Source: B. Giant component · p. 8
  • The paper plots the solution as a function of a for one particular choice of parameters.The passage points to Figure 5 for this example.Source: B. Giant component · p. 8

C. Position of the phase transition

The giant-component transition is determined by growth in the role-based branching process: it occurs when an eigenvalue of its matrix exceeds one. Special cases show how subgraph density and correlations between subgraph roles affect the threshold.

C. Position of the phase transition

  • A giant component exists if and only if at least one eigenvalue of M exceeds one; an eigenvalue of one with none greater marks the transition.Linear stability analysis locates the transition by expanding the fixed point around the no-giant-component solution.Source: C. Position of the phase transition · p. 8
  • In the independent Poisson-role case, a giant component appears when the average number of vertices shared through subgraphs by a random vertex exceeds one.The criterion follows from the model’s single eigenvalue in this case.Source: C. Position of the phase transition · pp. 8–9
  • The transition can occur with average degree below one, because membership in a subgraph connects a vertex to its other members.In the Erdős–Rényi random graph, the transition occurs at average degree one.Source: C. Position of the phase transition · p. 9
  • For two subgraph types, their densities can independently produce a giant component, while correlations in role placement can also produce one when those densities alone are insufficient.Vertices with many instances of both subgraphs may join to form a giant component.Source: C. Position of the phase transition · p. 9
  • For the examples examined, giant-component size and transition position depend on the role distribution and role counts, not on subgraph shape.Subgraph shape matters greatly for percolation, even though it does not affect these giant-component properties.Source: C. Position of the phase transition · p. 9

D. Percolation

The section extends the giant-component machinery to percolation by adjusting each subgraph’s reachability distribution for occupied vertices and edges. It applies this framework to site and bond percolation and derives transition criteria and clique-network results.

D. Percolation

  • Percolation uses the same machinery as giant-component calculations, with F_r changed to represent which vertices in a subgraph are reachable through occupied vertices and edges.For simultaneous site and bond percolation, the occupation probabilities are φs and φb; site-only or bond-only percolation is recovered when the other probability equals one.Source: D. Percolation · pp. 9–10
  • For pure site percolation on an m-clique, the reachable-vertex count follows a binomial distribution because an occupied vertex can reach another vertex exactly when that vertex is occupied.The transition is located where the gradient of φ[1 − H(1 − S)] at S = 0 equals 1.Source: D. Percolation · p. 10
  • The giant percolation-cluster predictions for cliques of sizes 2–5 agree excellently with simulations, and the transition condition matches that of an ordinary Poisson random graph.Figure 6 plots cluster size against site occupation probability, with simulation markers and analytic curves.Source: D. Percolation · p. 10, Figure 6 · p. 10
  • Linearizing around the trivial fixed point yields ε = Mε, and a giant component exists when M has an eigenvalue greater than one.The derivative [∂F_r/∂z_t] at z=1 gives the mean number of role-t vertices reachable from a role-r vertex within its subgraph.Source: D. Percolation · pp. 10–11

V. CONCLUSION

The model accommodates arbitrary distributions of chosen subgraphs while retaining analytic and numerical tractability for several network properties. The conclusion identifies unresolved motif-selection and generating-function computation challenges, alongside possible extensions.

V. CONCLUSION

  • The model incorporates arbitrary distributions of chosen subgraphs and uses a mapping to a locally tree-like bipartite graph to calculate network properties analytically.The paper calculates subgraph counts, giant-component size and transition position, and site and bond percolation properties.Source: §V · p. 11
  • Selecting which subgraphs to include remains unresolved, and the density of singly connected subgraphs is difficult to calculate for matching model and real networks.Biconnected subgraph density equals the density explicitly added, whereas singly connected density also includes subgraphs formed from other subgraphs.Source: §V · p. 11
  • Possible extensions include labeled stubs to induce multipartite structure or assortative mixing, and role–role correlations.The paper also notes that vertices in the same role could be distinguished by stub colors.Source: §V · p. 11
  • Faster computation of general subgraph generating functions remains open because the current exhaustive-enumeration method is exponentially slow.The generating functions can be characterized analytically for some families, such as cliques, but this is considered unlikely for more general cases.Source: §V · pp. 11–12
Loading 1005.1659v1…