# 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, get_modularity
from sknetwork.linalg import normalize
from sknetwork.utils import get_membership
from sknetwork.visualization import svg_graph, svg_bigraph


## Graphs

[4]:

graph = karate_club(metadata=True)
position = graph.position

[5]:

louvain = Louvain()

[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)
SVG(image)

[7]:

[8]:

# metric

[8]:

0.4188034188034188

[9]:

# aggregate graph (one node per cluster)

[10]:

average = normalize(get_membership(labels).T)
position_aggregate = average.dot(position)
labels_unique, counts = np.unique(labels, return_counts=True)

[11]:

image = svg_graph(adjacency_aggregate, position_aggregate, counts, labels=labels_unique,
display_node_weight=True, node_weights=counts)
SVG(image)

[11]:

[12]:

# probability distribution over clusters
probs = louvain.predict_proba()

[13]:

# scores for cluster 1
scores = probs[:,1]

[14]:

image = svg_graph(adjacency, position, scores=scores)
SVG(image)

[14]:


## Directed graphs

[15]:

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

[16]:

# clustering
louvain = Louvain()

[17]:

labels_unique, counts = np.unique(labels, return_counts=True)
print(labels_unique, counts)

[0 1 2] [5 5 4]

[18]:

image = svg_graph(adjacency, position, names=names, labels=labels)
SVG(image)

[18]:

[19]:

get_modularity(adjacency, labels)

[19]:

0.32480000000000003

[20]:

# aggregate graph

[21]:

average = normalize(get_membership(labels).T)
position_aggregate = average.dot(position)
labels_unique, counts = np.unique(labels, return_counts=True)

[22]:

image = svg_graph(adjacency_aggregate, position_aggregate, counts, labels=labels_unique,
display_node_weight=True, node_weights=counts)
SVG(image)

[22]:

[23]:

# probability distribution over clusters
probs = louvain.predict_proba()

[24]:

# scores for cluster 1
scores = probs[:,1]

[25]:

image = svg_graph(adjacency, position, scores=scores)
SVG(image)

[25]:


## Bipartite graphs

[26]:

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

[27]:

# clustering
louvain = Louvain()
labels_row = louvain.labels_row_
labels_col = louvain.labels_col_

[28]:

image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
SVG(image)

[28]:

[29]:

# metric

[29]:

0.5705782312925171

[30]:

# aggregate graph

[31]:

labels_unique_row, counts_row = np.unique(labels_row, return_counts=True)
labels_unique_col, counts_col = np.unique(labels_col, return_counts=True)

[32]:

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)
SVG(image)

[32]:

[33]:

# probability distribution over clusters
probs_row = louvain.predict_proba()
probs_col = louvain.predict_proba(columns=True)

[34]:

# soft clustering
scores_row = probs_row[:,1]
scores_col = probs_col[:,1]

[35]:

image = svg_bigraph(biadjacency, names_row, names_col, scores_row=scores_row, scores_col=scores_col)
SVG(image)

[35]: