Community Detection Algorithms

In the LPA, the nodes select their community based on their direct neighbors using the node labels. In addition, weights on nodes and relationships can also be considered. The idea is that a single label can quickly become dominant in a densely-connected group of nodes, but it will have trouble crossing a sparsely connected region.

Here is how the Label Propagation algorithm works. First, every node is initialized with a property. By default, the initial property is unique for every node. However, the LPA also lends itself well to semi-supervised learning because you can seed the initial properties with pre-assigned node labels that you know are predictive.

In this example, we have started with 2 A nodes, but left all other nodes as unique. We are using the node default weights of 1. Nodes are then processed randomly, with each node acquiring its neighbor’s label with the maximum weight. So, in the first iteration, the left A acquires the label F, B acquires the label D, and C now becomes A. The maximum weight is calculated based on the weights of neighbor nodes and their relationships. In addition, ties are broken uniformly and randomly. There will be times when a label is not updated because the neighbor with the maximum weight has the same label. Iterations continue until each node has the majority label of its neighbors or reached the maximum iteration limit. A maximum iteration limit will prevent endless cycles where the algorithm cannot converge on a solution, essentially getting caught in a flip-flop cycle for some labels. In contrast to other algorithms, LPA can return different community structures when run multiple times on the same graph. The order in which LPA evaluates nodes can influence the final communities it returns. Another factor is the random tie-breaking process.

The Louvain Modularity algorithm consists of repeated application of two steps. The first step is a “greedy” assignment of nodes to communities, favoring local optimizations of modularity. The modularity score quantifies the quality of an assignment of nodes to communities. This process evaluates how much more densely connected the nodes within a community are, compared to how connected they would be in a random network. It starts by calculating the change in modularity if that node joins a community with each of its immediate neighbors. The node then joins the node with the highest modularity change. The process is repeated for each node until the optimal communities are formed. The second step is defining a new coarse-grained network, based on the communities found in the first step. These two steps are repeated until no further modularity-increasing reassignments of communities are possible.

In this example, we can see how the Louvain Modularity algorithm works. First, the algorithm assigns nodes to communities by favoring local optimization of modularity. In our case, the algorithm found four groups of nodes, which are indicated by node color. In the second step, the algorithm merges each group of nodes into a single node. The count of links between nodes within the same community and between various communities is now represented as a weighted relationship between the newly-merged nodes. Once the new network is created, the whole process is repeated until a modularity maximum is reached. The Louvain Modularity algorithm is interesting, because you can observe both the final as well as the intermediate communities that are calculated at the end of each level. It is regarded as a hierarchical clustering algorithm because a hierarchy of communities is produced as a result. As a rule of thumb, the communities on lower levels are smaller and more fine-grained than the communities found on higher and final levels.

The goal of the Local Clustering Coefficient algorithm is to measure how tightly a group is clustered compared to how tightly it could be clustered. The algorithm uses Triangle Count in its calculations, which provides a ratio of existing triangles to possible relationships. A maximum value of 1 indicates a clique, where every node is connected to every other node.

The Local Clustering Coefficient describes how many of the node’s neighbors are also connected. In the left example, the probability of node U neighbors being connected is 20%. Node U has five neighbors. If all the neighbors were connected to each other, that would be ten relationships between neighbors. Because there are only two relationships between neighbors, the Local Clustering Coefficient is 0.2.