Community Detection

Community detection in networks really took off when the measure called ‘modularity’ was introduced in 2004. However, a few years later, it was found out that it suffered from a very particular problem: a resolution limit. This means the method is unable to detect small communities in large networks. One of the suggestions was for example to detect subcommunities on each of the communities you detect in the original graph. So, you need to `zoom in’ on a particular community, to find a more fine-grained substructure.

However, for long, it didn’t remain exactly clear what this limit exactly entailed, and more importantly: what the converse entailed. If there would be a method that would not have this problem, what does it look like? And do such methods exist?

In this project, we take a closer look to this resolution-limit, and define rigorously the opposite: resolution-limit-free. The idea behind the definition of resolution-limit-free is that, no matter what communities you will detect, you will never have to `zoom in’ to fined a more fine-grained substructure. So, whatever partition you will have, it will not change when you look at any communities separate from the rest of the network.


Using this definition, it is actually possible to show which type of methods are resolution-limit-free. Amazingly, there seem to be only a few of such methods, and can be easily described. Of course, you can also download the source code of the algorithm.

Some problems of scale remain however. In particular, it is not clear how to choose a “good” resolution parameter. This problem can be addressed by constructing a complete resolution profile. In addition, it is possible to approximate the significance of a partition based on subgraph probabilities. This addresses the question what the probability is to find such a dense partition in a random graph. Notice this is the opposite of many other methods, which focus on the probability a partition is so dense in a random graph, without considering whether another partition in the same random graph might be more dense. This measure of significance shows excellent performance in uncovering community partitions and pointing to some “good” resolution parameter.


Applications of community detection

Community detection has applications in very diverse research settings. One research question for example focuses on the question whether trade communities reduce conflict within those communities. Related issues such as polarization in the international state system could also be studied using such community partitions. We found that countries within the same trading community experience significantly less conflict.

Another analysis focused on a debate in Dutch newspapers on integration. In this network it becomes clear that a distinction between positive and negative links is crucial. When not distinguishing the two, the structure of the network mostly resembles particular publications and people discussing that. Once you distinguish between positive and negative links, it becomes clear there are mostly two opposing groups. This also points out that it is difficult to study polarization in a network without taking into account negative links.


Leave a Reply

Your email address will not be published. Required fields are marked *

Captcha *
Time limit is exhausted. Please reload CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.