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

[thumbnail of paper.pdf] PDF
paper.pdf

Download (1MB)

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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 06 Dec 2014 20:06
Last Modified: 26 Apr 2022 10:51
URI: https://research.sabanciuniv.edu/id/eprint/25329

Actions (login required)

View Item
View Item