Random line graphs and a linear law for assortativity

For a fixed number $N$ of nodes, the number of links $L$ in the line graph $H(N,L)$ can only appear in consecutive intervals, called a band of $L$. We prove that some consecutive integers can never represent the number of links $L$ in $H(N,L)$, and they are called a bandgap of $L$. We give the exact expressions of bands and bandgaps of $L$. We propose a model which can randomly generate simple graphs which are line graphs of other simple graphs. The essence of our model is to merge step by step a pair of nodes in cliques, which we use to construct line graphs. Obeying necessary rules to ensure that the resulting graphs are line graphs, two nodes to be merged are randomly chosen at each step. If the cliques are all of the same size, the assortativity of the line graphs in each step are close to 0, and the assortativity of the corresponding root graphs increases linearly from $-1$ to 0 with the steps of the nodal merging process. If we dope the constructing elements of the line graphs—the cliques of the same size—with a relatively smaller number of cliques of different size, the characteristics of the assortativity of the line graphs is completely altered. We also generate line graphs with the cliques whose sizes follow a binomial distribution. The corresponding root graphs, with binomial degree distributions, zero assortativity, and semicircle eigenvalue distributions, are equivalent to Erdős-Rényi random graphs.

Figure 1

(a) The example of constructing a line graph by merging the half nodes of cliques, and (b) the example of constructing a simple graph by the configuration model. The circles and disks denote the half nodes and nodes respectively. The lines with slash ending and the normal lines denote the half links and links, respectively.

Figure 2

The configuration of $H(N,L)$ for (a) $W_k$; (b) $W_{k-1}$; (c) $W_2$; (d) $W_1$. The labels of the nodes locate by the side of them.

Figure 3

The bandgaps of $L$ for $N=4,5,...,14$. The solid dots denote the forbidden integers, while the hollow circles denote the possible integers as the number of links $L$.

Figure 4

Using the line graph model, we construct line graphs with 50 cliques of the same size $S$. The assortativity coefficient of the line graphs and the corresponding root graphs are drawn as functions of the steps $t$ of the nodal merging process. The root graphs of the line graphs are computed by iligra, the inverse line graph construction algorithm [26]. One can also use other algorithms [27, 28, 29] to compute the root graphs.

Figure 5

(a) The merging of two randomly selected nodes of the cliques in the line graph. (b) The corresponding root graphs before and after the nodal merging.

Figure 6

(a) The line graph $H$ with 40 cliques of size 4 and 10 cliques of size 6, and (b) the line graph $H$ with 60 cliques of size 4 and 20 cliques of size 5 have been constructed with Algorithm 1. The assortativity coefficient ${\rho }_D$ of the line graphs and the corresponding root graphs in each merging step $t$ is shown in this figure.

Figure 7

Using Algorithm 1, we construct (a) the line graph $H$ with 30 cliques, the size of which follows a binomial distribution $S\mathrm{Bino}(20,0.3)$, and (b) the line graph $H$ with 50 cliques, the size of which follows a binomial distribution $S\mathrm{Bino}(20,0.4)$. The assortativity coefficient ${\rho }_D$ of the line graphs and the corresponding root graphs in each merging step $t$ has been computed. (c) For the 50 cliques in (b), we repeat the merging process for 1000 times, and computed the probability density function of adjacency eigenvalues of the root graphs.