Matthieu Latapy

TCS Journal 2016 Journal Article

Computing maximal cliques in link streams

• Tiphaine Viard
• Matthieu Latapy
• Clémence Magnien

A link stream is a collection of triplets ( t, u, v ) indicating that an interaction occurred between u and v at time t. We generalize the classical notion of cliques in graphs to such link streams: for a given Δ, a Δ-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least once during each sub-interval of duration Δ. We propose an algorithm to enumerate all maximal (in terms of nodes or time interval) cliques of a link stream, and illustrate its practical relevance to a real-world contact trace.

TCS Journal 2011 Journal Article

Post-processing hierarchical community structures: Quality improvements and multi-scale view

• Pascal Pons
• Matthieu Latapy

Dense sub-graphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Most existing community detection algorithms produce a hierarchical structure of communities and seek a partition into communities that optimizes a given quality function. We propose new methods to improve the results of any of these algorithms. First we show how to optimize a general class of additive quality functions (containing the modularity, the performance, and a new similarity based quality function which we propose) over a larger set of partitions than the classical methods. Moreover, we define new multi-scale quality functions which make it possible to detect different scales at which meaningful community structures appear, while classical approaches find only one partition.

TCS Journal 2008 Journal Article

Main-memory triangle computations for very large (sparse (power-law)) graphs

• Matthieu Latapy

Finding, counting and/or listing triangles (three vertices with three edges) in massive graphs are natural fundamental problems, which have recently received much attention because of their importance in complex network analysis. Here we provide a detailed survey of proposed main-memory solutions to these problems, in a unified way. We note that previous authors have paid surprisingly little attention to space complexity of main-memory solutions, despite its both fundamental and practical interest. We therefore detail space complexities of known algorithms and discuss their implications. We also present new algorithms which are time optimal for triangle listing and beats previous algorithms concerning space needs. They have the additional advantage of performing better on power-law graphs, which we also detail. We finally show with an experimental study that these two algorithms perform very well in practice, allowing us to handle cases which were previously out of reach.

TCS Journal 2006 Journal Article

Preface

• Ravi Kumar
• Matthieu Latapy

TCS Journal 2005 Journal Article

Graph encoding of 2 D -gon tilings

• Frédéric Chavanon
• Matthieu Latapy
• Michel Morvan
• Eric Rémila
• Laurent Vuillon

2 D -gon tilings with parallelograms are a model used in physics to study quasicrystals, and they are also important in combinatorics for the study of aperiodic structures. In this paper, we study the graph induced by the adjacency relation between tiles. This relation can been used to encode simply and efficiently 2 D -gon tilings for algorithmic manipulation. We show for example how it can be used to sample random 2 D -gon tilings.

TCS Journal 2004 Journal Article

Sandpile models and lattices: a comprehensive survey

• Éric Goles
• Matthieu Latapy
• Clémence Magnien
• Michel Morvan
• Ha Duong Phan

Starting from some studies of (linear) integer partitions, we noticed that the lattice structure is strongly related to a large variety of discrete dynamical models, in particular sandpile models and chip firing games. After giving an historical survey of the main results which appeared about this, we propose a unified framework to explain the strong relationship between these models and lattices. In particular, we show that the apparent complexity of these models can be reduced, by showing the possibility of simplifying them, and we show how the known lattice properties can be deduced from this.

TCS Journal 2001 Journal Article

Structure of some sand piles model

• Matthieu Latapy
• Roberto Mantaci
• Michel Morvan
• Ha Duong Phan

Sand pile model (SPM) is a simple discrete dynamical system used in physics to represent granular objects. It is deeply related to integer partitions, and many other combinatorics problems, such as tilings or rewriting systems. The evolution of the system started with n stacked grains generates a lattice, denoted by SPM(n). We study here the structure of this lattice. We first explain how it can be constructed, by showing its strong self-similarity property. Then, we define SPM(∞), a natural extension of SPM when one starts with an infinite number of grains. Again, we give an efficient construction algorithm and a coding of this lattice using a self-similar tree. The two approaches give different recursive formulae for |SPM(n)|.