Tag Archives: communities

Papers

Détection de communautés à long terme dans les graphes dynamiques

Thomas Aynaud and Jean-Loup Guillaume

La plupart des graphes de terrain peuvent être décomposés en sous graphes denses appelés communautés. Habituellement, dans des graphes dynamiques, les communautés sont détectées pour chaque instant indépendamment ce qui pose de nombreux problèmes tels que la stabilité ou le suivi de des communautés entre deux décompositions successives. Nous proposons ici une méthode pour trouver une partition unique, de qualité, couvrant une longue période. Cette décomposition peut être trouvée efficacement via une adaptation de la méthode de Louvain et la perte de qualité à chaque instant due à la contrainte de détecter des communautés globales s’avère assez faible.

Thomas Aynaud and Jean-Loup Guillaume

Posted in Papers | Also tagged |
Papers

Static community detection algorithms for evolving networks

Thomas Aynaud and Jean-Loup Guillaume

Complex networks can often be divided in dense sub-networks called communities. We study, using a partition edit distance, how three community detection algorithms transform their outputs if the input network is sligthly modified. The instabilities appear to be important and we propose a modification of one algorithm to stabilize it and to allow the tracking of the communities in a dynamic network. This modification has one parameter which is a tradeoff between stability and quality. The resulting algorithm appears to be very effective. We finally use it on a dynamic network of blogs.

Thomas Aynaud and Jean-Loup Guillaume

Posted in Papers | Also tagged |
Papers

Structure multi-échelle de grands graphes de terrain

Thomas Aynaud and Jean-Loup Guillaume

Most complex networks can be divided into dense sub-graphs called communities. These communities may also be divided recursively producing a hierarchical structure of communities, summarized in a tree named dendrogram. In this article we analyze this structure extracted from several complex networks. First we study the shape of the tree and, in particular, communities imbrications. Then we show that an excessive decomposition of communities can result in meaningless communities. We propose a couple of approaches to solve this problem.

Thomas Aynaud and Jean-Loup Guillaume

Posted in Papers | Tagged |
Papers

Interactive multiscale visualization of huge graphs: application to a network of weblogs

Massoud Seifi, Jean-loup Guillaume, Matthieu Latapy and Bénédicte Le Grand

De nombreux réseaux du monde réel peuvent être modélisés par des grands graphes. Réduire la complexité d'un graphe de manière à ce qu'il puisse être facilement interprété par l'oeil humain est une aide précieuse pour comprendre et analyser ce type de données. Nous proposons une méthodologie de visualisation interactive multi-échelle de grands graphes basée sur une classification des sommets qui nous permet de représenter ces graphes de manière lisible et interprétable. Nous appliquons notre méthodologie à un réseau de blogs francophones.

Massoud Seifi, Jean-loup Guillaume, Matthieu Latapy and Bénédicte Le Grand

Posted in Papers | Also tagged , |
Plots

Dynamics and stability of communities

Dynamics and stability of communities

> By Thomas Aynaud and Jean-Loup Guillaume To study the communities dynamics and stability, we have taken a network representing the co-authorship of scientists on www.arxiv.org and we have successively removed one random node and kept the biggest connected component. At each step, we have detected the communities in two ways. We have, first, used […]

Posted in Plots | Also tagged |
Plots

Stability of community detection

Stability of community detection

> By Jean-Loup Guillaume Many community detection algorithms are non deterministic and can therefore give different partitions for the same graph. Depending on the context, it can be important to obtain stable results so as to identify very pertinent communities, but it can also be interesting to find some less stable ones. For non deterministic […]

Posted in Plots | 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

Post-Processing Hierarchical Community Structures

Post-Processing Hierarchical Community Structures

> By Pascal Pons and Matthieu Latapy

Posted in Plots | Tagged |
Plots

Multi-scale visualization of a collaboration dataset

Multi-scale visualization of a collaboration dataset

> By Massoud Seifi, Jean-Loup Guillaume and Matthieu Latapy Many real-world networks can be represented as large graphs. Computational manipulation of such large graphs is common, but current tools for graph visualization are limited to datasets of a few thousand nodes. These graphs contain sets of highly connected nodes that we call “communities”. Furthermore, these […]

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 |