Geodesic based centrality: Unifying the local and the global

A variety of node-level centrality measures, including purely structural measures (such as degree and closeness centrality) and measures incorporating characteristics of actors (such as the Blau's measure of heterogeneity) have been developed to measure a person's access to resources held by others. Each of these node-level measures can be placed on a continuum depending on whether they focus only on ego's direct contacts (e.g. degree centrality and Blau's measure of heterogeneity), or whether they also incorporate connections to others at longer distances in the network (e.g. closeness centrality or betweenness centrality). In this paper we propose generalized measures, where a tuning parameter δ regulates the relative impact of resources held by more close versus more distant others. We first show how, when a specific δ is chosen degree-centrality and reciprocal closeness centrality are two specific instances of this more general measure. We then demonstrate how a similar approach can be applied to node-level measures that incorporate attributes. When more or less weight is given to other nodes at longer distances with specific characteristics, a generalized measure of resource-richness and a generalized measure for diversity among one's connections can be obtained (following Blau's measure of heterogeneity). Finally, we show how this approach can also be applied to betweenness centrality to focus on more local (ego) betweenness or global (Freeman) betweenness. The importance of the choice of δ is illustrated on some classic network datasets.     

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.     

Categorical attribute based centrality: E–I and G–F centrality

In a paper examining informal networks and organizational crisis, Krackhardt and Stern (1988) proposed a measure assessing the extent to which relations in a network were internal to a group as opposed to external. They called their measure the E–I index. The measure is now in wide use and is implemented in standard network packages such as UCINET ( Borgatti et al., 2002). The measure is based on a partition-based degree centrality measure and as such can be extended to other centrality measures and group level data. We explore extensions to closeness, betweenness and eigenvector centrality, and show how to apply the technique to sets of subgroups that do not form a partition. In addition, the extension to betweenness suggests a linkage to the Gould and Fernandez brokerage measures, which we explore.     

Bridging: Locating critical connectors in a network

This paper proposes several measures for bridging in networks derived from Granovetter's (1973) insight that links which reduce distances in a network are important structural bridges. Bridging is calculated by systematically deleting links and calculating the resultant changes in network cohesion (measured as the inverse average path length). The average change for each node's links provides an individual level measure of bridging. We also present a normalized version which controls for network size and a network-level bridging index. Bridging properties are demonstrated on hypothetical networks, empirical networks, and a set of 100 randomly generated networks to show how the bridging measure correlates with existing network measures such as degree, personal network density, constraint, closeness centrality, betweenness centrality, and vitality. Bridging and the accompanying methodology provide a family of new network measures useful for studying network structure, network dynamics, and network effects on substantive behavioral phenomenon.     

Embedding time in positions: Temporal measures of centrality for social network analysis

Digital data enable researchers to obtain fine-grained temporal information about social interactions. However, positional measures used in social network analysis (e.g., degree centrality, reachability, betweenness) are not well suited to these time-stamped interaction data because they ignore sequence and time of interactions. While new temporal measures have been developed, they consider time and sequence separately. Building on formal algebra, we propose three temporal equivalents to positional network measures that incorporate time and sequence. We demonstrate how these temporal equivalents can be applied to an empirical context and compare the results with their static counterparts. We show that, compared to their temporal counterparts, static measures applied to interaction networks obscure meaningful differences in the way in which individuals accumulate alters over time, conceal potential disconnections in the network by overestimating reachability, and bias the distribution of betweenness centrality, which can affect the identification of key individuals in the network.     

A Graph-theoretic perspective on centrality

The concept of centrality is often invoked in social network analysis, and diverse indices have been proposed to measure it. This paper develops a unified framework for the measurement of centrality. All measures of centrality assess a node's involvement in the walk structure of a network. Measures vary along four key dimensions: type of nodal involvement assessed, type of walk considered, property of walk assessed, and choice of summary measure. If we cross-classify measures by type of nodal involvement (radial versus medial) and property of walk assessed (volume versus length), we obtain a four-fold polychotomization with one cell empty which mirrors Freeman's 1979 categorization. At a more substantive level, measures of centrality summarize a node's involvement in or contribution to the cohesiveness of the network. Radial measures in particular are reductions of pair-wise proximities/cohesion to attributes of nodes or actors. The usefulness and interpretability of radial measures depend on the fit of the cohesion matrix to the one-dimensional model. In network terms, a network that is fit by a one-dimensional model has a core-periphery structure in which all nodes revolve more or less closely around a single core. This in turn implies that the network does not contain distinct cohesive subgroups. Thus, centrality is shown to be intimately connected with the cohesive subgroup structure of a network.     

