PhD Thesis Proposal: Benjamin Priest

Thursday, June 29, 2017, 1:00–3:00pm

Jackson Conference Room, Cummings Hall

“Sublinear Approximations of Vertex Importance in Evolving Graphs"

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, eigencentrality, and others) are used across many domains to accomplish this task. However, the computation of such indices is usually expensive on large graphs. Moreover, evolving graphs with edge insertions, updates, and deletions are increasingly important in many applications. These constraints place us in what is sometimes called the dynamic streaming model. Randomized algorithms maintaining sketches of salient graph properties are known to allow approximation of some graph properties in sublinear space.
 
It is therefore desirable to develop sublinear algorithms to approximate centrality indices. It is in particular desirable to develop such algorithms that require only one pass over the input stream, although a provably small number of passes is also interesting in some cases. In applications it is usually more important to recover the top k central vertices with respect to a given index than it is to know the exact scores of every vertex in the network. Accordingly, the relaxed problem of maintaining an on-line list of the approximate top k central nodes is of primary interest, especially in the single-pass case.

Thesis Committee

For more information, contact Daryl Laware at daryl.a.laware@dartmouth.edu.