#  Polcovar: Software for Computing the Mean and Variance of Subgraph Counts
in Random Graphs

Jérôme Kunegis

###### Abstract

The mean and variance of the number of appearances of a given subgraph $H$ in
an Erdős–Rényi random graph over $n$ nodes are rational polynomials in $n$
[2]. We present a piece of software named Polcovar (from _polynomial_ and
_covariance_) that computes the exact rational coefficients of these
polynomials in function of $H$.

##  1 Introduction

Large networks can be characterised by the number of times specific subgraphs
appear in them. For instance, the number of triangles measures the clustering
in a network and the number of wedges (i.e. 2-stars / 2-paths) characterises
the inequality of the degree distribution. Even the number of vertices and
edges in a graph can be characterised in this way as the number of times the
complete graphs on one and two nodes appear as subgraphs. To assess whether a
graph contains many or few subgraphs for its size, the subgraph count must be
compared to the expected subgraph count in random graphs. To do this, we must
know the distribution of subgraph counts. Under mild conditions which are
valid for all examples given above, the subgraph count becomes normal in the
large graph limit. Consequently, the distribution of subgraph counts is
characterised by its mean and average. Expressions for the mean and variance
of subgraph counts are given in [2], and are always rational polynomials in
the number of nodes $n$ of the network. In this paper, we present Matlab
software for computing the exact coefficients rational of these polynomials,
as their expressions are usually too unwieldy to be computed by hand.

##  2 Subgraph Counts

We consider a random graph $G$ on $n$ nodes distributed according to the
Erdős–Rényi model with parameter $p$, i.e., each edge in $G$ exists with
probability $p$ [1]. Let $H=(W,F)$ be a pattern, i.e. a small graph with
$k=|W|$ vertices and $l=|F|$ edges, and $c_{H}$ the number of times this
pattern appears as a subgraph of $G$. The mean of variance of $c_{H}$ are then
given by the following expressions [2]:

$\displaystyle\mathrm{E}[c_{H}]$
$\displaystyle=\frac{n^{\underline{k}}}{|\mathrm{Aut}(H)|}p^{-l}$
$\displaystyle\mathrm{Var}[c_{H}]$
$\displaystyle=\sum_{J}\left(\frac{n^{\underline{|V(J)|}}}{|\mathrm{Aut^{\prime}}(J)|}p^{-|E(J)|}\right)-\mathrm{E}[c_{H}]^{2}$

where $n^{\underline{i}}$ is the falling factorial111defined as
$n^{\underline{i}}=n(n-1)\cdots(n-i+1)$, the sum is over all graphs $J$
containing two differently colored copies of $H$ (which might overlap),
$\mathrm{Aut}(H)$ is the automorphism group of the graph $H$, and
$\mathrm{Aut^{\prime}}(J)$ is the group of automorphisms of $J$ that preserve
the edges of the underlying distinct copies of $H$.

Although the normal limit for $n\rightarrow\infty$ is only true when the graph
$H$ is _strictly balanced_ , the expressions for the mean and variance are
always correct. Note also that they are true exactly for any $n$, not just in
the large $n$ limit.

Alternatively, the following expression can be used, which gives the same
result. It is this expression that we implement in our code.

$\displaystyle\mathrm{Var}[c_{H}]$
$\displaystyle=-\mathrm{E}[c_{H}]^{2}+\frac{1}{\mathrm{Aut}(H)^{2}}\sum_{i=0}^{k}\frac{n^{\underline{2k-i}}}{i!(k-i)!^{2}}\sum_{P,Q}p^{-m(P,Q)}$

where the inner sum is over all pairs of $k$-permutations, and $m(P,Q)$
denotes the number of edges in the overlay of H permuted by $P$ and $H$
permuted by $Q$ which share $i$ nodes.

##  3 Special Cases

For specific small graphs $H$, we get the following exact results.

###  3.1 Node Count

