{'fraction_non_alphanumeric': 0.026341506751954513, 'fraction_numerical': 0.008173418621179816, 'mean_word_length': 4.8369198859217, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A surface-depth theory of the emergence of complex networks

The broadly general characteristics of complex networks found across disciplines-- such as high clustering coefficients and heavy-tailed degree distributions-- has long invited the question of whether there are general generating mechanisms behind them. Here, we propose a theory of such mechanisms and undertake several experiments which validate it. This theory proposes that there are two key principles at work in the emergence of a network, constituting a `surface' factor and a `depth' factor making up the existence probability of network edges. The surface factor describes nodes as having tendencies for attachment which follow a log-normal distribution. The deep factor suggests that beneath these potentials for attachment there exist any number of important latent variables describing the nodes. These variables are formulated as a high-dimensional manifold and the `distances' between pairs of nodes on this manifold constitute a similarity weighting informing on the probability that any two nodes are connected. Using standard network measures, the topology of 110 networks across a variety of disciplines shows agreement with a simple two-parameter model based on this theory. Importantly, we show that the log-normal surface factor can explain the power-law-like degree distributions of sparse networks and, more strongly, the variety of degree distributions found across networks of different densities. We also demonstrate how inverting an estimated surface factor of a complete weighted world city network provides more plausible clusters of nodes than the original network based on geometric and cultural considerations. This theory proposes a new fundamental formulation of complex networks with wide reaching consequences throughout the multidisciplinary domain of complex systems.


INTRODUCTION
Theories of the emergence of complex networks allow us to gather insights into their potential generative mechanisms [1,2]. If such a theory is accurate, it can establish new foundations from which to understand, analyse, deconstruct and interpret network phenomena. The seminal prototype of network models is the Erdös-Rényi random graph where all edges have equal probability, p, of appearing in the graph. A realisation of this random graph is generated by assigning uniformly random values to all node pairs and substantiating the existence of only those edges whose values lie above p [3]. Alternatively, one can specify that only the edges with the m highest values should be kept [4]. For a large enough number of nodes, each graph isomorphism class (i.e. distinct graph topology) of n nodes and m edges has roughly equal probability of appearing from this model [5]. Yet, the topological characteristics of real-world networks substantially and consistently deviate from those generated by this model [6], telling us that real-world networks occupy a relatively small and highly uncommon set of graph isomorphism classes.
We can classify network models either as being constructive or non-constructive. Non-constructive models such as configuration models [6,7], stochastic block models [8], and complex hierarchy models [9] are derived from observations of real world networks and are focused on practical issues for the study of specific network properties as they are found. They are not of much use for providing insights into the generative mechanisms explaining the emergence of real networks. Constructive models, on the other hand, seek to derive complex network topologies from proposed generative mechanisms, the aim of which is to provide plausible physical explanations for the non-arbitrary topological features of real world networks. The most dominant branch of constructive models derive from the theory of preferential attachment where nodes which are older in the network have a greater share of edges simply due to their age, and present with scalefree degree distributions seen in some networks [2]. More complicated formulations to fix the lack of clustering in the original model have been proposed [10,11]. Problems remain however, such as the recently shown rarity of scale-free networks [12]. Another branch of constructive models considers nodes existing in a geometrical space and connections occurring where those nodes are close together. The idea that nodes which are close together are connected together is intuitively sensible and recent evidence agrees [13]. The prototype of this approach is the random geometric graph where nodes are random samples of an n-dimensional Euclidean space [14]. This model has some interesting relevant properties to real world networks such as a high modularity and clustering, but they do not display the degree heterogeneity implicated by hub nodes typical of complex networks. Further to this, Serrano et al. proposed a hyperbolic geometric model constraining for the expected degree distribution of the network [15]. This has also recently been extended to weighted networks [16]. However, it does not provide an explanation for how these degree distributions themselves arise.
From the literature to date, it would appear that there are two main aspects to be explained in the emergence arXiv:1902.00336v1 [physics.soc-ph] 1 Feb 2019 of complex networks: i) the variability in the number of edges assigned to nodes, and ii) the likelihood of any given pair of nodes to form a connection. Here, we provide a new general generative theory of complex networks which addresses these two points as factors proportional to the probability of the existence of edges. Essentially, we propose that the heterogeneous degree distributions of complex networks can be explained by assuming that the propensity for forming connections is an attribute of nodes which follows a log-normal distribution. This is deemed as a surface consideration of the network as it is a property independent of which nodes connect to which. In conjunction, we propose that the specific ways in which connections are made between nodes depends on a number of latent variables describing how similar nodes are to one another. These variables can then be regarded as dimensions of a high-dimensional manifold on which the nodes lie, and their closeness on this manifold represents the similarity of the nodes over these variables. This is deemed as a 'deep' consideration of the network as it is the property which directly influences which nodes connect to which, given their surface propensities. These surface and depth considerations are then taken as factors precisely describing the probabilities of the existence of a connections between all node pairs. Importantly, because we provide an exact theoretical formulation to describe the emergence of complex networks, it opens up a new branch of complex network theory for exploration. For example, we describe how we can estimate the surface factor and invert it to get close to the depth factor explaining more accurately the similarities between nodes.

