Overview

Louvain algorithm is a community detection algorithm based on modularity calculations, which is an iterative process of nodes aggregation with the goal of maximizing the modularity. Proposed in 2008 by Vincent D.Blondel et al. of Université catholique de Louvain in Belgium, this algorithm has become the most mentioned and used community detection algorithm in recent years because of its high efficiency and satisfying outcomes.

Related materials of the algorithm:

• V.D. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks (2008)
• H. Lu, Parallel Heuristics for Scalable Community Detection (2014)

Basic Concept

Weighted Degree

Weighted degree is the degree that takes the weight of edge into consideration. Louvain algorithm uses the concepts of weighted degree of node and weighted degree of community when calculating modularity.

• Weighted degree of node refers to the sum of the weights of edges attached to the node, including adjacent edges (connect to other nodes) and self-loop edges (connect to the node itself).
• Weighted degree of community refers to the sum of weighted degrees of all nodes in a community.
• Weighted degree inside community refers to when calculating the weighted degree of a community, only to consider the edges whose both endpoints are in the community; or, weighted degree inside community can be obtained by deducting the weights of edges between the community and other communities from the weighted degree of community.
• Weighted degree of whole graph refers to the sum of weighted degrees of all nodes in the graph. If divides the whole graph into multiple communities, weighted degree of whole graph also equals to the sum of weighted degrees of those communities, since each node belongs to one and only one community.

Community Compression

Louvain algorithm uses a large amount of community compression to improve the subsequent (iteration) computing speed by minimizing the number of nodes and edges in the graph without changing the weighted degree of the local or the whole graph. After compression, nodes in the community will be calculated as a whole, but no longer separated, for modularity optimization, thus achieving a hierarchical (iterative) community division effect.

Community compression is to use one aggregated node to represent all nodes in a community, the weighted degree inside community is the weight of the self-loop edge of the aggregated node, and the sum of weights of edges between every two communities is the weight of the edge between the two corresponding aggregated nodes.

Modularity

Geometrically, modularity attempts to calculate the weighted degree to compare the closeness of nodes within and between communities.

Let 2m denote the weighted degree of the whole graph, if C is any community in the graph, Σ(tot) is the weighted degree of C, Σ(in) is the weighted degree inside C, then the modularity Q can be calculated by:

The value range of modularity is [-1, 1]; for connected graph (or connected subgraph), the value range of modularity is [-1/2, 1]. Modularity has been used to measure the quality of the community division, the higher the modularity, the more reasonable the community division.

When programming the algorithm, the modularity can be calculated using the following formula:

where 2m is the weighted degree of whole graph; i and j are any two nodes in the graph; δ is 1 when i and j belong to the same community, otherwise δ is 0.

Gain of Modularity

Gain of modularity refers to how much the modularity has increased by changing the community division. When adjusting the community of a node, Louvain algorithm decides whether to move the node by evaluating the gain of modularity. The threshold of the gain of modularity is a float number greater than 0, the modularity is regarded as not improved when ΔQ is under the threshold.

Modularity optimization is an NP-Hard problem. Louvain algorithm adopts the heuristic algorithm to optimize the modularity in multiple rounds of compound iterations. Each large cycle is divided into two phases:

• 1st phase: Iteration. At the beginning of this phrase, each node is considered as an independent community; in each round of iteration, calculate for each node whether there is a community of its neighbors, a maximum and positive ΔQ can be obtained by placing the node to that community (i.e. to maximize the modularity); if found, move the node to the new community; the same calculation and adjustment are applied sequentially to all nodes, then enter the next round of iteration. The first phase iteratively loops by this rule until no node can be reallocated, or the number of iterations reaches the limit.
• 2nd phase: Community compression. Compress the communities divided in the first phase to get a new graph. If the structure of the new compressed graph is consistent with the graph at the beginning of the current round of large cycle, that is, the modularity is not improved, then the algorithm ends, otherwise the new graph is used as the initial graph of the next round of large cycle.

Special Case

Lonely Node, Disconnected Graph

If lonely node exists in the graph, the lonely node must form a community of its own, it can not be combined with other nodes no matter how many rounds of cyclic iterations it undergoes. The reason is that lonely node has no adjacent edge, means that k(i,in) of lonely node to any other community or node is 0, the ΔQ that generated when it is moved to other community is negative.

For disconnected graph, there is no edge between different disconnected areas, nodes in different components cannot be combined, thus each disconnected area is an independent community, the community division by the Louvain algorithm is only meaningful inside the connected component.

Self-loop Edge

The way Louvain algorithm counts the weighted degree of self-loop edge is different from the Degree algorithm algo(degree). In Degree algorithm, each self-loop edge is counted twice, while each self-loop edge is counted only once in Louvain algorithm.

