RMiCS: A robust approach for mining coherent subgraphs in edge-labeled multi-layer graphs

Brigitte Boden, Stephan Günnemann, Holger Hoffmann, Thomas Seidl

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations

Abstract

Detecting dense subgraphs in a large graph is an important graph mining problem and various approaches have been proposed for its solution. While most existing methods only consider unlabeled and one-dimensional graph data, many real-world applications provide far richer information. Thus, in our work, we consider graphs that contain different types of edges - represented as different layers/dimensions of a graph - as well as edge labels that further characterize the relations between two vertices. We argue that exploiting this additional information supports the detection of more interesting clusters. In general, we aim at detecting clusters of vertices that are densely connected by edges with similar labels in subsets of the graph layers. So far, there exists only a single method that tries to detect clusters in such graphs. This method, however, is highly sensitive to noise: already a single edge with a deviating label can completely hinder the detection of interesting clusters. In this paper, we present the RCS (Robust Coherent Subgraph) model which enables us to detect clusters even in noisy data. This robustness greatly enhances the applicability on real-world data. In order to obtain interpretable results, RCS avoids redundant clusters in the result set. We present the algorithm RMiCS for an efficient detection of RCS clusters and we analyze its behavior in various experiments on synthetic and real-world data.

Original languageEnglish
Title of host publicationSSDBM 2013 - Proceedings of the 25th International Conference on Scientific and Statistical Database Management
DOIs
StatePublished - 2013
Externally publishedYes
Event25th International Conference on Scientific and Statistical Database Management, SSDBM 2013 - Baltimore, MD, United States
Duration: 29 Jul 201331 Jul 2013

Publication series

NameACM International Conference Proceeding Series

Conference

Conference25th International Conference on Scientific and Statistical Database Management, SSDBM 2013
Country/TerritoryUnited States
CityBaltimore, MD
Period29/07/1331/07/13

Keywords

  • Dense subgraphs
  • Graph clustering
  • Networks
  • Noise robust

Fingerprint

Dive into the research topics of 'RMiCS: A robust approach for mining coherent subgraphs in edge-labeled multi-layer graphs'. Together they form a unique fingerprint.

Cite this