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:
-
Optimize modularity for small local communities.
-
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.
-
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.
-
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)Parameters
| Name | Description | Data type |
|---|---|---|
|
Names of vertex types to use |
|
|
Names of edge types to use |
|
|
Name of edge weight attribute (must be type |
|
|
Maximum number of iterations |
|
|
If not empty, store community id values ( |
|
|
If not empty, write output to this file. |
|
|
If true, print results to JSON output. |
|
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
RUN QUERY tg_louvain(["Person"], ["Coworker","Friend"], "weight", _, _, _, TRUE)
{
"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. |