NetLogo Workshop Series� ��Model 11. Small Worlds

1

Small World Networks

• A small-world network refers to a family of networks in which the mean geodesic (i.e., shortest-path) distance between nodes increases sufficiently slowly as a function of the number of nodes in the network.
• It has been used frequently to refer specifically to a Watts–Strogatz toy network.

“Small Worlds” Network

Model Library > Network > Small Worlds

It looks like each node is linked only

with its two immediate neighbors.

​

Let’s inspect turtle 0

How many links does each node has?

1. Use your eyes
2. Or use “distance-from-other turtles”

Distance-from-other turtles

[0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1]

Distance in network?

An orange node is 2 degrees

apart from a blue node.

A purple node is 1 degree

apart from a blue node.

A blue node is 0 degrees

apart from a blue node (self).

Distance-from-other nodes =

Blue Purple Orange

Blue 0 1 2

Purple 1 0 1

Orange 2 1 0

Note: Distance is also called “Path Length”

What is the average path length for the blue node? 1.5

What is the average path length for the purple node? 1

A node with a short average path length = a well connected node

Degree distance between nodes

Degree distance

Between node i & j

1 2 3 … j

1 a11 a12 a13 … a1j

2 a21 a22 a23 … a2j

3 a31 a32 a33 … a3j

​

… … … … … …

​

i ai1 ai2 ai3 … aij

Turtle 0’s distance-from-other turtles =

[0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 10 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1]

t0

t1

t2

t39

t38

1. Click the highlight button.

​

2. Place your mouse cursor on a node.

(1) The node is now highlighted in pink color.

(2) The four neighboring nodes connected with

the white node are highlighted in red color.

​

3. Notice all nodes have 4 neighboring red nodes.

​

“node degree”

def. The degree of a node is the number of links connected to the node.

The node degree of all nodes = 4

​

Regular Network

“Regular networks”

def. Networks in which each node has exactly the same number of links. 

Ring lattice

(k = 4)

Square lattice

(k = 4)

Triangular grid

(k = 6)

Degree distribution of regular network

0 1 2 3 4 5 ... 40

Frequency

The number of nodes with node degree x

node degree (x)

40

39

​

​

​

…

​

​

​

​

4

3

2

1

0

All nodes have the same number of links

Ring lattice

(k = 4)

Let the network rewire

1. Set rewiring-probability = 1
• Each link randomly rewires with a probability.
• p = 1 means all links rewire
• p = .5 means each link rewires with a probability .5

​

1. Click rewire-all

​

1. Notice turtle 0 now has 5 new neighbors and two of them are also connected.

Random Network

def. A random network consists of nodes where each node pair is connected with probability p. 

Degree distribution of random network

0 … 18 19 20 21 22 23 … 40

The number of nodes with node degree x

node degree (x)

40

39

​

​

​

…

​

​

​

​

4

3

2

1

0

Most nodes are average-linked

Geodesic Distance

• Among several paths may exist between two nodes, the shortest path length between them is the geodesic distance.

What is the geodesic distance

between 4 and 8?

​

Average Geodesic Distance

• Average geodesic distance between all pairs of nodes.

Blue’s average Geodesic Distance = (1 + 2) /2 =1.5

Purple’s average Geodesic Distance = (1 + 1) /2 =1

Orange’s average Geodesic Distance = (1 + 2) /2 =1.5

​

Average Geodesic Distance = (1.5 + 1 + 1.5)/3 = 1.33

Average Geodesic Distance

• Average geodesic distance between all pairs of nodes.

Blue’s average Geodesic Distance = (1 + 1) /2 =1

Purple’s average Geodesic Distance = (1 + 1) /2 =1

Orange’s average Geodesic Distance = (1 + 1) /2 =1

​

Average geodesic Distance = (1 + 1 + 1)/3 = 1

Diameter

• The longest shortest path in a network.

(max. geodasic)

Diameter = 1

Diameter = 2

Bridges

• A node that ties together otherwise disconnected people.
• They are also called brokers, boundary spanners, etc.

Node 0, 1 are bridges.

A purple node is a bridge.

Average Geodesic Distance ( ℓ)

 ℓ= 5.4

 ℓ = 2.8

Node i ’s Clustering Coefficient (Cli)

# triangles connected to node i

# triples centered at node i

Cli =

(Watts & Strogatz, 1998)

i

i

Cli = 1

Cli = 0

2

1

3

4

5

# triangles connected to node i

# triples centered at node i

Cl3 =

1

6

=

(1,3,2)

(1,3,2)

(1,3,4)

(1,3,5)

(2,3,4)

(2,3,5)

(4,3,5)

1

6

5

1

2

1

3

4

1

n

Cl avg =

∑ Cli

= (1 + 1 + + 0 + 0) = ∙ =

5

5

1

6

13

30

13

A Global Clustering Coefficient (C)

# connected triples of nodes

C =

3 x # triangles

(Newman, 2003)

# all triples (open or closed)

C =

# closed triples

# closed triples = 3 x # triangles

Def. the fraction of triples that have their third edge filled in to complete the triangle.

It is a measure of the degree to which nodes in a graph tend to cluster together.

# connected triples of nodes

C =

3 x # triangles

C = 1

C = 0

“all my friends know each other”

or

“the friends of my friends are my friends”

​

Lots of subgroups

“my friends don’t know each other”

# connected triples of nodes

C =

3 x # triangles

(2,1,3)

(1,2,3)

(1,3,2)

(1,3,4)

(1,3,5)

(2,3,4)

(2,3,5)

(4,3,5)

2

1

3

4

5

=

3

8

A Global Clustering Coefficient (C)

 C = 0.5

 C = 0.1

Clustering coefficient C and mean geodesic distance ℓ between nodes in the Newman–Watts variant of the Watts–Strogatz small-world model as a function of rewiring probability p. Observe that there is a regime with high clustering but low mean geodesic distance. (For each value of p in this plot, one computes the values of C and ℓ as means over an ensemble of NW networks.)

Copyright © 2003 Society for Industrial and Applied Mathematics.

(Newman, 2003)

More clusters

Long distance

Less clusters

Short distance

More clusters

Short distance

Small-World Networks

• More clusters (large C): My friends know each other. There are lots of subgroups

​

• Short distance (small ℓ): They are only a few steps away from anybody in the world.

​

• “Wisdom”: It doesn’t take many rewiring. Just a few random rewiring make small worlds.