 |
Center for Nonlinear Studies |
The existing probabilistic methods have been most successful in the analysis of unstructured random graph instances that express a large degree of statistical independence. Real-world networks do not always respond well to such existing methods: they have multiscale structure imposed by geometry and other intrinsic correlations among nodes and edges. We developed and analyzed a new structured random generative model, the Geographical Threshold Graph model. This is a node-weighted generalization of Random Geometric Graphs, which more accurately characterizes large scale real-world networks. Nodes are distributed in space, and edges are assigned according to a threshold function involving the distance between nodes and randomly chosen node weights. We show how the structural properties, such as connectedness, diameter, existence and absence of the giant component, clustering coefficient, and chromatic number, as well as mixing time, relate to the threshold value and node weight distribution. These values play an important role not only in theory, but also in applications, such as latency in wireless communications, epidemic spread, or job scheduling. We believe that: (i) our work can can spark further theoretical research in modeling and analysis of structured random networks; (ii) the developed tools will lead to new ways to analyze algorithmic performance, and most excitingly, effective new algorithms on networks.
Host: Humberto C Godinez Vazquez, Mathematical Modeling and Analysis Theoretical Division, 5-9188