Effectively Handling New Relationship Formations in Closeness Centrality Analysis of Social Networks Using Anytime Anywhere Methodology

摘要

The flood of real time social data, generated by various social media applications and sensors, is enabling researchers to gain critical insights into important social modeling and analysis problems such as the evolution of social relationships and analysis of emergent social processes. However, current computational tools have to address the grand challenge of analyzing large and dynamic social networks within strict time constraints before the available social data can be effectively utilized. The computational issues are further exacerbated by the network size, which can range in the millions of nodes, and by the need for analytical tools to work with various computational architectures. Existing methodologies primarily deal with dynamic relationships in social networks by simply re-computing the results, and relying on massive parallel and distributed processing resources to maintain time constraints. In previous work, we introduced an overarching parallel/distributed algorithm design framework called the anytime anywhere framework, which leverages the inherent iterative property of graph algorithms to generate partial results, whose quality increase with the processing time, and which efficiently incorporates network changes. In this paper, we focus on closeness centrality algorithm design for dynamic social networks where new relationships are formed due to edge additions. Using both theoretical analysis and empirical results, we will demonstrate how this algorithm efficiently reuses the partial results and reduces the need for re-computations.