Tolerating the Community Detection Resolution Limit with Edge Weighting

Details Tolerating the Community Detection Resolution Limit with Edge Weighting Tolerating the Community Detection Resolution Limit with Edge Weighting

2009-03-05

arxiv.org/abs/0903.1072v2

Physics

Physics and Society

revision with 8 pages 3 figures 2 tables

Scientific paper

Communities of vertices within a giant network such as the World-Wide Web are likely to be vastly smaller than the network itself. However, Fortunato and Barth\'{e}lemy have proved that modularity maximization algorithms for community detection may fail to resolve communities with fewer than $\sqrt{L/2}$ edges, where $L$ is the number of edges in the entire network. This resolution limit leads modularity maximization algorithms to have notoriously poor accuracy on many real networks. Fortunato and Barth\'{e}lemy's argument can be extended to networks with weighted edges as well, and we derive this corollary argument. We conclude that weighted modularity algorithms may fail to resolve communities with fewer than $\sqrt{W \epsilon/2}$ total edge weight, where $W$ is the total edge weight in the network and $\epsilon$ is the maximum weight of an inter-community edge. If $\epsilon$ is small, then small communities can be resolved. Given a weighted or unweighted network, we describe how to derive new edge weights in order to achieve a low $\epsilon$, we modify the ``CNM'' community detection algorithm to maximize weighted modularity, and show that the resulting algorithm has greatly improved accuracy. In experiments with an emerging community standard benchmark, we find that our simple CNM variant is competitive with the most accurate community detection methods yet proposed.

Affiliated with

Also associated with

No associations

Rating

Tolerating the Community Detection Resolution Limit with Edge Weighting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tolerating the Community Detection Resolution Limit with Edge Weighting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tolerating the Community Detection Resolution Limit with Edge Weighting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115872