2015 LocallyDensestSubgraphDiscovery

• (Qin et al., 2015) ⇒ Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. (2015). “Locally Densest Subgraph Discovery.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783299

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Locally+Densest+Subgraph+Discovery
• http://dl.acm.org/citation.cfm?id=2783258.2783299&preflayout=flat#citedby

Quotes

Author Keywords

• Big data; data mining; dense subgraph; graph; graph algorithms

Abstract

Mining dense subgraphs from a large graph is a fundamental graph mining task and can be widely applied in a variety of application domains such as network science, biology, graph database, web mining, graph compression, and micro-blogging systems. Here a dense subgraph is defined as a subgraph with high density (#.edge / #.node). Existing studies of this problem either focus on finding the densest subgraph or identifying an optimal clique-like dense subgraph, and they adopt a simple greedy approach to find the top - k dense subgraph]]s. However, their identified subgraphs cannot be used to represent the dense regions of the graph. Intuitively, to represent a dense region, the subgraph identified should be the subgraph with highest density in its local region in the graph. However, it is non-trivial to formally model a locally densest subgraph. In this paper, we aim to discover top-k such representative locally densest subgraphs of a graph. We provide an elegant parameter-free definition of a locally densest subgraph. The definition not only fits well with the intuition, but is also associated with several nice structural properties. We show that the set of locally densest subgraphs in a graph can be computed in polynomial time. We further propose three novel pruning strategies to largely reduce the search space of the algorithm. In our experiments, we use several real datasets with various graph properties to evaluate the effectiveness of our model using four quality measures and a case study. We also test our algorithms on several real web-scale graphs, one of which contains 118.14 million nodes and 1.02 billion edges, to demonstrate the high efficiency of the proposed algorithms.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 LocallyDensestSubgraphDiscovery	Chengqi Zhang Lu Qin Rong-Hua Li Lijun Chang			Locally Densest Subgraph Discovery				10.1145/2783258.2783299		2015