# 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)
position = graph.position


Hierarchy

[5]:

ward = Ward()

[6]:

image = svg_dendrogram(dendrogram)

[7]:

SVG(image)

[7]:


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]:

[13]:

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

[14]:

SVG(image)

[14]:


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)
position = graph.position
names = graph.names


Hierarchy

[19]:

biward = BiWard()

[20]:

image = svg_dendrogram(dendrogram, names, n_clusters=3, rotate=True)

[21]:

SVG(image)

[21]:


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]:


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)
names_row = graph.names_row
names_col = graph.names_col


Hierarchy

[28]:

biward = BiWard(cluster_col = True, cluster_both = True)

[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]:

[32]:

image = svg_dendrogram(dendrogram_col, names_col, n_clusters=4, rotate=True)

[33]:

SVG(image)

[33]:


Cuts of the dendrogram

[34]:

labels = cut_straight(dendrogram_full, n_clusters = 4)

[35]:

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

[36]:

SVG(image)

[36]: