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