Group Assignment 1

Objective

To practice computing, manipulating and visualizing degree distribution information.

Data

In this lab, we will be working with two networks. The first is an undirected social network of frequent associations between 62 dolphins in a community living off Doubtful Sound, New Zealand, as compiled by Lusseau et al. (2003). See D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology 54, 396-405 (2003) for additional details.

The second network is an Erdos-Renyi random graph containing 62 nodes and generated to approximate the density of the dolphin network. It was generated using the erdos_renyi_graph() function in NetworkX with edge probability 0.084.

Analysis

Your task in this lab is to compare the two networks based on degree distribution, visualized several different ways, and on robustness to node removal. We will evaluate robustness based on experiments in which we remove nodes from the networks until the giant component (largest component) falls below 66% of its original size. (The networks are all fully connected at the start.)

You should treat this notebook like a worksheet with various questions to answer along the way. At the end, there is a place for a summary paragraph.

Imports

In [ ]:

import networkx as nx 

import scipy as sp 

import random 

import matplotlib.pyplot as plt 

%matplotlib inline 

import urllib 

Loading the networks

In [ ]:

url = "http://josquin.cti.depaul.edu/~rburke/courses/s14/dolphins.net" 

sock = urllib.urlopen(url) # open URL 

dolphin_multi = nx.read_pajek(sock) # Pajek graphs are multigraphs by default 

dolphin = nx.Graph(dolphin_multi) 

In [ ]:

url = url = "http://josquin.cti.depaul.edu/~rburke/courses/s14/er_graph2.net" 

sock = urllib.urlopen(url) # open URL 

er_multi = nx.read_pajek(sock) # Pajek graphs are multigraphs by default 

er_graph = nx.Graph(er_multi) 

Question 1

Draw the networks (include the names for the dolpins) 1 point

In [ ]:

In [ ]:

Question 2

Compute and print the density of the two networks. 1 point

In [ ]:

Question 3

How do the networks compare in terms of visual organization? 1 point

Type Markdown and LaTeX: 22

Question 4

Calculate and plot the degree distributions. The plots should have the same x and y axes (0-12 x 0-17) so that they can be more readily compared. Hints: Use the bins parameter to control the bins used in the histogram, and use the ylim function to control the y axis scale. 1 point

In [ ]:

In [ ]:

Question 5

What differences are apparent in the distributions? 1 point

Type Markdown and LaTeX: 22

Question 6

Networks with nodes sized as a function of degree 1 point

In [ ]:

In [ ]:

Question 7

How do the degree distribution differences show up in the network visualizations with degree mapped to node size? 1 point

Type Markdown and LaTeX: 22

Question 8

Random node removal

Write code to remove nodes randomly from each network, stopping when the largest component is 0.66 times the original network. (Don't forget to make a copy of the network before you start removing nodes.) Return the number of removals required. 2 points

In [ ]:

Question 9

Run the removal experiment 100 times on each of the dolphin network and the random network. Compute the average number of removals required in each network to shrink the largest component to 2/3 size. 1 point

In [ ]:

Question 10

How do these values compare? 1 point

Type Markdown and LaTeX: 22

Question 11

Compare reduced networks

Compute examples of the networks reduced by random removal and draw them. 1 point

In [ ]:

In [ ]:

Question 12

Display degree distributions for these two networks. As above, control the dimensions to be the same in both plots so they can be compared. Be careul not to lose any data! Plot first without setting the dimensions so you can see how they should be scaled. The y axis should be one unit larger than the maximum value so that the top of the bar does not overlap with the plot perimeter. 1 point

In [ ]:

In [ ]:

Question 13

How do the reduced networks compare with each other and with their original form? 1 point

Type Markdown and LaTeX: 22

Question 14

Targeted node removal

Write code to remove the largest degree nodes from each network, stopping when the largest component is 0.66 times the original network. As before, return the number of removals required. 2 point

In [ ]:

Question 15

Apply the targeted removal process to both networks. 1 point

In [ ]:

Question 16

How do these values compare? How do they compare with the values from random deletion? 1 point

Type Markdown and LaTeX: 22

Question 17

Draw the reduced networks 1 point

In [ ]:

In [ ]:

Question 18

Plot the degree distributions of the reduced networks. As before, control the dimensions to be the same in both plots so they can be compared. 1 point

In [ ]:

In [ ]:

Question 19

How do the networks compare to each other and to the original networks? 1 point

Type Markdown and LaTeX: 22

Question 20

Comparing the two conditions: Create a bar plot comparing the values for the random and target removal conditions for the two networks. Use different colors for the two networks -- this requires two calls to the bar() function. 1 point

Extra credit: Add legend, xticks, ylabel, and title as in the figure below: 2 points possible

In [ ]:

Question 21

Write a paragraph summarizing your comparison of the two networks on the basis of the analysis above. 2 points

Type Markdown and LaTeX: 22

Hints and notes

Make sure that you make a copy of the network and delete nodes from the copy.

To compute mean, you can use sp.mean, a function imported from the scipy package for scientific computing.

Note that the degrees of many nodes could potentially change when one node is removed. You have to recompute all the degree values when a node is removed.

For Question 19, you will need to make use of the following matplotlib.pylot functions

bar (color and label arguments)

legend (loc=2)

xticks

ylabel

title

Each group has a locker on D2L that you can use to share documents like this workbook. You may prefer to use Dropbox or Google Docs to achieve a similar effect. Don't share assignment work on Slack except in your group channel as the other channels are available to the entire class.

Suggested division of labor:

There is a lot to do in this assignment. A suggested division of labor would be as follows:

Data gathering specialists: Work in the programming-intensive parts Questions 8, 9, 14, and 15.

Data analysis specialists: Develop visualizations. Study the matplotlib documentation to determine how to create the plot for Question 20.

Project coordinator: Coordinate the project work. With the help of the data analyst, write the text answers to Questions 3, 5, 7, 13, 16, 19, 21.

Reducing giant component by 1/3 25 Dolphin ER graph 9 20 E 15 e 10 Max. degree Random Reducing giant component by 1/3 25 Dolphin ER graph 9 20 E 15 e 10 Max. degree Random