Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

Balancing Efficiency and Vulnerability in Social Networks Elisa Jayne Bienenstock University of California, Irvine Phillip Bonacich University of California, Los Angetes Abstract Network centrality is thought to be crucial for the efficient distribution of information or resources through a social network. Inherent to this structure, the flow of information in high- centraTity networks can be easily undermined. By introducing two concepts, network efficiency and vulnerability, we show that efficiency is compromised more in networks characterized by high degree centralization when degree and betweenness centrality are not distinct than in other networks, following the removal of network positions. Vulnerability is the loss in efficiency resulting from the elimination of nodes. The resiliency of a network was then assessed following progressive removal of nodes and all adjacent nodes. Nodes were removed in two ways: I) randomly, which modeled incidental vulnerability; or, 2) based on the calculated centrality measures. which modeled vulnerability to a strategic attack. Our findings highlight the social impact of removing a person from a network, which is likely to disable, or make inactive, all direct ties to that individual. Such network analyses can be used to undermine or fortify existing network structures necessary for law enforcement and those concerned with national security. DYNAMIC SOCIAL N~TWORKAJODE~WG ED TRYSTS 253

Introduction Social networks can be generally defined as a group of inter-connected individuals. The patterns of exchange of information or resources from person to person varies dependent on the inherent structure of the network. One simple network can be modeled as a pinwheel structure: each person, e.g.. node, is connected to a common tie, which is the individual occupying the hub, or center, of the network (Fig. la). This structure has been shown to facilitate the flow of communication, since information from any location requires only two steps to saturate the network. If, however, the center node is removed the entire network collapses as the nodes occupying the periphery of this structure become isolated. As such, the pinwheel network is both very efficient and highly vulnerable as it is easily penetrated from an outside attack. The stability of a network is, therefore, dependent on its organization and ability to withstand such an attack. Initial research found that networks with one, or several, central nodes were more efficient than networks in which the number of connections between nodes was more evenly dispersed (Bavelas, 1950). Freeman (1978) distinguished three conceptually different types of individual centrality: degree, betweenness and closeness, together with their corresponding system-wide, measure of the dispersion of the centrality, or centralization (Freeman, 1978:2281. Degree is number of connections: a node with high degree has many connections. A network with high degree centralization is likely to have a few nodes with many ties and many nodes with few ties, such as the hub in a pinwheel structure. Betweenness measures the frequency with which a node is located on a path between other nodes: a node with high betweenness is in a position to act as either a bridge or a bottleneck. A network with high betweenness centralization is likely to have a few nodes that act as bndges. Closeness measures the degree to which a node is close to over nodes in the network. Centrality measures have been shown to be indicators of prestige or importance amen;, actors in networks. Similarly, centralization has been associated with efficiency. In another study (Cook. 1983), it was shown that, for tasks other than communication. centrality measures are not good indicators of who has power in the network. While local centrality measures predicts which individuals in a network have more control of the flow of information, and global centrality measures are good predictors of overall el~f~ciency, this study (Cook, ~ 983) showed that in exchange networks, where the value of the commodity exchanged is lost to the person who relinquishes it, centrality measures do not predict who will have power to control resources. As an alternative to traditional centrality measures, this study (Cook, 1983) employed a vulnerability measure known as point vulnerability which measures the reduction in maximum resource flow (RMF) to the network that results when each position is removed. En an exchange network each individual adds value to the total value possible for the network, the network is vulnerable from the removal of an individual to the degree that value is lost to the network. This concept, point vuinerabiiity did not do any better than centrality, ultimately, as a measure of power in exchange networks, so development of this measure was abandoned (Markovsky et al., 1988). Application of network methods to cnminal and terrorists activity suggests that vulnerability may be an important and under-utilized network measure. 254 DYNAMIC SOCKS NETWO=MODELING AND ^^YSIS

A recent renon suggested that high decree centrality networks wore troth ~.ffic~i~nt ~nr1 invulnerable to random attacks when compared to random networks (Barabasi 2002~. This finding is in part a function of the definition used to define attack as the removal of one node from the network Consider the pinwheel (Fig ~ a). The only node essential for the functioning of the network is the central node and that node has only a I/9 chance of being selected. The odds are good that the network can withstand a random attack. However, this report also notes that these networks are very susceptible to strategic attacks. If the network structure is known and centrality measures are calculated, then critical nodes are easily identified. ~ O A ~ In this paper, we examine which network properties are required to design networks that are both efficient and resilient by compann;, of networks based on the following four prototypes: random, scale-free, lattice and bipartite. We show that lattice structures and bipartite graphs that include a small proportion of random ties are the best at achieving enduring efficiency. While scale-free. high centrality networks do well when compared to random networks, they do not do well when compared with these other structures. We also expanded the scope of vulnerability, defining, vulnerability as the removal of a node and all adjacent nodes. This models the likely effect of the removal of a node in a social network. When this more stringent type of vulnerability is considered the rewired lattice and rewired bipartite networks do well. wok A - a. b. c. Figure 1. A pinwheel' lattices and bipartite graph. Methods Efficiency is defined as: n n L/d E i=l Hi n(n- 1) E is the "efficiency" of a communications network' dij is the distance between vertices i and j. Shorter distances imply more effective communication and more efficient networks. When a network consists of more than one component such that ~ and j are not connected, dij is undefined. The reciprocal of the distance between nodes is zero for vertices in separate components and approaches ore as the distance between two nodes diminishes. The denominator creates a measure that vanes from zero to one where one is complete connectivity DYNAMIC SOCIAL N'~TWO=MODE~G ED ISIS 255

all nodes are directly connected to all other nodes and zero indicates the dissolution of the network into separate components. Vulnerability (EA ~ is a measure of the average decrease in efficiency of the network after attack and takes into account the entire history of the attack and the rapidity of the decline. K hi E=i=l A K Let E1, E2,....EK be the efficiency the network after the elimination of 1, 2, up to K nodes. EA measures the average loss of efficienyv during K attacks so that networks with ~ Marc. r~nir1 ~ Cal _ ~,^~^ ~ ~.r~ decline will have higher EA scores. Efficiency and the reduction in efficiency were compared for ten networks of each type. The reduction in efficiency resulting from random attacks, attacks aimed against individuals with high betweenness centrality and attacks aimed against individuals with high degree were was calculated for each network. Table ~ summarizes the measures calculated for each network and compared in the analysis that follows. Table I. Measures compared: Efficiency, reduction in efficiency and centralization. E ER EB ED CB . CD Initial efficiency. The range is from O to I. Recalculated efficiency after K attacks on randomly selected nodes. The range is from Oto K. . . . _ .. Recalculated efficiency after K attacks on nodes with highest betweenrness centrality. The ran~eis from Oto K. I' ~ ~ _ . Recalculated efficiency after K attacks on nodes with highest degree centrality The range is from O to K. Betweenness centralization. The range is from O to I. . . . _ . . Decree centralization. The range is from O to I. Networks Four network structures were compared. Networks were the same with respect to size (N=IOO) and density (density = 41. Random networks. Random networks serve as a baseline and have desirable properties of the own in terms of efficiency and vulnerability. Distances between vertices are short and they are decentralized and thus relatively invulnerable. To guarantee the connectedness of the network a circle frame network was imposed on lOO modes and lOO additional connections were randomly assigned. Scale-free networks. Scale-free networks are networks characterized by having hubs (Fig la). Therefore, we predicted high degree centralization. Beginning with a small random network of ninety-five, additional positions with initial degree ~ were added using the scare-free al~,or~thm; 256 DYNAMIC SOCKS NETWO~MODEL~G kD TRYSTS

the probability that a new node would connect to an existing node was proportional to the degree of the existing node. Lattice networks. A ten by ten lattice network on a torus was created using the Von Neumann definition of neighbors (Fig Ib). As counterpoint to the scale-free network, lattice degree and betweenness centralization are zero. We also investigated a lattice that was rewired so that forty connections from the lattice network were replaced with randomly chosen connections, modeling a small world network (Watts, 19991. Since a lattice is not an efficient structure, but it is very resistant to attack, we predicted a rewired lattice to be more efficient then the lattice with no random connections (Watts, ~ 9991. We hypothesized that this increase in efficiency would not undermine its resistance to attack in standard two-dimensional lattice. Lastly, we investigated the efficiency and resilience of three-dimensional lattices. Bipartite networks. Bipartite networks were included because they modeled a structure that resembled read world criminal network structures. The network was composed of two types of actors. Actors can only be connected to members of the other class (Fig lo). We were interested in a network that modeled a hierarchy where one class represented group leaders and the other the soldiers. The sizes of the two classes were twenty and eighty. Bipartite networks differ from actual criminal network insofar as in real networks members of the leadership are often directly connected. For that reason, bipartite network are likely less vulnerable than real life networks. In addition to strict bipartite networks we investigated bipartite networks that included some randomness. Forty edges from a bipartite network were randomly eliminated and replaced with 40 connections between positions in the larger class. We expected this to increase efficiency. To ensure networks were connected each of the eighty vertices in the larger class was randomly connected to one of the vertices in the smaller class and 120 additional randomly chosen edges were then added. Results Node Vulnerability A comparison of the loss in efficiency for the random, scale free, rewired bipartite and rewired lattice structures to removal one node from the network, for five consecutive attacks confirm results of prior research that scale free networks are better than random networks at resisting random attacks, but they do not do better then a rewired bipartite graph structure. Values in table 2 and the error bars in Figure 2 indicate that scale free networks are the least resistant to strategic attacks that target nodes based on degree or betweenness centrality. DYNAMIC SOCIAL NETWORK MODELING ED ^^YSIS 257

Table 2. Average Initial Efficiencies and Efficiencies Averaged over five attacks for ten networks of each type. I Random Scale-free 1 Bipartite Rewired 2D Lattice Rewired c ~ ~ O.,0 Initial E~ . rrlclency . . . . 0.329 0.370 0.373 0.307 ~ Random . . . . .. ~06 0346 0.349 0.286 - .. . . . ' -'-''-'-'''''''''1---"'''''' '''-'''''---'-''1--'- ' I Random Betweenness Degree Attack Type Average Efficiency during 5 Attacks Cnteria for Tareet Selection . _ ._ . _ . .... High Betweenness 0.165 0.037 0.155 E~,h Degree 0.167 () n41 Hi 0.145 0.181_ 0.179 Error Bars show 95.0% Cl of Mean rig _ Random S. - Scale Free -I Bipartite Rewired x Lattice Rewired ! I network ' Figure 2. Average Efficiency during random, betweenness and degree based attacks for four network types. Node Vulnerability vs. Neighborhood Vulnerability The removal of a node from a graph is only the first step toward modeling the effect of the removal of an individual from a social network. The nature of human interaction is such that when one person is removed from a network, others, especially those who are directly connected to that person, are also affected. When considenng the effect of the removal of an individual on network efficiency a model that focuses only on an isolated individual underestimates the impact that the Toss a key person can have on a network. For example, in a criminal network, the an-est of one individual could result in a lull in the cnminal activity simply because those connected to the arrested individual are alerted to the possibility that they may be under surveillance. 258 DYNAMIC SOCIAL NT:TWORKMODEL~G^D^=YSIS

Alternatively, one network member's ability to function may be contingent on the presences of another, for example when there is a division of labor in an organization. In this case the removal of one network member can incapacitate many. To expand the scope of vulnerability accordingly we define vulnerability as the removal of a node and all adjacent nodes. The following simulation illustrates the effect on network efficiency when vertices and their neighbors are eliminated by attacks rather than when vertices alone are eliminated. Random networks of size ~ 5 with different average degrees were created and attacked either by eliminating the most central (betweenness) position or by eliminating the mn.ct c:P.ntrn1 no~itinn plus its neighbors. Each cell table 3 is based on 10 simulations. · ,O~ ~ ~ ~ it. , ~ . Table 3. Average degree and efficiency in random networks when Dosition or nn~iti`'n Dilly its neighbors eliminated. Average degree Efficiency Nodal attack Neighborhood attack 3 .534 .456 .249 4 .607 .520 .252 5 .663 .571 .199 6 .707 .612 .268 . . 7 .750 .648 .191 8 .786 .683 .120 These results indicate that nodal vulnerability differs from neighborhood vulnerability. Depending on the research question the implications for vulnerability are different for different measures. As degree, or connectivity of the average node increases and high betweenness nodes are targeted the decrease in efficiency is minor. In fact, just as efficiency increases with degree so does efficiency in spite of nodal attack. However, if neighborhoods are implicated along with the node the opposite is true. As average degree increases network efficiency decreases. This is not only because more people are removed from the network, but also because there is an increasing likelihood that a random person will be connected to a person with higher degree centradity The implication is that cells of criminal activity, connected by a few individuals with high betweenness are very vulnerable to the discovery of these individuals. Centralization For each structure type, ten networks were generated, each network containing 100 vertices with an average degree of 4 (200 edges). When networks were rewired (the bipartite and lattice networks). the number of rewired edges was 40. The maximum number of attacks was 5. An attack is the removal of a node along with all adjacent nodes. Criteria for node selection were ~ ~ random, 2) high degree centrality, or 3) high betweenness centrality. For most networks, there was no difference between betweenness and decree centralization. This is, in part, because for most networks betweenness and degree were highly correlated, as high betweenness is a function of high decree centrality. Networks in which these two centrality measures were not synonymous were likely to be most capable of balancing, DYNAMIC SOCKS N~TWO=MODEL~G~D TRYSTS 259

260 efficiency and invulnerability. For example, when correlations of nodal degree and betweenness were compared for three rewired-lattice networks, the correlations were 0.785, 0.729, and 0.753; for three scale-free networks the correlations were 0.943, 0.973, and 0.957. Average values for initial efficiency, betweenness centralization and degree centralization for ten simulations runs for each type of network are presented in Table 4. The standard errors were small, so even small differences were significant. There was a relationship between centralization and efficiency: efficiency was related centralization as structures with high centrality also had high values for efficiency. The scaJe-free network, which is highest in both types of centralization, did not have the highest initial efficiency. Rather, the rewired bipartite graph had the highest initial efficiency score. Table 5 presents correlation coefficients for initial efficiency by betweenness and degree centralization. Table 4. Initial efficiency, betweenness centralization and degree centralization with standard errors for six network structures. Network Random ]~=e~ Betweenness Centralization ~ Degree Centralization ~ . _ 0.33 1 0.265 0.000 0.020 0.357 0.613 0.002 0.019 . __ . _ . . 0.341 0.639 0.001 0.038 l 0.373 0.449 0.001 0.096 . 0.2s8 O.ooo 0.000 0.000 . 0.307 0.238 0.001 0.014 l 0.095 0.006 Scale Free 0.34s 0.023 Bipartite 0.215 0.008 0.196 0.009 0.000 0.000 0.048 0.003 Bipartite Rewired Lattice Lattice Rewired Table 5. Correlation of Initial efficiency, betweenness centralization and degree centralization for six- network structures. Initial Betweenness Efficiency Centralization Initial ~ . . . . e Efficiency 1.000 0.75 ~ * ~ .... __ Betweenness Centralization 0.75 ~ ~ ~ .000 Degree Centralization 0.740* 0.921 ** . . . Correlation is significant at the 0.05 level (~-tailed) .. ~ . **Correlation is significant at the 0.01 level (2-tailed) Degree Centralization 0.740* 0.921*~ 1.000 DYNAMIC SOCIAL NETWO=MODELING AND ANALYSIS

Neighborhood Vulnerability to Attacks To be invulnerable to attacks, networks must be able to sustain successive attacks and still remain a network. In others words the network should not disintegrate into many components. A network should also be able to continue functioning. Table 6 presents data from ten runs of six network types. Each network was subject to a five hits of three types. After each hit the efficiency of the remaining network was computed and a~e~a~,ecl for ail attacks (EA). Values for random attacks, attacks based on degree centrality and attacks based on betweenness centrality are compared. Table 6. Efficiency and average reduction in efficiency due to random and selective attacks based on betweenness and degree centrality by network type. ~ Average Efficiency dunng 5 Attacks Cntena for Target selection ...... ._ . ~ _ _ _ . . .. Network Efficiency Random Between ness Degree Random 0.331 .238 .166 .165 . 0.000 0.016 0.008 0.009 Scale Free 0.357 .234 .058 .057 0.002 0.034 0.014 0.013 Bipartite 0.341 .207 .132 138 0.001 0.021 0.008 0.020 . . _ . _ Bipartite 0.373 0.220 0.1 46 0.1 46 Rewired 0.001 0.018 0.007 0.009 Lattice 0.258 .1 86 .1 87 .205 0.000 0.003 O.QOO O.000 Lattice 0.307 0.222 .182 .184 Rewired 0.001 0.006 0.006 0.006 . Scale-free networks are initially efficient, as are rewired bipartite graphs. The scale-free network is also more resistant than most other structures to random attacks (Figure 3) although again not as resistant as random networks or the rewired lattices. The distinction between these structures becomes salient when strategic attacks are considered (Figure 41. Scale-free networks are the least resistant of all networks to strategic attacks. Adding random connections to the lattice and bipartite networks increases efficiency without sacnf~cing resilience. In fact the rewired bipartite network has higher efficiency after any type of attack then its rigidly structured counterpart. Graphs for degree vulnerability are not plotted since they do not differ significantly from the values for betweenness vulnerability. DYNAMIC SOCIAL NETWO~MODEL~G ED ISIS 261

0.4 lo, 0.25 ~ =~can _ ~ 2 ~ 0.15 - ~. O. . 1 - --- ---- - -__ _ ____ _ . _. _ ._ __ _ . __ 0 . 0 5 ...... ._ _ .~_ ~ __ _ . __~ ~ ___ __ ._ . ~ . _ _._ I. _ __ _. _ __ _ . _ _ _ ._ ........ ° ''''''~~~~ ~ ~~~~~ ~ ~'~~ ~ ~~~ - ~ ~ ~ ~~ ~ ~~~r ~ ~_. _ ___ _ __ _ _ _ Efficiency Attack 1 Attack 2 Attack 3 Number of Attacks (K) Attack 4 Attack ~ '-i:.; Randon, ~Scale Free Bipartite ~Elipartite-R -Latticed _ Latt~ce2R,' Figure 3. Loss of Efficiency resulting from 5 random hits. 0.25 C, at_ C' - 0.2 0.15 0.1 - - ............................. 0.05 j - ~ i O ark,, Efficiency Attack 1 Attack 2 Attack 3 Attack 4 Attack 5 Number of Attacks (K] __. _ ._ i __ _ _ _. _ _ _ .. .. ....... ..................... . .. .... . . -I- Random ~ Scale Free + Bipartite ~ BipartiteR ~ Lattice2 ~ Lattice2R . Figure 4. Loss of Efficiency resulting, from 5 hits targeted at nodes with high betweenness. 262 DYNAMIC SOCIAL NETWO=MODELING AND ANALYSIS

Finally, the data clearly demonstrate that using centrality measures to select targets to weaken networks is beneficial. Table 5 presents the differences between measures of efficiency after attacks on targets chosen randomly or based on betweenness centrality. All but two values are positive indicating that efficiency levels after each attack are higher when the target is chosen randomly than when it is chosen strategically. In the two instances where this is not the case the values are nearly zero. Table 7. Differences in efficiency between random and selective attacks by network structure Scale Free Rewired Rewired Lattice Bipartite 0 0.000 0.000 -0.001 1 0.045 -0.003 0.063 2 0.139 0.007 0.089 . . _ 3 0.135 0.010 0.102 4 0.125 0.017 0.106 5 0.095 0.029 0.106 Conclusion Insights from social network analysis may assist those who design networks in constructing structures that maximize communication yet minimize vulnerability. Designers of networks that may come under attack face two dilemmas. First, centralized networks are very efficient but also vulnerable to selective attacks on their most central members. Second, a high density of connections leads to shorter communication paths and less dependence on particular members but to ensure resistance to attack network members must be separated from one another so an attack on one member does not unravel the entire network. This paper explores classes of networks, random' scale-free, bipartite, and small-world, to explore what properties of networks obviate these dilemmas. The focus of this paper was on the resistance of networks to random attacks and attacks aimed at positions of high centrality. Future work wild expand this to test network resilience to attacks based on other cnteria. For example. selecting targets based on point vulnerability rather than centrality may prove detnmentat to other structures. This research provides insight into the relationship between network structure in terms of centrality, density, efficiency and vulnerability. Future work will test the robustness of these results by expanding the model and the analysis to include larger networks of varying densities. Understanding the relationship of standard network measure to efficiency and vulnerability is a first step toward designing organizational networks that maximize both efficiency and resistance to attack. This will allow researchers and analyst a systematic way to evaluate existing networks to uncover vuInerabilities. DYNAMIC SOCIAL NETWORK AJODEL~G AND A!JAI~YSIS 263

References Barabasi, A. 2002. Linked: The New Science of Networks. Perseus Publishing. Cambridge. Bavelas, A. 1950. "Communication Patterns in Task-Onented Groups." The Journal of the acoustical Society of America 22 6: 725-730. Cook, K. S., R,M. Emerson, M.R. Gillmore, and T. Yarnagishi. 1983. "The Distribution of Power in Exchange Networks: Theory and Expenmenta1 Results." American Journal of Sociology 89:275-305. Freeman, L., ~ 9 7 8 . "Centrality in S o ci al Net w ork s: C onceptuat C l arid c ati on., ' Social Ne two rks 1:215-239. Markovsky, B., D. Wilier, and T. Patton. 1988. "Power Relations in Exchange Networks.~ American Sociological Review 53: 220-236. Watts. D.J. Small Worlds: The Dynamics of Networks between Order arid Randomness. Princeton University Press. New Jersey. 264 DYNAMIC SOCL4L NETWORK MODEL~G ED ISIS