Taking $H$ as the graph with one node gives the number of nodes. Plugging this
graph into the general form expression gives $\mathrm{E}[c_{H}]=n$ and
$\mathrm{Var}[c_{H}]=0$. In other words, the number of nodes is always exactly
$n$, as expected.

###  3.2 Edge Count

Edges are always independent of each other and therefore the binomial
approximation for the number of edges $m=c_{H}$ is exact.

$\displaystyle\mathrm{E}[m]$ $\displaystyle=\frac{1}{p}{n\choose
2}=\frac{n(n-1)}{2p}$ $\displaystyle\mathrm{Var}[m]$
$\displaystyle=\frac{n(n-1)}{8}\text{ when $p=1/2$}$

These expressions can be derived both by the general form we gave above, and
by the fact that the number of edges is a binomial distribution.

###  3.3 Triangle Count

In a random $n$-graph with parameter $p=1/2$, the number of triangles $t$ has
mean and variance given by

$\displaystyle\mathrm{E}[t]$ $\displaystyle=\frac{1}{8}{n\choose 3}$
$\displaystyle\mathrm{Var}[t]$
$\displaystyle=\frac{1}{128}n^{4}-\frac{11}{384}n^{3}+\frac{1}{32}n^{2}-\frac{1}{96}n$

The expressions follow from the general form given below.

###  3.4 Wedge Count

The number $s$ of wegdes (i.e., pairs of edges sharing one endpoint, also
known as 2-stars or 2-paths) has the following distributions when $p=1/2$:

$\displaystyle\mathrm{E}[s]$ $\displaystyle=\frac{n^{\underline{3}}}{8}$
$\displaystyle\mathrm{Var}[s]$
$\displaystyle=\frac{1}{8}n^{4}-\frac{19}{32}n^{3}+\frac{29}{32}n^{2}-\frac{7}{16}n$

The expressions follow from the general form given below.

###  3.5 Other Patterns

For the number $q$ of squares we get:

$\displaystyle\mathrm{E}[q]$
$\displaystyle=\frac{1}{128}n^{4}-\frac{3}{64}n^{3}+\frac{11}{128}n^{2}-\frac{3}{64}n$
$\displaystyle\mathrm{Var}[q]$
$\displaystyle=\frac{1}{512}n^{6}-\frac{5}{256}n^{5}+\frac{161}{2048}n^{4}-\frac{163}{1024}n^{3}+\frac{327}{2048}n^{2}-\frac{63}{1024}n$

For the number $c_{H}$ of 4-cliques we get:

$\displaystyle\mathrm{E}[c_{H}]$
$\displaystyle=\frac{1}{1536}n^{4}-\frac{1}{256}n^{3}+\frac{11}{1536}n^{2}-\frac{1}{256}n$
$\displaystyle\mathrm{Var}[c_{H}]$
$\displaystyle=\frac{1}{32768}n^{6}-\frac{17}{98304}n^{5}+\frac{19}{49152}n^{4}-\frac{73}{98304}n^{3}+\frac{115}{98304}n^{2}-\frac{11}{16384}n$

##  4 Proof Outline

A complete proof can be found in [2]. We here outline the proof as a starting
point. The total number of possible subgraphs $H$ in a graph with $n$ vertices
is

$\displaystyle\frac{n^{\underline{k}}}{|\mathrm{Aut}(H)|}.$

Define the random variables $x_{i}\in\\{0,1\\}$ to denote the presence or
absence of each possible pattern $i$. Then,

$\displaystyle c_{H}$ $\displaystyle=\sum_{i}x_{i}.$

The expected value of each $x_{i}$ is given by

$\displaystyle\mathrm{E}[x_{i}]=p^{-l}.$

Thus, the expected value of $c_{H}$ can be expressed as

$\displaystyle\mathrm{E}[c_{H}]=\mathrm{E}[\sum_{i}x_{i}]=\sum_{i}\mathrm{E}[x_{i}]=\frac{n^{\underline{k}}}{|\mathrm{Aut}(H)|}p^{-l}.$

