Wiki‎ > ‎

Community detection

One of the main areas of interest in the field of network analysis is the detection of the communities present in a give graph. Over the years, a large number of techniques have been proposed by different authors. These different approaches have their own advantages and disadvantages: some methods scale better, some obtain better results, some automatically obtain the number of communities instead of require this value as a parameter, etc.

The most relevant approaches have been implemented in the NOESIS framework, including a wide range of techniques from very different families of community detection methods. Using these algorithms in NOESIS is very simple. If we want to compute the XX algorithm for a given a network, we can do it as follows:

CommunityDetector communitydetector = new KernighanLinCommunityDetector(network);
communitydetector.compute();
Once the communities are computed, we can retrieve to which degree a node belongs to a community:

Matrix communities = communitydetector.getResults();

The returned matrix represents each node as a row and each community as a column. The degree to which a node belongs to a community is proportional to the value in the row associated to the node and the column associated to the given community. Most of the time, we are only interested on the main community of each node:

Vector community = communitydetector.getBest();

The vector community would contain the index of the main community for each node in the network.

Different families of community detection algorithms are included in NOESIS under the package algorithms/communities, including hierarchical, spectral, overlapping, partitioning, and modularity-based algorithms.

Comments