Forming a graph using two dimensional data points in scikit learn using networkX

Question

I have to do spectral clustering on moons shaped dataset and then have to create a graph showing the links between data points.

This is my code

import numpy as np
import os
from sklearn import metrics
from sklearn.cluster import SpectralClustering
from sklearn.neighbors import DistanceMetric
from sklearn.cluster import KMeans
import pandas as pd
import pylab as pl
import sklearn.metrics as sm
from sklearn.metrics import confusion_matrix,classification_report
from sklearn.preprocessing import MinMaxScaler
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt
import networkx as nx
X, y = make_moons(n_samples=20)
print(X)
clustering=SpectralClustering(n_clusters=2,
       assign_labels='kmeans',affinity='rbf',gamma=10, degree=3,
         random_state=0)
y_predict=clustering.fit_predict(X)
y_predict_labels = clustering.labels_
clustering.affinity_matrix_

I have got the nodes as data points and the affinity matrix as the weight over the edges. Can someone help me to create a graph using nearest neighbors=2 in the shape of two moons(as my dataset is of two moons) using data points as nodes and affinity matrix as edges between the nodes.

Answer 1

If by "nearest neighbours=2" you mean that, instead of returning a Complete Graph, each node must have an outdegree of 2, then one way to achieve this is with the code below:

Code

k = 2

# Make Graph
G = nx.DiGraph()
for i in range(0, len(X)):
  affinity_list = clustering.affinity_matrix_[i]
  affinity_list[i] = 0 # in case we don't want to consider the node as it's own neighbour
  nearest_neighbors_indices = np.argpartition(clustering.affinity_matrix_[i], -k)[-k:]
  for j in nearest_neighbors_indices:
    G.add_edge(tuple(X[i]), tuple(X[j]), weight = clustering.affinity_matrix_[i][j])

# Draw Graph
pos = {node_name: node_name for node_name in G.nodes}
nx.draw_networkx(G, pos, with_labels=False)

# for node in G.nodes:
#    print(list(G.neighbors(node)))

Output

Details

• For each node we get the indices corresponding to the two maximum values in the affinity matrix with the np.argpartition() method.
• We don't consider nodes as neighbors of themselves, so we change their affinity with themselves to 0, before applying the np.argparition().
• We need a nx.DiGraph instead of a nx.Graph to correctly retrieve only the 2 nearest neighbours of a node. If we use a standard, undirected graph instead, some nodes will have 3 neighbours because they are the closest to another node, which might not be reciprocal
  • As an example, the node with the highest Y in the output have two successors (neighbours) and three predecessors, while two of its predecessors are also successors. If it were an undirected graph, it would have 3 neighbours, since there is no discernment between successors and predecessors in undirected graphs.
  • I recommend uncommenting the print in the last 2 lines of the code, checking the outputs, and then changing the DiGraph to a Graph to understand what this means, if it is not clear yet.

Answer 2

Code

# Make Graph
G = nx.Graph()
i = 0
for i in range(0, len(X)):
  j = 0
  for affinity in clustering.affinity_matrix_[i]:
    G.add_edge(tuple(X[i]), tuple(X[j]), weight = affinity)
    j += 1
  i += 1

# Draw graph in moon shape
pos = {node_name: node_name for node_name in G.nodes}
nx.draw_networkx(G, pos, with_labels=False)

Output

Details

• Nodes' indices in Networkx need to be immutable. That's why we convert X[i] and X[j] to tuples;
• To plot the graph in a moon shape, we first get the positions of each node by getting their indices with G.nodes, and store them in a dictionary (the pos variable is constructed with a dict comprehension). Then we can use the pos dict to draw the graph with the custom layout;
• There might be a more "pythonic" way to make the graph, but this will work too.