THEORY
Let V = {1, . . . , n} be a set of nodes representative of individual agents. Then, suppose that these agents have individual tendencies to make connections to other agents, h i , and that these tendencies are distributed according to a log-normal distribution h ∼ LogN (µ, σ). For example, in social networks it stands to reason that the tendencies of people to make new friends is the result of a number of psychological variables, such as extroversion and charisma, while empirical evidence suggests that such variables should be modelled using a log-normal distribution [17]. We could consider whether such tendencies are additive or multiplicative for pairs of nodes, i.e. is the combined tendency of h i and h j (h i + h j ) or h i h j ? In practice, this is not of immediate importance since both the addition and product of two log-normally distributed variables are log-normal. For simplicity's sake, we shall assume that the combined tendency of h i and h j is additive. We relate to this as the surface factor of the network, since it does not really help to describe why any two nodes are connected together beyond that either or both have a strong tendency to make connections.
Below this surface, however, we assume that there are similarities between agents which make it more likely for connections to occur between them. Thus, we suppose that agents are distinguishable by some number, q, of independent latent variables, x 1 , x 2 , . . . , x q . Then, the similarity of nodes i and j across these variables can be described by some distance function A very obvious and important consideration of such latent variables is simply the geometry within which the agents are set. If two agents live nearby one another, it stands to reason they are more likely to be connected to one another than to some other agent that lives far away, disregarding other variables. It is important to point out that variables could also be categorical. For instance, in a social network, people who belong to the same club, A say, are more likely to be connected than to others in another club, B. We refer to these latent variables as making up a depth factor for the network as it accurately describes the similarities of agents beyond their tendency to make connections.
Combining these consideration, the probability of a connection being established between nodes i and j is proportional to node similarity (depth factor) and the combined tendency of making connections of i and j (surface factor), giving Assuming that these as the only considerations of the probability of existence of an edge, we can take the weights of edges in our network as up to linearity. For a complex binary network with m edges, we can then, for example, take the m largest weights as extant, as for the random graph, use a nearest neighbours connectivity approach [18], or use a combination of the two to ensure connectedness while specifiying the exact number of edges.

Model
Given the above, to construct a model, all we need is a description of the properties of the latent variables, x i . We know that geometry is a key consideration of networks, and thus we have up to three variables which can be approximated using a random geometric graph where coordinates are chosen uniformly at random over the interval [0, 1]. The most simple model would prescribe all variables as equivalent and independent, thus we shall simply model similarities between nodes as distances of a random geometric graph in q dimensions. Of course, it is likely that different variables will have different distributive properties in reality, but, as we shall demonstrate, this simple assumption actually works quite well in practice for modelling a diverse range of complex networks. Our model, then, has probabilistic weights for each edge proportional to where for each x i ∼ U ([0, 1]), and h ∼ LogN (µ, σ). Now, µ does not affect the relative values in (4), i.e. µ will not affect relationships of the form w ij ≤ w st for any i, j, s, t ∈ V, thus essentially, we only need to consider the shape parameter, σ, of the log-normal distribution. Thus, the only parameters of this model are the number of dimensions of the deep factor, q, and the shape parameter for the log-normal distribution of the surface factor, σ and, for a network, G, with n nodes and m edges, we can describe its surface-depth model as G s-d (q, σ).

