[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:


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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]