Supervision : Matthieu LATAPY

Co-supervision : MAGNIEN Clémence

Groups and Communities in link streams: from data to algorithms

Interactions are everywhere: in the contexts of face-to-face contacts, emails, phone calls, IP traffic, etc. In all of them, an interaction is characterized by two entities and a time interval: for instance, two individuals meet from 1pm to 3pm.
We model them as link stream which is a set of quadruplets (b,e,u,v) where each quadruplet means that a link exists between u and v from time b to time e. In graphs, a community is a subset which is more densely connected than a reference. Within the link stream formalism, the notion of density and reference have to be redefined. Therefore, we study how to extend the notion of density for link streams. To this end, we use a real data set where a community structure is known. Then, we develop a method that finds automatically substream which are considered relevant. These substream, defined as subsets of links, are discovered by a classical community detection algorithm applied on the link stream then transformed into a static graph. A substream is considered relevant, if it is denser than the substreams which are close temporally and structurally. Thus, we deepen the notion of neighbourhood and reference in link streams.
We apply our method on several real world interaction networks and we find relevant substream which would not have been found by existing methods. Finally, we discuss the generation of link streams having a given community structure and also a proper way to evaluate such community structure.

2014-2018 Publications

• 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)
• 2016
  • N. Gaumont : “Groupes et Communautés dans les flots de liens: des données aux algorithmes”, thesis, phd defence 10/11/2016, supervision Latapy, Matthieu, co-supervision : Magnien, Clémence (2016)
  • N. Gaumont : “Trouver des séquences de contacts pertinentes dans un flot de liens”, ALGOTEL 2016 - 18^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, ALGOTEL 2016 - 18^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Bayonne, France (2016)
  • N. Gaumont, T. Viard, R. Fournier‑S'niehotta, Q. Wang, M. Latapy : “Analysis of the Temporal and Structural Features of Threads in a Mailing-List”, Complex Networks VIIProceedings of the 7^th Workshop on Complex Networks CompleNet 2016, vol. 644, Studies in Computational Intelligence, Dijon, France, pp. 107-118, (Springer) (2016)
  • N. Gaumont, C. Magnien, M. Latapy : “Finding remarkably dense sequences of contacts in link streams”, Social Network Analysis and Mining, vol. 6 (1), pp. 87, (Springer) (2016)
• 2015
  • N. Gaumont, F. Queyroi, C. Magnien, M. Latapy : “Expected Nodes: A Quality Function for the Detection of Link Communities”, Complex Networks VI, vol. 597, Studies in Computational Intelligence, New-York, United States, pp. 57-64 (2015)
• 2014
  • N. Gaumont, F. Queyroi : “Partitionnement des Liens d’un Graphe : Critères et Mesures”, ALGOTEL 2014 -- 16^es Rencontres, Le Bois-Plage-en-Ré, France, pp. 1-4 (2014)