Ward

This notebook illustrates the hierarchical clustering of graphs by the Ward method, after embedding in a space of low dimension.

[1]:
from IPython.display import SVG
[2]:
import numpy as np
[3]:
from sknetwork.data import karate_club, painters, movie_actor
from sknetwork.embedding import Spectral
from sknetwork.hierarchy import Ward, BiWard, cut_straight, dasgupta_score, tree_sampling_divergence
from sknetwork.visualization import svg_graph, svg_digraph, svg_bigraph, svg_dendrogram

Graphs

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

Hierarchy

[5]:
ward = Ward()
dendrogram = ward.fit_transform(adjacency)
[6]:
image = svg_dendrogram(dendrogram)
[7]:
SVG(image)
[7]:
../../_images/tutorials_hierarchy_ward_10_0.svg

Cuts of the dendrogram

[8]:
labels = cut_straight(dendrogram)
print(labels)
[1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[9]:
n_clusters = 4
labels, dendrogram_aggregate = cut_straight(dendrogram, n_clusters, return_dendrogram=True)
print(labels)
[1 1 1 1 3 3 3 1 0 0 3 1 1 1 2 2 3 1 2 1 2 1 2 0 0 0 0 0 0 2 2 0 0 0]
[10]:
_, counts = np.unique(labels, return_counts=True)
[11]:
image = svg_dendrogram(dendrogram_aggregate, names=counts, rotate_names=False)
[12]:
SVG(image)
[12]:
../../_images/tutorials_hierarchy_ward_16_0.svg
[13]:
image = svg_graph(adjacency, position, labels=labels)
[14]:
SVG(image)
[14]:
../../_images/tutorials_hierarchy_ward_18_0.svg

Metrics

[15]:
dasgupta_score(adjacency, dendrogram)
[15]:
0.583710407239819
[16]:
tree_sampling_divergence(adjacency, dendrogram)
[16]:
0.4342993247923879

Other embedding

[17]:
ward = Ward(embedding_method=Spectral(4))

Digraphs

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

Hierarchy

[19]:
biward = BiWard()
dendrogram = biward.fit_transform(adjacency)
[20]:
image = svg_dendrogram(dendrogram, names, n_clusters=3, rotate=True)
[21]:
SVG(image)
[21]:
../../_images/tutorials_hierarchy_ward_29_0.svg

Cuts of the dendrogram

[22]:
# cut with 3 clusters
labels = cut_straight(dendrogram, n_clusters = 3)
print(labels)
[0 0 1 0 1 1 2 0 0 1 0 0 0 2]
[23]:
image = svg_digraph(adjacency, position, names=names, labels=labels)
[24]:
SVG(image)
[24]:
../../_images/tutorials_hierarchy_ward_33_0.svg

Metrics

[25]:
dasgupta_score(adjacency, dendrogram)
[25]:
0.49857142857142855
[26]:
tree_sampling_divergence(adjacency, dendrogram)
[26]:
0.48729193280825467

Bigraphs

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

Hierarchy

[28]:
biward = BiWard(cluster_col = True, cluster_both = True)
biward.fit(biadjacency)
[28]:
BiWard(embedding_method=GSVD(n_components=10, regularization=None, relative_regularization=True, factor_row=0.5, factor_col=0.5, factor_singular=0.0, normalized=True, solver=LanczosSVD(maxiter=None, tol=0.0)), cluster_col=True, cluster_both=True)
[29]:
dendrogram_row = biward.dendrogram_row_
dendrogram_col = biward.dendrogram_col_
dendrogram_full = biward.dendrogram_full_
[30]:
image = svg_dendrogram(dendrogram_row, names_row, n_clusters=4, rotate=True)
[31]:
SVG(image)
[31]:
../../_images/tutorials_hierarchy_ward_43_0.svg
[32]:
image = svg_dendrogram(dendrogram_col, names_col, n_clusters=4, rotate=True)
[33]:
SVG(image)
[33]:
../../_images/tutorials_hierarchy_ward_45_0.svg

Cuts of the dendrogram

[34]:
labels = cut_straight(dendrogram_full, n_clusters = 4)
n_row = biadjacency.shape[0]
labels_row = labels[:n_row]
labels_col = labels[n_row:]
[35]:
image = svg_bigraph(biadjacency, names_row, names_col, labels_row, labels_col)
[36]:
SVG(image)
[36]:
../../_images/tutorials_hierarchy_ward_49_0.svg