pythonigraphhierarchical-clustering

How to cluster a graph using python igraph


I've been using python igraph to try to make an easier time of generating and analyzing graphs. My code below generates a random graph of 50 nodes and clusters it:

from igraph import *
import random as rn

g = Graph()

size = 50

g.add_vertices(size)

vert = []

for i in range(size):
    for j in range(size):
        test = rn.randint(0,5)
        if j >= i or test is not 0:
            continue
        g.add_edges([(i,j)])

#layout = g.layout("kk")
#plot(g, layout = layout)

#dend = VertexDendrogram(graph=g, optimal_count=10)

clust = VertexClustering(g, membership=range(size))
#clust = dend.as_clustering()

c = clust.cluster_graph()

plot(clust, mark_groups=True)

layout = c.layout("kk")
#plot(c, layout = layout)

However, I'm not sure if this is correct, since the result has every single node as its own, isolated cluster. I am assuming this is somehow related to membership, the required parameter of VertexClustering, because I really don't understand what it means or why it is required.

Here is what the terse documentation says:

the membership list. The length of the list must be equal to the number of vertices in the graph. If None, every vertex is assumed to belong to the same cluster.

And doesn't explain what I am supposed to set membership to in order to get a normal regular clustering.

Alternatively I tried using the VertexDendrogram as seen in the two commented lines of code. However, running this comes up with this runtime error:

Traceback (most recent call last):
  File "sma_hw6_goedeke.py", line 22, in <module>
    dend = VertexDendrogram(graph=g, optimal_count=10)
TypeError: __init__() takes at least 3 arguments (3 given)

This is because VertexDendrogram requires the parameter merges. However, once again I have no clue what merges is supposed to be set to or why it is required. The documentation again says almost nothing:

merges - the merges performed given in matrix form.

And I have no clue what that is. So what should I do to this code to get a normal, regular clustering for my random graph I can experiment with?


Solution

  • I stand by my original assessment that the documentation for igraph is maddeningly too terse.

    The function I actually needed for what I am doing is igraph.Graph.community_fastgreedy(). In general, it seems all the functions that run a clustering algorithm all start with "community" in their name.