title   
  

Incremental closeness centrality in distributed memory

Sarıyüce, Ahmet Erdem and Saule, Erik and Kaya, Kamer and Çatalyürek, Ümit V. (2015) Incremental closeness centrality in distributed memory. Parallel Computing (SI), 47 . pp. 3-18. ISSN 0167-8191 (Print) 1872-7336 (Online)

[img]
Preview
PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1192Kb

Official URL: http://dx.doi.org/10.1016/j.parco.2015.01.003

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:Article
Uncontrolled Keywords:Closeness centrality; Incremental centrality; BFS; Parallel programming; Cluster Computing
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:27694
Deposited By:Kamer Kaya
Deposited On:15 Dec 2015 14:42
Last Modified:15 Dec 2015 14:42

Repository Staff Only: item control page