Distributed k-core decomposition and maintenance in large dynamic graphs

Sabeur Aridhi, Martin Brugnara, Alberto Montresor, Yannis Velegrakis

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

18 Citations (Scopus)

Abstract

Distributed processing of large, dynamic graphs has recently received considerable attention, especially in domains such as the analytics of social networks, web graphs and spatial networks. k-core decomposition is one of the significant figures of merit that can be analyzed in graphs. Efficient algorithms to compute k-cores exist already, both in centralized and decentralized setting. Yet, these algorithms have been designed for static graphs, without significant support to deal with the addition or removal of nodes and edges. Typically, this challenge is handled by re-executing the algorithm again on the updated graph. In this work, we propose distributed k-core decomposition and maintenance algorithms for large dynamic graphs. The proposed algorithms exploit, as much as possible, the topology of the graph to compute all the k-cores and maintain them in streaming settings where edge insertions and removals happen frequently. The key idea of the maintenance strategy is that whenever the original graph is updated by the insertion/deletion of one or more edges, only a limited number of nodes need their coreness to be re-evaluated. We present an implementation of the proposed approach on top of the akka framework, and experimentally show the efficiency of our approach in the case of large dynamic networks.

Original languageEnglish
Title of host publicationDEBS 2016 - Proceedings of the 10th ACM International Conference on Distributed and Event-Based Systems
PublisherACM
Pages161-168
Number of pages8
ISBN (Electronic)9781450340212
DOIs
Publication statusPublished - 13 Jun 2016
MoE publication typeA4 Article in a conference publication
EventACM International Conference on Distributed and Event-Based Systems - Irvine, United States
Duration: 20 Jun 201624 Jun 2016
Conference number: 10

Conference

ConferenceACM International Conference on Distributed and Event-Based Systems
Abbreviated titleDEBS
CountryUnited States
CityIrvine
Period20/06/201624/06/2016

Keywords

  • AKKA framework
  • Distributed K-core decomposition
  • Dynamic graphs
  • K-core maintenance

Fingerprint Dive into the research topics of 'Distributed k-core decomposition and maintenance in large dynamic graphs'. Together they form a unique fingerprint.

Cite this