Link prediction

This notebook illustrates the prediction of links of a graph by nearest neighbors in the embedding space. Most links are supposed to be actual edges of the graph.

[1]:

from IPython.display import SVG

[2]:

import numpy as np

[3]:

from sknetwork.data import karate_club, painters, movie_actor
from sknetwork.linkpred import NNLinker
from sknetwork.embedding import Spectral
from sknetwork.visualization import visualize_graph, visualize_bigraph

Graphs

[4]:

graph = karate_club(metadata=True)
adjacency = graph.adjacency
position = graph.position
labels_true = graph.labels

[5]:

image = visualize_graph(adjacency, position)
SVG(image)

[5]:

../../_images/tutorials_linkpred_nn_7_0.svg

[6]:

linker = NNLinker(n_neighbors=3)
links = linker.fit_predict(adjacency)

[7]:

image = visualize_graph(links, position, directed=False, display_edge_weight=False)
SVG(image)

[7]:

../../_images/tutorials_linkpred_nn_9_0.svg

[8]:

linker = NNLinker(threshold=0.5)
links = linker.fit_predict(adjacency)

[9]:

image = visualize_graph(links, position, directed=False, display_edge_weight=False)
SVG(image)

[9]:

../../_images/tutorials_linkpred_nn_11_0.svg

[10]:

# Nearest neighbors in embedding space
linker = NNLinker(n_neighbors=5, threshold=0.5, embedding_method=Spectral(2))
links = linker.fit_predict(adjacency)

[11]:

image = visualize_graph(links, position, directed=False, display_edge_weight=False)
SVG(image)

[11]:

../../_images/tutorials_linkpred_nn_13_0.svg

Directed graphs

[12]:

graph = painters(metadata=True)
adjacency = graph.adjacency
position = graph.position
names = graph.names

[13]:

image = visualize_graph(adjacency, position, names)
SVG(image)

[13]:

../../_images/tutorials_linkpred_nn_16_0.svg

[14]:

linker = NNLinker(embedding_method=Spectral(3))
links = linker.fit_predict(adjacency)

[15]:

image = visualize_graph(links, position, names, directed=True, display_edge_weight=False)
SVG(image)

[15]:

../../_images/tutorials_linkpred_nn_18_0.svg

Bipartite graphs

[16]:

graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col

[17]:

image = visualize_bigraph(biadjacency, names_row, names_col)
SVG(image)

[17]:

../../_images/tutorials_linkpred_nn_21_0.svg

[18]:

linker = NNLinker(n_neighbors=5, threshold=0.5, embedding_method=Spectral(3))
links = linker.fit_predict(biadjacency)

[19]:

image = visualize_bigraph(links, names_row, names_col, display_edge_weight=False)
SVG(image)

[19]:

../../_images/tutorials_linkpred_nn_23_0.svg