282. Communication among communities

This is a guest blog post by Massimo Ostilli from the Center of Statistical Mechanics and Complexity (INFM, Roma). Dmitry.

In recent times, in the network science, the problem of detecting the community structure of a given network (a random graph), has attracted more attention. The general idea behind the concept of community structure comes from the observation that, in many situations, real data show an intrinsic partition of the vertices of the graph into groups, called communities, such that between any two communities there is a number of bonds that is relatively small if compared with the number of bonds present in each community. The partition(s) can be used to build a higher-level meta-network where the meta-nodes are now the communities (cells, proteins, groups of people, tec…) and play important roles in unveiling the functional organization inside the network. Given an hypothetical community structure, one of the most important issue is to understand whether or not the communities exchange information and to what extent, and, more in general, what are their correlations. In a recent work, we have emphasized that such a problem cannot be faced through an analysis that takes into account only the network topology (that is, the detailed description of nodes and bonds) that, by its definition, neglects any kind of correlation among the nodes. Nodes, in fact, are the sites where some physical or abstract status manifests as a result of the status of the other nodes. The most elementary example is the case in which at any node there is a dichotomy variable taking values ON and OFF. This happens – for example – in an network in which individuals, in somehow equivalent, are asked to say YES or NO to some politic proposal. The fact that the individuals know, in part, the opinion of the others, makes the answer of each individual partly conditioned by the others, especially, but not only, by those that are near (neighbors) in the social space. Physicists immediately understand that – within the equilibrium statistical mechanics – such a system can be cast by defining a suitable disordered Ising model. In this approach, the temperature can be seen as a parameter describing the freedom of the vertices to assume a state independently of the state of the other vertices, while the Ising couplings between two vertices and belonging to the -th and -th community, respectively, as a tendency of the vertices to be positively or negatively correlated, according to the amplitude and to the sign of . At least in principle, if a Gibbs-Boltzmann distribution with some Hamiltonian has been assumed, one can obtain from the data of the given graph by isolating the two vertices from all vertices of the graph other then them, and by measuring the correlation function of the obtained isolated dimer.

It is well known that many natural, technological and -especially- social networks, display the SMALL-WORLD character, a feature that is perhaps better understood if we make use of the concept of community. For example, the persons living in a same house constitute a community in which they communicate via short-range interactions. However, each person of an house can communicate also to persons living in different and distance houses via long-range interactions. It turns out that, due to these long-range connections, small-world networks have the very nice property to be mean-field, though, due to the fact that there are also short-range connections, the mean-field behavior is special, and an exact quantitative analysis far from being simple. However, as has been shown in arXiv:0809.0606, an Ising model defined on a small-world network, within certain limits, can be exactly analyzed through a generalization of the Curie-Weiss mean-field equation able to takes into account both the infinite and finite dimensional geometry present in the system. More precisely, if the Hamiltonian of the model can be splitted as

,

where has only short-range couplings and has only long-range couplings , then the average magnetization of the system with Hamiltonian (1) obeys the mean-field equation:

,

where

,

is the average magnetization of the non disordered system with Hamiltonian and in the presence of an external field . To solve Eq. (2), therefore, one has to know (analytically or numerically) as a function of an arbitrary external field. More precisely, the above Eq. (2) concerns the case of infinite connectivity and no coupling disorder and it is immediate to check that for one recovers the Curie-Weiss equation. In the geneal case Eq. (2) essentially still holds, provided that the coupling be replaced with an effective coupling given by , where is the connectivity and is the probability distribution of the coupling disorder.

In arXiv:0902.0888, we have generalized the model defined in Eq. (1) to take into account the existence of communities having intra and inter interactions, both short-range and long-range alike. We have then found that the average magnetizations associated to each community, obey effective TAP (Thouless, Anderson and Palmer) equations in which each community plays the role of a single “microscopic”-spin and, depending on the sign of the couplings, behave as spins immersed in a ferro or glassy material. From the TAP equations is then easy, by simple derivation, to obtain the relative susceptibilities which tell us exactly how the communities are correlated. In particular, these correlations can be analyzed to understand how much two given communities exchange informations at and for positive couplings. This limit is very interesting because at there are no dissipation effects so that any signal propagates without loss of energy, and, furthermore, for positive couplings the model is not frustrated so that it can be analyzed by simple annealing procedures even for large sizes. One peculiar aspect that we have discovered is that, unlike the model with only short-range couplings, in the model having also long-range couplings, by a suitable tuning of the connectivities, the exchange of information among communities can undergoes a phase transition after which the communities communicate instantaneously. This scenario takes place at , however the time needed to exchange a bit of information follows essentially the same scaling-law also a finite . More in general, when the couplings are allowed to have arbitrary signs, due to the TAP-like structures of the equations, as is known, there are many metastable solutions whose number grows exponentially fast with . We see therefore that, in our models, the spin-glass landscape scenario takes place in a manner which is not very different to what happens in a spin-glass material (for example a disordered crystal with frustration). However, one difference to be stressed is that the number of independent parameters entering our model is much larger than that of a material and many of these parameters can be changed as to move from one metastable state to another via a virtual (that is not tuned by ) first-order phase transition. So, for example, in a tentative to modeling some aspect of society, in which many communities are negatively correlated, we will find that, by a slight variation of some parameter (size of the communities, inter and intra couplings, connectivities , etc… ), many communities undergo abrupt jumps, confirming, in a sense, the high sensitiveness and unpredictability of societies (stock markets offer a good example).