Inhomogeneous evolution of subgraphs and cycles in complex networks

Subgraphs and cycles are often used to characterize the local properties of complex networks. Here we show that the subgraph structure of real networks is highly time dependent: as the network grows, the density of some subgraphs remains unchanged, while the density of others increase at a rate that is determined by the network’s degree distribution and clustering properties. This inhomogeneous evolution process, supported by direct measurements on several real networks, leads to systematic shifts in the overall subgraph spectrum and to an inevitable overrepresentation of some subgraphs and cycles.

Figure 1

Examples of subgraphs and cycles with a central vertex. The subgraph shown in (a) has $n=5$ vertices and $n-1+t=5$ edges, where $t=1$ represents the number of edges connecting the neighbors of the central vertex (empty circle) together. In (b) we show a subgraph with $t=3$ edges among the neighbors, such that the central vertex and its neighbors form a cycle of length $h=5$, highlighted by the dotted circle.

Figure 2

Number of $(n=5,t)$ subgraphs for the (a) coauthorship, (b) Internet, and (c) semantic networks, and the (d) deterministic model as a function of $t$. Different symbols correspond to different snapshots of the networks evolution, from early stage (circles) to intermediate (squares) and current (i.e., largest) (triangles). $N_{nt}$ depends strongly on $t$ (spanning several orders of magnitude) making it difficult to observe the $N$ dependence. Thus we normalized all the quantities ($N_{5t}$, $C_0$, and $N$) to the first year available. The arrows correspond to the phase boundary $5-\gamma -\alpha t=0$, with type I and II subgraphs to the left and right of the arrow, respectively. The insets show the system size dependence were we plot $\log N_{5t}$ vs $\log N$ for different values of $t$.

Figure 3

Number of $h$ cycles as computed from (3), using $\gamma =2.5$, (a) $C_0=2$ and $\alpha =1.1$, and $k_{\mathit{max}}=500$ (dashed-dotted), 700 (dashed), and 900 (solid), (b) $h$ value at which $N_h$ has a maximum as a function of $k_{\mathit{max}}$, (c) $C_0=1$ and $\alpha =0.9$.

Figure 4

Density of all (open symbols) and centrally connected (filled symbols) cycles with $h=3$ (circles), 4 (squares), and 5 (diamond) cycles as a function of the graph size. The continuous lines corresponds with our predictions (Table ).