Testing centralization in random graphs

Centrality is an important concept in social network analysis which involves identification of important or prominent actors. Three common definitions of centrality are degree centrality, closeness centrality and betwenness centrality which yield actor indices. By aggregating these actor indices of centrality across actors, we obtain a single group-level index of centralization. In this paper, we consider the problem of testing whether the observed data is likely to have come from a particular kind of centralized structure of a given size, edge probability and extent of centralization. Eight different group-level indices of centralization are used as test statistics of graph centralization. As our graph model, we assume a general blockmodel which allows a rich probabilistic structure. By carrying out a simulation study the performance of the tests is evaluated by comparing their power functions. The results imply that two tests based on degree and four tests based on closeness have high power. In addition, critical values of the tests are modeled conditional on graph parameters via a linear regression model. An application is illustrated with analysis on a real data set.     

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.     

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.     

Centrality in affiliation networks

This paper discusses the conceptualization, measurement, and interpretation of centrality in affiliation networks. Although centrality is a well-studied topic in social network analysis, and is one of the most widely used properties for studying affiliation networks, virtually all discussions of centrality and centralization have concerned themselves with one-mode networks. Bonacich's work on simultaneous group and individual centralities is a notable exception (Social Networks, 1991, 13, 155–168). I begin by outlining the distinctive features of affiliation networks and describe four motivations for centrality indices in affiliation networks. I then consider properties of some existing centrality indices for affiliation networks, including the relationship between centralities for actors and events in these networks, and present a new conceptualization of centrality that builds on the formal properties of affiliation networks and captures important theoretical insights about the positions of actors and events in these networks. These centralities are then illustrated on Galaskiewicz's data on club and board memberships of a sample of corporate executive officers (Social Organization of an Urban Grants Economy. New York: Academic Press, 1985). The conclusion to this paper discusses strengths and weaknesses of centrality indices when applied to affiliation networks.     

You are who remembers you. Detecting leadership through accuracy of recall

We measured interpersonal perception accuracy by focusing on the relationship between actors’ centrality and their ability to accurately report their social interactions. We used the network measures of actors’ betweenness centrality and degree centrality to identify the most prominent members by correlating ego-perception and alter-perception in a “non-reciprocity” type of misalignment. We found a positive correlation between actors’ centrality and their centrality as assessed by senior management, and a negative correlation between actors’ centrality and their accuracy in recalling interactions. Underreporting social interactions may represent a third way of measuring the importance of members and finding the most influential actors.     

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.     

Assessing the performance of the bootstrap in simulated assemblage networks

Archaeologists are increasingly interested in networks constructed from site assemblage data, in which weighted network ties reflect sites’ assemblage similarity. Equivalent networks would arise in other scientific fields where actors’ similarity is assessed by comparing distributions of observed counts, so the assemblages studied here can represent other kinds of distributions in other domains. One concern with such work is that sampling variability in the assemblage network and, in turn, sampling variability in measures calculated from the network must be recognized in any comprehensive analysis. In this study, we investigated the use of the bootstrap as a means of estimating sampling variability in measures of assemblage networks. We evaluated the performance of the bootstrap in simulated assemblage networks, using a probability structure based on the actual distribution of sherds of ceramic wares in a region with 25 archaeological sites. Results indicated that the bootstrap was successful in estimating the true sampling variability of eigenvector centrality for the 25 sites. This held both for centrality scores and for centrality ranks, as well as the ratio of first to second eigenvalues of the network (similarity) matrix. Findings encourage the use of the bootstrap as a tool in analyses of network data derived from counts.     

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.     

Networks containing negative ties

