Proceedings of the VLDB Endowment · 2019 · 115 citations · 60 references
ComputingComputer ScienceAlgorithmsComputational BiologyData MiningGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryGraph DatabasesK-core DecompositionSubgraph ExtractionSubgraph Mining
Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph G , DSD aims to find a subgraph D of G with the highest density (e.g., the number of edges over the number of vertices in D ). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that the densest subgraph can be accurately found through a k -core (a kind of dense subgraph of G ), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based- and general pattern-based density. We have performed extensive experimental evaluation on both real and synthetic datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches.
60
Network structure and minimum degree
Stephen B. Seidman · Social Networks · 1983 · 1.9K citations
The H-index of a network node and its relation to degree and coreness
Linyuan Lü, Tao Zhou, Qian-Ming Zhang et al. · Nature Communications · 2016 · 689 citations · Full text
Reachability and Distance Queries via 2-Hop Labels
Edith Cohen, Eran Halperin, Haim Kaplan et al. · SIAM Journal on Computing · 2003 · 508 citations
Querying k-truss community in large and dynamic graphs
Xin Huang, Hong Cheng, Lu Qin et al. · 2014 · 490 citations