Re: [igraph] community detection

[Tamas Nepusz]

Hi,

> It goes against my intuition that is vertices in the same community should
> share more neighbors.
> So, I am wondering whether I get a wrong result of community division. Or
> any other explanation for my problem.
As I said before, every community detection algorithm is just a
heuristic that tries to formalise "some" intuition that the authors of
the algorithm had about what constitutes a good community. For instance,
for the fast greedy community detection, the intuition was that a good
community contains more edges that what one would observe if the edges
of the graph are rewired randomly while keeping the degree distribution.
In other words, an edge between two low-degree nodes is more
"surprising" than an edge between two high-degree nodes (since those
have a larger probability to be connected just by chance), and the
algorithm tries to connect more "surprising" edges into one community.
The modularity measures this directly, and the algorithm strives to
maximise the modularity. While it may be argued whether this intuition
makes sense or not, the algorithm does this and if you don't "like" the
results, you can either try a different approach or conclude that your
graph does not really have a pronounced community structure. Not all
graphs have communities, but nevertheless a community detection
algorithm will still try to find communities. Most algorithms find
communities even in a completely random Erdos-Renyi graph, and sometimes
the modularities of those community divisions are surprisingly high.

-- 
Tamas