EXPERIMENTS Explaining topological properties of sparse binary networks
We modelled 110 real world binary networks collected from two difference sources. This was done iteratively on the two model parameters and the best fit was achieved by minimising the Root Mean Squared Error (RMSE) of five important and distinct topological metrics. These were the clustering coefficient, C, global efficiency [19], E, normalised degree variance [20], V , Louvain's modularity [21], Q, and assortativity [22], r. These were chosen both so that they covered distinctly formulated topological aspects, and so that the values were all of similar magnitudes (between 0 and 1, or -1 for assortativity) and thus the minimisation was not biased to any particular index. This kind of minimisation has been previously used in e.g. [23,24]. Models were ensured to have all nodes with at least degree 1 by including the nearest neighbours for each node. The rest of the edges were then selected simply from the edges with highest weights across all model weights until the number of edges matched the real network.
We studied two datasets of networks for this. The first consists of 25 networks taken from the network repository across different domains [25]. This consists of eight social networks-karate club, hi-tech firm, dolphins, wikivote, Hamsterster, Enron email, Dublin contact, and Uni email; six biological networks-mouse brain, macaque cortex, c elegans metabolic, mouse protein, plant protein, and yeast protein; three ecological networks-Everglades, Mangwet and Florida; three infrastructure networks-US airports, euroroads and power grid; and three economic networks-global city network (binarised at 20% density), US transactions commodities 1979 and US transactions industries 1979. Many of these are classic benchmark networks.
The second network dataset is the corpus used in [26]. Of this dataset, we looked at the 184 static networks and, for the sake of computational time, chose to look only at those between 20 and 500 nodes in size. Further, we discarded bipartite networks as these have 0 clustering and thus obviously need a different depth factor consideration than the random geometric graph which has a large clustering coefficient. We thus ended up with 85 networks.
The most accurate surface-depth model was then chosen following Algorithm 1. Compute C, E, V Q and r of each of these models and take the mean over realisations for each 5: Compute the RMSE between indices of G and mean of G s-d (q, σ)

6:
Take σ as the σ parameter of minimum RMSE model Take the model with the minimum RMSE value from this step as the minimum for the model with q dimensions 9: The minimum across q of the minimum RMSEs across σ is then taken as the model of best fit to G Note, we took a maximum of q = 10 arbitrarily to save on time as we assume the topological properties of the model are asymptotic with q, as demonstrated in the supplementary material, so if it is still far away by q = 10 it is unlikely to ever get too close.
For the 25 network repository networks, the minimum RMSE score for each network, alongside the corresponding q and σ of the model, is shown in Table I. For 50 model realisation, we compared the degree distributions of the best-fit model with real networks using Kolmogorov-Smirnoff (KS) two-sample statistical tests. As is standard, the null hypothesis, that the distributions were not different, was rejected in the case that p < 0.05. The results indicate that only around half of the networks have degree distributions indistinguishable from their best-fit models, Table I   between minimum RSME and percentage of null hypothesis rejections. However, Fig 1 shows comparisons of degree distributions of the surface-depth model and network repository networks. The similarity between distributions across all networks of various size, density and domain is remarkable. We can see even those which failed the KS tests have very similar distributions. We thus suggest that these failures are not caused by the surface factor of the model, but rather by the simplified depth factor used. We then looked at the second network dataset using the same methods as above. The minimum RMSEs of the model are shown in Fig 3, grouped by network class. Of the larger classes, the connectomes were best fitted by our model, followed by protein interaction networks. Food webs, by comparison, were quite poorly approximated by our model, often with RMSE> 0.1. The similarity between degree distributions was assessed again using two sample KS tests. We found a greater rate of of distribution similarity in this dataset than in the network repository with 70.6% of networks having a fraction greater than 80% of successfully rejected null hypotheses. Observations were similar as for the network repository, where most of those which were not rejected still had observably similar distributions.
Interestingly, even though food web networks were not well approximated by our model, their degree distributions were on the whole largely indistinguishable from those of the model. Looking more closely, it appeared there was an exceptional difference in the clustering coefficients in this case. Median differences for each index across food web networks were as follows: The very low relative clustering in food web networks makes sense since we can expect that it is uncommon for predators of the same prey to hunt one another as well. This suggests that better modelling of the depth factor would help to capture the information in food web networks and we thus conjecture that accurate modelling of latent variables would be enough to help explain different real world network topologies.

