|
Items in cart [0] |
Questions? Call 888-624-8373 |
| Copyright © 2009. National Academy of Sciences. All rights reserved. Terms of Use and Privacy Statement |
Below are the first 10 and last 10 pages of uncorrected machine-read text (when available) of this chapter, followed by the top 30 algorithmically extracted key phrases from the chapter as a whole.
Intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text on the opening pages of each chapter.
Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.
Do not use for reproduction, copying, pasting, or reading; exclusively for search engines.
OCR for page 253
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
OCR for page 254
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
OCR for page 255
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
OCR for page 256
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
OCR for page 257
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
OCR for page 258
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
OCR for page 259
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
OCR for page 260
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
OCR for page 261
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
OCR for page 262
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
OCR for page 263
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
OCR for page 264
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
Representative terms from entire chapter:
degree centralization
