[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] Fastgreedy Community Finding Algorithm
From: |
Georgios Tsoukas |
Subject: |
[igraph] Fastgreedy Community Finding Algorithm |
Date: |
Fri, 14 Sep 2007 11:45:53 +0200 |
Hi,
i am trying to compute communities in a network of some millions of
vertices. The FastGreedy algorithm proposet by Clauset, Newman and
Moore seems a good starting point to me.
I have seen that you have modified the original algorithms data
structures with some of the proposals made in "Finding Commmunity
Structure in Mega-scale Social Networks" by Ken Wakita and Toshiyuki
Tsurumi.
Now i wonder if there is a special reason to not also implement the
improvements proposed by Wakita and Tsurumi for the merging
heuristics as well??? (except of the work necessary for implementation
of course.)
To me it seems true, that the original algorithm has a super quadratic
run time complexity on many networks since merges are often performed
in an "unbalanced" way and thus the d in O(md log n) is closer to n
than to log n.
Best regards,
Georgios
- [igraph] Fastgreedy Community Finding Algorithm,
Georgios Tsoukas <=