Skip to content

Instantly share code, notes, and snippets.

@sheymann
Forked from rjbriody/sigma.plugins.community.js
Last active August 29, 2015 14:15
Show Gist options
  • Save sheymann/f38adba92ac8ac0681ab to your computer and use it in GitHub Desktop.
Save sheymann/f38adba92ac8ac0681ab to your computer and use it in GitHub Desktop.
var 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,
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;
};
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;
};
(function () {
'use strict';
if (typeof sigma === 'undefined')
throw 'sigma is not declared';
sigma.utils.pkg('sigma.plugins');
sigma.plugins.community = function (g) {
var node_ids = [];
for (var ii = 0; ii < g.nodes.length; ii++) {
node_ids.push(g.nodes[ii].id);
}
var communities = jLouvain().nodes(node_ids).edges(g.edges)()
for (var ii = 0; ii < g.nodes.length; ii++) {
var node = g.nodes[ii];
node._community = communities[node.id];
}
// console.log(JSON.stringify(g.nodes));
}
}).call(window);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment