MiMAG: mining coherent subgraphs in multi-layer graphs with edge labels. Issue 2 (February 2017)

• Record Type: Journal Article
• Authors: Boden, Brigitte; Günnemann, Stephan; Hoffmann, Holger; Seidl, Thomas
• Is Part Of: Knowledge and information systems. Volume 50:Issue 2(2017:Feb.)
• Page Start: 417
• Page End: 446
• Publication Date: 2017-02
• Subjects: Clustering -- Graph -- Network -- Subspace -- Multi-layer graph -- Labels; Expert systems (Computer science) -- Periodicals; Information storage and retrieval systems -- Periodicals; 006.33
• DOI: 10.1007/s10115-016-0949-5
• Languages: English
• ISSNs: 0219-1377

Abstract

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 aredensely connected by edges withsimilar labels in asubset 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.