jLouvain

// Corneliu S.

Description

Formally, a community detection aims to partition a graph’s vertices in subsets, such that there are many edges connecting between vertices of the same sub-set compared to vertices of different sub-sets; in essence, a community has many more ties between each constituent part than with outsiders. There are numerous algorithms present in the literature for solving this problem, a complete survey can be found in [1].

One of the popular community detection algorithms is presented in [2]. This algorithm separates the network in communities by optimizing greedily a modularity score after trying various grouping operations on the network. By using this simple greedy approach the algorithm is computationally very efficient.

[1] Fortunato, Santo. "Community detection in graphs." Physics Reports 486, no. 3-5 (2010).

[2] V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre. "Fast unfolding of communities in large networks." J. Stat. Mech., 2008: 1008.

Usage

Import the script.

 <script type="text/javascript" src="jLouvain.js"></script>

Sample Data Format

Node Data

var node_data = ['id1', 'id2', 'id3']; // any type of string can be used as id

Edge Data

var edge_data = [
	{source: 'id1', target:'id2', weight: 10.0},
	{source: 'id2', target:'id3', weight: 20.0}, 
	{source: 'id3', target:'id1', weight: 30.0}
];

(Optional) Partition Data

	var init_part = {'id1':0, 'id2':0, 'id3': 1}; 
	// Object with ids of nodes as properties and community number assigned as value.

Run the Algorithm on your node and edge set by chaining the nodes and edges methods, optionally you can provide an intermediary community partition assignement with the partition_init method. [ Order of chaining is important ]

	var community = jLouvain().nodes(node_data).edges(edge_data).partition_init(init_part);
    	var result  = community();
	
	// Exposes the nodes and the communities they belong to 
	var communities = result['communities']; 
	
	// Exposes the last measure of modularity of the graph
	// If it is close to 0.0 most of the nodes belong to the same community
	// If it is about 0.4 and above the graph has a highly pronounced community structure
	// Can be used to quickly estimate how diversified the graph is
	var graph_modularity = result['modularity'];

Example

See example.html, use the console to view the raw input data and raw output.

Initial input graph for community detection.

After Community Detection

We can see the partitioned graph vertices with the help of color coding.

noduslabs/jLouvain