Community detection is an essential tool in analyzing networks; by default, we place Community Detection results (called “Louvain Community”) on Color. Communities are crucial in that they partition the network into a human-interpretable number of elements. There are many ways to partition the network into communities, but some methods are more efficient than others.

Virtualitics uses a hybrid of Markov Clustering and Louvain Modularity to rapidly produce community detection results. Ultimately, this hybrid approach ensures stable, reasonable, and quick results that can be used to enable the rest of the analytical tools in Explore.

Louvain Modularity

Modularity is a metric (between -1 and 1) that measures how well a network has been partitioned into modules or communities. The Louvain Modularity Algorithm is a community detection algorithm that aims to iteratively increase modularity. The algorithm works by initially placing each node in a unique community and then iteratively moving nodes from their current community to the neighboring community that would create the biggest increase in modularity. This algorithm is dependent on the structure of the network, and not based on the layout of the nodes in the visualization.

This algorithm is a hierarchal partitioning algorithm; as a result, the initial steps can be slow in reducing the total number of communities but is quick in the final steps for determining the final labels.

Markov Clustering

The Markov Clustering Algorithm leverages linear algebra operations to identify clusters/communities of nodes that have a heavy level of interconnectivity. This algorithm uses a weighted adjacency matrix representation of the network data and alternatively multiplies the matrix with itself and subsequently prunes weaker edges from the matrix. After several iterations, the community structures emerge.

This algorithm quickly reduces the size of the network (in terms of the number of communities) but can take a long time to stabilize on final community labels (each iteration has diminishing returns).

Virtualitics Hybrid Community Detection

The Virtualitics Community Detection algorithm uses the algorithms for what they are most effective at doing. Specifically, we use the Markov Clustering algorithm to rapidly limit the size of the network: we compute the initial community labels based on the results from the first few iterations of the Markov Clustering algorithm. Then we pass the initial labels to our Louvain Modularity algorithm to handle the fine-tuning of the final community detection results, which are stored in the Louvain Community column.

The minimum number of communities is 1 and the maximum number of communities is the same as the total number of nodes in the network.