Giulio Cimini - Interacting Networks and Communities

Interacting Networks and Communities

Networks observed in nature are often characterised by the presence of densely connected group of nodes, called communities. Finding communities in networks is a challenging task. The first method proposed in the literature is based on the maximization of a quality function, the modularity, which compares the actual number of links in the network inside each community to the expectation of such number under a null network model. Despite its popularity and the many generalizations and extension proposed, modularity suffers from a resolution limit: it cannot find communities smaller than a minimum size (which depends on the scale of the whole system). Another popular branch of community detection methods is based on random walks, with the idea is that communities correspond to network regions where the walker's dynamics spends a relatively long time, because of the high density of links within communities and the sparse connections across communities. This phenomenon leads to the definition of a quality function known as Markov stability, where the time scale of the dynamics acts as a resolution parameter, with short scales leading to many small communities and long scales to a few large communities.

Generalised Markov Stability

In this work we derived a generalised definition of Markov stability, based on the difference between the probability fluxes of a Markov chain on the network at different time scales. The specific implementation of the quality function and the resulting optimal community structure thus become dependent both on the type of Markov process and on the specific Markov times considered. The possibility to use finite-time transition probabilities to define the null model naturally allows the method to detect communities at different resolutions, without the need to consider a continuous-time Markov chain in the small-time limit. Our proposal is grounded on the definition of lumped Markov chains on network partitions, whose stationary distributions follow the same aggregating rules of the dynamics. Thanks to this property the form of the quality function becomes invariant under network partitioning, leading to a self-consistent definition of communities at different aggregation scales. This leads not only to an elegant theoretical formulation of the problem but also to a convenient recursive algorithm for the optimization of the quality function.

Communities of the "Dolphins" network found by generalised Markov stability with standard random walk (a), PageRank (b) and Maximum-entropy random walk (c).

Critical Phenomena on Weakly Interacting Networks

A case of particular interest arises when the number of links between communities is sufficiently small, so that the removal of a few of them can easily separate the communities into isolated modules. Systems of this kind are known as weakly interacting networks (or networks of networks). In this work we proposed a perturbative approach to study the connectivity properties of interacting networks. We focused on the spectrum of the graph Laplacian, which is important to determine both structural properties of the network (connectivity, diameter, number of spanning trees, and so on) as well as dynamical properties such as diffusion and synchronization. We revealed multiple structural transitions for the algebraic connectivity of such systems as inter-community interactions are established, between regimes in which each community keeps its independent identity or drives the diffusive processes over the whole system. Furthermore, we showed that, at first order in perturbation theory, the growth of the algebraic connectivity of each community depends only on the degree configuration of the interaction network (projected on the respective Fiedler vector), and not on the actual interaction topology.

Heat map of the transition for the algebraic connectivity of a weakly interacting network with two random communities. Depending on the region, one or two transitions can be observed.

In this work we focused instead on the percolation properties of weakly interacting networks. Percolation theory is a very successful framework for understanding a broad range of critical phenomena taking place on networks, such as robustness to failures or attacks and spreading of diseases or information. Weakly interacting networks are often characterised by a mixed percolation phase, in which only one or some of the communities do percolate. Both continuous and abrupt phase transition are observed in the size of the giant component. The continuous (second order) transition corresponds to the formation of a giant cluster inside one community, and has a well-defined percolation threshold. The abrupt transition instead corresponds to the merger of coexisting clusters among different communities and is characterised by a remarkable uncertainty in the percolation threshold, which in turns causes an anomalous trend in the observed susceptibility. We characterise the percolation process in terms of a powder keg: due to the scarcity of the interlinks, the aggregation of the coexisting giant clusters is delayed, therefore giving rise to an abrupt percolation transition. We developed a simple mathematical model able to describe this phenomenon and to estimate the critical threshold for which the abrupt transition is more likely to occur.

Susceptibility of the air transportation networks of Lufthansa-Ryainair. χC is the susceptibility of the corresponding non-interacting system and χD is the anomalous value.

Spurious Links Detection

The shape of weakly interacting networks also allows to understand an issue that is typically encountered when trying to remove spurious interactions. Indeed, network data often contain inaccurate and misleading information, resulting in missing and spurious links. The problem of identifying missing interactions, known as link prediction, is very popular and consists in estimating the likelihood of the existence of a link between two nodes according to the observed links and node's attributes. The problem of identifying spurious interactions is trickier, since a spurious link removal error has far more serious consequences than a missing link addition one. If some unexpected links are incorrectly identified as spurious and removed from the network, the system's structure and function may be altered significantly or even compromised. For instance, the network may break up into separate components so that the system's functionality is destroyed. The main challenge for a spurious link detection method is hence to identify the spurious interactions and at the same time to construct a network with close functionalities to the original one.

In this work we showed that many simple spurious links detection methods have indeed the serious drawback to remove real and important links, which causes the networks' structure to be altered significantly. Hence, we propose a hybrid algorithm which combines a similarity-based index known as common neighbors with the edge-betweenness centrality. We show that this method can not only effectively identify and remove spurious links but also prevent the removal of inter-community links that keep the whole system connected, so to preserve the size of the giant component and many important structural and dynamical properties of the network.

Resources

A. Patelli, A. Gabrielli, G. Cimini. Generalized Markov stability of network communities. Physical Review E 101, 052301 (2020)
G. Rapisardi, A. Arenas, G. Caldarelli, G. Cimini. Multiple structural transitions in interacting networks. Physical Review E 98, 012302 (2018)
G. Rapisardi, A. Arenas, G. Caldarelli, and G. Cimini. Fragility and anomalous susceptibility of weakly interacting networks. Physical Review E 99, 042302 (2019)
A. Zeng, G. Cimini. Removing spurious interactions in complex networks. Physical Review E 85, 036101 (2012)

Page updated

Google Sites

Report abuse