Supervision : Marie-Jeanne LESOT

Co-supervision : DETYNIECKI Marcin, REVAULT D'ALLONNES Adrien

Vertex-oriented community detection for mobile opportunistic networks

Our research tackles a complex-networks mining task known as community detection, in a strongly decentralised and distributed context: we consider the case of opportunistic networks comprised of small wireless connected devices, communicating peer-to-peer. We propose to combine the Think-Like-a-Vertex graph processing paradigm with leader and seed-based community detection methods, suitable for decentralisation. We propose a global working principle which we implemented through three algorithms dealing with three different aspects of the community detection task: detection of disjoint communities on static graphs, detection of overlapping communities on static graphs and the case of dynamic graphs. We present these algorithms, together with an experimental study on benchmarks and real data to assess the quality of the results and to compare them with state-of-the-art methods. We also consider, in the specific case of an opportunistic mobile network comprised of smart communicating clothing, a task of pathfinding towards target, an unknown member of the social network. We propose a recommandation strategy exploiting the graph's community structure, designed and evaluated through an algorithm.

2014-2017 Publications

• 2017
  • M. Canu : “Détection de communautés orientée sommet pour réseaux mobiles opportunistes sociaux”, thesis, phd defence 12/20/2017, supervision Lesot, Marie-Jeanne, co-supervision : Detyniecki, Marcin, Revault, D'ALLONNES Adrien (2017)
• 2016
  • M. Canu, M.‑J. Lesot, A. Revault D'Allonnes : “Overlapping Community Detection by Local Decentralised Vertex-centred Process”, Proceedings of the 2016 16^th IEEE International Conference on Data Mining Workshops (ICDMW'16), Barcelone, Spain, pp. 77-84, (IEEE) (2016)
  • M. Canu, M.‑J. Lesot, A. Revault D'Allonnes : “Détection de communautés recouvrantes orientée sommet”, Actes de la 7^e Conférence sur les modèles et l’analyse des réseaux : Approches mathématiques et informatiques, Cergy, France (2016)
  • M. Canu, M.‑J. Lesot, A. Revault D'Allonnes : “Vertex-centred Method to Detect Communities in Evolving Networks”, Proceedings of the 5^th International Workshop on Complex Networks and their Applications (COMPLEX NETWORKS 2016), vol. 683, Studies in Computational Intelligence, Milan, Italy, pp. 275-286, (Springer International Publishing) (2016)
• 2015
  • M. Canu, M. Detyniecki, M.‑J. Lesot, A. Revault D'Allonnes : “Fast community structure local uncovering by independent vertex-centred process”, Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Paris, France, pp. 823-830, (ACM) (2015)
• 2014
  • M. Canu, M. Detyniecki, M.‑J. Lesot : “Utilisation de la structure communautaire pour guider une marche aléatoire”, Actes de la 5^e Conférence sur les Modèles et l’Analyse des Réseaux : Approches Mathématiques et Informatique (MARAMI'14), Paris, France, pp. p5 (2014)