Small-world network

0 views

Skip to first unread message

LCFwentao

unread,

May 8, 2006, 2:41:29 AM5/8/06

to myl...@googlegroups.com

Small-world network

From Wikipedia, the free encyclopedia

(Redirected from Small world network
</w/index.php?title=Small_world_network&redirect=no>)
Jump to: navigation <#column-one>, search <#searchInput>

In mathematics </wiki/Mathematics> and physics </wiki/Physics>, a
*small-world network* is a class of random graphs
</wiki/Graph_%28mathematics%29> where most nodes are also neighbors of
one another, but every node can be reached from every other by a small
number of hops or steps. A small world network, where nodes represent
people and edges connect people that know each other, captures the small
world phenomenon </wiki/Small_world_phenomenon> of strangers being
linked by a mutual acquaintance.

Many empirical graphs are well modeled by small world networks. Social
networks </wiki/Social_networks>, the connectivity of the Internet
</wiki/Internet>, and gene networks all exhibit small-world network
characteristics.

Small-world networks were identified as a class of random graphs by
Duncan Watts </wiki/Duncan_J._Watts> and Steven Strogatz
</wiki/Steven_Strogatz> in 1998 </wiki/1998>. They noted that graphs
could be classified according to their clustering coefficient
</wiki/Clustering_coefficient> and their mean-shortest path length
</wiki/Distance_%28graph_theory%29>. Small-world networks, as compared
to other random graphs with the same number of nodes and edges, are
characterized by clustering coefficients significantly higher than
expected and mean shortest-path length lower than expected.

Contents

[hide <javascript:toggleToc()>]

* 1 Properties of small-world networks
<#Properties_of_small-world_networks>
* 2 Examples of small-world networks
<#Examples_of_small-world_networks>
* 3 Network robustness <#Network_robustness>
* 4 Construction of small-world networks
<#Construction_of_small-world_networks>
* 5 Footnotes <#Footnotes>
* 6 See also <#See_also>
* 7 References <#References>
o 7.1 Books <#Books>
o 7.2 Journal Articles <#Journal_Articles>
* 8 External links <#External_links>

[edit </w/index.php?title=Small-world_network&action=edit&section=1>]

Properties of small-world networks

By virtue of the above definition, small-world networks will inevitably
have high representation of cliques </wiki/Clique_%28graph_theory%29>,
and subgraphs </wiki/Subgraph> that are a few edges shy of being
cliques, i.e. small-world networks will have sub-networks that are
characterized by the presence of connections between almost any two
nodes within them. This follows from the requirement of a high cluster
coefficient. Secondly, most pairs of nodes will be connected by at least
one short path. This follows from the requirement that the mean-shortest
path length be small.

Additionally, there are several properties that are commonly associated
with small-world networks even though they are not required for that
classification. Typically there is an over-abundance of /hubs/ - nodes
in the network with a high number of connections (known as high degree
</wiki/Degree_%28graph_theory%29>). These hubs serve as the common
connections mediating the short path lengths between other edges. By
analogy, the small-world network of airline flights has a small
mean-path length (i.e. between any two cities you are likely to have to
take three or fewer flights) because many flights are routed through hub
</wiki/Airline_hub> cities.

This property is often analyzed by considering the fraction of nodes in
the network that have a particular number of connections going into them
(the degree distribution of the network). Networks with a greater than
expected number of hubs will have a greater fraction of nodes with high
degree, and consequently the degree distribution will be enriched at
high degree values. This is known colloquially as a fat-tailed
</wiki/Skewness> distribution. Specifically, if a small-world network
has a degree-distribution which can be fit </wiki/Goodness_of_fit> with
a power law </wiki/Power_law> distribution, it is taken as a sign that
the network is small-world. Power law distributions have fat tails when
compared to exponential distributions </wiki/Exponential_distribution>
characteristic of random networks. These networks are known as
scale-free networks </wiki/Scale-free_network>.

This type of network is by no means the only kind of small-world
network. Graphs of very different topology can still qualify as
small-world networks as long as they satisfy the two definitional
requirements above.

[edit </w/index.php?title=Small-world_network&action=edit&section=2>]

Examples of small-world networks

