what-when-how
In Depth Tutorials and Information
Table 5.1
QualitativeComparisonofStructuralParametersforSomeReal
SocialandInfrastructureNetworksandRandomNetworks
Average
clustering
coefficient
Average
degree
Network
Diameter
Robustness
Paper network
Very low
Very low
Medium
Easy to shatter
Wireless ad hoc
network
Medium
High
Medium
Hard to shatter
Social network
High
High
Low
Very hard to
shatter
Erdös-Rényi
random network
Variable
Variable
Low
Hard to shatter
Random
geometric graph
Medium
High
Large
Hard to shatter
Note:
The Erdös-Rényi random graph is obtained by placing each edge between a
pair of vertices independently with a given probability. The random geo-
metric graph is obtained by placing points in a unit square uniformly at ran-
dom and adding edges between points that are within a chosen threshold
value of distance [4].
properties. In the table, the degree of a node is the number of neighbors connected
directly to it. he “clustering coeicient” of node
i
is given as
c
i
= 2
n
i
/[
k
i
(
k
i
- 1)],
where
n
i
is the number of edges between the neighbors of
i,
and
k
i
is the degree of
i
. he “diameter” of the network is the maximum, over all pairs of nodes
u
and
v
,
of the shortest-path distance between
u
and
v
. Some observations that follow from
the results are
◾
Social and infrastructure networks are not necessarily scale-free or small-
world networks.
◾
Structural measures for real infrastructure and social networks are often dif-
ferent from similar measures for classic random networks.
◾
Social networks are characterized by high levels of local clustering. In con-
trast, many physical networks, such as power and transport networks, have
very low clustering coefficients.
An informal definition of robustness is whether or not the deletion of a few edges
or nodes breaks the network up into smaller components. he work of Barret
et al. [4] shows that robustness and reliability generally differ for social and
infrastructure networks. hey found the most robust class of networks to be social
networks, followed by mobile ad hoc networks. he least robust are transporta-
tion and electric power networks. A graph showing how different networks shatter
