Maximum-entropy models for networks

Over the last two decades, the study of networks has been flourishing into a very active and popular discipline, often referred to as "Network Science". This tremendous growth of interest is due to the fact that network theory represents the natural framework to approach (and solve) several problems of scientific and societal relevance: how diseases, crises and opinions spread throughout organisms, economies and societies ultimately depends on the structure of some underlying network that describes how different cells, companies and people are connected together. My presentation is devoted to illustrate how seemingly unrelated challenges encountered in network science have a common theoretical underpinning. For the sake of illustration, I have selected three key problems: pattern detection, network reconstruction and graph combinatorics.

Pattern detection is the identification of empirical properties that systematically deviate from some simple null model (e.g. the unexpectedly large number of triangles forming around some particular nodes). These "surprising" properties are likely to represent important structures emboding non-trivial information about the (unknown) network formation process. In the "Big Data" era dominated by the need of identifying meaningful information in huge streams of noisy data, the importance of pattern detection is becoming recognized as increasingly important.

Network reconstruction is the problem of inferring the unknown structure of a network, given only partial knowledge about some of its structural properties. In many practical situations, network data are privacy-protected: for example, banks only publicly disclose their total exposures towards "all other banks" while the information about "who is connected to whom" is not available. In order to carry out any network-dependent analysis such as the estimation of the level of systemic risk embodied in the interbank market, one has to resort to reconstruction techniques identifying the most likely set of networks compatible with the partial information available.

Graph combinatorics refers to various graph-related operations in discrete mathematics such as sampling of graphs with given topological properties, their enumeration in some appropriate asymptotic limit, etc. While the number of simple undirected graphs with N vertices and L of links can be computed straightforwardly and their set can be sampled efficiently and uniformly for any value of L, counting how many graphs meet some more heterogeneous topological constraint can be a hard task. An important example is the asymptotic enumeration of graphs with a given degree sequence - a problem that, at present, is solved only under stringent conditions on the heterogeneity of degrees. Similarly, sampling this set of graphs uniformly becomes more and more challenging as the heterogeneity of degrees increases.

There are deep connections, of both theoretical and applied nature between the three scientific challenges outlined above: as a consequence, it is possible to define certain problem-specific techniques within a common framework. The unifying notion is that of entropy maximization which will be employed to construct ensembles of graphs whose topology is maximally random, apart from a controlled set of structural properties enforced as constraints. Such ensembles provide a common answer to the problems of the maximally random construction of null models for pattern detection, the maximally unbiased inference of networks from partial information and the maximally uniform sampling of graphs with given constraints.

Programme