Louvain

This notebook illustrates the clustering of a graph by the Louvain algorithm.

[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import karate_club, painters, movie_actor
from sknetwork.clustering import Louvain, BiLouvain, modularity, bimodularity
from sknetwork.linalg import normalize
from sknetwork.utils import bipartite2undirected, membership_matrix
from sknetwork.visualization import svg_graph, svg_digraph, svg_bigraph

Graphs

[4]:
graph = karate_club(metadata=True)
adjacency = graph.adjacency
position = graph.position

Clustering

[5]:
louvain = Louvain()
labels = louvain.fit_transform(adjacency)
[6]:
labels_unique, counts = np.unique(labels, return_counts=True)
print(labels_unique, counts)
[0 1 2 3] [12 11  6  5]
[7]:
image = svg_graph(adjacency, position, labels=labels)
[8]:
SVG(image)
[8]:
../../_images/tutorials_clustering_louvain_11_0.svg

Metrics

[9]:
modularity(adjacency, labels)
[9]:
0.4188034188034188

Aggregate graph

[10]:
adjacency_aggregate = louvain.adjacency_
[11]:
average = normalize(membership_matrix(labels).T)
position_aggregate = average.dot(position)
labels_unique, counts = np.unique(labels, return_counts=True)
[12]:
image = svg_graph(adjacency_aggregate, position_aggregate, counts, labels=labels_unique,
                  display_node_weight=True, node_weights=counts, scale=0.5)
[13]:
SVG(image)
[13]:
../../_images/tutorials_clustering_louvain_18_0.svg

Soft clustering

[14]:
scores = louvain.membership_[:,1].toarray().ravel()
[15]:
image = svg_graph(adjacency, position, scores=scores)
[16]:
SVG(image)
[16]:
../../_images/tutorials_clustering_louvain_22_0.svg

Digraphs

[17]:
graph = painters(metadata=True)
adjacency = graph.adjacency
names = graph.names
position = graph.position

Clustering

[18]:
louvain = Louvain()
labels = louvain.fit_transform(adjacency)
[19]:
labels_unique, counts = np.unique(labels, return_counts=True)
print(labels_unique, counts)
[0 1 2] [5 5 4]
[20]:
image = svg_digraph(adjacency, position, names, labels)
[21]:
SVG(image)
[21]:
../../_images/tutorials_clustering_louvain_29_0.svg

Metrics

[22]:
modularity(adjacency, labels)
[22]:
0.32480000000000003

Aggregate graph

[23]:
adjacency_aggregate = louvain.adjacency_
[24]:
average = normalize(membership_matrix(labels).T)
position_aggregate = average.dot(position)
labels_unique, counts = np.unique(labels, return_counts=True)
[25]:
image = svg_digraph(adjacency_aggregate, position_aggregate, counts, labels=labels_unique,
                    display_node_weight=True, node_weights=counts, scale=0.5)
[26]:
SVG(image)
[26]:
../../_images/tutorials_clustering_louvain_36_0.svg

Soft clustering

[27]:
scores = louvain.membership_[:,1].toarray().ravel()
[28]:
image = svg_graph(adjacency, position, scores=scores)
[29]:
SVG(image)
[29]:
../../_images/tutorials_clustering_louvain_40_0.svg

Bigraphs

[30]:
graph = movie_actor(metadata=True)
biadjacency = graph.biadjacency
names_row = graph.names_row
names_col = graph.names_col

Clustering by BiLouvain

[31]:
bilouvain = BiLouvain()
bilouvain.fit(biadjacency)
labels_row = bilouvain.labels_row_
labels_col = bilouvain.labels_col_
[32]:
image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
[33]:
SVG(image)
[33]:
../../_images/tutorials_clustering_louvain_46_0.svg

Metrics

[34]:
bimodularity(biadjacency, labels_row, labels_col)
[34]:
0.5742630385487529

Aggregate graph

[35]:
biadjacency_aggregate = bilouvain.biadjacency_
[36]:
labels_unique_row, counts_row = np.unique(labels_row, return_counts=True)
labels_unique_col, counts_col = np.unique(labels_col, return_counts=True)
[37]:
image = svg_bigraph(biadjacency_aggregate, counts_row, counts_col, labels_unique_row, labels_unique_col,
                    display_node_weight=True, node_weights_row=counts_row, node_weights_col=counts_col,
                    scale=0.5)
[38]:
SVG(image)
[38]:
../../_images/tutorials_clustering_louvain_53_0.svg

Soft clustering

[39]:
scores_row = bilouvain.membership_row_[:,1].toarray().ravel()
scores_col = bilouvain.membership_col_[:,1].toarray().ravel()
[40]:
image = svg_bigraph(biadjacency, names_row, names_col, scores_row=scores_row, scores_col=scores_col)
[41]:
SVG(image)
[41]:
../../_images/tutorials_clustering_louvain_57_0.svg

Clustering by Louvain

[42]:
louvain = Louvain()
adjacency = bipartite2undirected(biadjacency)
labels = louvain.fit_transform(adjacency)
[43]:
n_row = biadjacency.shape[0]
labels_row = louvain.labels_[:n_row]
labels_col = louvain.labels_[n_row:]
[44]:
image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
[45]:
SVG(image)
[45]:
../../_images/tutorials_clustering_louvain_62_0.svg

Aggregate graph

[46]:
biadjacency_aggregate = louvain.adjacency_[:n_row][:n_row]
[47]:
labels_unique_row, counts_row = np.unique(labels_row, return_counts=True)
labels_unique_col, counts_col = np.unique(labels_col, return_counts=True)
[48]:
image = svg_bigraph(biadjacency_aggregate, counts_row, counts_col, labels_unique_row, labels_unique_col,
                    display_node_weight=True, node_weights_row=counts_row, node_weights_col=counts_col,
                    scale=0.5)
[49]:
SVG(image)
[49]:
../../_images/tutorials_clustering_louvain_67_0.svg