Tag Archives: modularity

Papers

Optimisation locale multi-niveaux de la modularité

Thomas Aynaud, Vincent Blondel, Jean-Loup Guillaume and Renaud Lambiotte

Dans ce chapitre, nous présentons une méthode gloutonne pour optimiser la modularité d'un graphe. Cette méthode de partionnement permet de traiter avec une excellente précision des systèmes de taille inégalée, allant jusqu'à plusieurs milliards de liens. Notre algorithme a de surcroît l'avantage de ne pas être limité à l'optimisation de la modularité puisqu'il peut être généralisé à d'autres fonctions de qualité, et de découvrir des communautés à différentes échelles. Les performances de l'algorithme sont évaluées sur des graphes artificiels pour lesquels la structure communautaire est connue, ainsi que sur des graphes de terrain réels.

Posted in Papers | Also tagged , |
Papers

Long range community detection

Thomas Aynaud and Jean-Loup Guillaume

Complex networks can usually be divided in dense subnetworks called communities. In evolving networks, the usual way to detect communities is to find several partitions independently, one for each time step. However, this generally causes troubles when trying to track communities from one time step to the next. We propose here a new method to detect only one decomposition in communities that is good for (almost) every time step. We show that this unique partition can be computed with a modification of the Louvain method and that the loss of quality at each time step is generally low despite the constraint of global maximization. We also show that some specific modifications of the networks topology can be identified using this unique partition in the case of the Internet topology.

Posted in Papers | Also tagged , , , |
Plots

Maximizing modularity: time VS. quality

Maximizing modularity: time VS. quality

> By Jean-Loup Guillaume Community detection in complex networks is a hard problem whose classical formulation is the maximisation of the modularity. Since this problem cannot be solved exactly in a reasonable time, heuristics are used to find the best communities. The Louvain method is an efficient technique to study this problem and consists in […]

Posted in Plots | Also tagged |
Plots

Maximizing the modularity: what is left behind

Maximizing the modularity: what is left behind

> By Thomas Aynaud and Jean-Loup Guillaume The modularity is widely used to evaluate the quality of a partition of a graph in communities. Each community contributes to the global modularity according to the formula below, where m is the number of links of the graph, e is the number of links inside a given […]

Posted in Plots | Also tagged |