NDLI: Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis

Content Provider	Springer Nature Link
Author	Khopkar, Sushant S. Nagi, Rakesh Nikolaev, Alexander G. Bhembre, Vaibhav
Copyright Year	2014
Abstract	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)$$ time ( $$\Omega (n^2)$$ is the theoretical lower bound of the APSP problem), (2) The incremental closeness algorithm that runs in $$O(n^2)$$ time, and (3) The incremental betweenness algorithm runs in $$O(nm + n^2\, {\mathrm{log}} \, n)$$ time. Here, $$m$$ is the number of edges and $$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.
Starting Page	1
Ending Page	20
Page Count	20
File Format	PDF
ISSN	18695450
Journal	Social Network Analysis and Mining
Volume Number	4
Issue Number	1
e-ISSN	18695469
Language	English
Publisher	Springer Vienna
Publisher Date	2014-08-03
Publisher Place	Vienna
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Incremental graph algorithms Centrality metrics APSP Social network analysis Data Mining and Knowledge Discovery Complex Networks Game Theory, Economics, Social and Behav. Sciences Statistics for Social Science, Behavorial Science, Education, Public Policy, and Law Methodology of the Social Sciences
Content Type	Text
Resource Type	Article
Subject	Information Systems Human-Computer Interaction Communication Computer Science Applications Media Technology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An incremental algorithm for updating betweenness centrality and k-betweenness centrality and its performance on realistic dynamic social network data

Incremental maintenance of all-pairs shortest paths in relational DBMSs

Identifying high betweenness centrality nodes in large social networks

A penalty box approach for approximation betweenness and closeness centrality algorithms

SSRM: structural social role mining for dynamic social networks

Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

A new approach to role and position detection in networks

Intrinsic Correlation with Betweenness Centrality and Distribution of Shortest Paths

Temporal betweenness centrality on shortest walks variants

Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis

Similar Documents

An incremental algorithm for updating betweenness centrality and k-betweenness centrality and its performance on realistic dynamic social network data

Incremental maintenance of all-pairs shortest paths in relational DBMSs

Identifying high betweenness centrality nodes in large social networks

A penalty box approach for approximation betweenness and closeness centrality algorithms

SSRM: structural social role mining for dynamic social networks

Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality

A new approach to role and position detection in networks

Intrinsic Correlation with Betweenness Centrality and Distribution of Shortest Paths

Temporal betweenness centrality on shortest walks variants

Efficient algorithms for incremental all pairs shortest paths, closeness and betweenness in social network analysis