Back to Search
Start Over
Fully Dynamic Algorithm for Top- k Densest Subgraphs
- Source :
- CIKM
- Publication Year :
- 2017
- Publisher :
- ACM, 2017.
-
Abstract
- Given a large graph, the densest-subgraph problem asks to find a subgraph with maximum average degree. When considering the top-$k$ version of this problem, a na\"ive solution is to iteratively find the densest subgraph and remove it in each iteration. However, such a solution is impractical due to high processing cost. The problem is further complicated when dealing with dynamic graphs, since adding or removing an edge requires re-running the algorithm. In this paper, we study the top-$k$ densest-subgraph problem in the sliding-window model and propose an efficient fully-dynamic algorithm. The input of our algorithm consists of an edge stream, and the goal is to find the node-disjoint subgraphs that maximize the sum of their densities. In contrast to existing state-of-the-art solutions that require iterating over the entire graph upon any update, our algorithm profits from the observation that updates only affect a limited region of the graph. Therefore, the top-$k$ densest subgraphs are maintained by only applying local updates. We provide a theoretical analysis of the proposed algorithm and show empirically that the algorithm often generates denser subgraphs than state-of-the-art competitors. Experiments show an improvement in efficiency of up to five orders of magnitude compared to state-of-the-art solutions.<br />Comment: 10 pages, 8 figures, accepted at CIKM 2017
- Subjects :
- FOS: Computer and information sciences
ta113
Theoretical computer science
Degree (graph theory)
Computer science
Contrast (statistics)
02 engineering and technology
Graph
Orders of magnitude (bit rate)
Dynamic problem
020204 information systems
Sliding window protocol
Computer Science - Data Structures and Algorithms
0202 electrical engineering, electronic engineering, information engineering
Data Structures and Algorithms (cs.DS)
020201 artificial intelligence & image processing
Enhanced Data Rates for GSM Evolution
Algorithm
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 2017 ACM on Conference on Information and Knowledge Management
- Accession number :
- edsair.doi.dedup.....0d766ff3879728b8ba07af6f1a3807be