jLouvain.js

/* 
 Author: Corneliu S. (github.com/upphiminn)

 This is a javascript implementation of the Louvain
 community detection algorithm (http://arxiv.org/abs/0803.0476)
 Based on https://bitbucket.org/taynaud/python-louvain/overview

 */
(function () {
	jLouvain = function () {
		//Constants
		var __PASS_MAX = -1;
		var __MIN = 0.0000001;

		//Local vars
		var original_graph_nodes;
		var original_graph_edges;
		var original_graph = {};
		var partition_init;

		//Helpers
		function make_set(array) {
			var set = {};
			array.forEach(function (d, i) {
				set[d] = true;
			});

			return Object.keys(set);
		}

		function obj_values(obj) {
			var vals = [];
			for (var key in obj) {
				if (obj.hasOwnProperty(key)) {
					vals.push(obj[key]);
				}
			}

			return vals;
		}

		function get_degree_for_node(graph, node) {
			var neighbours = graph._assoc_mat[node] ? Object.keys(graph._assoc_mat[node]) : [];
			var weight = 0;
			neighbours.forEach(function (neighbour, i) {
				var value = graph._assoc_mat[node][neighbour] || 1;
				if (node === neighbour) {
					value *= 2;
				}
				weight += value;
			});

			return weight;
		}

		function get_neighbours_of_node(graph, node) {
			if (typeof graph._assoc_mat[node] === 'undefined') {
				return [];
			}

			var neighbours = Object.keys(graph._assoc_mat[node]);

			return neighbours;
		}


		function get_edge_weight(graph, node1, node2) {
			return graph._assoc_mat[node1] ? graph._assoc_mat[node1][node2] : undefined;
		}

		function get_graph_size(graph) {
			var size = 0;
			graph.edges.forEach(function (edge) {
				size += edge.weight;
			});

			return size;
		}

		function add_edge_to_graph(graph, edge) {
			update_assoc_mat(graph, edge);

			var edge_index = graph.edges.map(function (d) {
				return d.source + '_' + d.target;
			}).indexOf(edge.source + '_' + edge.target);

			if (edge_index !== -1) {
				graph.edges[edge_index].weight = edge.weight;
			} else {
				graph.edges.push(edge);
			}
		}

		function make_assoc_mat(edge_list) {
			var mat = {};
			edge_list.forEach(function (edge, i) {
				mat[edge.source] = mat[edge.source] || {};
				mat[edge.source][edge.target] = edge.weight;
				mat[edge.target] = mat[edge.target] || {};
				mat[edge.target][edge.source] = edge.weight;
			});

			return mat;
		}

		function update_assoc_mat(graph, edge) {
			graph._assoc_mat[edge.source] = graph._assoc_mat[edge.source] || {};
			graph._assoc_mat[edge.source][edge.target] = edge.weight;
			graph._assoc_mat[edge.target] = graph._assoc_mat[edge.target] || {};
			graph._assoc_mat[edge.target][edge.source] = edge.weight;
		}

		function clone(obj) {
			if (obj === null || typeof(obj) !== 'object')
				return obj;

			var temp = obj.constructor();

			for (var key in obj) {
				temp[key] = clone(obj[key]);
			}

			return temp;
		}

		//Core-Algorithm Related 
		function init_status(graph, status, part) {
			status['nodes_to_com'] = {};
			status['total_weight'] = 0;
			status['internals'] = {};
			status['degrees'] = {};
			status['gdegrees'] = {};
			status['loops'] = {};
			status['total_weight'] = get_graph_size(graph);

			if (typeof part === 'undefined') {
				graph.nodes.forEach(function (node, i) {
					status.nodes_to_com[node] = i;
					var deg = get_degree_for_node(graph, node);

					if (deg < 0)
						throw 'Bad graph type, use positive weights!';

					status.degrees[i] = deg;
					status.gdegrees[node] = deg;
					status.loops[node] = get_edge_weight(graph, node, node) || 0;
					status.internals[i] = status.loops[node];
				});
			} else {
				graph.nodes.forEach(function (node, i) {
					var com = part[node];
					status.nodes_to_com[node] = com;
					var deg = get_degree_for_node(graph, node);
					status.degrees[com] = (status.degrees[com] || 0) + deg;
					status.gdegrees[node] = deg;
					var inc = 0.0;

					var neighbours = get_neighbours_of_node(graph, node);
					neighbours.forEach(function (neighbour, i) {
						var weight = graph._assoc_mat[node][neighbour];

						if (weight <= 0) {
							throw "Bad graph type, use positive weights";
						}

						if (part[neighbour] === com) {
							if (neighbour === node) {
								inc += weight;
							} else {
								inc += weight / 2.0;
							}
						}
					});
					status.internals[com] = (status.internals[com] || 0) + inc;
				});
			}
		}

		function __modularity(status) {
			var links = status.total_weight;
			var result = 0.0;
			var communities = make_set(obj_values(status.nodes_to_com));

			communities.forEach(function (com, i) {
				var in_degree = status.internals[com] || 0;
				var degree = status.degrees[com] || 0;
				if (links > 0) {
					result = result + in_degree / links - Math.pow((degree / (2.0 * links)), 2);
				}
			});

			return result;
		}

		function __neighcom(node, graph, status) {
			// compute the communities in the neighb. of the node, with the graph given by
			// node_to_com
			var weights = {};
			var neighboorhood = get_neighbours_of_node(graph, node);//make iterable;

			neighboorhood.forEach(function (neighbour, i) {
				if (neighbour !== node) {
					var weight = graph._assoc_mat[node][neighbour] || 1;
					var neighbourcom = status.nodes_to_com[neighbour];
					weights[neighbourcom] = (weights[neighbourcom] || 0) + weight;
				}
			});

			return weights;
		}

		function __insert(node, com, weight, status) {
			//insert node into com and modify status
			status.nodes_to_com[node] = +com;
			status.degrees[com] = (status.degrees[com] || 0) + (status.gdegrees[node] || 0);
			status.internals[com] = (status.internals[com] || 0) + weight + (status.loops[node] || 0);
		}

		function __remove(node, com, weight, status) {
			//remove node from com and modify status
			status.degrees[com] = ((status.degrees[com] || 0) - (status.gdegrees[node] || 0));
			status.internals[com] = ((status.internals[com] || 0) - weight - (status.loops[node] || 0));
			status.nodes_to_com[node] = -1;
		}

		function __renumber(dict) {
			var count = 0;
			var ret = clone(dict); //deep copy :) 
			var new_values = {};
			var dict_keys = Object.keys(dict);
			dict_keys.forEach(function (key) {
				var value = dict[key];
				var new_value = typeof new_values[value] === 'undefined' ? -1 : new_values[value];
				if (new_value === -1) {
					new_values[value] = count;
					new_value = count;
					count = count + 1;
				}
				ret[key] = new_value;
			});

			return ret;
		}

		function __one_level(graph, status) {
			//Compute one level of the Communities Dendogram.
			var modif = true;
			var nb_pass_done = 0;
			var cur_mod = __modularity(status);
			var new_mod = cur_mod;

			while (modif && nb_pass_done !== __PASS_MAX) {
				cur_mod = new_mod;
				modif = false;
				nb_pass_done += 1

				graph.nodes.forEach(function (node, i) {
					var com_node = status.nodes_to_com[node];
					var degc_totw = (status.gdegrees[node] || 0) / (status.total_weight * 2.0);
					var neigh_communities = __neighcom(node, graph, status);
					__remove(node, com_node, (neigh_communities[com_node] || 0.0), status);
					var best_com = com_node;
					var best_increase = 0;
					var neigh_communities_entries = Object.keys(neigh_communities);//make iterable;

					neigh_communities_entries.forEach(function (com, i) {
						var incr = neigh_communities[com] - (status.degrees[com] || 0.0) * degc_totw;
						if (incr > best_increase) {
							best_increase = incr;
							best_com = com;
						}
					});

					__insert(node, best_com, neigh_communities[best_com] || 0, status);

					if (best_com !== com_node) {
						modif = true;
					}
				});
				new_mod = __modularity(status);
				if (new_mod - cur_mod < __MIN) {
					break;
				}
			}
		}

		function induced_graph(partition, graph) {
			var ret = {nodes: [], edges: [], _assoc_mat: {}};
			var w_prec, weight;
			//add nodes from partition values
			var partition_values = obj_values(partition);
			ret.nodes = ret.nodes.concat(make_set(partition_values)); //make set
			graph.edges.forEach(function (edge, i) {
				weight = edge.weight || 1;
				var com1 = partition[edge.source];
				var com2 = partition[edge.target];
				w_prec = (get_edge_weight(ret, com1, com2) || 0);
				var new_weight = (w_prec + weight);
				add_edge_to_graph(ret, {'source': com1, 'target': com2, 'weight': new_weight});
			});

			return ret;
		}

		function partition_at_level(dendogram, level) {
			var partition = clone(dendogram[0]);
			for (var i = 1; i < level + 1; i++) {
				Object.keys(partition).forEach(function (key, j) {
					var node = key;
					var com = partition[key];
					partition[node] = dendogram[i][com];
				});
			}

			return partition;
		}


		function generate_dendogram(graph, part_init) {
			if (graph.edges.length === 0) {
				var part = {};
				graph.nodes.forEach(function (node, i) {
					part[node] = node;
				});
				return part;
			}
			var status = {};

			init_status(original_graph, status, part_init);
			var mod = __modularity(status);
			var status_list = [];
			__one_level(original_graph, status);
			var new_mod = __modularity(status);
			var partition = __renumber(status.nodes_to_com);
			status_list.push(partition);
			mod = new_mod;
			var current_graph = induced_graph(partition, original_graph);
			init_status(current_graph, status);

			while (true) {
				__one_level(current_graph, status);
				new_mod = __modularity(status);
				if (new_mod - mod < __MIN) {
					break;
				}

				partition = __renumber(status.nodes_to_com);
				status_list.push(partition);

				mod = new_mod;
				current_graph = induced_graph(partition, current_graph);
				init_status(current_graph, status);
			}

			return status_list;
		}

		var core = function () {
			var status = {};
			var dendogram = generate_dendogram(original_graph, partition_init);

			return partition_at_level(dendogram, dendogram.length - 1);
		};

		core.nodes = function (nds) {
			if (arguments.length > 0) {
				original_graph_nodes = nds;
			}

			return core;
		};

		core.edges = function (edgs) {
			if (typeof original_graph_nodes === 'undefined')
				throw 'Please provide the graph nodes first!';

			if (arguments.length > 0) {
				original_graph_edges = edgs;
				var assoc_mat = make_assoc_mat(edgs);
				original_graph = {
					'nodes': original_graph_nodes,
					'edges': original_graph_edges,
					'_assoc_mat': assoc_mat
				};
			}

			return core;

		};

		core.partition_init = function (prttn) {
			if (arguments.length > 0) {
				partition_init = prttn;
			}
			return core;
		};

		return core;
	}
})();