I'm a bit confused. I tried this on an empty graph with ten vertices, and
it puts all of the vertices in the same cluster. Is this the correct
behavior? Similarly, if I have a K_9 with a single isolated vertex, I also
get one big cluster. Printing the dendrogram after running it through the
fixing function still causes an exception, though now it looks like a
Python 3 compatibility issue
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "/usr/local/.../igraph/clustering.py", line 607, in __str__
return self.summary(verbosity=1)
File "/usr/local/.../igraph/clustering.py", line 680, in summary
char_array = array("c", " "*width)
ValueError: bad typecode (must be b, B, u, h, H, i, I, l, L, q, Q, f or d)
Jeremy Kun
Mathematics PhD Candidate
University of Illinois at Chicago
On Sat, May 24, 2014 at 3:57 PM, Tamás Nepusz <[email protected]> wrote:
> 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 [email protected]
> Reply: Help for igraph users [email protected]
> Date: 22 May 2014 at 20:15:13
> To: [email protected] [email protected]
> 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
> > [email protected]
> > https://lists.nongnu.org/mailman/listinfo/igraph-help
> >
>
>
_______________________________________________
igraph-help mailing list
[email protected]
https://lists.nongnu.org/mailman/listinfo/igraph-help