Bridging,brokerage and betweenness

Valente and Fujimoto (2010) proposed a measure of brokerage in networks based on Granovetter's classic work on the strength of weak ties. Their paper identified the need for finding node-based measures of brokerage that consider the entire network structure, not just a node's local environment. The measures they propose, aggregating the average change in cohesion for a node's links, has several limitations. In this paper we review their method and show how the idea can be modified by using betweenness centrality as an underpinning concept. We explore the properties of the new method and provide point, normalized, and network level variations. This new approach has two advantages, first it provides a more robust means to normalize the measure to control for network size, and second, the modified measure is computationally less demanding making it applicable to larger networks.     

Ego network betweenness

In this paper, we look at the betweenness centrality of ego in an ego network. We discuss the issue of normalization and develop an efficient and simple algorithm for calculating the betweenness score. We then examine the relationship between the ego betweenness and the betweenness of the actor in the whole network. Whereas, we can show that there is no theoretical link between the two we undertake a simulation study, which indicates that the local ego betweenness is highly correlated with the betweenness of the actor in the complete network.     

A measure of betweenness centrality based on random walks

Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. Here, we propose a betweenness measure that relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes. We show how our measure can be calculated using matrix methods, and give some examples of its application to particular networks.     

Resistance distance,closeness, and betweenness

In a seminal paper Stephenson and Zelen (1989) rethought centrality in networks proposing an information-theoretic distance measure among nodes in a network. The suggested information distance diverges from the classical geodesic metric since it is sensible to all paths (not just to the shortest ones) and it diminishes as soon as there are more routes between a pair of nodes. Interestingly, information distance has a clear interpretation in electrical network theory that was missed by the proposing authors. When a fixed resistor is imagined on each edge of the graph, information distance, known as resistance distance in this context, corresponds to the effective resistance between two nodes when a battery is connected across them. Here, we review resistance distance, showing once again, with a simple proof, that it matches information distance. Hence, we interpret both current-flow closeness and current-flow betweenness centrality in terms of resistance distance. We show that this interpretation has semantic, theoretical, and computational benefits.     

Measurement error in network data: A re-classification

Research on measurement error in network data has typically focused on missing data. We embed missing data, which we term false negative nodes and edges, in a broader classification of error scenarios. This includes false positive nodes and edges and falsely aggregated and disaggregated nodes. We simulate these six measurement errors using an online social network and a publication citation network, reporting their effects on four node-level measures – degree centrality, clustering coefficient, network constraint, and eigenvector centrality. Our results suggest that in networks with more positively-skewed degree distributions and higher average clustering, these measures tend to be less resistant to most forms of measurement error. In addition, we argue that the sensitivity of a given measure to an error scenario depends on the idiosyncracies of the measure's calculation, thus revising the general claim from past research that the more ‘global’ a measure, the less resistant it is to measurement error. Finally, we anchor our discussion to commonly-used networks in past research that suffer from these different forms of measurement error and make recommendations for correction strategies.     

Some unique properties of eigenvector centrality

Eigenvectors, and the related centrality measure Bonacich's c(β), have advantages over graph-theoretic measures like degree, betweenness, and closeness centrality: they can be used in signed and valued graphs and the beta parameter in c(β) permits the calculation of power measures for a wider variety of types of exchange. Degree, betweenness, and closeness centralities are defined only for classically simple graphs—those with strictly binary relations between vertices. Looking only at these classical graphs, where eigenvectors and graph–theoretic measures are competitors, eigenvector centrality is designed to be distinctively different from mere degree centrality when there are some high degree positions connected to many low degree others or some low degree positions are connected to a few high degree others. Therefore, it will not be distinctively different from degree when positions are all equal in degree (regular graphs) or in core-periphery structures in which high degree positions tend to be connected to each other.     

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.     

