[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] determining communities in large graphs
From: |
Gábor Csárdi |
Subject: |
Re: [igraph] determining communities in large graphs |
Date: |
Fri, 16 Jan 2009 14:17:34 +0100 |
On Thu, Jan 15, 2009 at 3:11 PM, Rajarshi Guha <address@hidden> wrote:
> Hi, I'm working on a project which involves analysing thousands of networks,
> trying to identify those networks that might exhibit communities. Some of
> these graphs have more than 10,000 edges and I was wondering whether anybody
> on the list has dealt with large graphs and any strategies they may have
> employed. I'm using igraph via the R interface.
I think the fast greedy community algorithm should be able to handle
your graphs. It is only a couple of seconds to run it on a graph with
3000 vertices and about 10000 edges, on a rather moderate laptop.
> On a related note, while I've been using the modularity function to get a
> single number characterizing the presence of communities, I've also been
> looking at the betweeness of individual nodes. The thing I notice is that in
> many cases, the modularity is pretty low,
Compared to what exactly?
> but the difference between the
> average betweeness of the nodes and maximum betweenness is very high. This
> suggests that one of the nodes is acting like a 'bridge' - would this be a
> reasonable way to consider the presence of groups in a network, either in
> addition to the modularity value or inspite of a low modularity value?
Well, obviously you can work out a measure that suits your purposes.
In this particular case, don't forget that 'modularity' is not just a
property of the graph, but a property of a given partitioning of the
graph. Betweenness, however, is a property of the graph.
You can of course define the modularity of a graph as the highest
modularity for all partitions, this definition is fine, except that it
takes forever to calculate it.
G.
> Thanks,
>
> --
> Rajarshi Guha
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
--
Gabor Csardi <address@hidden> UNIL DGM