Communication and correlation among communities

Given a network and a partition in communities, we consider the issues “how communities influence each other” and “when two given communities do communicate.” Specifically, we address these questions in the context of small-world networks, where an arbitrary quenched graph is given and long-range connections are randomly added. We prove that, among the communities, a superposition principle applies and gives rise to a natural generalization of the effective field theory already presented by M. Ostilli and J. F. F. Mendes [Phys. Rev. E 78, 031102 (2008)] $(n=1)$, which here $(n>1)$ consists in a sort of effective TAP (Thouless, Anderson, and Palmer) equations in which each community plays the role of a microscopic spin. The relative susceptibilities derived from these equations calculated at finite or zero temperature, where the method provides an effective percolation theory, give us the answers to the above issues. Unlike the case $n=1$, asymmetries among the communities may lead, via the TAP-like structure of the equations, to many metastable states whose number, in the case of negative shortcuts among the communities, may grow exponentially fast with $n$. As examples we consider the $n$ Viana-Bray communities model and the $n$ one-dimensional small-world communities model. Despite being the simplest ones, the relevance of these models in network theory, as, e.g., in social networks, is crucial and no analytic solution were known until now. Connections between percolation and the fractal dimension of a network are also discussed. Finally, as an inverse problem, we show how, from the relative susceptibilities, a natural and efficient method to detect the community structure of a generic network arises.

Figure 1

(Color online) Solution of self-consistent system (24) for the CW model in the symmetric case $n=2$ with $J^{(1,1)}=0$ and $J^{(1,2)}=2.5$ or $-J^{(1,2)}=2.5$. There is only one critical temperature located at $T_c=2.5$. Note that here we plot all the possible solutions. For $J^{(1,2)}>0$, $m^{(\mathrm{F};1)}$ and $m^{(\mathrm{F};2)}$ (continuous lines) are parallel and coincide, whereas for $J^{(1,2)}<0$ they are antiparallel. The plot of $\det \left(A\right)$ (dashed line) represents the stability curve—under iteration—of the solution $(m^{(\mathrm{F};1)},m^{(\mathrm{F};2)})$, Eq. (44), and similarly the plot of $\det \left(A_0\right)$ represents the stability curve for the trivial solution $m^{(\mathrm{F};1)}=m^{(\mathrm{F};2)}=0$; in the case of only mutual interactions the two coincide: $\det \left(A\right)=\det \left(A_0\right)$. Clearly, in this example, for $T<T_c$, no solution results stable under iteration. We plot also the free energy term $L$ (dotted line) applied, via Eq. (38), to the nontrivial solution $(m^{(\mathrm{F};1)},m^{(\mathrm{F};2)})$. The free energy term $L$ obtained applied instead to the trivial solution $m^{(\mathrm{F};1)}=m^{(\mathrm{F};2)}=0$ is a constant (for more details about the CW model see Sec. 7), $L=L_0=-\log \left(2\right)$ and is plotted only in the region where the trivial solution is the unique (and—of course—stable) solution.

Figure 2

(Color online) Solution of self-consistent system (24) for the CW model in the symmetric case $n=2$ with $J^{(1,1)}=2$ and $J^{(1,2)}=2.5$, or $J^{(1,2)}=-2.5$. Note that here we plot all the possible solutions. For $J^{(1,2)}>0$, $m^{(\mathrm{F};1)}$ and $m^{(\mathrm{F};2)}$ (stars) are parallel, whereas for $J^{(1,2)}<0$ they are antiparallel. The several branches of $\det \left(A\right)$ (circles) represent the stability—under iteration—of the several nontrivial solutions $(m^{(\mathrm{F};1)},m^{(\mathrm{F};2)})$, Eq. (44), and similarly the plot of $\det \left(A_0\right)$ (dashed line) represents the stability for the trivial solution $m^{(\mathrm{F};1)}=m^{(\mathrm{F};2)}=0$. We plot also the several branch’s of the free energy term $L$ (squares) applied, via Eq. (38), to the several solutions. Here Eqs. (55, 56) give two instability points at the temperatures $T_{c1}=2.5$ and $T_{c2}=1.5$. In the thermodynamic limit, only $T_{c1}$ corresponds to a true critical temperature, whereas the other corresponds to a metastable solution. Furthermore we see another metastable solution at $T_{c3}=1.18$ featured as two broken symmetries where $(m^{(\mathrm{F};1)},m^{(\mathrm{F};2)})$ do not transit around 0, but around the values $\pm 0.67$.

Figure 3

(Color online) Solution of self-consistent system (24) for the CW model in the symmetric case $n=3$ with $J^{(1,1)}=3$ and $J^{(1,2)}=0.5$. Note that here we plot all the possible solutions. We plot also the several branches of the free energy term $L$ applied, via Eq. (38), to the several solutions. Here Eqs. (55, 56) give two instability points at the temperatures $T_{c1}=4$ and $T_{c2}=2.5$. In the thermodynamic limit, only $T_{c1}$ corresponds to a true critical temperature, whereas the other corresponds to a metastable solution. Furthermore we see another metastable solution at $T_{c3}=1.32$ featured as two broken symmetries where $(m^{(\mathrm{F};1)},m^{(\mathrm{F};2)},m^{(\mathrm{F};3)})$ do not transit around 0, but around the values $\pm 0.75$.

Figure 4

(Color online) Solution of self-consistent system (24) for the CW model in the symmetric case $n=3$ with $J^{(1,1)}=3$ and $J^{(1,2)}=-0.5$. Note that here we plot all the possible solutions. We plot also the several branches of the free energy term $L$ applied, via Eq. (38), to the several solutions. Here Eqs. (55, 56) give two instability points at the temperatures $T_{c1}=3.5$ and $T_{c2}=2$. In the thermodynamic limit, only $T_{c1}$ corresponds to a true critical temperature, whereas the other corresponds to a metastable solution. We see further metastable solutions at $T_{c3}=1.6$. with multiple broken symmetries where $(m^{(\mathrm{F};1)},m^{(\mathrm{F};2)},m^{(\mathrm{F};3)})$ do not transit around 0, but around the values $\pm 0.75$ and $\pm 0.80$.

Figure 5

(Color online) Solutions of self-consistent system (24) for the VB model $n=2$ with couplings $J^{(1,1)}=1$, $J^{(2,2)}=-1$ and $J^{(1,2)}=-1$ or $J^{(1,2)}=1$, and connectivities $c^{(1,1)}=2$, $c^{(2,2)}=2$, and $c^{(1,2)}=0$ (empty squares for $m^{(\mathrm{F};1)}$ and continuous line for $m^{(\mathrm{F};2)}$) or $c^{(1,2)}=1$ (stars for $m^{(\mathrm{F};1)}$ and circles for $m^{(\mathrm{F};2)}$). We plot also the free energy terms $L$ (rhombus and filled squares for the two cases).