2012 MiningCoherentSubgraphsinMultiL

• (Boden et al., 2012) ⇒ Brigitte Boden, Stephan Günnemann, Holger Hoffmann, and Thomas Seidl. (2012). “Mining Coherent Subgraphs in Multi-layer Graphs with Edge Labels.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339726

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Mining+Coherent+Subgraphs+in+Multi-layer+Graphs+with+Edge+Labels
• http://dl.acm.org/citation.cfm?id=2339530.2339726&preflayout=flat#citedby

Quotes

Author Keywords

• Clustering; data mining; dense subgraphs; graph clustering; networks

Abstract

Mining dense subgraphs such as cliques or quasi-cliques is an important graph mining problem and closely related to the notion of graph clustering. In various applications, graphs are enriched by additional information. For example, we can observe graphs representing different types of relations between the vertices. These multiple edge types can also be viewed as different "layers" of the same graph, which is denoted as a “multi-layer graph” in this work. Additionally, each edge might be annotated by a label characterizing the given relation in more detail. By exploiting all these different kinds of information, the detection of more interesting clusters in the graph can be supported.

In this work, we introduce the multi-layer coherent subgraph (MLCS) 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 clusters 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 datasets.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 MiningCoherentSubgraphsinMultiL	Thomas Seidl Stephan Günnemann Brigitte Boden Holger Hoffmann			Mining Coherent Subgraphs in Multi-layer Graphs with Edge Labels				10.1145/2339530.2339726		2012