APS March Meeting 2016
Volume 61, Number 2
Monday–Friday, March 14–18, 2016;
Session Y12: Inference in Complex Networks
11:15 AM–2:15 PM,
Friday, March 18, 2016
Chair: Adilson Motter, Northwestern Unviersity
Abstract ID: BAPS.2016.MAR.Y12.5
Abstract: Y12.00005 : Clustering means geometry in networks
1:39 PM–2:15 PM
Using maximum-likelihood estimation techniques, any real network data can be fit to essentially any network model, inferring the most likely values of the model parameters for the network. However there is one caveat. The results of such fitting are not spurious but meaningful and predictive, only if the network is a typical network in the unbiased ensemble of random graphs with the inferred values of model parameters. Therefore, given a particular combination of a real network and a model, the first question one has to answer is what structural properties of the network ensure that this network is a typical element in the ensemble of random graphs defined by the model. This question is usually highly intractable, explaining why it is almost never answered before the fitting/inference task is performed.
Inspired by recent observations that random geometric graphs reproduce many structural and dynamical properties of a variety of real networks, we find the network structural properties that guarantee that networks that have these properties are in fact geometric, meaning that latent space network models are their true models. Specifically we prove that peculiar organization of clustering observed in real networks is one of the main such properties. In other words, maximum-entropy random graphs with specific clustering properties, which are quite different from the clustering properties of random graphs in the Strauss model, are actually soft random geometric graphs with a specific form of the connection probability function. Using this function we can then infer the coordinates of nodes in a latent space for any given network, and reliably check if the network is a typical network in the resulting ensemble of soft random geometric graphs. If it is, then the inferred coordinates are meaningful and real, and can be used for prediction tasks with proved guarantees that the results of such predictions are reliable and not just transient artifacts.
To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2016.MAR.Y12.5