Grad Student Talks
http://www.cs.utexas.edu/
Tue, 30 Sep 2014 13:50:12 -0500Tue, 30 Sep 2014 13:50:12 -0500RPE: Matteo Pontecorvi, GDC 4.516
http://www.cs.utexas.edu/node/54452
<p>RPE: Matteo Pontecorvi</p>
<p>Date: Friday, October 3, 2014<br />Time: 2.00pm<br />Place: GDC 4.516</p>
<p>Committee Members: Vijaya Ramachandran (chair), Inderjit Dhillon, David Zuckerman</p>
<p>Title: Algorithms for Dynamic Betweenness Centrality</p>
<p>Abstract:</p>
<p>Betweenness Centrality (BC) is a measure for the centrality (importance) of a node<br />in a network. It is widely used in real-world scenarios such as social networks,<br />computer networks, traffic networks, biology, mobile networks etc.<br />BC is often maintained in a dynamic network where the structure changes often<br />over time because of the addition or deletion of nodes and connections in the network.</p>
<p>In this talk, we present an algorithm that updates the BC scores for all nodes<br />in a network when an edge is added, or the weight of an existing edge is reduced.<br />This is the first algorithm that is provably faster than the current best static<br />method (due to Ulrik Brandes) on sparse graphs, and it is also likely to be much<br />faster than Brandes' algorithm for dense graphs. We achieve the same bound for the<br />more general case of updating a vertex instead of an edge.<br />Our algorithm is simple and uses only basic data structures.</p>
<p>In recent work, we have considered the complementary problem of updating the BC scores<br />when a node is removed, or the weights of a subset of edges incident to a node are increased.<br />We have developed an algorithm for this case as well as one for an arbitrary sequence of<br />weight changes on a subset of edges incident to a node.<br />These algorithms require more elaborate tools than our method for weight decreases.<br />We will present an overview of some of the features in these results.</p>
Fri, 03 Oct 2014 14:00 CDT