| In social network analysis, graph-theoretic concepts are used to understand and explain social phenomena. Calculations of centrality metrics such as Degree centrality, Closeness centrality, and Betweenness centrality are essential parts of network analysis. These centrality metrics indicate the prominence of individual nodes within a social network. In case of static graphs, algorithms have been designed and implemented to compute the aforementioned metrics. However if a graph is dynamic, that is if some nodes and edges are added or deleted from a graph at some later stage, then recalculating values of these centrality metrics from scratch is a costly operation in terms of computational efforts and time. This work involves design and implementation of incremental algorithms which will compute values of Degree, Closeness and Betweenness Centralities for dynamically changing social networks. Closeness and Betweenness Centralities are based on the concept of All Pairs Shortest Paths. Hence, the design of incremental algorithms for these Centrality Metrics are built on the foundations of an incremental All Pairs Shortest Path algorithm. Our incremental All Pairs Shortest Path algorithm runs in O( n2) time, which is an improvement over current fastest implemented algorithm running in O(n 2logn) time. We also show that O(n2) is a theoretical lower bound for Dynamic All Pairs Shortest Path algorithm. This work also compares repeated use of static algorithms for Centrality Metrics with the newly designed incremental algorithms. Results indicate that the incremental versions are capable of running approximately 655 times faster than their static counterparts for a graph of 1000 nodes. |
