This page implements the Poisson community algorithm of Ball, Karrer and Newman (2011). The visualization is based on Mike Bostock's d3.js force-directed map demo. Reload the page to start with a new random initialization.

Here's the community detection code. View source for context.

  graph.nodes.forEach( function(node) {
    node.communities = [];
    node.communityBuffer = [];
    for (var community = 0; community < numCommunities; community++) {
      // Initialize with a small Exponential variate
      node.communities[community] = 0.01 * -Math.log(Math.random());
      node.communityBuffer[community] = 0.0;
    }
  });

  var communitySums = [];

  for (var iteration = 0; iteration < 20; iteration++) {
    for (var community = 0; community < numCommunities; community++) {
      communitySums[community] = 0.0;
    } 

    // Estimate community memberships for each edge
    graph.links.forEach( function(edge) {
      var sourceCommunities = graph.nodes[ edge.source ].communities;
      var targetCommunities = graph.nodes[ edge.target ].communities;
      var distribution = [];

      // Multiply the two community membership vectors
      for (var community = 0; community < numCommunities; community++) {
        distribution[community] = sourceCommunities[community] * targetCommunities[community];
      }

      // Normalize and add to the gradient
      var normalizer = edge.value / d3.sum(distribution);
      for (var community = 0; community < numCommunities; community++) {
        distribution[community] *= normalizer;
        communitySums[community] += distribution[community];
        graph.nodes[ edge.source ].communityBuffer[community] += distribution[community];
        graph.nodes[ edge.target ].communityBuffer[community] += distribution[community];
      }
    });

    // We need to divide each node value by the square root of the community sum.
    var communityNormalizers = []
    for (var community = 0; community < numCommunities; community++) {
      communityNormalizers[community] = 1.0 / Math.sqrt(communitySums[community]);
    }

    // Update parameters and clear the buffer.
    graph.nodes.forEach( function(node) {
      for (var community = 0; community < numCommunities; community++) {
        node.communities[community] = node.communityBuffer[community] * communityNormalizers[community];
        node.communityBuffer[community] = 0.0;
      }
    });
  }