Abstract
Increasing proliferation of mobile and online social networking platforms have given us unprecedented opportunity to observe and study social interactions at a fine temporal scale. A collection of all such social interactions among a group of individuals (or agents) observed over an interval of time is referred to as a temporally-detailed (TD) social network. A TD social network opens up the opportunity to explore TD questions on the underlying social system, e.g., “How is the betweenness centrality of an individual changing with time?” To this end, related work has proposed temporal extensions of centrality metrics (e.g., betweenness and closeness). However, scalable computation of these metrics for long time-intervals is challenging. This is due to the non-stationary ranking of shortest paths (the underlying structure of betweenness and closeness) between a pair of nodes which violates the assumptions of classical dynamic programming based techniques. To this end, we propose a novel computational paradigm called epoch-point based techniques for addressing the non-stationarity challenge of TD social networks. Using the concept of epoch-points, we develop a novel algorithm for computing shortest path based centrality metric such as betweenness on a TD social network. We prove the correctness and completeness of our algorithm. Our experimental analysis shows that the proposed algorithm out performs the alternatives by a wide margin.
Original language | English (US) |
---|---|
Pages (from-to) | 1133-1169 |
Number of pages | 37 |
Journal | Machine Learning |
Volume | 106 |
Issue number | 8 |
DOIs | |
State | Published - Aug 1 2017 |
Bibliographical note
Funding Information:We are particularly grateful to the members of the Spatial Database Research Group at the University of Minnesota and Computational Analysis of Social and Organizational Systems at Carnegie Mellon University for their helpful comments and valuable suggestions. This work was supported by the Center for Artificial Intelligence at the IIIT-Delhi, NSF Grants (Grant No. NSF IIS-1320580, NSF No. 0940818, NSF IIS-1218168) and USDOD Grant (Grant No. HM1582-08-1-0017). The content does not necessarily reflect the position or the policy of the government and no official endorsement should be inferred.
Publisher Copyright:
© 2016, The Author(s).
Keywords
- Centrality
- Dynamic programming
- Graph theory
- Time varying networks
- Time-varying social networks