Louvain method for community detection

Louvain method for community detection

#r "FSharp.FGL"
#r "FSharp.FGL.ArrayAdjacencyGraph"

open FSharp.FGL
open FSharp.FGL.ArrayAdjacencyGraph
open ArrayAdjacencyGraph.Algorithms

The louvain method for communty detection is a easy method to extract the community structure of large networks. It is based on the concept of modularity optimization. The algorithm is divided into two phases that are repeated iteratively:

• Modularity optimization, in which every vertex is assigned its own community. After that, for each vertex its neighbours are used to calculate the gain of modularity by removing the vertex from its community and placing it in the community of a neighbour. The new commnuity for the vertex is the one with the biggest modularity gain. This is repeated until no furhter changes that increase the overall modularity can be done.
• Community aggregation, in which the communities found are aggregated in order to build a new, reduced network of communities.

These steps are repeated until no further increase of modularity is possible.

Example

Example Graph

The first step of the tutorial is the creation of a graph that Louvain can analyse. In this case the graph was taken from wikipedia.

//Creating a list of labeled vertices
let vertexList : LVertex<int,string> list =
    [
        for i=0 to 13 do
            (i),(sprintf "%i"i)
    ]

//Creating a list of labeled edges
let edgeList : LEdge<int,float> list =
    [
        0,1,1.; 0,2,1.; 1,2,1.; 1,3,1.;2,3,1.; 3,4,1.; 3,13,1.; 4,5,1.; 4,8,1.; 
        5,6,1.; 5,8,1.; 5,7,1.; 6,7,1.; 7,8,1.; 7,10,1.; 8,9,1.; 9,10,1.; 
        9,12,1.; 9,13,1.; 10,11,1.; 10,13,1.; 11,12,1.; 11,13,1.; 12,13,1.
    ]

//Creating a graph out of the two lists 
let myGraph :ArrayAdjacencyGraph<int,string,float> =
    ArrayAdjacencyGraph(vertexList,edgeList)

Louvain algorithm

The application of the louvain algorithm on the example graph would look like this:

//Returns the graph with the louvain calculation on top of it
let myGraphLouvain : ArrayAdjacencyGraph<int,string*int,float> =
    Louvain.Louvain.louvain myGraph 0.00001

Visualization

The visualization of the graph is made possible by means of Cyjs.NET and looks like this. The different colors each represent their own community.

No value returned by any evaluator