Finding Dense Subgraphs in Relational Graphs
Abstract
This paper considers the problem of finding large dense subgraphs in relational graphs, i.e., a set of graphs which share a common vertex set. We present an approximation algorithm for finding the densest common subgraph in a relational graph set based on an extension of Charikar’s method for finding the densest subgraph in a single graph. We also present a simple greedy heuristic which can be implemented efficiently for analysis of larger graphs. We give graph dependent bounds on the quality of the solutions returned by our methods. Lastly, we show by empirical evaluation on several benchmark datasets that our method out-performs existing approaches.
Cite
Text
Jethava and Beerenwinkel. "Finding Dense Subgraphs in Relational Graphs." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2015. doi:10.1007/978-3-319-23525-7_39Markdown
[Jethava and Beerenwinkel. "Finding Dense Subgraphs in Relational Graphs." European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, 2015.](https://mlanthology.org/ecmlpkdd/2015/jethava2015ecmlpkdd-finding/) doi:10.1007/978-3-319-23525-7_39BibTeX
@inproceedings{jethava2015ecmlpkdd-finding,
title = {{Finding Dense Subgraphs in Relational Graphs}},
author = {Jethava, Vinay and Beerenwinkel, Niko},
booktitle = {European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases},
year = {2015},
pages = {641-654},
doi = {10.1007/978-3-319-23525-7_39},
url = {https://mlanthology.org/ecmlpkdd/2015/jethava2015ecmlpkdd-finding/}
}