<jupyter_start><jupyter_text>1 Graphs<jupyter_code>import numpy as np
import scipy as sp
import matplotlib.pyplot as plt
from pygsp import graphs<jupyter_output><empty_output><jupyter_text>1.1 CreationMost likely, the first thing you would like to do is to create a graph. In this toolbox, a graph is encoded as a weighted adjacency matrix. That is because it’s the most efficient representation to deal with when using spectral methods. As such, you can construct a graph from any adjacency matrix as follows.<jupyter_code>W = np.random.uniform(size=(30, 30))  # Full graph.
W[W < 0.93] = 0  # Sparse graph.
W = W + W.T  # Symmetric graph.
np.fill_diagonal(W, 0)  # No self-loops.

G = graphs.Graph(W)

print(f'{G.N} nodes, {G.Ne} edges')<jupyter_output><empty_output><jupyter_text>Graphs can also be created from network models, such as the well-known [Erdős–Rényi](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).<jupyter_code>G = graphs.ErdosRenyi(50, p=0.2)
print(f'{G.N} nodes, {G.Ne} edges')
G = graphs.Community(N=100, Nc=5)
print(f'{G.N} nodes, {G.Ne} edges')<jupyter_output><empty_output><jupyter_text>Finally, graphs can also be constructed from a set of points in $\mathbb{R}^d$.Let $\mathbf{X}$ be a data matrix $\mathbf{X} = [\mathbf{x}_1, \ldots, \mathbf{x}_N]^\intercal \in \mathbb{R}^{N \times d}$, where each $\mathbf{x} \in \mathbb{R}^d$ is a sample for which we have $d$ features.<jupyter_code>n_points = 100
dimensionality = 2
points = np.random.uniform(size=(n_points, dimensionality))
plt.scatter(points[:, 0], points[:, 1]);<jupyter_output><empty_output><jupyter_text>We may separate the task of building a graph from a set of points in two sub-tasks:* **Finding the structure (the existing edges)**. Two classical approaches are:    * connecting a point to its $k$-nearest neighbors (kNN graph),    * connecting a point to all points closer than $\epsilon$ (in some measure); * **Associate a weight to each existing edge** (optional). In general, we want that the closer a pair of points, the larger the weight on the associated edge. A classical option is the Gaussian kernel:$$\mathbf{W}[i,j] = \exp(-\frac{||\mathbf{x}_i - \mathbf{x}_j||^2_2 }{ \sigma^2})$$<jupyter_code>sigma=0.1
G = graphs.NNGraph(points, NNtype='knn', k=2, sigma = sigma**2, rescale=False, symmetrize_type='maximum')
print(f'{G.N} nodes, {G.Ne} edges')
G = graphs.NNGraph(points, NNtype='radius', epsilon=0.1, sigma = sigma**2, rescale=False, symmetrize_type='maximum')
print(f'{G.N} nodes, {G.Ne} edges')<jupyter_output><empty_output><jupyter_text>1.2 Properties The [pygsp.graphs.Graph](https://pygsp.readthedocs.io/en/stable/reference/graphs.html) class we just instantiated is the base classfor all graph objects, which offers many methods and attributes.Given, a graph object, we can access and test some properties. As we've used before, there is the number of nodes and edges.<jupyter_code>print(G.N)
print(G.Ne)<jupyter_output><empty_output><jupyter_text>We can also test if the graph is connected or directed.<jupyter_code>print(G.is_connected())
print(G.is_directed())<jupyter_output><empty_output><jupyter_text>We can retrieve the weighted adjacency matrix, which is stored in a sparse format.<jupyter_code>G.W<jupyter_output><empty_output><jupyter_text>And visualize its sparsity pattern:<jupyter_code>plt.spy(G.W, markersize=5);
#plt.imshow(G.W.toarray());<jupyter_output><empty_output><jupyter_text>We can access the [graph Laplacian](https://en.wikipedia.org/wiki/Laplacian_matrix), defined as$$ L = D - W $$for the combinatorial Laplacian, and$$ L = I - D^{-1/2} W  D^{-1/2} $$for the normalized Laplacian, where $D$ is the diagonal degree matrix.<jupyter_code>G.compute_laplacian('combinatorial') 
#or G.compute_laplacian('normalized') ##the normalized Lap may yield an error if there exist a node with degree 0!
G.L<jupyter_output><empty_output><jupyter_text>We can also get another representation of a graph: the edge list.Note that if the graph is not directed the number of edges is half the number of non-zeros in the adjacency matrix.<jupyter_code>v_in, v_out, weights = G.get_edge_list()
print(v_in.shape, v_out.shape, weights.shape)<jupyter_output><empty_output><jupyter_text>1.3 Visualization To be able to plot a graph, we need to embed its nodes in a 2D or 3D space. The process to find coordinates for each nodes is called [layout](https://en.wikipedia.org/wiki/Graph_drawing). Most included graph models define these. If that's not the case, or if you create the graph from an adjacency matrix, [`pygsp.graphs.Graph.set_coordinates()`](https://pygsp.readthedocs.io/en/stable/reference/graphs.htmlpygsp.graphs.Graph.set_coordinates) can be used to set it. In our previous example, the nodes had a natural 2D embedding. It is thus logical to plot it using the 2D coordinates of each point in the point cloud:<jupyter_code>G.plot()<jupyter_output><empty_output><jupyter_text>Nevertheless, the **same** graph could be drawn in many different ways. Below are two different options:<jupyter_code>G2 = graphs.Graph(G.W)
G2.set_coordinates(kind='ring2D') #here with a spring based algorithm
G2.plot()
G2 = graphs.Graph(G.W)
G2.set_coordinates(kind='spring') #here with a spring based algorithm
G2.plot()<jupyter_output><empty_output><jupyter_text>For a more interactive visualization, you can use [Gephi](https://gephi.org/) or [Cytoscape](http://www.cytoscape.org/).  1.4 Exercise: The Barabasi-Albert model1. Create a graph from the [Barabási–Albert](https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model) model.2. Compute and plot its degree distributions.3. Plot the graph in 2D with a force-directed layout.<jupyter_code># Your code here.<jupyter_output><empty_output><jupyter_text>1.5 Exercise: connectedness phase transition in Erdös-Rényi graphs Erdös Rényi graphs have a "connectedness phase transition" at $p=\frac{\log{N}}{N}$. That is, as $N\rightarrow\infty$:* if $p<\frac{\log{N}}{N}$ the graph is a.s. disconnected* if $p>\frac{\log{N}}{N}$ the graph is a.s. connectedIllustrate this phase transition computationally<jupyter_code># Your code here.<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12569195701725822, 'fraction_numerical': 0.013513513513513514, 'mean_word_length': 5.879059350503919, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 62, 'https://': 7, 'lorem ipsum': 0, 'www.': 1, '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': '270993', 'license': 'MIT', 'n_tokens_mistral': 2151, 'n_tokens_neox': 2052, 'n_words': 642, 'path': 'notebooks/01_graphs.ipynb', 'repo_name': 'mdeff/pygsp_tutorial_graphsip', 'size': '6142'}