An information theoretic derivation of spectral graph partitioning

At the APS meeting in 2004, we introduced an information-theoretic algorithm called the ``network information bottleneck" (NIB) for clustering nodes of a network into modules (cf. arxiv.org/q-bio/0411033). Numerical experiments show that, although the modules are found by minimizing a free energy with no references to normalized edge-cuts or numbers of edges between modules, the resulting partitions are both information-modular and edge-modular (exhibiting low normalized edge-cuts). Moreover, the resulting partioning algorithm is competitive both in accuracy and efficiency with methods popular in the physics community. These numerical results along with asymptotic equivalence between the information-optimal and edge-optimal partitionings are presented.