Betweenness centrality is an important index widely used in different domains such as social networks, traffic networks and the world wide web. However, even for mid-size networks that have only a few hundreds thousands vertices, it is computationally expensive to compute exact betweenness scores. Therefore in recent years, several approximate algorithms have been developed. In this paper, first given a network @math and a vertex @math , we propose a Metropolis-Hastings MCMC algorithm that samples from the space @math and estimates betweenness score of @math . The stationary distribution of our MCMC sampler is the optimal sampling proposed for betweenness centrality estimation. We show that our MCMC sampler provides an @math -approximation, where the number of required samples depends on the position of @math in @math and in many cases, it is a constant. Then, given a network @math and a set @math , we present a Metropolis-Hastings MCMC sampler that samples from the joint space @math and @math and estimates relative betweenness scores of the vertices in @math . We show that for any pair @math , the ratio of the expected values of the estimated relative betweenness scores of @math and @math respect to each other is equal to the ratio of their betweenness scores. We also show that our joint-space MCMC sampler provides an @math -approximation of the relative betweenness score of @math respect to @math , where the number of required samples depends on the position of @math in @math and in many cases, it is a constant.
Everett and Borgatti @cite_14 defined as a natural extension of betweenness centrality for sets of vertices. Group betweenness centrality of a set is defined as the number of shortest paths passing through at least one of the vertices in the set @cite_14 . The other natural extension of betweenness centrality is . Co-betweenness centrality is defined as the number of shortest paths passing through all vertices in the set. Kolaczyk et. al. @cite_4 presented an @math time algorithm for co-betweenness centrality computation of sets of size 2. Chehreghani @cite_3 presented efficient algorithms for co-betweenness centrality computation of any set or sequence of vertices in weighted and unweighted networks. Puzis et. al. @cite_33 proposed an @math time algorithm for computing successive group betweenness centrality, where @math is the size of the set. The same authors in @cite_15 presented two algorithms for finding . A of a network is a set vertices of minimum size, so that every shortest path in the network passes through at least one of the vertices in the set. The first algorithm is based on a heuristic search and the second one is based on iterative greedy choice of vertices.
@cite_14 @cite_4 @cite_33 @cite_3 @cite_15
2089370556 1992229444 2003408562 1790404493
This paper extends the standard network centrality measures of degree, closeness and betweenness to apply to groups and classes as well as individuals. The group centrality measures will enable researchers to answer such questions as ‘how central is the engineering department in the informal influence network of this company?’ or ‘among middle managers in a given organization, which are more central, the men or the women?’ With these measures we can also solve the inverse problem: given the network of ties among organization members, how can we form a team that is maximally central? The measures are illustrated using two classic network data sets. We also formalize a measure of group centrality efficiency, which indicates the extent to which a group's centrality is principally due to a small subset of its members. Abstract Vertex betweenness centrality is a metric that seeks to quantify a sense of the importance of a vertex in a network in terms of its ‘control’ on the flow of information along geodesic paths throughout the network. Two natural ways to extend vertex betweenness centrality to sets of vertices are (i) in terms of geodesic paths that pass through at least one of the vertices in the set, and (ii) in terms of geodesic paths that pass through all vertices in the set. The former was introduced by Everett and Borgatti [Everett, M., Borgatti, S., 1999. The centrality of groups and classes. Journal of Mathematical Sociology 23 (3), 181–201], and called group betweenness centrality. The latter, which we call co-betweenness centrality here, has not been considered formally in the literature until now, to the best of our knowledge. In this paper, we show that these two notions of centrality are in fact intimately related and, furthermore, that this relationship may be exploited to obtain deeper insight into both. In particular, we provide an expansion for group betweenness in terms of increasingly higher orders of co-betweenness, in a manner analogous to the Taylor series expansion of a mathematical function in calculus. We then demonstrate the utility of this expansion by using it to construct analytic lower and upper bounds for group betweenness that involve only simple combinations of (i) the betweenness of individual vertices in the group, and (ii) the co-betweenness of pairs of these vertices. Accordingly, we argue that the latter quantity, i.e., pairwise co-betweenness, is itself a fundamental quantity of some independent interest, and we present a computationally efficient algorithm for its calculation, which extends the algorithm of Brandes [Brandes, U., 2001. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25, 163] in a natural manner. Applications are provided throughout, using a handful of different communication networks, which serve to illustrate the way in which our mathematical contributions allow for insight to be gained into the interaction of network structure, coalitions, and information flow in social networks. In this paper, we propose a method for rapid computation of group betweenness centrality whose running time (after preprocessing) does not depend on network size. The calculation of group betweenness centrality is computationally demanding and, therefore, it is not suitable for applications that compute the centrality of many groups in order to identify new properties. Our method is based on the concept of path betweenness centrality defined in this paper. We demonstrate how the method can be used to find the most prominent group. Then, we apply the method for epidemic control in communication networks. We also show how the method can be used to evaluate distributions of group betweenness centrality and its correlation with group degree. The method may assist in finding further properties of complex networks and may open a wide range of research opportunities. In many applications we are required to locate the most prominent group of vertices in a complex network. Group Betweenness Centrality can be used to evaluate the prominence of a group of vertices. Evaluating the Betweenness of every possible group in order to find the most prominent is not computationally feasible for large networks. In this paper we present two algorithms for finding the most prominent group. The first algorithm is based on heuristic search and the second is based on iterative greedy choice of vertices. The algorithms were evaluated on random and scale-free networks. Empirical evaluation suggests that the greedy algorithm results were negligibly below the optimal result. In addition, both algorithms performed better on scale-free networks: heuristic search was faster and the greedy algorithm produced more accurate results. The greedy algorithm was applied for optimizing deployment of intrusion detection devices on network service provider infrastructure.