<jupyter_start><jupyter_text>[NTDS'19] tutorial 4: Manipulating graphs with NetworkX[ntds'19]: https://github.com/mdeff/ntds_2019[<NAME>](https://people.epfl.ch/effrosyni.simou), [EPFL LTS4](https://lts4.epfl.ch).Adapted from [NTDS'17 NetworkX demo](https://nbviewer.jupyter.org/github/mdeff/ntds_2017/blob/outputs/demos/04_networkx.ipynb). In this session we will get introduced to NetworkX, explore some of the most common network models, look at their basic properties and compare them.  1 Creating graphs using network modelsThere are many libraries that deal with creation and manipulation of graph data.We will use NetworkX to create basic network models, as they are already implemented in the library.The full documentation of NetworkX 2.3 (installed in your `ntds_2019` environment) can be found [online](https://networkx.github.io/documentation/stable/).<jupyter_code>%matplotlib inline

import collections

import numpy as np
from scipy import spatial
from matplotlib import pyplot as plt
import networkx as nx<jupyter_output><empty_output><jupyter_text>Create an Erdős-Rényi graph with $N=100$ vertices, and a probability of connecting each pair of vertices equal to $p=0.15$.<jupyter_code>N = 100  # number of nodes
p = 0.15  # probability of connection
er = nx.erdos_renyi_graph(N, p)<jupyter_output><empty_output><jupyter_text>You can retrieve the adjacency matrix of the graph, from the `Graph` object `er` as follows:<jupyter_code>er_adj = nx.adjacency_matrix(er, range(N))
er_adj = er_adj.todense()<jupyter_output><empty_output><jupyter_text>You can now visualise the adjacency matrix:<jupyter_code>plt.spy(er_adj);<jupyter_output><empty_output><jupyter_text>2 Plotting graphsWith NetworkX and Matplotlib we can also plot a graph. For example, we can plot the Erdős-Rényi graph that we created before as follows:<jupyter_code>nx.draw(er)<jupyter_output>//anaconda3/envs/ntds_2019/lib/python3.7/site-packages/networkx/drawing/nx_pylab.py:579: MatplotlibDeprecationWarning: 
The iterable function was deprecated in Matplotlib 3.1 and will be removed in 3.3. Use np.iterable instead.
  if not cb.iterable(width):<jupyter_text>2.1 ExerciseCreate a Barabasi-Albert graph and a Watts-Strogatz graph and plot them.<jupyter_code># Create a Barabasi-Albert graph.
ba =  nx.barabasi_albert_graph(100, 1, 87)
nx.draw(ba)
# Create a Watts-Strogartz graph.
ws = nx.watts_strogatz_graph(100, 5, 0.23)
nx.draw(ws)<jupyter_output><empty_output><jupyter_text>3 Modifying graphsIt's easy to add or remove edges, but also nodes. If we add an edge between nodes that don't yet exist, they will be automatically created.<jupyter_code>er.add_node(100)
er.nodes()<jupyter_output><empty_output><jupyter_text>Similarly, you can add and remove a collection of nodes or edges, and add and remove one node or edge:* Adding nodes with:    * `G.add_node`: One node at a time    * `G.add_nodes_from`: A container of nodes* Adding edges with:    * `G.add_edge`: One edge at a time    * `G.add_edges_from`: A container of edges* Removing nodes with:    * `G.remove_node`: One node at a time    * `G.remove_nodes_from`: A container of nodes* Removing edges with:    * `G.remove_edge`: One edge at a time    * `G.remove_edges_from`: A container of edgesYou can get the number of edges with `G.size()`. Add an edge between two non-existant vertices. Remove all nodes up to node 50. Draw the graph after each change.<jupyter_code>er.add_edge(101, 102)
nx.draw(er)
er.remove_nodes_from(range(50))
nx.draw(er)
er.nodes()
er.size()<jupyter_output><empty_output><jupyter_text>4 Degree distribution `G.degree()` returns a ``DegreeView`` object with pairs of nodes and their degree.If we specify a node, `G.degree(node)` will return the degree of that node. Create an Erdős-Rényi network and plot a histogram of node degrees.<jupyter_code>N = 100  # number of nodes
p = 0.15  # probability of connection
er = nx.erdos_renyi_graph(N, p)
d = er.degree()
print(d)
# Erdős-Rényi node degree histogram.
degree_sequence = sorted([d for n, d in er.degree()], reverse=True)  # degree sequence
degreeCount = collections.Counter(degree_sequence)
deg, cnt = zip(*degreeCount.items())

