MiMAG: mining coherent subgraphs in multi-layer graphs with edge labels

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

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

10 Zitate (Scopus)

Abstract

Detecting dense subgraphs such as cliques or quasi-cliques is an important graph mining problem. While this task is established for simple graphs, today’s applications demand the analysis of more complex graphs: In this work, we consider a frequently observed type of graph where edges represent different types of relations. These multiple edge types can also be viewed as different “layers” of a graph, which is denoted as a “multi-layer graph”. Additionally, each edge might be annotated by a label characterizing the given relation in more detail. By simultaneously exploiting all this information, the detection of more interesting subgraphs can be supported. We introduce the multi-layer coherent subgraph model, which defines clusters of vertices that are densely connected by edges with similar labels in a subset of the graph layers. We avoid redundancy in the result by selecting only the most interesting, non-redundant subgraphs for the output. Based on this model, we introduce the best-first search algorithm MiMAG. In thorough experiments, we demonstrate the strengths of MiMAG in comparison with related approaches on synthetic as well as real-world data sets.

OriginalspracheEnglisch
Seiten (von - bis)417-446
Seitenumfang30
FachzeitschriftKnowledge and Information Systems
Jahrgang50
Ausgabenummer2
DOIs
PublikationsstatusVeröffentlicht - 1 Feb. 2017

Fingerprint

Untersuchen Sie die Forschungsthemen von „MiMAG: mining coherent subgraphs in multi-layer graphs with edge labels“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren