A figure from the presentation.
Citation:
Kas, Miray, Wachs, Matthew, Carley, L. Richard, & Carley, Kathleen M. (2012). Incremental Centrality Computations for Dynamic Social Networks. Paper presented at the XXXII International Sunbelt Social Network Conference, Redondo Beach, CA, March 12-18, 2012.
Keywords:
Centrality Computation, Incremental Algorithm Design, Dynamic Social Networks, Large-Scale Data
Abstract:
The increasing availability of online resources such as digital libraries and social networking websites has led to an upsurge of interest in the analysis of large-scale social networks that can be extracted using information available on these websites. Researchers are excited about extracting information from these large-scale social networks as these networks now have a significant impact on trends in society.
To date, a wealth of social centrality measures (e.g. degree centrality, closeness centrality, betweenness centrality, bridging centrality, etc.) have been designed, each of which is geared towards determining the importance of a node in a social network from different aspects. A significant number of social centrality metrics depend on the shortest paths in the network, usually requiring solving the all-pairs shortest path problem. However, most of these metrics were designed for static snapshots of 20-30 node networks. Computing social centrality metrics in continuously-growing dynamic networks is almost infeasibly costly on large-scale networks, especially if it involves repeatedly calculating these metrics from scratch.
In this work, we aim to design scalable, incremental algorithms for social centrality metrics that avoid computations from scratch performing early-pruning and achieving substantial performance improvements. The key idea in the incremental algorithm design is to start with the old output of the algorithm and modify/update only the affected values such that the changes in the dynamic network (e.g. edge/node insertions/deletions/modifications) are reflected on the output (i.e., centrality) values as well. Our preliminary results suggest that incremental approaches can provide significant speedup over their static, non-incremental counterparts.
A figure from the presentation.