Louvain

Algorithm link: Louvain

The Louvain Method for community detection [1] partitions the vertices in a graph by approximately maximizing the graph’s modularity score. The modularity score for a partitioned graph assesses the difference in density of links within a partition vs. the density of links crossing from one partition to another. If a partitioning is good, then the within-density should be high and the inter-density should be low.

The most efficient and empirically effective method for calculating modularity was published by a team of researchers at the University of Louvain. The Louvain method uses agglomeration and hierarchical optimization:

  1. Optimize modularity for small local communities.

  2. Treat each optimized local group as one unit, and repeat the modularity operation for groups of these condensed units.

The Louvain Method contains two phases.

  1. The first phase incrementally calculates the modularity change of moving a vertex into every other community and moves the vertex to the community with the highest modularity change.

  2. The second phase coarsens the graph by aggregating the vertices which are assigned in the same community into one vertex.

The first phase and second phase make up a pass. The Louvain Method performs the passes iteratively. In other words, the algorithm assigns an initial community label to every vertex, then performs the first phase, during which the community labels are changed until there is no modularity gain. Then it aggregates the vertices with the same labels into one vertex and calculates the aggregated edge weights between new vertices. For the coarsened graph, the algorithm conducts the first phase again to move the vertices into new communities. The algorithm continues until the modularity is not increasing, or runs to the preset iteration limits.

However, phase one is sequential, and thus slow for large graphs. An improved Parallel Louvain Method (PLM) calculates the best community to move to for each vertex in parallel[2]. In Parallel Louvain Method(PLM), the positive modularity gain is not guaranteed, and it may also swap two vertices to each other’s community.

Specifications

CREATE QUERY tg_louvain(SET<STRING> v_type, SET<STRING> e_type,
    STRING wt_attr = "weight", INT max_iter = 10,
    STRING result_attr = "cid", STRING file_path = "",
    BOOL print_info = FALSE)

Time complexity

This algorithm has a time complexity of \(O(V^2*L)\), where \(V\) is the number of vertices and \(L\) is the total number of iterations.

Graph type

Runs on graph with undirected, weighted edges

An edge weight attribute is required.

Parameters

Name Description Data type

v_type

Names of vertex types to use

STRING

e_type

Names of edge types to use

STRING

wt_attr

Name of edge weight attribute (must be type FLOAT)

STRING

max_iter

Maximum number of iterations

INT

result_attr

If not empty, store community id values (INT) to this attribute

STRING

file_path

If not empty, write output to this file.

STRING

print_info

If true, print results to JSON output.

BOOL

Result

If result_attr is provided, the algorithm assigns a component ID (INT) to each vertex, such that members of the same component have the same ID value.

if print_info is set to true or file_path is provided, the JSON or .csv output contains the following information:

  • The number of vertices and communities in the graph.

  • The heuristic statistics used by Louvain.

Example

You can run the algorithm on the social10 graph by slightly modifying the schema. Since the algorithm requires weighted edges, we can add an attribute to all edges and set edge weight to 1.

By running the algorithm on social10, we can see that the vertices that are in the same community have more intra-community edges than inter-community edges.

  • Run command

  • Visualized result

  • JSON result

RUN QUERY tg_louvain(["Person"], ["Coworker","Friend"], "weight", _, _, _, TRUE)
louvain eample
{
  "error": false,
  "message": "",
  "version": {
    "schema": 1,
    "edition": "enterprise",
    "api": "v2"
  },
  "results": [
    {"AllVertexCount": 10},
    {"InitChangeCount": 7},
    {"IterChangeCount": 0},
    {"VertexFollowedToCommunity": 0}, (1)
    {"VertexFollowedToVertex": 0}, (2)
    {"VertexAssignedToItself": 0},
    {"FinalCommunityCount": 4}
  ]
}
1 Number of vertices followed to community assigned by Louvain.
2 Num of vertex followed to its only neighbor. For example, if we have (A)---(B), A and B will become a community with only vertex A and B.

1. Blondel, Vincent D., et al. "Fast unfolding of communities in large networks." Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.
2. Staudt, Christian L., and Henning Meyerhenke. "Engineering parallel algorithms for community detection in massive networks." IEEE Transactions on Parallel and Distributed Systems 27.1 (2016): 171-184.