Réinitialiser mot de passe
E-mail
Password
RNTI

MODULAD
Finding Overlapping Communities in Networks Using Propositional Satisfiability
In EDA 2017, vol. RNTI-B-13, pp.67-80
Résumé
La détection de communautés est devenue un problème fondamental permettant la com-
préhension de la structure des réseaux complexes tels que les réseaux sociaux, biologiques ou
encore les réseaux d'informations. Dans cet article, nous proposons une approche pour dé-
tecter les communautés chevauchantes dans les grands réseaux complexes. Nous introduisons
d'abord une nouvelle notion de communauté paramétrée dite communauté k-liée. Cela nous
permettrait de caractériser les communautés k-liées centrées noeud/arête de diamètre borné.
Une telle communauté admet un noeud ou une arête avec une distance au plus k
2 des autres
noeuds de la même communauté. Ensuite, nous montrons comment le problème de détec-
tion de communautés chevauchantes k-liées centrées noeud/arête peut être exprimé sous forme
d'un problème d'optimisation Max-SAT partiel. Puis, nous proposons une stratégie de post-
traitement pour réduire le chevauchement entre les communautés. Finalement, une évaluation
expérimentale extensive sur des réseaux réels montrent que notre approche améliore significa-
tivement plusieurs algorithmes de l'état de l'art de détection de communautés.