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.     

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.     

Learning in social networks: Selecting profitable choices among alternatives of uncertain profitability in various networks

Social capital theory assumes that information is valuable. However, only rarely is this value explicitly modeled, and there are few examples of empirical tests of mechanisms that connect social network structure to valuable information. We model an individual decision problem in which individuals make choices that yield uncertain outcomes. The individuals can learn about the profitability of options from their own choices and from the network. We generate computer-simulated data to derive hypotheses about the effect of network characteristics on making profitable choices. We conduct a laboratory experiment to empirically test these hypotheses and find that, at the individual level, degree centrality has a positive effect on making profitable choices whereas betweenness centrality has no effect. At the network level, density has a positive effect on making profitable choices, whereas centralization does not have an effect.     

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.     

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.     

Affinity Paths and information diffusion in social networks

Widespread interest in the diffusion of information through social networks has produced a large number of Social Dynamics models. A majority of them use theoretical hypothesis to explain their diffusion mechanisms while the few empirically based ones average out their measures over many messages of different contents. Our empirical research tracking the step-by-step email propagation of an invariable viral marketing message delves into the content impact and has discovered new and striking features. The topology and dynamics of the propagation cascades display patterns not inherited from the email networks carrying the message. Their disconnected, low transitivity, tree-like cascades present positive correlation between their nodes probability to forward the message and the average number of neighbors they target and show increased participants’ involvement as the propagation paths length grows. Such patterns not described before, nor replicated by any of the existing models of information diffusion, can be explained if participants make their pass-along decisions based uniquely on local knowledge of their network neighbors affinity with the message content. We prove the plausibility of such mechanism through a stylized, agent-based model that replicates the Affinity Paths observed in real information diffusion cascades.     

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.     

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.     

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.     

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.     

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.     

Effects of temporal resolution adjustments on dynamic sexual contact models

Simulation and inferential modeling of sexual contact dynamics can be used to help predict the propagation of sexually transmitted infections (STI) such as HIV, by providing information on both cross-sectional network structure and how that structure changes over time. Researchers’ choices regarding the temporal resolution of such network models is often driven by the resolution of the data collected to support model fitting and evaluation. These inherited temporal resolutions can become problematic if they differ from the resolution of other processes to which the network must be related. In such cases, a model “correction” is necessary: specifically, we would like to have a systematic method for adjusting a fitted model to allow it to make predictions at a different timescale than the one on which it was initially based. Here, we introduce a basic set of desiderata for such adjustments, and assess three very simple approaches to timescale adjustments for models of sexual contact networks (SCNs), with focus on models parameterized within the separable temporal exponential family random graph model (STERGM) framework. We also examine the impact of time-scale changes on SCN characteristics themselves, and outline a set of desiderata for what an adjustment strategy may be expected to achieve. Our findings have implications both for timescale correction of dynamic network models, and for dynamic network data collection.     

Sorting out centrality: An analysis of the performance of four centrality models in real and simulated networks

Although the concept of centrality has been well developed in the social networks literature, its empirical development has lagged somewhat. This paper moves a step in that direction by assessing the performance of four centrality models under a variety of known and controlled situations. It begins by examining the assumptions underlying each model, as well as its behavior in a community influence network. It then assesses the robustness and sensitivity of each model under conditions of random and systematic variation introduced into this network.     

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.     

Rational voters in a partisanship model

This paper examines a voter model for the US which is interconnected with the partisan theory. In our model, voters are rational and forward-looking. They are perfectly informed about the preferences of political parties and about the state of the economy. The predictions of our voter model differ from the predictions of conventional voter models, according to which the incumbent benefits from low unemployment and low inflation, irrespective of its political colour. In a partisan setting, the democratic party benefits from high unemployment and the republican party benefits from high inflation. Regressions of presidential approval rates indicate that the predictions of both the partisan voter model and the conventional model are consistent with the data.     

Positions,Roles, and Dependencies in a Community Interorganization System*

This study focuses on community structure as a network of interorganizational linkages, with an eye toward (1) generating new conceptual schemes to study the community as a social network and (2) developing a methodology to measure new dimensions of community structure. An analysis of structurally equivalent roles is performed in two communities for three organizational resource networks: money, information, and moral support. Global dependencies on resource generator, consumer, and transmitter roles for the money network are analyzed using loglinear models. Local dependencies within the money network are also examined. Finally, the study examines the perceived influence of organizations in community affairs as a function of the organizations' global positions within the community network.     

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.     

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.