/* 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 */ exports._jLouvain = (function(){ return 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){ return Object.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 = get_neighbours_of_node(graph, 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 []; return Object.keys(graph._assoc_mat[node]); } 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, nb_pass_done = 0, cur_mod = __modularity(status), 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; } else { return original_graph_nodes; } }; 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; } else { return original_graph_edges; } }; core.partition_init = function(prttn){ if(arguments.length > 0){ partition_init = prttn; } return core; }; return core; } })(); exports._init = function(louvain, nodes, edges) { return Object.entries(louvain.nodes(nodes).edges(edges)()); }