Emergent complex network geometry

Abstract

Networks are mathematical structures that are universally used to describe a large variety of complex systems such as the brain or the Internet. Characterizing the geometrical properties of these networks has become increasingly relevant for routing problems, inference and data mining. In real growing networks, topological, structural and geometrical properties emerge spontaneously from their dynamical rules. Nevertheless we still miss a model in which networks develop an emergent complex geometry. Here we show that a single two parameter network model, the growing geometrical network, can generate complex network geometries with non-trivial distribution of curvatures, combining exponential growth and small-world properties with finite spectral dimensionality. In one limit, the non-equilibrium dynamical rules of these networks can generate scale-free networks with clustering and communities, in another limit planar random geometries with non-trivial modularity. Finally we find that these properties of the geometrical growing networks are present in a large set of real networks describing biological, social and technological systems.

Figure 1. The two dynamical rules for constructing the growing simplicial complex and the corresponding growing geometrical network

. In process (a) a single triangle with one new node and two new links is added to a random unsaturated link, where by unsaturated link we indicate a link having less than triangles incident to it. In process (b) with probability two nodes at distance two in the simplicial complex are connected and all the possible triangles that can link these two nodes are added as long as this is allowed (no link acquires more than triangles incident to it). The growing geometrical network is just the network formed by the nodes and the links of the growing simplicial complex. In the Figure we show the case in which .

Figure 2. The growing geometrical network model can generate networks with different topology and geometry.

In the case , a random planar geometry is formed. In the case , a scale-free network with power-law exponent and non trivial community structure and clustering coefficient is formed. In the intermediate case a network with broad degree distribution, small-world properties and finite spectral dimension is formed. The colours here indicate division into communities found by running the Leuven algorithm.

Figure 3. Local properties of the growing geometrical model.

We plot the degree distribution , the distribution of curvature , and the average clustering coefficient of nodes of degree for networks of sizes , parameter chosen as either or , and different values of . The network has exponential degree distribution for and scale-free degree distribution for . For and it shows broad degree distribution. The networks are always hierarchical, to the extent that with shown in the figure. The distribution of curvature is exponential for and scale-free for . For the curvature has a positive tail.

Figure 4. Maximum distance from the initial triangle and Euler characteristic as a function of the network size

. The geometrical network model is growing exponentially, with . Here we show the data and (panel A). The Euler characteristic is given by for and and grows linearly with for the other values of the parameters of the model (panel B).

Figure 5. Modularity and clustering of the growing geometrical model.

The modularity calculated using the Leuven algorithm on realisations of the growing geometrical network of size is reported as a function of the parameters and of the model. Similarly the average local clustering coefficient calculated over realisations of the growing geometrical networks of size is reported as a function of the parameters and . The value of of the maximal -core is shown for a network of nodes as a function of and . These results show that the growing geometrical networks have finite average clustering coefficient together with non-trivial community and -core structure on all the range of parameters and .

Figure 6. The spectral dimension of the geometrical growing networks.

Asymptotically in time, the geometrical growing networks have a finite spectral dimension. Here we show typical plots of the spectral density of networks with nodes, and (panel A). In panel B we plot the fitted spectral dimension for averaged over network realizations for .

Figure 7. Curvature distribution in real datasets.

We plot the distribution in a a variety of datasets with additional structural and local properties shown in Table 1.