Shape of shortest paths in random spatial networks

In the classic model of first-passage percolation, for pairs of vertices separated by a Euclidean distance L, geodesics exhibit deviations from their mean length L that are of order L^{χ}, while the transversal fluctuations, known as wandering, grow as L^{ξ}. We find that when weighting edges directly with their Euclidean span in various spatial network models, we have two distinct classes defined by different exponents ξ=3/5 and χ=1/5, or ξ=7/10 and χ=2/5, depending only on coarse details of the specific connectivity laws used. Also, the travel-time fluctuations are Gaussian, rather than Tracy-Widom, which is rarely seen in first-passage models. The first class contains proximity graphs such as the hard and soft random geometric graph, and the k-nearest neighbor random geometric graphs, where via Monte Carlo simulations we find ξ=0.60±0.01 and χ=0.20±0.01, showing a theoretical minimal wandering. The second class contains graphs based on excluded regions such as β skeletons and the Delaunay triangulation and are characterized by the values ξ=0.70±0.01 and χ=0.40±0.01, with a nearly theoretically maximal wandering exponent. We also show numerically that the so-called Kardar-Parisi-Zhang (KPZ) relation χ=2ξ-1 is satisfied for all these models. These results shed some light on the Euclidean first-passage process but also raise some theoretical questions about the scaling laws and the derivation of the exponent values and also whether a model can be constructed with maximal wandering, or non-Gaussian travel fluctuations, while embedded in space.

SIR epidemics on a scale-free spatial nested modular network

We propose a class of random scale-free spatial networks with nested community structures called SHEM and analyze Reed–Frost epidemics with community related independent transmissions. We show that in a specific example of the SHEM the epidemic threshold may be trivial or not as a function of the relation among community sizes, distribution of the number of communities, and transmission rates.

Phase Transitions for Random Geometric Preferential Attachment Graphs

Vertices arrive sequentially in space and are joined to existing vertices at random according to a preferential rule combining degree and spatial proximity. We investigate phase transitions in the resulting graph as the relative strengths of these two components of the attachment rule are varied.

Previous work of one of the authors showed that when the geometric component is weak, the limiting degree sequence mimics the standard Barabási-Albert preferential attachment model. We show that at the other extreme, in the case of a sufficiently strong geometric component, the limiting degree sequence mimics a purely geometric model, the on-line nearest-neighbour graph, for which we prove some extensions of known results. We also show the presence of an intermediate regime, with behaviour distinct from both the on-line nearest-neighbour graph and the Barabási-Albert model; in this regime, we obtain a stretched exponential upper bound on the degree sequence.

Features and heterogeneities in growing network models

Many complex networks from the World Wide Web to biological networks grow taking into account the heterogeneous features of the nodes. The feature of a node might be a discrete quantity such as a classification of a URL document such as personal page, thematic website, news, blog, search engine, social network, etc., or the classification of a gene in a functional module. Moreover the feature of a node can be a continuous variable such as the position of a node in the embedding space. In order to account for these properties, in this paper we provide a generalization of growing network models with preferential attachment that includes the effect of heterogeneous features of the nodes. The main effect of heterogeneity is the emergence of an "effective fitness" for each class of nodes, determining the rate at which nodes acquire new links. The degree distribution exhibits a multiscaling behavior analogous to the the fitness model. This property is robust with respect to variations in the model, as long as links are assigned through effective preferential attachment. Beyond the degree distribution, in this paper we give a full characterization of the other relevant properties of the model. We evaluate the clustering coefficient and show that it disappears for large network size, a property shared with the Barabási-Albert model. Negative degree correlations are also present in this class of models, along with nontrivial mixing patterns among features. We therefore conclude that both small clustering coefficients and disassortative mixing are outcomes of the preferential attachment mechanism in general growing networks.

Preferential attachment in growing spatial networks

We obtain the degree distribution for a class of growing network models on flat and curved spaces. These models evolve by preferential attachment weighted by a function of the distance between nodes. The degree distribution of these models is similar to that of the fitness model of Bianconi and Barabási, with a fitness distribution dependent on the metric and the density of nodes. We show that curvature singularities in these spaces can give rise to asymptotic Bose-Einstein condensation, but transient condensation can be observed also in smooth hyperbolic spaces with strong curvature. We provide numerical results for spaces of constant curvature (sphere, flat, and hyperbolic space) and we discuss the conditions for the breakdown of this approach and the critical points of the transition to distance-dominated attachment. Finally, we discuss the distribution of link lengths.