Social network analysts have often collected data on negative relations such as dislike, avoidance, and conflict. Most often, the ties are analyzed in such a way that the fact that they are negative is of no consequence. For example, they have often been used in blockmodeling analyses where many different kinds of ties are used together and all ties are treated the same, regardless of meaning. However, sometimes we may wish to apply other network analysis concepts, such as centrality or cohesive subgroups. The question arises whether all extant techniques are applicable to negative tie data. In this paper, we consider in a systematic way which standard techniques are applicable to negative ties and what changes in interpretation have to be made because of the nature of the ties. We also introduce some new techniques specifically designed for negative ties. Finally we show how one of these techniques for centrality can be extended to networks with both positive and negative ties to give a new centrality measure (PN centrality) that is applicable to directed valued data with both positive and negative ties.     

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.     

Centrality and power revisited: actor success in group decision making

For many years, network analysts viewed positional centrality as a source of social power. More recently, laboratory studies of exchange networks have called the centrality–power link into question: under zero-sum exchange conditions, the ability of certain actors to directly exploit others has been found to account for power independent of actors' centrality. But most observers believe that in non-zero-sum communication networks, centrality should positively affect power. In this study we examine the effect of centrality on power in a communication network involving group voting on political issues. Using a model in which actors' votes are determined by the strength of their initial positions and the social pressures to which they are subjected, we conduct computer simulations to examine the extent to which actors in various network positions achieve favorable political outcomes. Our findings indicate that the link between centrality and power is highly contingent on the structure of the network. In networks with a central actor and an odd number of subgroups, central actors fail to dominate. In fact, in these networks, when peripheral actors are able to directly influence one another, the central actor becomes the least powerful in the network. In networks with a central actor and an even number of subgroups, however, the central actor dominates even in situations with connected peripherals. The highly contingent effect of centrality on power accords with the findings of exchange theorists who have studied power under zero-sum conditions. This raises questions about the nature of the distinction between communication and exchange networks.     

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.     

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.     

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.     

Informal lending networks in rural Ethiopia

Economic development in emergent nations is tied to smallholder subsistence populations whose livelihoods are vulnerable to exogenous shocks. When shocks occur, individuals often rely on resources embedded within informal insurance networks. Resource access is related to network position and reflected in properties such as centrality and reachability. We analyze a complete informal lending network (188 nodes, 295 ties) among the Sidama, an agro-pastoralist population in southwestern Ethiopia. Results indicate that culturally salient indicators of wealth, such as cattle ownership and gender, largely account for network structure. Analysis of a complete network further allows us to discuss the impact of global network properties, such as overall typology, on a communities response to different types of shocks (covariate and idiosyncratic). These findings extend our understanding of how individuals and communities engage informal lending networks in response to exogenous shocks.     

Adolescent network positions and memory performance in adulthood: Evidence from sibling fixed effects models with sociometric network data

Although research has explored social factors influencing memory performance during adolescence, the impact of adolescent social network positions remains largely unknown. This study examines whether adolescent network position is associated with memory performance in adulthood, while also considering potential gender differences. The study used a sibling sample from the National Longitudinal Study of Adolescent to Adult Health (N = 2462) and employed sibling fixed effects models to account for unobserved family background factors, such as genetics, parental characteristics, family environment, and childhood neighborhood. Four dimensions of adolescent network position—i.e., popularity, sociality, degree centrality, and closeness centrality—were sociometrically assessed in schools. Memory performance in adulthood was measured using the Rey Auditory Verbal Learning Test. The sibling fixed effects estimates indicate that sociality, degree centrality, and closeness centrality are significantly associated with increased memory performance in adulthood, even after controlling for unobserved family heterogeneity as well as a set of individual-level covariates. In contrast, controlling for unobserved family heterogeneity attenuated the association for popularity, making it statistically insignificant. This study also provides evidence of gender differences in the association between social network position and memory performance. The associations for popularity, sociality, and degree centrality are more pronounced among men than women. This study’s findings highlight the importance of adolescent network positions as social determinants in shaping cognitive outcomes over the life course. Interventions that encourage positive peer interactions and reduce social isolation during adolescence may help improve cognitive health in the population.     

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.     

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