Ph.D thesis [pdf]

My PhD (2004-2007) in computer science was supervised by Matthieu Latapy at LIAFA (University Paris Diderot - Paris 7). My research work was about community detection in complex networks. Complex networks are graphs that model real-world phenomena such as social, biological or technological networks. They have heterogeneous degree distibution and present community structures: localy dense area in a globaly sparse graph. The challenge was to design efficient algorithm to compute such structures in (very) large graphs

The main idea was to define a distance between vertices based on random walks in the graph. This distance captures a structural similarity of nodes and communities. An efficient hierachical clustering algorithm makes use of this distance and a postprocessing analysis makes it posible to uncover the different scales at wich appear relevant community strcutures.

Publications

  • Post-processing hierarchical community structures: Quality improvements and multi-scale view (with Matthieu Latapy). Theoretical Computer Science (TCS) 412(8-10): 892-900 (2011) [pdf]
  • Computing communities in large networks using random walks (with Matthieu Latapy). Journal of Graph Algorithms and Applications (JGAA) Vol. 10, no. 2, pp. 191-218, 2006 [pdf]
  • Computing communities in large networks using random walks (extended abstract) (with Matthieu Latapy). 20th International Symposium on Computer and Information Sciences (ISCIS'05), LNCS 3733, Istanbul, Turquie, 2005. [pdf]
  • Algorithms to evaluate the reliability of a network (with Jérôme Galtier and Alexandre Laugier). 5th International Workshop on Design of Reliable Communication Networks (DRCN'05), Ischia, Italie, 2005. [pdf]
  • Policy-driven multi-file distribution (with Catherine Rosenberg and Dongyan Xu). 12th International Workshop on Quality of Service (IWQoS'04), Montréal, Canada, 2004 [pdf]
  • Détection de structures de communautés dans les grands réseaux d'interactions. Septièmes Rencontres Francophones sur les aspects Algorithmiques des Télécommunications (AlgoTel'05), Giens, France, 2005. [pdf]
  • Algorithmique des grands réseaux d'interactions: détection de structures de communautés. Rapport de D.E.A, 2004 [pdf]