Supervision : Bénédicte LE GRAND

Co-supervision : GUILLAUME Jean-Loup

Mesures de proximité appliquées à la détection de communautés dans les grands graphes de terrain

Un grand nombre de données sont naturellement représentables sous la forme d'un graphe (ensemble de nœuds liés par des liens) : Facebook, où des profils sont associés par des liens d'amitié, Internet où des ordinateurs sont liés par des connexions internet, le cerveau où des neurones sont connectés par des synapses, ou bien des protéines réagissant chimiquement entre elles. D'autres types de données peuvent également être convertis, de manière moins naturelle, sous ce format : deux entités sont liées si elles sont suffisamment similaires.
Bien qu'ils viennent de milieux différents, ces graphes de terrain ont des propriétés topologiques communes et l’explosion de leur taille et de leur nombre a créé le besoin d'avoir des algorithmes rapides et génériques permettant de les comprendre et d'en extraire des connaissances utiles. L'une des problématiques privilégiées est liée à leur organisation ; en effet, le nombre de nœuds étant très important, il est intéressant de rassembler ces nœuds dans des groupes afin de mieux comprendre la structure générale du graphe. La détection de communautés qui sont généralement définies, de manière informelle, comme des groupes de nœuds fortement liés les uns aux autres et peu liés vers l'extérieur est un premier pas vers cette description mésoscopique. Une autre problématique est de savoir dans quelle mesure deux nœuds sont topologiquement proches et consiste en l'élaboration de mesures de proximité.
Dans cette thèse, je défends l'idée que ces deux problèmes majeurs, la détection de communautés et la mise au point de mesures de proximité sont fortement intriquées. En particulier, je présente une méthode qui permet, à l'aide d'une mesure de proximité, d'isoler des groupes de nœuds. Son principe général de fonctionnement est plutôt simple et peut être décrit comme suit. Étant donné un nœud d'intérêt dans le graphe, on calcule la proximité de chaque nœud dans le graphe à ce nœud d'intérêt. Ensuite, si un petit groupe de nœuds obtient une proximité très élevée à ce nœud d'intérêt et que tous les autres nœuds du graphe ont une proximité très faible, alors on peut directement conclure que le petit groupe de nœuds est "la communauté" du nœud d'intérêt. Je montre ensuite comment décliner cette idée pour résoudre efficacement les trois problèmes suivants : (i) trouver toutes les communautés auxquelles un nœud donné appartient, (ii) compléter un ensemble de nœuds en une communauté et (iii) trouver des communautés recouvrantes dans un réseau. Je valide les trois méthodes sur des jeux de données réels et synthétiques et montre qu'elles sont des alternatives viables aux approches classiques consistant en l'optimisation gloutonne d'une fonction de qualité.

1 PhD graduated 2020

2013-2022 Publications

• 2022
  • M. Danisch, I. Panagiotas, L. Tabourier : “Compressing bipartite graphs with a dual reordering scheme”, (2022)
  • N. Arhachoui, E. Bautista, M. Danisch, A. Giovanidis : “A Fast Algorithm for Ranking Users by their Influence in Online Social Platforms”, Proc. of the 2022 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, Istanbul, Turkey (2022)
  • A. Baudin, M. Danisch, S. Kirgizov, C. Magnien, M. Ghanem : “Clique percolation method: memory efficient almost exact communities”, The 17^th International Conference on Advanced Data Mining and Applications (ADMA), Syndey, Australia (2022)
• 2021
  • F. Lécuyer, M. Danisch, L. Tabourier : “[Re] Speedup Graph Processing by Graph Ordering”, The ReScience journal, vol. 7 (1), pp. #3, (GitHub) (2021)
• 2020
  • A. Bhowmick, K. Meneni, M. Danisch, J.‑L. GUILLAUME, B. Mitra : “LouvainNE: Hierarchical Louvain Method for High Quality and Scalable Network Embedding *”, 13^th ACM International WSDM Conference, WSDM '20: Proceedings of the 13^th International Conference on Web Search and Data Mining, Houston, Texas, United States, pp. 43-51 (2020)
  • B. Sun, M. Danisch, T.‑H. Chan, M. Sozio : “KClist++: A Simple Algorithm for Finding k-Clique Densest Subgraphs in Large Graphs”, Proceedings of the VLDB Endowment (PVLDB), (VLDB Endowment) (2020)
• 2019
  • S. Pramanik, M. Sharma, M. Danisch, Q. Wang, J.‑L. GUILLAUME, B. Mitra : “Easy-Mention: a model-driven mention recommendation heuristic to boost your tweet popularity”, International Journal of Data Science and Analytics, vol. 7 (2), pp. 131-147, (Springer Verlag) (2019)
