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.

Distributed k-core decomposition and maintenance in large dynamic graphs / Aridhi, Sabeur; Brugnara, Martin; Montresor, Alberto; Velegrakis, Yannis. - (2016), pp. 161-168. (Intervento presentato al convegno 10th ACM International Conference on Distributed and Event-Based Systems, DEBS 2016 tenutosi a Beckman Center of the National Academies of Sciences and Engineering, usa nel 20-24 June 2016) [10.1145/2933267.2933299].

Distributed k-core decomposition and maintenance in large dynamic graphs

Aridhi, Sabeur;Brugnara, Martin;Montresor, Alberto;Velegrakis, Yannis
2016-01-01

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.
2016
DEBS 2016 - Proceedings of the 10th ACM International Conference on Distributed and Event-Based Systems
USA
Association for Computing Machinery, Inc
9781450340212
Aridhi, Sabeur; Brugnara, Martin; Montresor, Alberto; Velegrakis, Yannis
Distributed k-core decomposition and maintenance in large dynamic graphs / Aridhi, Sabeur; Brugnara, Martin; Montresor, Alberto; Velegrakis, Yannis. - (2016), pp. 161-168. (Intervento presentato al convegno 10th ACM International Conference on Distributed and Event-Based Systems, DEBS 2016 tenutosi a Beckman Center of the National Academies of Sciences and Engineering, usa nel 20-24 June 2016) [10.1145/2933267.2933299].
File in questo prodotto:
File Dimensione Formato  
AridhiBMV16.pdf

accesso aperto

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 363.71 kB
Formato Adobe PDF
363.71 kB Adobe PDF Visualizza/Apri
2933267.2933299.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 762.95 kB
Formato Adobe PDF
762.95 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/194998
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 39
  • ???jsp.display-item.citation.isi??? ND
social impact