World's most popular travel blog for travel bloggers.

# [Solved]: How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?

, ,
Problem Detail:

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?

#### Answered By : Sasho Nikolov

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.