[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Walktrap / Community / Modularity
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Walktrap / Community / Modularity |
Date: |
Fri, 6 Jul 2012 15:40:05 +0200 |
> Thanks for your reply. Do you know if there is a way I can calculate vertex
> modularity? I want to know how modular a vertex is - ie. does its edges stay
> within the community or cross communities - is it a hub of the community or
> is it the community/rest of graph communicator.
I am not aware of any formal definition for "vertex modularity", but an
informal measure that some people have used is to count what fraction of the
edges incident on the vertex stay inside the community. This can be calculated
relatively easily.
Suppose that you have a membership vector called "membership", and your graph
is in "g". Then first we get the adjacency list of the graph:
adjlist <- get.adjlist(g)
and then apply the following (pretty convoluted) expression:
sapply(1:vcount(g), function(v) { sum(membership[adjlist[[v]]] ==
membership[v]) / length(adjlist[[v]]) })
Let's dissect the above expression a bit. sapply() takes two arguments; the
first is a list, the second is a function. sapply() will call the function with
each element of the list and store the values in a vector. The list we pass
here is simply the list of vertex identifiers (from 1 to the number of
vertices), and the function itself calculates the "vertex modularity" for a
single vertex. In the function, we do the following. First, we take the
neighbors of vertex v by calling adjlist[[v]] (note the double brackets), then
fetch the community ids for each vertex:
membership[adjlist[[v]]]
Then we compare each element of this vector with the community id of v itself:
membership[adjlist[[v]]] == membership[v]
The result is a binary vector where TRUE means that a given neighbor is in the
same community as v itself and FALSE means that it is not. Applying sum() to
this vector gives us the number of neighbors that are in the same community as
v, and dividing it by the number of neighbors gives us the number you are
looking for.
Best,
T.
- [igraph] Walktrap / Community / Modularity, Amanda Schierz, 2012/07/05
- Re: [igraph] Walktrap / Community / Modularity, Tamás Nepusz, 2012/07/05
- Re: [igraph] Walktrap / Community / Modularity, Amanda Schierz, 2012/07/06
- Re: [igraph] Walktrap / Community / Modularity, Gábor Csárdi, 2012/07/06
- Re: [igraph] Walktrap / Community / Modularity,
Tamás Nepusz <=
- Re: [igraph] Walktrap / Community / Modularity, Amanda Schierz, 2012/07/17
- Re: [igraph] Walktrap / Community / Modularity, Tamás Nepusz, 2012/07/17
- Re: [igraph] Walktrap / Community / Modularity, Bernie Hogan, 2012/07/17
- Re: [igraph] Walktrap / Community / Modularity, Tamás Nepusz, 2012/07/17
- Re: [igraph] Walktrap / Community / Modularity, Amanda Schierz, 2012/07/17
- Re: [igraph] Walktrap / Community / Modularity, Gábor Csárdi, 2012/07/17