CS4423 - Networks

Prof. Götz Pfeiffer
School of Mathematics, Statistics and Applied Mathematics
NUI Galway

Assignment 1

Provide answers to the problems in the boxes provided. Marks will be awarded for participation and engagement.

When finished, print this notebook into a pdf file and submit this to blackboard.

Deadline is next Monday at 5pm.

Setup

This is a jupyter notebook. Find an environment that allows you to work with it. You can either install jupyter as a python packag on your own laptop or PC. Or you can use a suitable website on the internet, such as nbviewer and binder.

The following packages need to be loaded. In order to execute the code in a box, use the mouse or arrow keys to highlight the box and then press SHIFT-RETURN.

Should it ever happen that the notebook becomes unusable, start again with a fresh copy.

In [ ]:
import networkx as nx
import matplotlib.pyplot as plt

1. Warmup.

The purpose of this task is to get you used to working with the networkx package in the jupyter notebook environment.

  1. Define a new (simple) graph G on the vertex set $X = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ with edges $0-1$, $1-2$, $2-3$, $3-4$, $4-5$, $5-6$, $6-7$, $7-8$, $8-9$, and $9-0$. Draw the graph. Hence or otherwise determine its order (the number of nodes) and its size (the number of links).
In [ ]:
 
  1. Find the adjacency matrix A of the graph G. Then compute its square, $A^2$, and draw the graph G2 that has $A^2$ as its adjacency matrix. What are the connected components of G2?
In [ ]:
 

2. Projections

For the affilliation network below, with six people labelled $A$ to $F$, and three foci labelled $X$, $Y$ and $Z$, draw the projection on (just) the people, in which two people are joined by an edge if they have a common focus.

(Of course, one can do this easily by hand. It would be nice to get networkx to do it for you.)

In [ ]:
 

3. A Collaborations Network

The social graph of a node $x$ in a (social) network is the induced subgraph on the set of friends of $x$ (that is the graph which has (only) the friends of $x$ as its vertices, and between them all the edges from the original network). The clustering coefficient of $x$ is the density $m / \binom{n}{2}$ of the social graph of $x$, the proportion its number of edges, $m$, and its potential number of edges, $\binom{n}{2} = \frac12 n(n-1)$, where $n$ is its number of vertices.

MathSciNet describes the social network of mathematical researchers defined by collaboration.

Pick a (local) mathematician with at least $10$ friends (i.e., co-authors), determine their social graph and hence compute their clustering coefficient.

In [ ]:
 

4. The Counties of Ireland.

Define a graph I on the $32$ counties of Ireland by joining two counties whenever they have a common border. (A list of county names, suitable for cut-and-paste, can be found on the internet)

What is the order and the size of the resulting graph?

In terms of centrality measures, what are the $3$ most central counties, for

  1. degree centrality?
  2. eigenvector centrality?
  3. closeness centrality?
  4. betweenness centrality?
In [ ]: