We will continue the netsci data exploration from the warm-up excercise.
Just to recap, we first load the network science data subset:
Start Python in the same directory by typing “python” or “ipython –pylab”, and then load the data and checked that it has been loaded correctly:
import networkx as nx
gs = nx.read_gml('./netsci_subgraph.gml', relabel = True)
nx.draw_spring(gs)If you are not in an ipython shell, also type:
import matplotlib.pyplot as plt
plt.show()The key concepts we will go through in this excercise are Eccentricity, Diameter and Radius.
Let \(d(u,v)\) be the shortest distance, or graph geodesic, between two nodes u and v.
The eccentricity \(\epsilon(v)\) of a node \(v\) is the greatest deodesic distance between \(v\) and any other node. i.e., \(\max_{u \neq v} d(u,v)\). It can be thought of as how far a node is from the node most distant from it in the graph 1.
ec1 = {}
# compute all shortest path from Watts
spath = nx.shortest_path(gs, source='WATTS, D')
# display it
spath
# compute the eccentricity of Watts
ec1['WATTS, D'] = max(map(len, spath.values())) - 1
Now compute all eccentricity in one line.
ec2 = dict (map(lambda v: (v, max(map(len, nx.shortest_path(gs, source=v).values())) - 1), gs.nodes() ))
# display it
ec2Note that this is compact for tutorial purposes, but poor in programming style and readability. One python excercise is for you to re-write the line above as short loop.
Compare your results with those obtained by NetworkX:
ec = nx.eccentricity(gs)The radius \(r\) of a graph is the minimum eccentricity of any node, \(r = \min_{v} \epsilon(v)\). It can be computed as:
min(ec2.values())
## OR
nx.radius(gs)The diameter \(d\) of a graph is the maximum eccentricity of any node, \(d = \max_{v} \epsilon(v)\).
Question 1: What is the diameter of this graph?
A. 2
B. 3
C. 4
D. 5Question 2: Is radius or diameter always defined? why, or why not?
http://en.wikipedia.org/wiki/Distance_(graph_theory)↩