### 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 [ ]: