Computer Science > Social and Information Networks
[Submitted on 19 May 2016]
Title:Combining Density and Overlap (CoDO): A New Method for Assessing the Significance of Overlap Among Subgraphs
View PDFAbstract: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.
Submission history
From: Shahin Mohammadi [view email][v1] Thu, 19 May 2016 22:24:26 UTC (1,633 KB)
Current browse context:
cs.SI
Change to browse by:
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.