Re: [igraph] community detection

[Tamas Nepusz]

Hi,

> I found it has 253 edges inside the community, but 391 edges towards
> vertices outside the community. [...]
> This is contrary to my intuition of community. A good community should have
> more edges inside, and less edges towards outside.
> So, what is wrong?
Nothing. Every community detection algorithm is a heuristics that tries
to solve the problem of finding dense subgraphs within a network. Some
heuristics work better in some cases while others work better in other
cases. None of the algorithms guarantee that the communities it detects
conform to your intuition. While your intuition coincides with the
definition of a community "in the weak sense" as defined by Radicchi et
al, note that this might be misleading in some cases. Imagine a clique
of 23 vertices in an undirected graph. This clique has 253 edges, like
your community. Now, let us add 391 more vertices to this network, each
of them connecting to only one of the vertices in the original clique.
The result is a tightly connected "core" consisting of 253 internal
edges and 391 boundary edges. According to your intuition, this is not a
community; however, the subgraph spanned by the 23 original vertices
could not be made any denser than that. So, I would say it is a
community.

-- 
Tamas