Spatially-embedded random networks: Mathematical framework
Many real-world networks analysed in modern network theory have a natural spatial element; e.g. the Internet, social networks, neural networks, etc. Yet, aside from a comparatively small number of somewhat specialised and domain-specific studies, the spatial element is mostly ignored and, in particular, its relation to network structure disregarded. In work in collaboration with Lionel Barnett and Seth Bullock, we have introduced a model framework to analyse the mediation of network structure by spatial embedding; specifically, we have modelled connectivity as dependent on the distance between network nodes. Our Spatially Embedded Random Networks (SERN) construction is not primarily intended as an accurate model of any specific class of real-world networks, but rather to gain intuition for the effects of spatial embedding on network structure; nevertheless we are able to demonstrate, in a quite general setting, some constraints of spatial embedding on connectivity such as the effects of spatial symmetry, conditions for scale free degree distributions and the existence of small-world spatial networks.
One interesting result is the lack of transition to a giant component. Below: Fraction of network occupied by largest component plotted against mean connectivity with increasing network size, for several Generalised Random Geometric Graphs (GRGGs: spatial networks with truncation decay in spatial connectivity), estimated in sample. The small arrow marks the value estimated connectivity for the phase transition to the appearance of a giant component for a uniform GRGG of corresponding dimension. Sample sizes are large enough that standard error bars are insignificant.
Barnett, L., Di Paolo, E. A., and Bullock, S. (2007) Spatially embedded random networks. Phys. Rev. E., 76, 056115.
Bullock, S., Barnett, L. and Di Paolo, E. A. (2010) Spatial embedding and the structure of complex networks, Complexity, 16(2): 20 – 28, doi:10.1002/cplx.20338.
Ripple-spreading algorithm for network design
Ripple-spreading modelling is a novel approach inspired by the natural ripple-spreading phenomenon on fluid surfaces invented by Xiaobing Hu. It has good potential as an encoding scheme for modeling random complex networks using stochastic optimization and improving the performance of such genetic algorithms for combinatorial optimization problems. Suppose a bunch of stakes are randomly distributed in a quiet water pool. Then a stone is thrown into the pool and an initial ripple is generated from the point where the stone enters the water. When the ripple reaches a stake, a new ripple is generated around the stake due to wave reflection. As the initial stimulating ripple is spreading, more and more responding ripples are stimulated around stakes. This can be used to create connections (e.g., network links) between the spatio-temporaly distributed nodes.
An energy decay model for the spreading ripples can be used to determine connectivity or probabilities of connectivity in stochastic or semi-stochastic versions of the model. The advantage of this idea (also used for optimization problems like multi-objective scheduling in ATC where complex solution encodings create a consistency problem for operators like crossover) is that only a very simple encoding is necessary (the coordinates of the epicentre of the ripple-spreading process). Different networks are created from a same spatial distribution of nodes depending of this initial parameter.
Hu, X-B. Wang, M., Leeson, M. S, Hines, E. L., and Di Paolo, E. A. (2011) A Deterministic Ripple-Spreading Model for Complex Networks, Physical Review E, 83, 046123, doi: 10.1103/PhysRevE.00.006100.
Hu, X-B., Di Paolo E. A. and Barnett, L. (2008). Ripple-spreading model and genetic algorithm for random complex networks: Preliminary study. In The World Congress on Computer Intelligence (WCCI2008), Hong Kong, China, 01-06 June 2008.
EZEQUIEL A. DI PAOLO 