Distributed k-core decomposition and maintenance in large dynamic graphs - Archive ouverte HAL Access content directly
Conference Papers Year :

Distributed k-core decomposition and maintenance in large dynamic graphs

(1, 2, 3) , (3) , (3) , (3)


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.

Dates and versions

hal-03025953 , version 1 (26-11-2020)



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⟩
22 View
0 Download



Gmail Facebook Twitter LinkedIn More