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

详细信息    查看全文

• 作者：Brigitte Boden ; Stephan Günnemann ; Holger Hoffmann…
• 关键词：Clustering ; Graph ; Network ; Subspace ; Multi ; layer graph ; Labels
• 刊名：Knowledge and Information Systems
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：50
• 期：2
• 页码：417-446
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Information Systems and Communication Service; IT in Business;
• 出版者：Springer London
• ISSN：0219-3116
• 卷排序：50

文摘

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.