Re: [igraph] On walktrap clustering and isolated vertices

[Tamás Nepusz]

Hi Jeremy,

This is a bug in igraph. We use the original walktrap implementation of Latapy 
& Pons in our code, and their implementation builds the dendrogram up to the 
level where there are no more edges between the components. The dendrogram 
printing methods and the as_clustering() method are not properly prepared for 
this, therefore you get an error. I think the easiest workaround would be to 
write a function that "fixes" the dendrogram by merging the remaining clusters 
in an arbitrary order. You can find such a function in one of my earlier emails:

http://lists.gnu.org/archive/html/igraph-help/2014-02/msg00067.html
 
--  
T.

------------------------------------------------------
From: Jeremy Kun address@hidden
Reply: Help for igraph users address@hidden
Date: 22 May 2014 at 20:15:13
To:address@hidden address@hidden
Subject:  [igraph] On walktrap clustering and isolated vertices

> Hi there,
>  
> I've been working with igraph's walktrap clustering function for a while
> now, but I've noticed some behavior that strikes me as strange. In
> particular, if I run walktrap on a graph with an isolated vertex, the
> resulting dendrogram is either empty, raises an exception when I try to
> print it, or raises an exception when I try to convert it to a clustering
> via as_clustering(). This use case shows up in my work in a way that's hard
> to avoid, because I'm essentially sampling graphs from a distribution that
> gives a modest nonzero probability for a vertex to be isolated.
>  
> I've pasted an example use case below that tries to run walktrap on an
> empty graph on ten vertices, then adds an edge and tries again, then forms
> the complete graph K_9 plus a single isolated vertex and tries again.
>  
> What I don't understand is why these errors are occurring. Do the igraph
> devs (who are hopefully reading this :)) want to unilaterally ban anyone
> from doing walktrap on a graph with multiple components? I don't see any
> technical reasons to do this: even if there's an isolated vertex the
> walktrap function could add a self-loop, as Pons/Latapy do IIRC, and then
> the distances between vertices in different components can be defined to be
> 1+max so that they are merged last in the dendrogram, and in an arbitrary
> fashion.
>  
> Or, does this appear to be a true bug?
>  
> Note that when I try to do walktrap with, say, a disjoint union of two
> small cliques, the as_clustering() produces a good clustering, but printing
> the dendrogram sill raises an exception. So the issue does appear to be
> isolated to isolated vertices.
>  
> Thanks in advance for your advice and help!
>  
> Python 3.3.3 (default, Dec 30 2013, 23:51:18)
> [GCC 4.2.1 Compatible Apple LLVM 5.0 (clang-500.2.79)] on darwin
> Type "help", "copyright", "credits" or "license" for more information.
> >>> import igraph
> >>> G = igraph.Graph(10)
> >>> cl1 = G.community_walktrap()
> >>> print(cl1)
> Dendrogram, 0 elements, 0 merges
> >>> cl1.as_clustering()
> Traceback (most recent call last):
> File "", line 1, in  
> File ".../igraph/clustering.py", line 959, in as_clustering
> num_elts - n)
> igraph._igraph.InternalError: Error at ../../../src/community.c:767:
> `steps' to big or `merges' matrix too short, Invalid value
> >>> G[1,2] = 1
> >>> cl2 = G.community_walktrap()
> >>> print(cl2)
> Traceback (most recent call last):
> File "", line 1, in  
> File ".../igraph/clustering.py", line 607, in __str__
> return self.summary(verbosity=1)
> File ".../igraph/clustering.py", line 673, in summary
> width = max(positions)+1
> TypeError: unorderable types: int() > NoneType()
> >>> cl2.as_clustering()
> Traceback (most recent call last):
> File "", line 1, in  
> File ".../igraph/clustering.py", line 959, in as_clustering
> num_elts - n)
> igraph._igraph.InternalError: Error at ../../../src/community.c:767:
> `steps' to big or `merges' matrix too short, Invalid value
> >>> G.add_edges([(i,j) for i in range(1,10) for j in range(1,10) if i != j])
> >>> len(G.es)
> 73
> >>> cl3 = G.community_walktrap()
> >>> print(cl3)
> Traceback (most recent call last):
> File "", line 1, in  
> File ".../igraph/clustering.py", line 607, in __str__
> return self.summary(verbosity=1)
> File ".../igraph/clustering.py", line 673, in summary
> width = max(positions)+1
> TypeError: unorderable types: int() > NoneType()
> >>> cl3.as_clustering()
> Traceback (most recent call last):
> File "", line 1, in  
> File ".../igraph/clustering.py", line 959, in as_clustering
> num_elts - n)
> igraph._igraph.InternalError: Error at ../../../src/community.c:767:
> `steps' to big or `merges' matrix too short, Invalid value
>  
>  
> Jeremy Kun
> Mathematics PhD Candidate
> University of Illinois at Chicago
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>