3
$\begingroup$

So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman algorithm. I've read the paper and have a doubt which I couldn't really figure out.

The algorithm works by removing the edge which has the highest value of "edge betweenness" in every iteration. Suppose I have a graph $G(V, E)$ such that $V = \{ v_{1}, v_2, \cdots , v_n\}$. Now suppose this graph is such that it has 2 distinct communities (something we already know but that's what the algorithm should detect). After the first iteration, it would remove the edge which has the highest value of edge betweenness. Now my question is, after this is done (or even after a few iterations), say I have any vertex $v_i$, how do we know which community this vertex belong to? Am I missing something here?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

This is hierarchical clustering method. As you remove edges, at some point the graph will become disconnected: the connected components are your top-level communities. As you keep removing edges, the top-level communities become disconnected too, and you can think of the new smaller connected components as sub-communities. So you can think of the algorithm as building a tree of finer and finer communities, where the leaves are individual vertices.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks a lot! :D So since we have a hierarchy of communities, to determine the best split we would need to find the modularity after every iteration and pick the division with the highest modularity? While the paper described how to calculate it, do we calculate it after every iteration? $\endgroup$
    – muddy
    Mar 10, 2013 at 19:14
  • $\begingroup$ I do not think that the Girvan and Newman paper you linked discusses modularity. AFAIK, it predates modularity. You can evaluate the clustering after each edge removal using your favorite measure of the a good clustering. But isn't it better to find a clustering that optimizes that measure instead? There are algorithms that optimize modularity directly $\endgroup$
    – Sasho Nikolov
    Mar 11, 2013 at 1:00
  • $\begingroup$ Oh yeah, that paper doesn't discuss modularity, they published the modularity measure a couple of years later to help identify a "good" split after which a lot of work was done on optimizing that parameter. I'm trying to look into an evolutionary approach to community detection and was just trying to figure out exactly how this algorithm distinguishes where a vertex should belong. Since a LOT of work is based off the GN algorithm. $\endgroup$
    – muddy
    Mar 11, 2013 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.