Depth Factor Recovery of the World City Network
Given our theory, it would be of great interest to see what the depth factor of a real network would look like. However, recovering the depth factor of a sparse binary network poses a very challenging problem, as we are unable to determine which edges are stronger to a given node than any other from the binary edges. What we can do, however is to apply our methods to a fully weighted network by assuming that the weights of the network are linearly proportional to the underlying surface-depth factors of the network. Just such a network is available from the Globalisation and World Cities research network [27,28], constructed using relationships of producer service firms at the forefront of economic influence within each city.
First, we looked at an example of recovering the depth factor from a surface-depth model, where we could directly compare the depth factor with our estimation attempts. We considered estimating the surface factor using both the weighted degree distribution and just by tuning a log-normal distribution to get the best result. In this case, we just generated another set of log-normally distributed samples using the same parameters as our known surface factor. Fig 4, bottom row, shows the outcome. Although the weighted degree distribution worked fairly well, it was clear that tuning a log-normal distribution could achieve a more accurate result.
For the world city network, we fine-tuned a log-normal distribution until it produced an observably balanced adjacency matrix, where the original node hierarchy appeared to be successfully inverted, as seen in Fig 5. This was achieved at parameters µ = 0.5, σ = 0.55. K-Nearest Neighbour (KNN) graphs with K = 5 were then computed from the global city network and its estimated depth factor.
Modules were computed using Louvain's modularity method [19]. The KNN graphs were then plotted using the same force-based algorithm where connected nodes are attracted and non-connected nodes repelled from one another [29], Fig 6. Remarkably, surface inversion of the hub-centric world city network produced a highly mod- ular network with geometric qualities. On inspection, spaces within the network layout were notable by their global proximity and cultural ties. We analysed this statistically in the case of global proximity (details in the supplementary material). The supplementary material contains tables of the five nearest neighbours of each city for each approach. Of these, 63.64% were found to be proximal on the globe (either being in the same continent or observably close) for the tuned log-normal inversion compared to 50.55% for the degree-based inversion and just 37.82% for the original network. Furthermore, the five cities with greatest weighted degree (London, New York, Paris, Tokyo and Hong Kong) appeared in 76.64% of the nearest neighbours in the original network, compared to 46.18% in the degree-based inversion and just 14.91% of the tuned log-normal inversion, with 9.27% being that expected by random chance. In addition, 52 of the 55 cities were found within the 5 nearest neighbours of all cities in the tuned log-normal inversion approach, whereas this number was just 15 for the original network and 38 for the degree-based inversion. Cultural ties were assessed qualitatively, for example Barcelona and Madrid being in the same community as all Latin American cities appeals to their cultural ties, whereas Latin American cities were not all found in the same community in the original network. Also, Eastern Europe and East Asia both had clearly distinct communities in the recovered depth factor but not so in the original network.

DISCUSSION
Evolution and dynamics of networks can be easily accounted for in our theory by shifts occurring in shallow and deep factors. For instance, a node may take on different values of its latent variables thus changing the nodes to which it is most similar which would result in a change to the edges the node makes. Otherwise, the node may increase or decrease its surface factor value giving it a higher/lower tendency to make connections, again resulting in a dynamic change of the network. New nodes could be assumed to appear somewhere within the latent variable space but with an initially low tendency to make the connections.
The proposal that a depth factor of weight similarities can be extracted has clear implications in terms of geometric deep learning [30]. Along similar lines, a recent study considered using machine learning approaches on a hyperbolic network model [31]. It seems that such methods can be fairly straightforwardly translated to the geometries of the proposed depth factor and we expect our study will open up interesting future research along these lines.
FIG. 5. Weighted adjacency matrices (ordered by weighted degree) of the global city network, an estimated depth factor of the network using the weighted degree and an estimated depth factor using a tuned log-normal distribution, respectively.
FIG. 6. Plot of the five-nearest neighbours graph of the world city network (left) and its recovered depth factor (right) with detected communities shown in different colours. Clusters in the depth factor are observably more distinguishable, whereas relationships between the nodes in the original network are dominated by a few nodes.