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.     

Centrality and network flow

Centrality measures, or at least popular interpretations of these measures, make implicit assumptions about the manner in which traffic flows through a network. For example, some measures count only geodesic paths, apparently assuming that whatever flows through the network only moves along the shortest possible paths. This paper lays out a typology of network flows based on two dimensions of variation, namely the kinds of trajectories that traffic may follow (geodesics, paths, trails, or walks) and the method of spread (broadcast, serial replication, or transfer). Measures of centrality are then matched to the kinds of flows that they are appropriate for. Simulations are used to examine the relationship between type of flow and the differential importance of nodes with respect to key measurements such as speed of reception of traffic and frequency of receiving traffic. It is shown that the off-the-shelf formulas for centrality measures are fully applicable only for the specific flow processes they are designed for, and that when they are applied to other flow processes they get the “wrong” answer. It is noted that the most commonly used centrality measures are not appropriate for most of the flows we are routinely interested in. A key claim made in this paper is that centrality measures can be regarded as generating expected values for certain kinds of node outcomes (such as speed and frequency of reception) given implicit models of how traffic flows, and that this provides a new and useful way of thinking about centrality.     

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.     

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.     

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.     

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.     

The use of sparsest cuts to reveal the hierarchical community structure of social networks

We show that good community structures can be obtained by partitioning a social network in a succession of divisive sparsest cuts. A network flow algorithm based on fundamental principles of graph theory is introduced to identify the sparsest cuts and an underlying hierarchical community structure of the network via maximum concurrent flow. Matula [Matula, David W., 1985. Concurrent flow and concurrent connectivity in graphs. In: Alavi, Y., et al. (Eds.), Graph Theory and its Applications to Algorithms and Computer Science. Wiley, New York, NY, pp. 543–559.] established the maximum concurrent flow problem (MCFP), and papers on divisive vs. agglomerative average-linkage hierarchical clustering [e.g., Matula, David W., 1983. Cluster validity by concurrent chaining. In: Felsenstein, J. (Ed.), Numerical Taxonomy: Proc. of the NATO Adv. Study Inst., vol. 1. Springer-Verlag, New York, pp. 156–166 (Proceedings of NATO ASI Series G); Matula, David W., 1986. Divisive vs. agglomerative average linkage hierarchical clustering. In: Gaul, W., and Schader, M. (Eds.), Classification as a Tool of Research. Elsevier, North-Holland, Amsterdam, pp. 289–301; Thompson, Byron J., 1985. A flow rerouting algorithm for the maximum concurrent flow problem with variable capacities and demands, and its application to cluster analysis. Master Thesis. School of Engineering and Applied Science, Southern Methodist University] provide the basis for partitioning a social network by way of sparsest cuts and/or maximum concurrent flow.     

Equicentrality and network centralization: A micro–macro linkage

This paper investigates a linkage between micro- and macrostructures as an intrinsic property of social networks. In particular, it examines the linkage between equicentrality [Kang, S.M., 2007. A note on measures of similarity based on centrality. Social Networks 29, 137–142] as a conceptualization of a microstructural process (i.e., the likelihood of social actors to be connected with similarly central others) and network centralization as a macrostructural construct, and shows that they have a negative linear association. In other words, when actors are connected with similarly central alters (i.e., high equicentrality), the overall network centralization is low. Conversely, when highly central actors are connected with low-centrality actors (i.e., low equicentrality), the overall network centralization is high. The relationship between degree equicentrality and degree centralization is more significant in observed networks, especially those evolving over time, as compared to random networks. An application of this property is given by venture capital co-investment networks.     

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.     

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.     

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.     

Unpacking Burt’s constraint measure

Burt (1992) proposed two principal measures of structural holes, effective size and constraint. However, the formulas describing the measures are somewhat opaque and have led to a certain amount of confusion. Borgatti (1997) showed that, for binary data, the effective size formula could be written very simply as degree (ego network size) minus average degree of alters within the ego network. The present paper presents an analogous reformulation of the constraint measure. We also derive minima and maxima for constraint, showing that, for small ego networks, constraint can be larger than one, and for larger ego networks, constraint cannot get as large as one. We also show that for networks with more than seven alters, the maximum constraint does not occur in a maximally dense or closed network, but rather in a relatively sparse “shadow ego network”, which is a network that contains an alter (the shadow ego) that is connected to every other alter, and where no other alter-alter ties exist.     

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.     

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.     

The worldwide maritime network of container shipping: spatial structure and regional dynamics

Port and maritime studies dealing with containerization have observed traffic concentration and dispersion throughout the world. Globalization, intermodal transportation, and technological revolutions in the shipping industry have resulted in both network extension and rationalization. However, lack of precise data on inter‐port relations prevent the application of wider network theories to global maritime container networks, which are often examined through case studies of specific firms or regions. In this article, we present an analysis of the global liner shipping network in 1996 and 2006, a period of rapid change in port hierarchies and liner service configurations. While we refer to literature on port system development, shipping networks, and port selection, the article is one of the only analyses of the properties of the global container shipping network. We analyse the relative position of ports in the global network through indicators of centrality. The results reveal a certain level of robustness in the global shipping network. While transhipment hub flows and gateway flows might slightly shift among nodes in the network, the network properties remain rather stable in terms of the main nodes polarizing the network and the overall structure of the system. In addition, mapping the changing centrality of ports confirms the impacts of global trade and logistics shifts on the port hierarchy and indicates that changes are predominantly geographic.     

Reinterpreting network measures for models of disease transmission

In the wake of AIDS and HIV, a better framework is needed to model the pattern of contacts between infectious and susceptible individuals. Several network measures have been defined elsewhere which quantify the distance between 2 nodes, and the centrality of a node, in a network. Stephenson and Zelen (S-Z), however, have recently presented a new measure based on statistical estimation theory and applied it to a network of AIDS cases. This paper shows that the closeness measure proposed by S-Z is equivalent to the effective conductance in an electrical network, fits the measure into the existing theory of percolation, and provides a more efficient algorithm for computing S-Z closeness. The S-Z methodology is compared with the closeness measures of maximal flow, first passage time, and random hitting time. Computational problems associated with the measure are discussed in a closing section.     

Centrality in social networks conceptual clarification

The intuitive background for measures of structural centrality in social networks is reviewed and existing measures are evaluated in terms of their consistency with intuitions and their interpretability.Three distinct intuitive conceptions of centrality are uncovered and existing measures are refined to embody these conceptions. Three measures are developed for each concept, one absolute and one relative measure of the centrality of positions in a network, and one reflecting the degree of centralization of the entire network. The implications of these measures for the experimental study of small groups is examined.     

Computing core/periphery structures and permutation tests for social relations data

The core/periphery structure is ubiquitous in network studies. The discrete version of the concept is that individuals in a group belong to either the core, which has a high density of ties, or to the periphery, which has a low density of ties. The density of ties between the core and the periphery may be either high or low. If the core/periphery structure is given a priori, then there is no problem in finding a suitable statistical test. Often, however, the structure is not given, which presents us with two problems, searching for the optimal core/periphery structure, and devising a valid statistical test to replace the one invalidated by the search. UCINET [Borgatti, S.P., Everett, M.G., Freeman, L.C., 2002. UCINET for Windows, Version 6.59: Software for Social Network Analysis. Analytic Technologies, Harvard], the oldest and most trusted network program, gives incorrect answers in some simple cases for the first problem and does not address the second. This paper solves both problems with an adaptation of the Kernighan–Lin search algorithm, and with a permutation test incorporating this algorithm.