Biclique communities

Sune Lehmann, Martin Schwartz, Lars Kai HansenPhysical 2008 · DOI

TL;DR

This paper introduces a novel method for detecting communities in bipartite networks by extending the k-clique community detection algorithm. This "biclique community" approach preserves crucial structural information lost in traditional one-mode projections, offering greater flexibility and insight into complex relationships within bipartite data.

What Problem Does This Paper Address?

Understanding community structure – how nodes in a network group together into densely connected modules with sparse connections between them – is a fundamental challenge in network science. While significant progress has been made for unipartite (single-set) networks, bipartite networks (networks with two distinct sets of nodes, where links only connect nodes from different sets) have been less explored. Many real-world networks, such as scientific collaboration networks (authors and papers), social networks (actors and movies), and biological networks (genes and diseases), are inherently bipartite.

A common approach to analyze bipartite networks is to "project" them into unipartite networks. However, this process discards valuable information. For instance, two different bipartite network structures can result in identical unipartite projections, making it impossible to distinguish them. This loss of information can lead to an incomplete understanding of the underlying community structure. The authors aim to address this by developing a method that directly analyzes bipartite networks, retaining more structural detail.

Methods

The core of the paper is the introduction of the "biclique community detection" algorithm. This method is an extension of the k-clique community detection algorithm, which identifies communities as overlapping k-cliques (complete subgraphs of size k).

The biclique approach works by:

  1. Identifying Maximal Bicliques: It first finds all maximal bicliques within the bipartite network. A biclique is a complete bipartite subgraph, denoted as $K_{a,b}$, meaning it has $a$ nodes from one set and $b$ nodes from the other, with all possible links between them.
  2. Constructing Overlap Matrices: Two matrices are created to represent the overlap between these maximal bicliques. One matrix ($L_A$) captures how bicliques share nodes from the first set (e.g., authors), and the other ($L_\Gamma$) captures overlap in the second set (e.g., papers).
  3. Thresholding Overlap Matrices: Crucially, the algorithm allows for independent thresholding of these overlap matrices. This means one can set different thresholds for the number of shared nodes from each set ($a$ and $b$). This provides a flexible way to probe communities at different resolutions and with varying emphasis on the two node sets.
  4. Finding Connected Components: Finally, connected components in the thresholded overlap matrices are identified. Each connected component represents a biclique community.

This method retains the advantages of the k-clique algorithm, such as allowing overlapping communities, and adds the ability to analyze bipartite structure directly, avoiding the information loss of one-mode projections.

Datasets

The authors evaluate their method using real-world bipartite networks:

  • IMDb network: A network of actors and movies.
  • Cond-mat network: A scientific collaboration network of authors and papers from the arXiv database.

They also use randomized versions of these networks to demonstrate the significance of the structural features captured by their method.

Key Insights and Ideas

  • One-mode projections are lossy: The paper powerfully illustrates how projecting bipartite networks into unipartite ones can obscure crucial structural differences, leading to potentially misleading community analyses. The example with three distinct bipartite networks yielding identical one-mode projections is particularly striking.
  • Bipartite structure offers richer context: Analyzing bipartite networks directly provides "context" for communities. For example, in a scientific collaboration network, a community of authors is naturally accompanied by the papers they've co-authored, offering a clearer understanding of why they form a community.
  • Flexible community definition: The ability to set independent thresholds ($a$ and $b$) for the two node sets in $K_{a,b}$ communities allows for a nuanced exploration of network structure. This means researchers can look for communities of many authors working on few papers, or vice versa, revealing different facets of collaboration.
  • Overlapping communities are natural: The method naturally handles overlapping communities, reflecting the reality of many real-world scenarios where individuals or entities participate in multiple groups.

Key Results

The paper demonstrates that the biclique community detection algorithm can:

  • Retain important structural information: Unlike one-mode projections, it distinguishes between bipartite networks that appear identical in their projected forms.
  • Provide context for communities: The identified biclique communities inherently link nodes from both sets, offering a richer understanding of their relationships.
  • Offer enhanced flexibility: Independent thresholds for $a$ and $b$ allow for targeted analysis of different types of bipartite relationships.
  • Be computationally manageable: For sparse real-world networks, the algorithm's complexity is manageable, with maximal biclique enumeration being the most computationally intensive step, but efficient algorithms exist. The authors provide a tool called BCFinder for practical application.

Limitations and Future Work

  • NP-completeness: The problem of enumerating maximal bicliques is NP-complete. While efficient algorithms exist for sparse networks, performance might degrade on very dense graphs.
  • Threshold selection: While the flexibility of $a$ and $b$ is a strength, selecting the "optimal" thresholds for a given analysis might require further investigation and domain expertise.
  • Future work: The authors suggest that this method will be of practical importance in various fields with bipartite networks, including biological networks, affiliation networks, and information networks. They also hint at further exploration of "biclique motifs" in a forthcoming paper.

Summary updated

Abstract

We present a method for detecting communities in bipartite networks. Based on an extension of the k -clique community detection algorithm, we demonstrate how modular structure in bipartite networks presents itself as overlapping bicliques. If bipartite information is available, the biclique community detection algorithm retains all of the advantages of the k -clique algorithm, but avoids discarding important structural information when performing a one-mode projection of the network. Further, the biclique community detection algorithm provides a level of flexibility by incorporating independent clique thresholds for each of the nonoverlapping node sets in the bipartite network.
BibTeX
@inproceedings{lehmann2008biclique,
  author = {Sune Lehmann and Martin Schwartz and Lars Kai Hansen},
  title = {{Biclique communities}},
  booktitle = {Physical},
  year = {2008},
  doi = {10.1103/physreve.78.016108},
}
Figure