Information Technology Reference
In-Depth Information
2.2
Small World Theory and Scale-Free Networks
This chapter is devoted to the introduction of small-world theory and scale-free
networks. Introducing these formal notions in a separate section will allow us
to freely build the discussion around the examples studied by members of the
SPANGEO project without having to pause for mathematical digressions. The next
chapter goes into technical details and formally defines and compares the various
network indices that we refer to throughout the topic. Here, we aim to introduce the
main concepts that we transpose from graph theory to geography.
Graph theory, developed especially by Erdös and his school since the 1950s, was
based on the concept of a “random graph”, making the strong assumption that all
relationships are likely to occur with equal probability (
Erdös & Rényi
,
1959
,
1960
).
Put simply, a random graph is one in which edges are drawn at random, playing
heads or tails; that is, there are no regions in the graph where edges have a higher
probability to appear, leading to uniformly distributed connections among nodes.
Since the late 1990s, many researchers have proposed alternatives to this model,
showing the importance of “small worlds” in the organization of societies and their
dynamics, where networks are not seen as homogeneous (
Newman
,
2000
;
Newman,
Watts, & Barabàsi
,
2006
). Small worlds are built from groups of tightly connected
communities, themselves connected through privileged nodes. The small-world
phenomena, experimentally identified by Milgram (
1967
) in social networks, was
observed in many other fields, giving this notion a hint of universality. In biology,
for instance, networks of interacting proteins show a small-world character, where
communities of proteins embody cell functions (
Vespignani
,
2003
). The internet
is another well known and extensively studied example, beginning with Adamic
(
1999
). Two main properties typify these networks:
The average path length from one individual to another is small and compares to
the average path length of random graphs (with the same number of nodes and
edges);
The networks have a strong propensity to create sub-groups (also called commu-
nities or clusters). This propensity is the strongest characteristic of small-world
networks and is the result of several micro processes, like transitivity, homophily,
and the range of ties.
In parallel to Watts and Strogatz's theory of small worlds, some authors observed
and investigated another property of networks, referring to the networks as being
scale-free. These networks organize into an order hierarchy with respect to the
degree of nodes and evolve along a basic process. According to Barabási and Albert
(
1999
) (see also Barabási,
2002
), who popularized these “scale-free networks”,
this order hierarchy is due to the “preferential attachment” that characterizes the
development of networks: new links preferentially link to nodes that already have
a greater number of links, favoring the hierarchy. In reality, we can find early
Search WWH ::
Custom Search