Share Email Print
cover

Proceedings Paper

Approximating centrality in evolving graphs: toward sublinearity
Author(s): Benjamin W. Priest; George Cybenko
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

The identification of important nodes is a ubiquitous problem in the analysis of social networks. Centrality indices (such as degree centrality, closeness centrality, betweenness centrality, PageRank, and others) are used across many domains to accomplish this task. However, the computation of such indices is expensive on large graphs. Moreover, evolving graphs are becoming increasingly important in many applications. It is therefore desirable to develop on-line algorithms that can approximate centrality measures using memory sublinear in the size of the graph. We discuss the challenges facing the semi-streaming computation of many centrality indices. In particular, we apply recent advances in the streaming and sketching literature to provide a preliminary streaming approximation algorithm for degree centrality utilizing CountSketch and a multi-pass semi-streaming approximation algorithm for closeness centrality leveraging a spanner obtained through iteratively sketching the vertex-edge adjacency matrix. We also discuss possible ways forward for approximating betweenness centrality, as well as spectral measures of centrality. We provide a preliminary result using sketched low-rank approximations to approximate the output of the HITS algorithm.

Paper Details

Date Published: 5 May 2017
PDF: 9 pages
Proc. SPIE 10184, Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security, Defense, and Law Enforcement Applications XVI, 101840G (5 May 2017); doi: 10.1117/12.2266376
Show Author Affiliations
Benjamin W. Priest, Thayer School of Engineering at Dartmouth (United States)
George Cybenko, Thayer School of Engineering at Dartmouth (United States)


Published in SPIE Proceedings Vol. 10184:
Sensors, and Command, Control, Communications, and Intelligence (C3I) Technologies for Homeland Security, Defense, and Law Enforcement Applications XVI
Edward M. Carapezza, Editor(s)

© SPIE. Terms of Use
Back to Top
PREMIUM CONTENT
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?
close_icon_gray