Louvain iteration

This notebook illustrates the hierarchical clustering of graphs by Louvain iteration (successive applications of the Louvain algorithm to build the dendrogram in a top-down manner).

[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import karate_club, painters, movie_actor
from sknetwork.hierarchy import LouvainIteration
from sknetwork.hierarchy import cut_straight, dasgupta_score, tree_sampling_divergence
from sknetwork.visualization import visualize_graph, visualize_bigraph, visualize_dendrogram

Graphs

[4]:
graph = karate_club(metadata=True)
adjacency = graph.adjacency
position = graph.position
[5]:
# hierarchical clustering
louvain = LouvainIteration()
dendrogram = louvain.fit_predict(adjacency)
[6]:
image = visualize_dendrogram(dendrogram)
SVG(image)
[6]:
../../_images/tutorials_hierarchy_louvain_iteration_8_0.svg
[7]:
# cuts
labels = cut_straight(dendrogram)
print(labels)
[0 0 0 0 3 3 3 0 1 0 3 0 0 0 1 1 3 0 1 0 1 0 1 2 2 2 1 2 2 1 1 2 1 1]
[8]:
labels, dendrogram_aggregate = cut_straight(dendrogram, n_clusters=4, return_dendrogram=True)
print(labels)
[0 0 0 0 3 3 3 0 1 0 3 0 0 0 1 1 3 0 1 0 1 0 1 2 2 2 1 2 2 1 1 2 1 1]
[9]:
_, counts = np.unique(labels, return_counts=True)
[10]:
image = visualize_dendrogram(dendrogram_aggregate, names=counts, rotate_names=False)
SVG(image)
[10]:
../../_images/tutorials_hierarchy_louvain_iteration_12_0.svg
[11]:
image = visualize_graph(adjacency, position, labels=labels)
SVG(image)
[11]:
../../_images/tutorials_hierarchy_louvain_iteration_13_0.svg
[12]:
# metrics
dasgupta_score(adjacency, dendrogram)
[12]:
np.float64(0.6293363499245852)

Directed graphs

[13]:
graph = painters(metadata=True)
adjacency = graph.adjacency
position = graph.position
names = graph.names
[14]:
# hierarchical clustering
louvain = LouvainIteration()
dendrogram = louvain.fit_predict(adjacency)
[15]:
image = visualize_dendrogram(dendrogram, names, rotate=True)
SVG(image)
[15]:
../../_images/tutorials_hierarchy_louvain_iteration_18_0.svg
[16]:
# cut with 3 clusters
labels = cut_straight(dendrogram, n_clusters = 3)
print(labels)
[1 0 2 0 2 2 1 0 1 2 1 0 0 1]
[17]:
image = visualize_graph(adjacency, position, names=names, labels=labels)
SVG(image)
[17]:
../../_images/tutorials_hierarchy_louvain_iteration_20_0.svg
[18]:
# metrics
dasgupta_score(adjacency, dendrogram)
[18]:
np.float64(0.53)

Bipartite graphs

[19]:
graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col
[20]:
# hierarchical clustering
louvain = LouvainIteration()
louvain.fit(biadjacency)
dendrogram_row = louvain.dendrogram_row_
dendrogram_col = louvain.dendrogram_col_
dendrogram_full = louvain.dendrogram_full_
[21]:
image = visualize_dendrogram(dendrogram_row, names_row, n_clusters=4, rotate=True)
SVG(image)
[21]:
../../_images/tutorials_hierarchy_louvain_iteration_25_0.svg
[22]:
image = visualize_dendrogram(dendrogram_col, names_col, n_clusters=4, rotate=True)
SVG(image)
[22]:
../../_images/tutorials_hierarchy_louvain_iteration_26_0.svg
[23]:
# cuts
labels = cut_straight(dendrogram_full, n_clusters = 4)
n_row = biadjacency.shape[0]
labels_row = labels[:n_row]
labels_col = labels[n_row:]
[24]:
image = visualize_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
SVG(image)

[24]:
../../_images/tutorials_hierarchy_louvain_iteration_28_0.svg