title   
  

Incremental closeness centrality in distributed memory

Sarıyüce, Ahmet Erdem and Saule, Erik and Kaya, Kamer and Çatalyürek, Ümit V. (2014) Incremental closeness centrality in distributed memory. [Working Paper / Technical Report] Sabanci University ID:UNSPECIFIED

[img]PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1175Kb

Abstract

Networks are commonly used to model traffic patterns, social interactions, or web pages. The vertices in a network do not possess the same characteristics: some vertices are naturally more connected and some vertices can be more important. Closeness centrality (CC) is a global metric that quantifies how important is a given vertex in the network. When the network is dynamic and keeps changing, the relative importance of the vertices also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose Streamer, a distributed memory framework for incrementally maintaining the closeness centrality scores of a network upon changes. It leverages pipelined, replicated parallelism, and SpMM-based BFSs, and it takes NUMA effects into account. It makes maintaining the Closeness Centrality values of real-life networks with millions of interactions significantly faster and obtains almost linear speedups on a 64 nodes 8 threads/node cluster.

Item Type:Working Paper / Technical Report
Uncontrolled Keywords:Closeness centrality; Incremental centrality; BFS; Parallel programming; Cluster Computing
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:25329
Deposited By:Kamer Kaya
Deposited On:06 Dec 2014 20:06
Last Modified:06 Dec 2014 20:06

Repository Staff Only: item control page