fig, ax = plt.subplots()
ax.bar(deg, cnt)
ax.set_title("Degree Histogram")
ax.set_ylabel("Count")
ax.set_xlabel("Degree");<jupyter_output><empty_output><jupyter_text>4.1 Fitting a distributionTry to fit a Poisson distribution.<jupyter_code># Poisson distribution.
def poisson(mu, k):
    return np.exp(-mu) * mu**k * (np.math.factorial(k)**-1)
# Erdős-Rényi node degree histogram.
degree_sequence = sorted([d for n, d in er.degree()], reverse=True)  # degree sequence
degreeCount = collections.Counter(degree_sequence)
deg, cnt = zip(*degreeCount.items())

fig, ax = plt.subplots()
ax.bar(deg, cnt, label='Histogram')

# Poisson distribution
mu = 2 * er.size() / 100
k = np.linspace(1, 25, 25)
deg = [100 * poisson(mu, i) for i in k]
ax.plot(k, deg, color='r', label='Poisson distribution')

ax.legend()
ax.set_title("Degree Histogram")
ax.set_ylabel("Count")
ax.set_xlabel("Degree");<jupyter_output><empty_output><jupyter_text>4.2 ExerciseDo it for the Barabasi-Albert and Watts-Strogatz networks.<jupyter_code># your code here<jupyter_output><empty_output><jupyter_text>5 Creating a graph that approximates a manifoldWe can represent data laying on a manifold (sampled from a manifold) as a graph of connected samples. Generate 100 two-dimensional data points from a uniform random distribution in $[0, 1]$.These will be the coordinates of your nodes.<jupyter_code>N = 100
nodes_coords = np.random.rand(N, 2)<jupyter_output><empty_output><jupyter_text>Two nodes are connected if the Euclidean distance between them is smaller than a threshold.In that case, the weight of the edge is set to$$w(i,j) = \exp \left( -{\frac{\operatorname{dist}^2(i,j)}{2\sigma^2}} \right),$$for some *kernel width* $\sigma$.<jupyter_code>sigma = 0.9
threshold = 0.2
def gaussian_kernel(dist, sigma):
    return np.exp(-dist**2 / (2*sigma**2))
dist = spatial.distance.pdist(nodes_coords, metric='euclidean')
dist = spatial.distance.squareform(dist)
adj = gaussian_kernel(dist, sigma)
adj -= np.identity(N)
adj[dist > threshold] = 0
plt.spy(adj);<jupyter_output><empty_output><jupyter_text>Plot the graph with NetworkX. Hints: * `nx.from_numpy_array(adj)` creates a graph object from an adjacency matrix (in numpy form)* `nx.draw(G,pos)` will draw vertices at coordinates specified in pos. Variable pos is a dictionary assigning a pair of coordinates to each node.<jupyter_code>g = nx.from_numpy_matrix(adj)
plt.spy(nx.adjacency_matrix(g).todense());
pos = dict(zip(range(N), nodes_coords))
nx.draw(g, pos)<jupyter_output><empty_output><jupyter_text>Plot a degree distribution of this graph. What can you say about the distribution?<jupyter_code># node degree histogram
degree_sequence = sorted([d for n, d in g.degree()], reverse=True)  # degree sequence
degreeCount = collections.Counter(degree_sequence)
deg, cnt = zip(*degreeCount.items())

fig, ax = plt.subplots()
ax.bar(deg, cnt)
ax.set_title("Degree Histogram")
ax.set_ylabel("Count")
ax.set_xlabel("Degree");<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11396491228070176, 'fraction_numerical': 0.01782456140350877, 'mean_word_length': 5.838771593090211, 'pattern_counts': {'":': 0, '<': 61, '<?xml version=': 0, '>': 62, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '176309', 'license': 'MIT', 'n_tokens_mistral': 2524, 'n_tokens_neox': 2392, 'n_words': 725, 'path': 'tutorials/04_networkx.ipynb', 'repo_name': 'yehchunhung/ntds-2019', 'size': '7134'}