• 2018
  • M. Danisch, N. Gaumont, J.‑L. GUILLAUME : “A Modular Overlapping Community Detection Algorithm: Investigating the ``From Local to Global’’ Approach”, 16^th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, Paris, France, pp. 167-170 (2018)
  • M. Danisch, O. Balalau, M. Sozio : “Listing k-cliques in Sparse Real-World Graphs”, WWW '18 Proceedings of the 2018 World Wide Web Conference, Lyon, France, pp. 589-598 (2018)
• 2017
  • S. Pramanik, Q. Wang, M. Danisch, J.‑L. GUILLAUME, B. Mitra : “Modeling cascade formation in Twitter amidst mentions and retweets”, Social Network Analysis and Mining, vol. 7 (1), (Springer) (2017)
• 2016
  • S. Pramanik, Q. Wang, M. Danisch, S. Bandi, A. Kumar, J.‑L. GUILLAUME, B. Mitra : “On the Role of Mentions on Tweet Virality”, 2016 IEEE International Conference on Data Science and Advanced Analytics (DSAA), Montreal, Canada, pp. 204-213, (IEEE) (2016)
• 2015
  • M. Danisch : “Mesures de proximité appliquées à la détection de communautés dans les grands graphes de terrain”, thesis, defence 06/15/2015, supervision Le grand, Bénédicte, co-supervision : Guillaume, Jean-Loup (2015)
  • S. Pramanik, Q. Wang, M. Danisch, M. Sharma, S. Bandi, J.‑L. GUILLAUME, S. Raux, B. Mitra : “Augmenter les retweets sur Twitter : comment tirer parti des mentions ?”, Actes de MARAMI 2015, Nîmes, France (2015)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Déplier la structure communautaire d’un réseau en mesurant la proximité aux représentants de communauté”, Actes de MARAMI 2015, Nîmes, France (2015)
  • N. Dugué, A. Perez, M. Danisch, F. Bridoux, A. Daviau, T. Kolubako, S. Munier, H. Durbano : “A reliable and evolutive web application to detect social capitalists”, ASONAM 2015, Paris, France (2015)
  • S. Pramanik, M. Danisch, Q. Wang, B. Mitra : “An empirical approach towards an efficient “whom to mention?” Twitter app”, Twitter for Research, 1^st International & Interdisciplinary Conference, Lyon, France (2015)
• 2014
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Multi-ego-centered communities in practice”, Social Network Analysis and Mining, vol. 4 (1), pp. 180, (Springer) (2014)
  • M. Danisch, N. Dugué, A. Perez : “On the importance of considering social capitalism when measuring influence on Twitter”, BESC 2014 - International Conference on Behavioral, Economic, and Socio-Cultural Computing, Shanghai, China, pp. 1-7, (IEEE) (2014)
  • M. Danisch, N. Dugué, A. Perez : “Prendre en compte le capitalisme social dans la mesure de l’influence sur Twitter”, Modèles et Analyses Réseau : Approches Mathématiques et Informatiques, MARAMI 2014, Paris, France (2014)
  • R. Tackx, M. Danisch, F. Tarissan : “Structures biparties et communautés recouvrantes des graphes de terrains”, Actes de MARAMI 2014, Paris, France, pp. 1-12 (2014)
  • D. Obradovic, M. Danisch : “Direct Generation of Random Graphs Exactly Realising a Prescribed Degree Sequence”, Proceedings of CASON 2014, Porto, Portugal (2014)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Learning a proximity measure to complete a community”, Proceedings of the 2014 International Conference on Data Science and Advanced Analytics (DSAA2014), Shanghai, China, pp. 90-96, (IEEE) (2014)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Complétion de communautés par l’apprentissage d’une mesure de proximité”, ALGOTEL 2014 -- 16^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Le Bois-Plage-en-Ré, France, pp. 1-4 (2014)
  • R. Fournier, M. Danisch : “Mining bipartite graphs to improve semantic pedophile activity detection”, Proceedings of the 8^th IEEE International Conference on Research Challenges in Information Science 2014 (RCIS2014), Marrakech, Morocco (2014)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Multi-ego-centered communities”, chapter in Complex Networks, pp. 76-111, (Cambridge Scholars Publishing) (2014)
• 2013
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Une approche à base de proximité pour la détection de communautés egocentrées”, 15^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel), Portnic, France, pp. 1-4 (2013)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Unfolding ego-centered community structures with "a similarity approach"”, Proceedings of the 4^th Workshop on Complex Networks CompleNet 2013, vol. 476, Studies in Computational Intelligence, Berlin, Germany, pp. 145-153, (Springer) (2013)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Déplier les structures communautaires egocentrées - une approche à base de similarité”, Actes de l'atelier Fouille de Grands Graphes - EGC, Toulouse, France (2013)
  • M. Danisch, J.‑L. GUILLAUME, B. Le Grand : “Towards multi-ego-centered communities: a node similarity approach”, International Journal of Web Based Communities, vol. 9 (3), pp. 299-322, (Inderscience) (2013)