Bilkent University
Department of Computer Engineering
S E M I N A R
Streaming Algorithms for k-core Decomposition
Ahmet Erdem Sariyüce
Ph.D. Student
Ohio State UniversityA k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction and visualization, and solving NP-Hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for streaming graph data. In this talk, I will introduce the incremental k-core decomposition algorithms we proposed for streaming graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values has to be updated, and efficiently process this subgraph to update the k-core decomposition. Our results show a significant reduction in run-time compared to non-incremental alternatives. We show the efficiency of our algorithms on different types of real and synthetic graphs, at different scales. For a graph of 16 million vertices, we observe speedups reaching a million times, relative to the non-incremental algorithms.
DATE: 06 November, 2012, Tuesday @ 13:40
PLACE: EA-409