Editing Small World Networks 2008 (section)

== Worked examples ==
=== Directed graph ===
http://www.berrymanconsulting.com/images/SimpleDirectedGraph.jpg

Pajek .net file
 *vertices 4
 1 "1"
 2 "2"
 3 "3"
 4 "4"
 *arcslist
 1 2 4
 2 3 4
 3 1
 4 1 2
Note that in my drawing done with different software I have drawn the bidirectional edges as two separate edges, whereas Pajek draws them as a single edge with arrows on both ends.

In-degree of nodes:
# Node 1 has 2 incoming edges
# 2
# 1
# 2

So the in-degree distribution is:
# 1
# 3
(i.e. the number of edges with 1 incoming edge is 1, and the number of edges with 2 incoming edges is 3)
Average in-degree is (1*1+3*2)/4=1.75

Out-degree of nodes:
# 2
# 2
# 1
# 2

So the out-degree distribution is:
# 1
# 3
Average out-degree is (1*1+3*2)/4=1.75
Note in general that for a directed graph, the out-degree distribution is not the same as the in-degree. 


To calculate the clustering coefficients we first need to find the neighbourhoods of each node. The neighbourhood of node i, is all the other nodes that either have an edge from node i or to node i.
The neighbourhood of node 1 is {2,3,4}, the neighbourhood of node 2 is {1,3,4}, the neighbourhood of node 3 is {1,2} and the neighbourhood of node 4 is {1,2}.

We also need the total degree of each node = in-degree + out-degree, thus
# 4
# 4
# 2
# 4
Using the notation from [http://en.wikipedia.org/wiki/Clustering_coefficient here], these are the k_i (k underscore i). 

We also need the number of edges between nodes j and k in the neighbourhood of i, i.e. for node 1, we count all the edges between nodes 2, 3, and 4 (the neighbourhood of 1).
The counts are:
# 3
# 3
# 1
# 1

So the clustering coefficient for each node is the count divided by k_i(k_i - 1), i.e.
# 3/(4*3) = 1/4
# 3/(4*3) = 1/4
# 1/(2*1) = 1/2
# 1/(4*3) = 1/12

The clustering coefficient for the graph as a whole is just the average of the clustering coefficients of the nodes, i.e. (1/4 + 1/4 + 1/2 + 1/12) / 4 = 13/48 approx. 0.271
=== Undirected Graph ===
http://www.berrymanconsulting.com/images/SimpleUndirectedGraph.jpg

Pajek .net file:
 *vertices = 5
 1 "1"
 2 "2"
 3 "3"
 4 "4"
 5 "5"
 *edges
 1 2
 1 3
 2 3
 2 4
 2 5
 3 5
 4 5

Degree:
# 2
# 4
# 3
# 2
# 3

Degree distribution:
# 0
# 2
# 2
# 1

Average degree = (2*2 + 2*3 + 4)/5 = 14/5 = 2.8

Neighbourhoods:
# {2,3}
# {1,3,4,5}
# {1,2,5}
# {2,5}
# {2,3,4}

Number of edges within neighbourhoods:
# 1
# 3
# 2
# 1
# 2

Clustering coefficients
# 2*1/(2*1) = 1
# 2*3/(4*3) = 1/2
# 2*2/(3*2) = 2/3
# 2*1/(2*1) = 1
# 2*2/(3*2) = 2/3

Average clustering coefficient = (1 + 1/2 + 2/3 + 1 + 2/3) / 5 approx. 0.767