Small-world networks have been discovered in a surprising number of
natural phenomena. For example, networks [1]
<http://polaris.icmb.utexas.edu/paper-pdfs/cosb-review.pdf> composed of
proteins with connections indicating that the proteins physically
interact </wiki/Protein-protein_interaction> have power-law obeying
degree distributions and are small-world. Similarly transcriptional
networks </w/index.php?title=Transcriptional_network&action=edit> in
which genes </wiki/Gene> correspond to nodes, and up or down-regulatory
genetic influence correspond to connections are small world networks
obeying power-laws [2] <http://www.jsbi.org/journal/GIW05/GIW05F030.html>.

There are also many other graphs which have been found to exhibit
small-world properties. Examples include road maps, food chains,
electric power grids, metabolite processing networks, neural networks,
telephone call graphs and social influence networks.

In 2004, Sara Solla et al. developed a computer model of short-term
memory </wiki/Short-term_memory> constructed around a small-world
network [3] <http://www.newscientist.com/article.ns?id=dn5012>. This
model successfully demonstrated bistability </wiki/Bistable>, a property
thought to be important in memory </wiki/Memory> storage. The
bistability appears to be the result of recurrent self-sustaining loops
of activity after an activating pulse is given. A second pulse would
turn off the system. Hence, the pulses switch the system between its
bistable states.

[edit </w/index.php?title=Small-world_network&action=edit&section=3>]

Network robustness

It is hypothesized by some researchers such as Barabasi
</wiki/Albert-Laszlo_Barabasi> that the prevalence of small world
networks in biological systems may reflect an evolutionary advantage of
such an architecture. One possibility is that small-world networks are
more robust to perturbations than other network architectures. If this
were the case, it would provide an advantage to biological systems that
are subject to damage by mutation </wiki/Mutation> or viral infection
</wiki/Virus>.

In a power law </wiki/Power_law> distributed small world network,
deletion of a random node rarely causes a dramatic increase in
mean-shortest path length (or a dramatic decrease in the clustering
coefficient). This follows from the fact that most shortest paths
between nodes flow through hubs, and if a peripheral node is deleted it
is unlikely to interfere with passage between other peripheral nodes.
For example, if the small airport in Sun Valley, Idaho
</wiki/Sun_Valley%2C_Idaho> was shut down, it would not increase the
average number of flights that other passengers traveling in the United
states would have to take to arrive at their respective destinations.
That said, if random deletion of a node hits a hub by chance, the
average path length can increase dramatically. This can be observed
annually when northern hub airports are shut down because of snow. If
Chicago's O'Hare </wiki/O%27Hare_International_Airport> airport shut
down, many people would have to take additional flights.

By contrast, in a random network, in which all nodes have roughly the
same number of connections, deleting a random node is likely to increase
the mean-shortest path length slightly but significantly for almost any
node deleted. In this sense, random networks are vulnerable to random
perturbations, whereas small-world networks are robust. However,
small-world networks are vulnerable to targeted attack of hubs, whereas
random networks cannot be targeted for catastrophic failure.

Appropriately, viruses have evolved to interfere with the activity of
hub proteins such as p53 </wiki/P53>, thereby bringing about the massive
changes in cellular behavior which are conducive to viral replication.

[edit </w/index.php?title=Small-world_network&action=edit&section=4>]

Construction of small-world networks

Several procedures are known to generate small-world networks from
scratch. One of these methods is known as /preferential attachment/ [4]
<http://arxiv.org/abs/cond-mat/9910332>. In this model, new nodes are
added to a pre-existing network, and connected to each of the original
nodes with a probability proportional to the number of connections each
of the original nodes already had. I.e., new nodes are more likely to
attach to hubs than peripheral nodes. Statistically, this method will
generate a power-law distributed small-world network.

Elements of this mechanism can be seen to contribute to the
small-worldness of the World Wide Web </wiki/World_Wide_Web>. A new site
is more likely to have links to major pre-existing sites, such as Google
</wiki/Google> or Wikipedia </wiki/Wikipedia> than arbitrary small
obscure sites. This observation is known colloquially as a /rich get
richer/ model.

/See also:/ Diffusion-limited aggregation
</wiki/Diffusion-limited_aggregation>, pattern formation
</wiki/Pattern_formation>

[edit </w/index.php?title=Small-world_network&action=edit&section=5>]

Footnotes

1. Review article on protein interaction networks
<http://polaris.icmb.utexas.edu/paper-pdfs/cosb-review.pdf>
2. Article on topology of mammalian transcription networks
<http://www.jsbi.org/journal/GIW05/GIW05F030.html>
3. Barabasi preferential attachment article
<http://arxiv.org/abs/cond-mat/9910332>

[edit </w/index.php?title=Small-world_network&action=edit&section=6>]