Skip to Main content Skip to Navigation
Conference papers

Distributed k-core decomposition and maintenance in large dynamic graphs

Sabeur Aridhi 1, 2, 3 Martin Brugnara 3 Alberto Montresor 3 Yannis Velegrakis 3
1 CAPSID - Computational Algorithms for Protein Structures and Interactions
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : Distributed processing of large, dynamic graphs has recentlyreceived considerable attention, especially in domains suchas the analytics of social networks, web graphs and spatialnetworks.k-core decomposition is one of the significant fig-ures of merit that can be analyzed in graphs. Efficient algo-rithms to computek-cores exist already, both in centralizedand decentralized setting. Yet, these algorithms have beendesigned for static graphs, without significant support todeal with the addition or removal of nodes and edges. Typi-cally, this challenge is handled by re-executing the algorithmagain on the updated graph. In this work, we propose dis-tributedk-core decomposition and maintenance algorithmsfor large dynamic graphs. The proposed algorithms exploit,as much as possible, the topology of the graph to compute allthek-cores and maintain them in streaming settings whereedge insertions and removals happen frequently. The keyidea of the maintenance strategy is that whenever the orig-inal graph is updated by the insertion/deletion of one ormore edges, only a limited number of nodes need their core-ness to be re-evaluated. We present an implementation ofthe proposed approach on top of theakkaframework, andexperimentally show the efficiency of our approach in thecase of large dynamic networks.
Complete list of metadatas
Contributor : Sabeur Aridhi <>
Submitted on : Thursday, November 26, 2020 - 2:49:25 PM
Last modification on : Monday, November 30, 2020 - 11:23:02 AM

Links full text




Sabeur Aridhi, Martin Brugnara, Alberto Montresor, Yannis Velegrakis. Distributed k-core decomposition and maintenance in large dynamic graphs. the 10th ACM International Conference, Jun 2016, Irvine, France. pp.161-168, ⟨10.1145/2933267.2933299⟩. ⟨hal-03025953⟩



Record views