Re: [igraph] trying to understand edge betweeness community detection implemented in igraph (re-send)

[Gábor Csárdi]

Hi Enzo,

On Thu, May 21, 2009 at 8:16 AM, Enzo Tagliazucchi <address@hidden> wrote:
>  (sorry for duplicate!)
>
>
> Hi all Igraphers,
>
> I'm trying to get a grasp of the community detection algorithms implemented
> in igraph, focusing in Girvan-Newman. Unfortunately, I'm getting nowhere.
> I'm working (as you'd probably guess) with Zachary Karate Club graph to test
> my results.
>
> My first and most fundamental question will be: what is the format of the
> membership vector? If a have 34 nodes, I expect to find a list of 34 numbers
> which would be the list of the 34  nodes components ID?

It is actually exactly that:

g <- graph.full(5) %du% graph.full(5) %du% graph.full(5)
g <- add.edges(g, c(0,5, 0,10, 5, 10))
ebc <- edge.betweenness.community(g)
community.to.membership(g, ebc$merges, steps=12)
$membership
 [1] 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2

$csize
[1] 5 5 5

> Is the merging from
> leaf nodes to bigger clusters or in reverse?

You mean agglomerative vs. divisive? The algorithm is divisive, but
the merges are represented in an agglomerative way.

> I couldn't find much help in the igraph documentation , so any help will be
> greatly appreciated!

See e.g. http://igraph.sourceforge.net/doc/R/community.edge.betweenness.html
(which is the same as ?edge.betweenness.community)

merges  Logical constant, whether to return the merge matrix
representing the hierarchical community structure of the network. This
argument is called merges, even if the community structure algorithm
itself is divisive and not agglomerative: it builds the tree from top
to bottom. There is one line for each merge (ie. split) in matrix, the
first line is the first merge (last split). The communities are
identified by integer number starting from zero. Community ids smaller
than ‘N’, the number of vertices in the graph, belong to singleton
communities, ie. individual vertices. Before the first merge we have
‘N’ communities numbered from zero to ‘N-1’. The first merge, the
first line of the matrix creates community ‘N’, the second merge
creates community ‘N+1’, etc.

Gabor

> Enzo
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM