This repository has been archived by the owner. It is now read-only.
Optimized implementation of the Louvain Method
C++ Makefile
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.gitignore
LICENSE
Makefile
README.md
louvain.h
sample.cpp

README.md

The Louvain method for community detection in large networks

Implementation of Louvain method in C++.

How to

Copy louvain.h to your project.

Here is the sample code:

// sample.
// This program creates the dummy friendship graph
// and then, clustering by this library.

#include "louvain.h"
#include <vector>
#include <iostream>

// Data structure that stick to each node.
struct Person {
	int id;
};

struct Merger {
	// It is called when the algorithm merge the nodes into the cluster.
	Person operator()(std::vector<louvain::Node<Person> > const& nodes, std::vector<int> idxs) const{
		// Select the most popular person
		louvain::Node<Person> const* most_popular = &nodes[idxs.front()];
		for(int idx : idxs){
			auto next = &nodes[idx];
			if(most_popular->degree() < next->degree()){
				most_popular = &*next;
			}
		}
		return Person{most_popular->payload().id};
	}
};

int main(int argc, char** argv){
	std::mt19937 mt((std::random_device()()));
	// make 100 persons
	std::vector<louvain::Node<Person>> persons(100);
	int totalLinks = 0;
	// connect the friends
	for(int i=0;i<100;++i){
		persons[i].payload().id = i+1;
		int from = mt() % persons.size();
		int to = mt() % persons.size();
		int weight = mt() % 100;
		if(from == to){
			persons[from].selfLoops(persons[from].selfLoops()+weight);
		}else{
			persons[from].neighbors().push_back(std::pair<int,int>(to,weight));
		}
		totalLinks += weight;
	}
	// clustering hierarchically
	louvain::Graph<Person, Merger> graph(totalLinks, std::move(persons));
	for(int i=0;i<10;++i){
		const size_t nedges = graph.edges();
		const size_t nnodes = graph.nodes().size();
		std::cout << "[Iter "<< i <<"] Edges: " << nedges << " / Nodes: " << nnodes << std::endl;
		size_t n = 0;
		for(auto node : graph.nodes()){
			std::cout << "  Cluster@"<< n << " / Leader: " << node.payload().id<<"" << std::endl;
			++n;
		}
		graph = graph.nextLevel();
		// exit if it converged
		if( graph.edges() == nedges && graph.nodes().size() == nnodes ) {
			break;
		}
	}
	std::cout << "Done" << std::endl;
	return 0;
}

Reference

Fast unfolding of communities in large networks,
Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre,
Journal of Statistical Mechanics: Theory and Experiment 2008 (10), P10008 (12pp)
doi: 10.1088/1742-5468/2008/10/P10008. ArXiv: http://arxiv.org/abs/0803.0476