This continues from last week. The NetworkX modules need to be imported:
from networkx import *
from operator import *
1 Analysing relations
Download the file friends.csv and save it on
your I:-drive. This is a comma-separated variable (csv) file.
You can look at the file if you open it
in Wordpad. If you double click a csv-file, it will open in Excel.
The file contains a binary relation which can be
represented as a graph using:
F = read_edgelist("friends.csv",delimiter=",",create_using=DiGraph())
(Notes: F is specified as a directed graph because whether someone calls
someone else a "friend" may not be symmetric.
If you create a csv file yourself, make sure that it does not contain any
blank lines at the end of the file.)
1) Something to think about: What is the domain/co-domain for
the friends relation?
2) Create a gif file for F. Try different layouts.
Which layout seems most suitable? Is it easy to see
who is considered "friend" by most people and who has the most friends?
1.2 Calculating Google's PageRank
PageRank is an algorithm that calculates the "relative importance" of
nodes in a directed graph. Basically, nodes that have more incoming edges are
more important. Edges coming from more important nodes count more
than edges coming from less important nodes.
The code below calculates the PageRank for each node in F and then
prints a list of nodes in decreasing order of importance.
pg = pagerank(F)
for item in sorted(pg.iteritems(), key=itemgetter(1), reverse=True):
Who is considered "friend" by most people according to PageRank?
Who has the least friends?
3) Calculate the reverse graph using F.reverse(),
i.e., if (John,Paul) is in the original, then (Paul,John) is in the
4) Calculate the PageRank of the reverse graph. Create gif files for
both F and the reverse graph. Answer the following questions based
on what you observe in the pictures and the PageRank data:Why is Claire high in F and low in the reverse graph?
Why are Helen and Sue highly ranked in F and in the reverse graph?
What does this mean for websites: how can a website achieve a high
PageRank in Google?
2 Small-world networks
A small-world network has a small average shortest path
lenght (eg below 6) and an average clustering coefficient that is
larger than the clustering coefficient of a random graph
with the same number of nodes and edges.
The average clustering coefficient determines whether the neighbours
of nodes are also connected and thus the graph forms clusters.
average_clustering(G) ### for the clustering coefficient
gnm_random_graph(n, m) ### for a random graph with n nodes, m edges
G.to_undirected() ### returns an undirected graph from DiGraph
5) Determine whether the friends graph is a small-world network.
3 Exercise with pen and paper
Suppose you are going to a party with your girlfriend/boyfriend.
There are three other couples at the party. Several people shake
hands. Obviously nobody shakes hands with themselves or their
girlfriend/boyfriend. Nobody shakes hands with the same person
more than once. At the end of the party, you ask everybody
including your girlfriend/boyfriend
how many hands they have shaken. Each person gives a different
Can you figure out how many hands you shook and how many hands your
Consider this a graph problem where the nodes are people
and the edges are handshakes.
What is the maximum number of handshakes possible for a single
person in this graph? What is the minimum number?
Because each person gives a different answer, you can figure out
what the answers must have been.
Insert edges into the graph, starting with the person with the
most handshakes and then the one with the second most handshakes.