As shown in the graph above, the weighted degree of the red node in Degree algorithm is 1 + 0.5 + 3 + 1.5 * 2 = 7.5, the weighted degree of the red node in Louvain algorithm is 1 + 0.5 + 3 + 1.5 = 6.

Directed Edge

For directed edges, Louvain algorithm ignores the direction of edges but calculates them as undirected edges.

Results and Statistics

Run Louvain algorithm on the graph below, the weight of each edge is 1, the threshold of the gain of modularity is 0.01, and the maximum number of iterations of the 1st phase is 5:

Algorithm results 1: Return node and its community ID, i.e. _uuid, community

Algorithm results 2: Return community and its number of nodes, i.e. community_id, count

Algorithm statistics: The number pf communities community_count and modularity modularity

Command and Configuration

• Command: algo(louvain)
• Configurations for the parameter params():

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 3

algo(louvain).params({ 
  phase1_loop_num: 3, 
  min_modularity_increase: 0.1 
}) as com
return com

Algorithm Execution

Task Writeback

1. File Writeback

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 5, write the algorithm results back to files named communityID, ids and num

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1 
}).write({
  file:{
    filename_community_id: "communityID",
    filename_ids: "ids",
    filename_num: "num"
  }
})

2. Property Writeback

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 5, write the algorithm results back to node property named communityID

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1 
}).write({
  db:{
    property: "communityID"
  }
})

3. Statistics Writeback

Example: Run Louvain algorithm in the graph, use the default threshold of the gain of modularity as 0.01 and 5 iterations in the first phase, write the algorithm statistics back to task information

algo(louvain).params().write()

Direct Return

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 5, define algorithm results and statistics as aliases named results and stats, and return the results and statistics

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1 
}) as results, stats
return results, stats

Streaming Return

Configurations for the parameter stream():

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 5, define algorithm results (community and its number of nodes) as alias named results, and return the results ordered by the descending number of nodes in the community

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1,
  order: "desc"
}).stream({
  mode: 2
}) as results
return results

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 5, define algorithm results (node and its community ID) as alias named results, and return the results ordered by the ascending UUID of nodes

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1 
}).stream() as results
return results order by results._uuid

Real-time Statistics

Example: Run Louvain algorithm in the graph, set the threshold of the gain of modularity as 0.1, the number of iterations in the first phase as 5, define algorithm statistics as alias named stats, and return the statistics

algo(louvain).params({ 
  phase1_loop_num: 5, 
  min_modularity_increase: 0.1 
}).stats() as stats
return stats

Algorithm Efficiency

Louvain algorithm achieves lower time complexity than previous community detection algorithms through its improved greedy optimization, which is usually regarded as O(N*LogN), where N is the number of nodes in the graph, and the result is more intuitive. That is to say, in theory, in a graph with 10,000 nodes, the complexity of Louvain algorithm is O(40000); in a connected graph with 100 million nodes, the algorithm complexity is O(800000000). In fact, according to the above detailed breakdown of the algorithm process, we could see that the complexity of Louvain algorithm depends on both the number of nodes and the number of edges, roughly speaking, it should be O(N * E/N) = O(E), where E is the number of edges in the graph - because the dominant algorithm logic of Louvain is to calculate the weights of edges attached to each node.

The table below shows the performance comparison of Louvain algorithm and other community detection algorithms, it is given by the original author of Louvain algorithm in his paper. It can be seen that Louvain achieves some significant (exponential) increase in both modularity and efficiency:

The system architecture, data structure, programming language, etc. would cause huge difference in the final result and efficiency of Louvain algorithm, even though they are all implementations of Louvain algorithm. For example, the serial Louvain algorithm achieved by Python can cost hours in just 10,000 grade small graphs; besides, the difference in data structure also leads to significant performance gaps as the algorithm calculates the degree of nodes and the weight of edges frequently. The native Louvain algorithm adopts C++, but it is a serial implementation, so the time consumption can be reduced by using parallel computation as much as possible, thereby improving the efficiency of the algorithm.

For medium-sized graphset with tens of millions of nodes and edges, Ultipa's Louvain algorithm can be completed in real time literally; for large graphs with over 100 million nodes and edges, it can be implemented in seconds to minutes. In addition, operations such as whether to writeback to database property or to disk file also have impact on the time consumption of the entire algorithm. The table below demonstrates the modularity and execution time of Louvain algorithm running in a graphset with 5 million nodes and 100 million edges, note that the computation process costs ~1 minute, and operations to writeback to the database or generate disk file costs additional ~1 minute.

Consistency of Results

Affected by factors such as the order of nodes, the parallel computation, and the execution logic of the heuristic algorithm on local data, the community division results of Louvain algorithm may vary with each execution. But the overall trend will not change much (as indicated in the table above).