Communicability and multipartite structures in complex networks at negative absolute temperatures

Ernesto Estrada, Desmond J. Higham, Naomichi HatanoPhysical 2008 · DOI · arXiv

Abstract

This paper presents a novel method for identifying multipartite subgraphs in complex networks by extending the concept of network communicability. While communicability at positive temperatures is a proven tool for community detection, we demonstrate that communicability at negative absolute temperatures effectively identifies multipartite structures. In this regime, the communicability between two nodes is positive if they belong to the same partition and negative if they do not. This approach allows for the discovery of "quasi-multipartite" structures in real-world systems where inter-community connections significantly outweigh intra-community links. We validate this method using synthetic graphs and empirical datasets, including food webs, protein-protein interaction networks, and neuronal maps.

Introduction

In network science, research typically focuses on identifying communities—clusters of nodes with dense internal connections. However, many biological and ecological systems exhibit the opposite organization: multipartite structures. In a bipartite network, for instance, nodes are divided into two sets where edges only exist between the sets, not within them. Examples include food webs (predators and prey), protein-protein interaction (PPI) networks (complementary binding domains), and buyer-seller marketplaces.

Detecting these structures is mathematically challenging, especially when they are "quasi-multipartite"—containing a small number of internal edges that act as noise. This paper introduces a parameter-free method to uncover these hidden organizational patterns by applying a physics-inspired concept: negative absolute temperature.

Methodology: The Physics of Repulsion

Network Communicability

Network communicability measures the ease with which information flows between two nodes by counting all possible walks between them, weighting shorter walks more heavily. Mathematically, this is expressed through the matrix exponential of the adjacency matrix $\mathbf{A}$:

$$G_{pq} = [e^{\beta \mathbf{A}}]_{pq}$$

where $\beta$ represents the inverse temperature.

The Negative Temperature Shift

In traditional community detection, $\beta$ is positive, representing an "attractive" force that groups nodes into cliques. The authors propose setting $\beta$ to a negative value (specifically $\beta = -1$). This shift effectively treats connected nodes as "repelling" one another.

The logic relies on the Taylor expansion of $e^{-\mathbf{A}}$, which alternates signs for even and odd walk lengths. In a bipartite graph, any walk starting and ending in the same partition must have an even number of steps, while walks between different partitions must have an odd number of steps. By using a negative temperature, the algorithm ensures that nodes sharing many even-length walks (structural equivalents) have positive communicability, while those connected by odd-length walks have negative communicability.

The Node-Repulsion Graph

To identify the partitions, the authors construct a "node-repulsion graph" where an edge exists between two nodes only if their communicability at $\beta = -1$ is positive. They then apply the Bron-Kerbosch algorithm to find maximal cliques in this new graph. These cliques correspond to the distinct partitions of the original multipartite network.

Empirical Results

Food Webs and Ecological Niche

The method was applied to the Canton Creek food web, a network of 108 species in a New Zealand stream. The algorithm successfully identified two primary quasi-bipartite clusters. Remarkably, 97.2% of all trophic links in the network occurred between these two clusters, with only 2.8% being internal "noise" links. This demonstrates the method's robustness in identifying functional roles in ecology.

Protein-Protein Interactions (PPI)

In the Kaposi sarcoma-associated herpesvirus (KSHV) PPI network, the algorithm identified 34 small quasi-partite clusters that resolved into two large, disjoint sets containing 78% of the total proteins. This "orthogonality" suggests a high degree of functional specialization, where proteins interact across groups to perform viral functions rather than clustering into self-contained modules.

Neuronal Networks

When tested on the C. elegans neuronal network (280 neurons), the algorithm found over 43,000 tiny clusters. This lack of large-scale multipartite structure confirms previous findings that the worm's synaptic map is "super-homogeneous," lacking the distinct bipartite organization seen in food webs or specialized PPI networks.

Discussion and Limitations

While the negative temperature approach is highly effective for medium-sized networks, it faces computational hurdles. The Bron-Kerbosch algorithm is NP-hard, which may limit the method's application to massive social networks without further optimization. Additionally, while $\beta = -1$ serves as a robust default, the authors note that the limit as $T \to -0$ (very large negative $\beta$) is dominated by the lowest eigenvalue of the adjacency matrix, suggesting that different "resolutions" of multipartite structure could be explored by varying the temperature.

Conclusion

By flipping the sign of the interaction strength, we can transition from finding communities of "friends" to finding groups of "structural equivalents." This negative temperature framework provides a mathematically elegant and physically grounded way to detect multipartite organization in complex systems, offering new insights into the functional architecture of biological and ecological networks.

Summary updated

Abstract

We here present a method of clearly identifying multipartite subgraphs in a network. The method is based on a recently introduced concept of the communicability, which very clearly identifies communities in a complex network. We here show that, while the communicability at a positive temperature is useful in identifying communities, the communicability at a negative temperature is useful in identifying multipartite subgraphs; the latter quantity between two nodes is positive when the two nodes belong to the same subgraph and is negative when they do not. The method is able to discover "almost" multipartite structures, where intercommunity connections vastly outweigh intracommunity connections. We illustrate the relevance of this work to real-life food web and protein-protein interaction networks.
BibTeX
@inproceedings{estrada2008communicability,
  author = {Ernesto Estrada and Desmond J. Higham and Naomichi Hatano},
  title = {{Communicability and multipartite structures in complex networks at negative absolute temperatures}},
  booktitle = {Physical},
  year = {2008},
  doi = {10.1103/physreve.78.026102},
}
Figure