To compute the variance we exploit the fact that the variance equals the
expected value of the square minus the square of the expected value:

$\displaystyle\mathrm{Var}[c_{H}]$
$\displaystyle=\mathrm{E}[c_{H}^{2}]-\mathrm{E}[c_{H}]^{2}$
$\displaystyle=\mathrm{E}[(\sum_{i}x_{i})(\sum_{i}x_{i})]-\mathrm{E}[c_{H}]^{2}$
$\displaystyle=\mathrm{E}[\sum_{ij}x_{i}x_{j}]-\mathrm{E}[c_{H}]^{2}$
$\displaystyle=\sum_{ij}\mathrm{E}[x_{i}x_{j}]-\mathrm{E}[c_{H}]^{2}$

Then, each possible pair corresponds to one possible pattern graph $J$, of
which the possible number is
$\frac{n^{\underline{|V(J)|}}}{|\mathrm{Aut^{\prime}}(J)|}$, and each exists
with independently with probability $p^{-|E(J)|}$. From this follows the given
expression.

##  5 Extension to Covariances

The method can be extended to covariances between the count statistics of
different patterns. As an example:

$\displaystyle\mathrm{Cov}[c_{\mathrm{edge}},c_{\mathrm{triangle}}]$
$\displaystyle=\frac{1}{32}n^{3}-\frac{3}{32}n^{2}+\frac{1}{16}n$

##  6 The Software

Our code is written in the programming language Matlab, and contains two entry
points, the function polcovar_mu() that computes the mean and the function
polcovar_sigma() that computes the variance or covariance.

    r = polcovar_mu(H);
    r = polcovar_sigma(H1, H2);

The input graphs H must be given as $k\times k$ adjacency matrices. The
function polcovar_sigma() expects two graphs H1 and H2 and returns the
covariance of their subgraph counts. To compute the variance, pass the same
adjacency matrix as both arguments. All input matrices must be symmetric 0/1
matrices with zero diagonals. All computations are valid for Erdős–Rényi
graphs with $p=1/2$.

The return values are rational polynomials in form of $2\times(m+1)$ matrices,
where $m$ is the degree, coded in the following way:

$\displaystyle r$
$\displaystyle=\left[\begin{array}[]{ccccc}a_{m}&a_{m-1}&\cdots&a_{1}&a_{0}\\\
b_{m}&b_{m-1}&\cdots&b_{1}&b_{0}\end{array}\right]$

representing the following rational polynomial in $n$:

$\displaystyle P_{r}(n)$
$\displaystyle=\sum_{i=0}^{m}\frac{a_{i}}{b_{i}}n^{i}$

All fractions $a_{i}/b_{i}$ are returned in simplified form.

###  6.1 Example

The following example uses Polcovar to compute the mean and standard deviation
of the number of triangles in a random graph with 1,000,000 nodes.

    % Adjacency matrix of a triangle
    H = [ 0 1 1; 1 0 1; 1 1 0]

    % Compute polynomials
    r_mu = polcovar_mu(H)
    r_sigma = polcovar_sigma(H, H)

    % Evaluate polynomials for a graph with 1,000,000 nodes
    n = 1000000
    mu = polyval(r_mu(1,:) ./ r_mu(2,:), n)
    sigma = polyval(r_sigma(1,:) ./ r_sigma(2,:), n)
    sigma_stddev = sqrt(sigma)

This will compute that a random graph with 1,000,000 nodes can be expected to
contain $2.0833\times 10^{16}\pm 8.8388\times 10^{10}$ triangles.

## Acknowledgements

We thank Thomas Sauerwald from the University of Cambridge.

## References

  * [1] Paul Erdős and Alfréd Rényi.  On random graphs I.  Publ. Math. Debrecen, 6:290–297, 1959.
  * [2] Andrzej Ruciński.  When are small subgraphs of a random graph normally distributed?  Prob. Th. Rel. Fields, 78:1–10, 1988.