ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 30/4 - 2016  - pp.393-418  - doi:10.3166/ria.25.393-418
TITRE
Un nouvel algorithme de propagation de labels avec barrages

TITLE
A new label progagation with dams

RÉSUMÉ
La propagation de labels est l’une des méthodes les plus rapides pour la détection de communautés, de complexité quasi-linéaire en termes d’arêtes. Il s’agit d’une méthode locale où chaque nœud possède son propre label qui change par interaction avec son voisinage. Malheureusement, cette méthode présente deux inconvénients majeurs. Le premier est qu’une mauvaise propagation peut mener à de trop grandes communautés (le problème des communautés géantes). Le second inconvénient est l’instabilité de la méthode, ne donnant que très rarement le même résultat après chaque lancement. Dans cet article, nous proposons des algorithmes et une étude portant sur la propagation de labels en plaçant des barrages sur certaines arêtes dans le but d’éviter de mauvaises propagations. Puis nous appliquons une méthode de détection de cœurs basée sur l’alimentation d’une matrice de fréquence de coapparition dans le but de stabiliser la propagation de labels.


ABSTRACT
Label propagation is one of the fastest methods for community detection, with a near linear time complexity. It’s a local method, where each node has its own label which changes by interaction with its neighbourhood. Unfortunately, this method has two major drawbacks. The first is a bad propagation which can lead to huge communities without sense (giant communities problem). The second is the instability of the method. Each trial of a label propagation algorithm gives rarely the same result. In this paper, we propose algorithms and a study on the label propagation by putting artificial dams on edges in order to avoid bad propagations. We then apply an ensemble learning clustering method based on a frequency matrix in order to stabilize the algorithm.


AUTEUR(S)
Maria MALEK, Jean-Philippe ATTAL

MOTS-CLÉS
détection de communautés, propagation de labels, barrages, ensemble learning, détection de cœurs.

KEYWORDS
community detection, label propagation, dams, ensemble learning, core detection.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (1,63 Mo)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier