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.     

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.     

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.     

Network centralization with the Gil Schmidt power centrality index

Network centralization is a network index that measures the degree of dispersion of all node centrality scores in a network from the maximum centrality score obtained in the network. The Gil Schmidt power centrality index was developed for use in describing the political networks of Mexico, Gil and Schmidt [Gil, J., Schmidt, S., 1996a. The origin of the Mexican network of power. In: International Social Network Conference, Charleston, SC, USA, pp. 22–25; Gil, J., Schmidt, S., 1996b. The political network in Mexico. Social Networks 18, 355–381]. Upper bounds for network centralization, using the Gil Schmidt power centrality index, are derived for networks of fixed order and for when the network is bipartite, such as can arise from two mode data. In each case the networks that have maximum network centralization are described.     

Egocentric and sociocentric measures of network centrality

Egocentric centrality measures (for data on a node’s first-order zone) parallel to Freeman’s [Social Networks 1 (1979) 215] centrality measures for complete (sociocentric) network data are considered. Degree-based centrality is in principle identical for egocentric and sociocentric network data. A closeness measure is uninformative for egocentric data, since all geodesic distances from ego to other nodes in the first-order zone are 1 by definition. The extent to which egocentric and sociocentric versions of Freeman’s betweenness centrality measure correspond is explored empirically. Across seventeen diverse networks, that correspondence is found to be relatively close—though variations in egocentric network composition do lead to some notable differences in egocentric and sociocentric betweennness. The findings suggest that research design has a relatively modest impact on assessing the relative betweenness of nodes, and that a betweenness measure based on egocentric network data could be a reliable substitute for Freeman’s betweenness measure when it is not practical to collect complete network data. However, differences in the research methods used in sociocentric and egocentric studies could lead to additional differences in the respective betweenness centrality measures.     

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.     

The structure of global centrality measures

The aim of this article is to identify and analyse the logic and structure of centrality measures applied to social networks. On the basis of the article by Borgatti and Everett, identifying the latent functions of centrality, we first use a survey of personal networks with 450 cases to perform an empirical study of the differences and correspondences between degree, closeness and betweenness centrality in personal networks. Then, we examine the correspondences between the three global indicators in each type of centrality: the maximum value, the mean value and the hierarchy or centralization. The results provide a better understanding of the centrality indicators of networks and the reality that they express in an empirical context.     

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.     

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.     

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.     

Network centrality and social movement media coverage: A two-mode network analytic approach

This article examines the relationship between structural location (namely, degree centrality) and news media coverage. Our central hypothesis is that the network centrality of social movement actors is positively associated with the prevalence of actors being cited in the print news media. This paper uses two-mode data from a communication network of environmentalists in British Columbia, and examines the relationship between their structural location and the frequency by which they are cited in newsprint media with regard to particular frames (about forest conservation, environmental protest, and related issues). We asked a sample of social movement participants about their ties to a target list of relatively high profile actors (environmental activists). We turned the resulting network matrix into a bipartite graph that examined the relationships amongst the target actors vis a vis the respondents. Next we calculated point in-degree for the target actors. For the target actors we also have data from a representative sample of 957 print news articles about forestry and conservation of old growth forests in British Columbia. We compare the effects of network centrality of the target actor versus several attributes of the target actors (gender, level of radicalism, leadership status) on the amount of media coverage that each of the target actors receives. We find that network centrality is associated with media coverage controlling for actor attributes. We discuss theoretical implications of this research. Finally, we also discuss the methodological pros and cons of using a “target name roster” to construct two-mode data on social movement activists.     

Reliability of measures of centrality and prominence

This paper evaluates the reliability of measures of centrality and prominence of social networks among high school students. The authors present and discuss results from eight experiments. Four types of social support: (1) instrumental support, (2) informational support, (3) social companionship, and (4) emotional support—were measured three times within each class. Four measurement scales: (1) binary, (2) categorical, (3) categorical with labels and (4) line production—were applied. Reliability of in- and out-degree, in- and out-closeness, betweenness and flow betweenness was estimated by the Pearson correlation coefficient. Meta analysis of factors affecting the test-retest reliability of measures of centrality and prominence was done by multiple classification analysis. Results show that,

• -Global measures (considering direct and indirect choices) are more sensitive to measurement errors than local measures (considering only direct choices).
• -In-measures are more stable than out-measures.
• -Among types of social support, emotional support gives the least stable measures of centrality and prominence, whereas social companionship gives the most stable results.
• -The reliability of centrality and prominence measures is higher when the network is denser.

     

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.     

Measuring centrality in film narratives using dynamic character interaction networks

The tools of social network analysis offer a promising framework for studying fictional texts and the relational activity of the characters therein. The goal of this paper is to offer both a conceptual refinement of the project of measuring the centrality of characters within narratives using network tools, as well as the proposal of a novel measure with which to do so. Conceptually, we argue that as questions of time, order and sequence are central in narratives, measures of characters’ narrative importance should be based on dynamic network representations which respect the time-ordering of narrative events. We suggest a directed dynamic measure of relative character importance based on character interactions and illustrate it through an examination of gender in the 2015 film Star Wars: The Force Awakens. We find that the measure helps illuminate important narrative dynamics which cannot be captured by static measures, and presents a platform on which future character network research can productively build.     

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].     

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.     

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.     

On the robustness of centrality measures under conditions of imperfect data

An analysis is conducted on the robustness of measures of centrality in the face of random error in the network data. We use random networks of varying sizes and densities and subject them (separately) to four kinds of random error in varying amounts. The types of error are edge deletion, node deletion, edge addition, and node addition. The results show that the accuracy of centrality measures declines smoothly and predictably with the amount of error. This suggests that, for random networks and random error, we shall be able to construct confidence intervals around centrality scores. In addition, centrality measures were highly similar in their response to error. Dense networks were the most robust in the face of all kinds of error except edge deletion. For edge deletion, sparse networks were more accurately measured.     

Degree-like centrality with structural zeroes or ones: When is a neighbor not a neighbor?

In the field of social network analysis, there are situations in which researchers hope to ignore certain dyads in the computation of centrality to avoid biased or misleading results, but simply deleting these dyads will result in wrong conclusions. There is little work considering this particular problem except the eigenvector-like centrality method presented in 2015. In this paper, we revisit this problem and present a new degree-like centrality method which also allows some dyads to be excluded in the calculations. This new method adopts the technique of weighted symmetric nonnegative matrix factorization (abbreviated as WSNMF), and we will show that it can be seen as the generalized version of the existing eigenvector-like centrality. After applying it to several data sets, we test this new method's efficiency.