Social networkers: Measuring and examining individual differences in propensity to connect with others

The research examined individual differences in people's propensity to connect with others (PCO). A measure of PCO, with components for making friends (strong ties), making acquaintances (weak ties), and joining others (bridging ties), was developed and tested in two studies involving 144 undergraduates and 197 health-care employees. PCO and its components were significantly positively associated with social network characteristics (including size, betweenness centrality, and brokerage) and indicators of personal adjustment including support received, attainment, well-being, influence, and suggestion-making. PCO had effects beyond those of major personality traits, and PCO components displayed distinctive relationships with work network characteristics.     

Are respondents more likely to list alters with certain characteristics?: Implications for name generator data

Analyses of egocentric networks make the implicit assumption that the list of alters elicited by name generators is a complete list or representative sample of relevant alters. Based on the literature on free recall tasks and the organization of people in memory, I hypothesize that respondents presented with a name generator are more likely to name alters with whom they share stronger ties, alters who are more connected within the network, and alters with whom they interact in more settings. I conduct a survey that presents respondents with the GSS name generator and then prompts them to remember other relevant alters whom they have not yet listed. By comparing the alters elicited before and after prompts I find support for the first two hypotheses. I then go on to compare network-level measures calculated with the alters elicited by the name generator to the same measures calculated with data from all alters. These measures are not well correlated. Furthermore, the degree of underestimation of network size is related to the networks’ mean closeness, density, and mean duration of relationships. Higher values on these variables result in more accurate estimation of network size. This suggests that measures of egocentric network properties based on data collected using a single name generator may have high levels of measurement error, possibly resulting in misestimation of how these network properties relate to other variables.     

Structural effects of network sampling coverage I: Nodes missing at random

Network measures assume a census of a well-bounded population. This level of coverage is rarely achieved in practice, however, and we have only limited information on the robustness of network measures to incomplete coverage. This paper examines the effect of node-level missingness on 4 classes of network measures: centrality, centralization, topology and homophily across a diverse sample of 12 empirical networks. We use a Monte Carlo simulation process to generate data with known levels of missingness and compare the resulting network scores to their known starting values. As with past studies (0035 and 0135), we find that measurement bias generally increases with more missing data. The exact rate and nature of this increase, however, varies systematically across network measures. For example, betweenness and Bonacich centralization are quite sensitive to missing data while closeness and in-degree are robust. Similarly, while the tau statistic and distance are difficult to capture with missing data, transitivity shows little bias even with very high levels of missingness. The results are also clearly dependent on the features of the network. Larger, more centralized networks are generally more robust to missing data, but this is especially true for centrality and centralization measures. More cohesive networks are robust to missing data when measuring topological features but not when measuring centralization. Overall, the results suggest that missing data may have quite large or quite small effects on network measurement, depending on the type of network and the question being posed.     

A New Model for Information Diffusion in Heterogeneous Social Networks

This paper discusses a new model for the diffusion of information through heterogeneous social networks. In earlier models, when information was given by one actor to another the transmitter did not retain the information. The new model is an improvement on earlier ones because it allows a transmitter of information to retain that information after telling it to somebody else. Consequently, the new model allows more actors to have information during the information diffusion process. The model provides predictions of diffusion times in a given network at the global, dyadic, and individual levels. This leads to straightforward generalizations of network measures, such as closeness centrality and betweenness centrality, for research problems that focus on the efficiency of information transfer in a network. We analyze in detail how information diffusion times and centrality measures depend on a series of network measures, such as degrees and bridges. One important finding is that predictions about the time actors need to spread information in the network differ considerably between the new and old models, while the predictions about the time needed to receive information hardly differ. Finally, some cautionary remarks are made about using the model in empirical research.     

Node centrality in weighted networks: Generalizing degree and shortest paths

Ties often have a strength naturally associated with them that differentiate them from each other. Tie strength has been operationalized as weights. A few network measures have been proposed for weighted networks, including three common measures of node centrality: degree, closeness, and betweenness. However, these generalizations have solely focused on tie weights, and not on the number of ties, which was the central component of the original measures. This paper proposes generalizations that combine both these aspects. We illustrate the benefits of this approach by applying one of them to Freeman’s EIES dataset.     

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.