A note on measures of similarity based on centrality

This note presents a measure of similarity between connected nodes in terms of centrality based on Euclidean distances, and compares it to ‘assortative mixing’ [Newman, M.E.J., 2002. Assortative mixing in networks. Physical Review Letters 89, 208701], which is based on Pearson correlation coefficient. This study suggests that the measure based on Euclidean distances may be more appropriate for relatively smaller (N < 500) and denser networks.     

Eigenvector centrality and structural zeroes and ones: When is a neighbor not a neighbor?

There will be occasions in which a researcher wants to ignore some dyads in the computation of centrality in order to avoid biased or misleading results. This paper presents a principled way of computing eigenvector-like centrality scores when some dyads are not included in the calculations.     

Group betweenness and co-betweenness: Inter-related notions of coalition centrality

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.     

Ranking terrorists in networks: A sensitivity analysis of Al Qaeda's 9/11 attack

All over the world, intelligence services are collecting data concerning possible terrorist threats. This information is usually transformed into network structures in which the nodes represent the individuals in the data set and the links possible connections between these individuals. Unfortunately, it is nearly impossible to keep track of all individuals in the resulting complex network. Therefore, Lindelauf et al. (2013) introduced a methodology that ranks terrorists in a network. The rankings that result from this methodology can be used as a decision support system to efficiently allocate the scarce surveillance means of intelligence agencies. Moreover, usage of these rankings can improve the quality of surveillance which can in turn lead to prevention of attacks or destabilization of the networks under surveillance.The methodology introduced by Lindelauf et al. (2013) is based on a game theoretic centrality measure, which is innovative in the sense that it takes into account not only the structure of the network but also individual and coalitional characteristics of the members of the network. In this paper we elaborate on this methodology by introducing a new game theoretic centrality measure that better takes into account the operational strength of connected subnetworks.Moreover, we perform a sensitivity analysis on the rankings derived from this new centrality measure for the case of Al Qaeda's 9/11 attack. In this sensitivity analysis we consider firstly the possible additional information available about members of the network, secondly, variations in relational strength and, finally, the absence or presence of a small percentage of links in the network. We also introduce a case specific method to compare the different rankings that result from the sensitivity analysis and show that the new centrality measure is robust to small changes in the data.     

A network centrality bias: Central individuals in workplace networks have more supportive coworkers

Combining the results of two empirical studies, we investigate the role of alters’ motivation in explaining change in ego’s network position over time. People high in communal motives, who are prone to supportive and altruistic behavior in their interactions with others as a way to gain social acceptance, prefer to establish ties with co-workers occupying central positions in organizational social networks. This effect results in a systematic network centrality bias: The personal network of central individuals (individuals with many incoming ties from colleagues) is more likely to contain more supportive and altruistic people than the personal network of individuals who are less central (individuals with fewer incoming ties). This result opens the door to the possibility that the effects of centrality so frequently documented in empirical studies may be due, at least in part, to characteristics of the alters in an ego’s personal community, rather than to egos themselves. Our findings invite further empirical research on how alters’ motives affect the returns that people can reap from their personal networks in organizations.     

Closeness centrality via the Condorcet principle

We provide a characterization of closeness centrality in the class of distance-based centralities. To this end, we introduce a natural property, called majority comparison, that states that out of two adjacent nodes the one closer to more nodes is more central. We prove that any distance-based centrality that satisfies this property gives the same ranking in every graph as closeness centrality. The axiom is inspired by the interpretation of the graph as an election in which nodes are both voters and candidates and their preferences are determined by the distances to the other nodes.     

Entropy as a measure of centrality in networks characterized by path-transfer flow

Recently, Borgatti [Borgatti, S.P., 2005. Centrality and network flow. Social Networks 27, 55–71] proposed a taxonomy of centrality measures based on the way that traffic flows through the network—whether over path, geodesic, trail, or walk, and whether by means of transfer, serial duplication, or parallel duplication. Most of the extant centrality measures assume that traffic propagates via parallel duplication or, alternatively, that it travels over geodesics. Few of the other flow possibilities have centrality measures associated with them. This article proposes an entropy-based measure of centrality appropriate for traffic that propagates by transfer and flows along paths. The proposed measure can be applied to most network types, whether binary or weighted, directed or undirected, connected or disconnected. The measure is illustrated on the gang alliance network of Kennedy et al. [Kennedy, D.M., Braga, A. A., Piehl, A.M., 1998. The (un)known universe: mapping gangs and gang violence in Boston. Crime Prevention Studies 8, 219–262].     

A representation for the Mexican political networks

A compressed graph representation for use with the Mexican political networks is introduced. Properties of these graphs are investigated. It is also explained how the Jorge–Schmidt power centrality index can be used to index the centrality of nodes in the original network from the compressed graph representation.     

Induced, endogenous and exogenous centrality

Centrality measures are based upon the structural position an actor has within the network. Induced centrality, sometimes called vitality measures, take graph invariants as an overall measure and derive vertex level measures by deleting individual nodes or edges and examining the overall change. By taking the sum of standard centrality measures as the graph invariant we can obtain measures which examine how much centrality an individual node contributes to the centrality of the other nodes in the network, we call this exogenous centrality. We look at exogenous measures of degree, closeness and betweenness.     

Correlations among centrality indices and a class of uniquely ranked graphs

Various centrality indices have been proposed to capture different aspects of structural importance but relations among them are largely unexplained. The most common strategy appears to be the pairwise comparison of centrality indices via correlation. While correlation between centralities is often read as an inherent property of the indices, we argue that it is confounded by network structure in a systematic way. In fact, correlations may be even more indicative of network structure than of relationships between indices. This has substantial implications for the interpretation of centrality effects as it implies that competing explanations embodied in different indices cannot be separated from each other if the network structure is close to a certain generalization of star graphs.