Proposition de sujet de stage dans l'équipe KID du laboratoire LGI2P à
Nîmes de l'Ecole des Mines d'Ales

EXTRACTION DE COMMUNAUTÉS RECOUVRANTES PAR COMPLÉMENTARITÉ ET ÉQUILIBRE
DE NASH DANS LES RÉSEAUX SOCIAUX

Encadrants : Michel Plantié

Laboratoire et équipe : LGI2P de l'EMA, équipe KID (Knowledge and Image
for Decision making)

Lieu : Nîmes, site EERIE, parc Georges Besse, 30000 Nîmes

Sujet

Les réseaux sociaux occupent une part de plus en plus importante dans
l'échange de données sur le web. La recommandation de produits et de
services, les modèles utilisateurs enrichis par des données sociales
peuvent revêtir une grande importance.

La recherche de communautés dans les graphes est un problème ancien, et
la grande majorité des techniques utilisées cherchent à optimiser les
temps de calcul de ces communautés et le meilleur arrangement possible
de ces communautés selon des critères de cohésion ou de modularité,
etc.[1][2][3][4]

La signification et la stabilité de ces communautés ainsi constituées
n'est que peu abordée dans les travaux actuels. Les auteurs appliquent
un algorithme unique d'optimisation et observent ensuite les
performances.

Le recouvrement revêtant des fondements sémantiques importants sont peu
étudiés. Plusieurs auteurs dont Roth [5] en construisant des communautés
épistémiques ont abordé le sujet. De même la stabilité et la répartition
équitable et équilibrée des personnes dans les communautés sont peu
étudiés. Nos travaux récents montrent la possibilité d'obtenir un
équilibre de Nash dans les constructions des communautés [6].

La complémentarité est une problématique intéressante pour montrer la
couverture sémantique de communautés.

Nous nous intéressons à ce champ de recherche qui pose de nombreuses
questions théoriques et pratiques.

Le sujet proposé a les objectifs suivants :

- Après un état de l'art, étudier et compléter les définitions de la
  complémentarité adaptée à la détection de communautés dans des grands
  volumes de données de graphes provenant des réseaux sociaux

- Etudier la stabilité et la complémentarité de communautés extraites à
  partir de données sociales

- rechercher les optimums de stabilité et d'équilibre tout en tenant
  compte de leur sémantique.

- Approfondir les travaux de recherche de complémentarité de communautés
  recouvrantes.

[1] Papadopoulos, Y. Kompatsiaris, A. Vakali, and P. Spyridonos,
"Community detection in Social Media," Data Mining and Knowledge
Discovery, no. June, pp. 1-40, 2011.

[2] M. F. Porter, "An algorithm for suffix stripping," Program, pp. pp
130-137, 1980.

[3] B. Yang, D. Liu, J. Liu, and B. Furht, Discovering communities from
Social Networks: Methodologies and Applications. Boston, MA: Springer
US, 2010, pp. 331-346.

[4] S. Fortunato, "Community detection in graphs," Physics Reports,
vol. 486, no. 3-5, p. 103, Jun. 2009.

[5] C. Roth and P. Bourgine, "Epistemic Communities: Description and
Hierarchic Categorization," Mathematical Population Studies: An
International Journal of Mathematical Demography, vol. 12, no. 2, pp.
107-130, 2005.

[6] Michel Crampes and Michel Plantié, "A Unified Community Detection,
Visualization and Analysis method. Advanced Complex Systems, World
Scientific Publishing, Imperial College Press, 2013.

[7] Michel Crampes and Michel Plantié, Organisation de communautés et
Equilibre de Nash, IC - 25èmes Journées francophones d'Ingénierie des
Connaissances, France (2014)

=====================================================
Dr. Michel Plantié - +33 466387035
Enseignant-Chercheur Laboratoire LGI2P

Ecole des Mines d'Ales, Institut Mines-Télécom
Parc scientifique Georges Besse, 30035 Nîmes Cedex 1
www.socialnetworks.wp.mines-telecom.fr
=====================================================