Combining Density and Overlap (CoDO): A New Method for Assessing the Significance of Overlap Among Subgraphs

Abram Magner, Shahin Mohammadi, Ananth GramaarXiv 2016 · arXiv

Introduction

In network science, identifying clusters—such as social circles or functional protein modules—is a fundamental task. However, real-world networks are rarely composed of disjoint sets; clusters frequently overlap. Determining whether a shared set of nodes between two clusters represents a meaningful functional connection or a mere statistical coincidence is a significant challenge. Traditional methods often fail to capture the full structural context of these overlaps.

To address this, Magner, Mohammadi, and Grama introduced CoDO (Combining Density and Overlap), a statistical framework that quantifies the significance of subgraph overlaps by integrating both node-set size and edge density into a unified $p$-value.

The Limitations of Existing Approaches

Current methods for assessing overlap significance generally fall into two categories, both of which have notable drawbacks:

  1. Size-based (Hypergeometric Tail - HGT): This approach calculates the probability of a specific number of nodes being shared by chance. While computationally simple, it ignores the internal connectivity (edges) within the overlap, missing vital structural information.
  2. Density-based (Erdős-Rényi Density - ERD): This method focuses on the edge density within the overlapping region. However, it often exhibits "sharp transitions," where $p$-values jump from insignificance to extreme significance (e.g., $10^{-70}$) with minor data changes. This lack of "smoothness" makes it difficult to rank or prioritize results in practical applications.

The CoDO Framework

CoDO treats the overlap as a two-part probabilistic experiment. It asks: given two clusters of specific sizes and edge densities, what is the probability that their intersection would be at least as large and at least as dense as observed?

By considering the sizes and densities of the constituent subgraphs, CoDO provides a context-aware measure. The authors derived a closed-form mathematical expression for this $p$-value, allowing for efficient computation without the need for slow Monte Carlo simulations.

Comparison of p-values for HGT, ERD, and CoDO across different overlap scenarios.

As shown in the figure above, CoDO acts as a bridge between HGT and ERD. In cases of significant overlap but low density (panel c), it tracks closely with HGT. In cases of low overlap but high density (panel b), it provides a more moderate, discriminative $p$-value than the extreme results of ERD, which often drops to near zero.

Experimental Validation

The authors validated CoDO using synthetic graphs and real-world datasets from social and biological domains:

  • Social Networks: Using ego networks from Facebook, Google+, and Twitter, CoDO outperformed HGT and ERD in predicting meaningful overlaps (defined by shared user features), achieving AUC scores as high as 0.878.
  • Biological Systems: In a human protein-protein interaction (PPI) network, CoDO's $p$-values showed a much stronger correlation (0.41) with functional relatedness (co-transcriptional activity) than HGT (0.28) or ERD (0.16). It successfully identified significant "crosstalk" between critical pathways, such as Immune Response and Cancer Signaling.

Conclusion and Future Directions

CoDO offers a robust, "best-of-both-worlds" approach to subgraph overlap analysis. Its ability to provide smooth, discriminative $p$-values makes it a powerful tool for ranking interactions in complex networks. Future work includes adapting the framework for non-random background models (e.g., power-law graphs) and developing search algorithms that utilize CoDO to discover significant overlapping communities directly.

Summary updated

Abstract

Algorithms for detecting clusters (including overlapping clusters) in graphs have received significant attention in the research community. A closely related important aspect of the problem -- quantification of statistical significance of overlap of clusters, remains relatively unexplored. This paper presents the first theoretical and practical results on quantifying statistically significant interactions between clusters in networks. Such problems commonly arise in diverse applications, ranging from social network analysis to systems biology. The paper addresses the problem of quantifying the statistical significance of the observed overlap of the two clusters in an Erdős-Rényi graph model. The analytical framework presented in the paper assigns a $p$-value to overlapping subgraphs by combining information about both the sizes of the subgraphs and their edge densities in comparison to the corresponding values for their overlapping component. This $p$-value is demonstrated to have excellent discrimination properties in real applications and is shown to be robust across broad parameter ranges. Our results are comprehensively validated on synthetic, social, and biological networks. We show that our framework: (i) derives insight from both the density and the size of overlap among communities (circles/pathways), (ii) consistently outperforms state-of-the-art methods over all tested datasets, and (iii) when compared to other measures, has much broader application scope. In the context of social networks, we identify highly interdependent (social) circles and show that our predictions are highly co-enriched with known user features. In networks of biomolecular interactions, we show that our method identifies novel cross-talk between pathways, sheds light on their mechanisms of interaction, and provides new opportunities for investigations of biomolecular interactions.
BibTeX
@misc{magner2016combining,
  author = {Abram Magner and Shahin Mohammadi and Ananth Grama},
  title = {{Combining Density and Overlap (CoDO): A New Method for Assessing the Significance of Overlap Among Subgraphs}},
  year = {2016},
  eprint = {1605.06167},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.06167},
}
Figure