Communication and correlation among communities

Abstract

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 in [Phys. Rev. E 78, 031102] (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 short-cuts 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. For a short presentation of the main result see arXiv:0812.0608.

29 pages, 5 figures

References in corpus (29)

• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Evolution of networks
• Critical phenomena in complex networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• The Bethe lattice spin glass revisited
• Detecting fuzzy community structures in complex networks with a Potts model
• Clique percolation in random networks
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Ising Model on Networks with an Arbitrary Distribution of Connections
• Robustness of community structure in networks
• Detecting communities in large networks
• Exact solution of site and bond percolation on small-world networks
• The Fractal Properties of Internet
• Loop series for discrete statistical models on graphs
• Percolation and epidemics in a two-dimensional small world
• Nonequilibrium Phase Transitions in Directed Small-World Networks
• Exact solutions for diluted spin glasses and optimization problems
• How to Compute Loop Corrections to Bethe Approximation
• Replicated Transfer Matrix Analysis of Ising Spin Models on `Small World' Lattices
• Loop expansion around the Bethe-Peierls approximation for lattice models
• Mean field dilute ferromagnet I. High temperature and zero temperature behavior
• Antiferromagnetic Ising model in small-world networks
• Replica symmetry breaking in the `small world' spin glass
• Effective field theory for models defined over small-world networks. First and second order phase transitions
• Replica-symmetric solutions of a dilute Ising ferromagnet in a random field
• Ising spin glass models versus Ising models: an effective mapping at high temperature I. General result
• Diluted antiferromagnet in a ferromagnetic enviroment

Cited by in corpus (9)

• The unreasonable effectiveness of tree-based theory for networks with clustering
• Critical behavior and correlations on scale-free small-world networks. Application to network design
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Phase diagram and metastability of the Ising model on two coupled networks
• Sandpile cascades on interacting tree-like networks
• Long-time tails in sheared fluids
• Emergence of chaos in interacting communities
• Small-world of communities: communication and correlation of the meta-network
• Criticality and Chaos in Systems of Communities