Sorry, in some places above I wrote "multiple components" where I meant "isolated vertices."
Jeremy Kun Mathematics PhD Candidate University of Illinois at Chicago On Thu, May 22, 2014 at 1:14 PM, Jeremy Kun <[email protected]> wrote: > 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 "<stdin>", line 1, in <module> > 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 "<stdin>", line 1, in <module> > 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 "<stdin>", line 1, in <module> > 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 "<stdin>", line 1, in <module> > 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 "<stdin>", line 1, in <module> > 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
