TY - JOUR
T1 - Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis
AU - Khopkar, Sushant S.
AU - Nagi, Rakesh
AU - Nikolaev, Alexander G.
AU - Bhembre, Vaibhav
N1 - Funding Information:
This work was supported by the National Science Foundation via grant number ICES-1216082. This support is gratefully acknowledged.
Publisher Copyright:
© 2014, Springer-Verlag Wien.
PY - 2014/1/1
Y1 - 2014/1/1
N2 - One of the biggest challenges in today’s social network analysis (SNA) is handling dynamic data. Real-world social networks evolve with time, forcing their corresponding graph representations to dynamically update by addition or deletion of edges/nodes. Consequently, a researcher is often interested in fast recomputation of important SNA metrics pertaining to a network. Recomputations of SNA metrics are expensive. Use of dynamic algorithms has been found as a solution to this problem. For calculating closeness and betweenness centrality metrics, computations of all pairs shortest paths (APSP) are needed. Thus, to compute these SNA metrics dynamically, APSP are needed to be computed dynamically. This paper presents fast incremental updating algorithms along with the time complexity results for APSP, closeness centrality and betweenness centrality, considering two distinct cases: edge addition and node addition. The following time complexity results are presented: (1) The incremental APSP algorithm runs in $$O(n^2)$$O(n2) time ($$\Omega (n^2)$$Ω(n2) is the theoretical lower bound of the APSP problem), (2) The incremental closeness algorithm that runs in $$O(n^2)$$O(n2) time, and (3) The incremental betweenness algorithm runs in $$O(nm + n^2\, {\mathrm{log}} \, n)$$O(nm+n2logn) time. Here, $$m$$m is the number of edges and $$n$$n is the number of nodes in the network. Though the time complexity of the presented incremental betweenness algorithm is no better than its static counterpart (Brandes, J Math Sociol 25(2):163–177, 2001), the experimental comparisons demonstrate that the former performs better than the latter. All the presented methods are applicable to weighted, directed or undirected graphs with non-negative real-valued edge weights. An alternate version of the incremental APSP algorithm is presented in the Appendix section. It is demonstrated that this version works better on large graphs.
AB - One of the biggest challenges in today’s social network analysis (SNA) is handling dynamic data. Real-world social networks evolve with time, forcing their corresponding graph representations to dynamically update by addition or deletion of edges/nodes. Consequently, a researcher is often interested in fast recomputation of important SNA metrics pertaining to a network. Recomputations of SNA metrics are expensive. Use of dynamic algorithms has been found as a solution to this problem. For calculating closeness and betweenness centrality metrics, computations of all pairs shortest paths (APSP) are needed. Thus, to compute these SNA metrics dynamically, APSP are needed to be computed dynamically. This paper presents fast incremental updating algorithms along with the time complexity results for APSP, closeness centrality and betweenness centrality, considering two distinct cases: edge addition and node addition. The following time complexity results are presented: (1) The incremental APSP algorithm runs in $$O(n^2)$$O(n2) time ($$\Omega (n^2)$$Ω(n2) is the theoretical lower bound of the APSP problem), (2) The incremental closeness algorithm that runs in $$O(n^2)$$O(n2) time, and (3) The incremental betweenness algorithm runs in $$O(nm + n^2\, {\mathrm{log}} \, n)$$O(nm+n2logn) time. Here, $$m$$m is the number of edges and $$n$$n is the number of nodes in the network. Though the time complexity of the presented incremental betweenness algorithm is no better than its static counterpart (Brandes, J Math Sociol 25(2):163–177, 2001), the experimental comparisons demonstrate that the former performs better than the latter. All the presented methods are applicable to weighted, directed or undirected graphs with non-negative real-valued edge weights. An alternate version of the incremental APSP algorithm is presented in the Appendix section. It is demonstrated that this version works better on large graphs.
KW - APSP
KW - Centrality metrics
KW - Incremental graph algorithms
KW - Social network analysis
UR - http://www.scopus.com/inward/record.url?scp=84947282981&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947282981&partnerID=8YFLogxK
U2 - 10.1007/s13278-014-0220-6
DO - 10.1007/s13278-014-0220-6
M3 - Article
AN - SCOPUS:84947282981
VL - 4
SP - 1
EP - 20
JO - Social Network Analysis and Mining
JF - Social Network Analysis and Mining
SN - 1869-5450
IS - 1
M1 - 220
ER -