Re: [igraph] determining communities in large graphs

[Gábor Csárdi]

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