Abstract:
We consider the incremental computation of the betweenness centrality of all vertices in a large complex network modeled as a graph G = (V, E), directed or undirected, with positive real edge-weights. The current widely used algorithm to compute the betweenness centrality of all vertices in G is the Brandes algorithm that runs in O(mn + n^2 log n) time, where n = |V| and m = |E|. We present an incremental algorithm that updates the betweenness centrality score of all vertices in G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(m' n + n^2) time, where m' is the size of a certain subset of E*, the set of edges in G that lie on a shortest path. We achieve the same bound for the more general incremental update of a vertex v, where the edge update can be performed on any subset of edges incident to v. Our incremental algorithm is the first algorithm that is asymptotically faster on sparse graphs than recomputing with the Brandes algorithm. Our algorithm is also likely to be much faster than the Brandes algorithm on dense graphs since m*, the size of E*, is often close to linear in n. Our incremental algorithm is very simple and the only data structures it uses are arrays, lists, and stack. We give an efficient cache-oblivious implementation that incurs O(scan(n^2) + n sort(m')) cache misses, where scan and sort are well-known measures for efficient caching. We also give a static algorithm for computing betweenness centrality of all vertices that runs in time O(m* n + n^2 log n), which is faster than the Brandes algorithm on any graph with n log n = o(m) and m* = o(m).

Abstract:
Betweenness centrality is a classic measure that quantifies the importance of a graph element (vertex or edge) according to the fraction of shortest paths passing through it. This measure is notoriously expensive to compute, and the best known algorithm runs in O(nm) time. The problems of efficiency and scalability are exacerbated in a dynamic setting, where the input is an evolving graph seen edge by edge, and the goal is to keep the betweenness centrality up to date. In this paper we propose the first truly scalable algorithm for online computation of betweenness centrality of both vertices and edges in an evolving graph where new edges are added and existing edges are removed. Our algorithm is carefully engineered with out-of-core techniques and tailored for modern parallel stream processing engines that run on clusters of shared-nothing commodity hardware. Hence, it is amenable to real-world deployment. We experiment on graphs that are two orders of magnitude larger than previous studies. Our method is able to keep the betweenness centrality measures up to date online, i.e., the time to update the measures is smaller than the inter-arrival time between two consecutive updates.

Abstract:
Betweenness centrality ranks the importance of nodes by their participation in all shortest paths of the network. Therefore computing exact betweenness values is impractical in large networks. For static networks, approximation based on randomly sampled paths has been shown to be significantly faster in practice. However, for dynamic networks, no approximation algorithm for betweenness centrality is known that improves on static recomputation. We address this deficit by proposing two incremental approximation algorithms (for weighted and unweighted connected graphs) which provide a provable guarantee on the absolute approximation error. Processing batches of edge insertions, our algorithms yield significant speedups up to a factor of $10^4$ compared to restarting the approximation. This is enabled by investing memory to store and efficiently update shortest paths. As a building block, we also propose an asymptotically faster algorithm for updating the SSSP problem in unweighted graphs. Our experimental study shows that our algorithms are the first to make in-memory computation of a betweenness ranking practical for million-edge semi-dynamic networks. Moreover, our results show that the accuracy is even better than the theoretical guarantees in terms of absolutes errors and the rank of nodes is well preserved, in particular for those with high betweenness.

Abstract:
A class of centrality measures called betweenness centralities reflects degree of participation of edges or nodes in communication between different parts of the network. The original shortest-path betweenness centrality is based on counting shortest paths which go through a node or an edge. One of shortcomings of the shortest-path betweenness centrality is that it ignores the paths that might be one or two steps longer than the shortest paths, while the edges on such paths can be important for communication processes in the network. To rectify this shortcoming a current flow betweenness centrality has been proposed. Similarly to the shortest path betwe has prohibitive complexity for large size networks. In the present work we propose two regularizations of the current flow betweenness centrality, \alpha-current flow betweenness and truncated \alpha-current flow betweenness, which can be computed fast and correlate well with the original current flow betweenness.

Abstract:
One of the most fundamental problems in large scale network analysis is to determine the importance of a particular node in a network. Betweenness centrality is the most widely used metric to measure the importance of a node in a network. In this paper, we present a randomized parallel algorithm and an algebraic method for computing betweenness centrality of all nodes in a network. We prove that any path-comparison based algorithm cannot compute betweenness in less than O(nm) time.

Abstract:
There are several centrality measures that have been introduced and studied for real world networks. They account for the different vertex characteristics that permit them to be ranked in order of importance in the network. Betweenness centrality is a measure of the influence of a vertex over the flow of information between every pair of vertices under the assumption that information primarily flows over the shortest path between them. In this paper we present betweenness centrality of some important classes of graphs.

Abstract:
We analyze the betweenness centrality (BC) of nodes in large complex networks. In general, the BC is increasing with connectivity as a power law with an exponent $\eta$. We find that for trees or networks with a small loop density $\eta=2$ while a larger density of loops leads to $\eta<2$. For scale-free networks characterized by an exponent $\gamma$ which describes the connectivity distribution decay, the BC is also distributed according to a power law with a non universal exponent $\delta$. We show that this exponent $\delta$ must satisfy the exact bound $\delta\geq (\gamma+1)/2$. If the scale free network is a tree, then we have the equality $\delta=(\gamma+1)/2$.

Abstract:
Scale-free (SF) networks exhibiting a power-law degree distribution can be grouped into the assortative, dissortative and neutral networks according to the behavior of the degree-degree correlation coefficient. Here we investigate the betweenness centrality (BC) correlation for each type of SF networks. While the BC-BC correlation coefficients behave similarly to the degree-degree correlation coefficients for the dissortative and neutral networks, the BC correlation is nontrivial for the assortative ones found mainly in social networks. The mean BC of neighbors of a vertex with BC $g_i$ is almost independent of $g_i$, implying that each person is surrounded by almost the same influential environments of people no matter how influential the person is.

Abstract:
In addition to science citation indicators of journals like impact and immediacy, social network analysis provides a set of centrality measures like degree, betweenness, and closeness centrality. These measures are first analyzed for the entire set of 7,379 journals included in the Journal Citation Reports of the Science Citation Index and the Social Sciences Citation Index 2004, and then also in relation to local citation environments which can be considered as proxies of specialties and disciplines. Betweenness centrality is shown to be an indicator of the interdisciplinarity of journals, but only in local citation environments and after normalization because otherwise the influence of degree centrality (size) overshadows the betweenness-centrality measure. The indicator is applied to a variety of citation environments, including policy-relevant ones like biotechnology and nanotechnology.

Abstract:
Betweenness centrality is taken as a sensible indicator of the synchronizability of complex networks. To test whether betweenness centrality is a proper measure of the synchronizability in specific realizations of random networks, this paper adds edges to the networks and then evaluates the changes of betweenness centrality and network synchronizability. It finds that the two quantities vary independently.