Complexity and Graph Theory: A Brief Note

Santo Fortunato has published an interesting and densly rich article, Community Detection in Graphs, in  Complexity (Inter-Wiley). This article is over 100 pages long, it is relatively complete, with numerous references and excellent figures.

It is a bit surprising, however, that this extensive discussion misses one of the things that would seem to be most important in discussing graphs, and particularly, clusters within graphs: the stability of these clusters. That is; the theoretical basis for cluster stability.

Yedidia et al., in Understanding Belief Propagation, makes the point that there is a close connection between Belief Propagation (BP) and the Bethe approximation of statistical physics. This suggests there is a way to construct new message-passing algorithms. In particular, more general approaches to the work undertaken by Bethe’s approximation, namely  the Cluster Variation Method (CVM) introduced by Kikuchi and later by Kikuchi and Brush, generalize the Bethe approximation. In essence, the free energy is minimized across not only distribution between simple “on” and “off” states, but also across the distribution of physical clusters. This expansion of the entropy concept into cluster distribution (across the available types of clusters) is important.

Free energy minimization provides a natural and intuitive means for determining “equilibrium,” or at least, “reasonably stationary” system states. These would correspond to natural evolutions of communities which can be interpreted as clusters.

Pelizzola, in Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models points out that graph theory subsumes CVM and other approximation methods. This makes graph theory the nexus at which the CVM methods, belief inference, and community-formation “connect.” Or perhaps, they form an interesting “graph community.”

References:

• Fortunato, S. (preprint), “Community Detection in Graphs,” Complexity (July-August, 2010); online as: http://arxiv.org/PS_cache/arxiv/pdf/0906/0906.0612v2.pdf  
• Yedidia, J.S.; Freeman, W.T.; Weiss, Y., “Understanding Belief Propagation and Its Generalizations”, Exploring Artificial Intelligence in the New Millennium, ISBN 1558608117, Chap. 8, pp. 239-236, January 2003 (Science & Technology Books). Also available online as Mitsubishi Electronic Research Laboratories Technical Report MERL TR-2001-22, online as: http://www.merl.com/reports/docs/TR2001-22.pdf
• Kikuchi, R., & Brush, S.G. (1967), “Improvement of the Cluster‐Variation Method,” J. Chem. Phys. 47, 195; online as: http://jcp.aip.org/jcpsa6/v47/i1/p195_s1?isAuthorized=no
• Pelizzola, A. (2005), “Cluster variation method in statistical physics and probabilistic graphical models,” J. Physics A: Mathematical & General, 38 (33) R308;online as: http://iopscience.iop.org/0305-4470/38/33/R01/