RNTI

MODULAD
Énumération efficace des cliques maximales dans les flots de liens réels massifs
In EGC 2023, vol. RNTI-E-39, pp.139-150
Abstract
Link streams provide a consistent formalism to represent interactions in time. A link con-sists of two vertices that interact over a given time interval. With this formalism, a clique corresponds to a set of vertices and a time interval during which they are all linked together. It is maximal if neither its set of vertices nor its time interval can be increased. Existing algorithms for enumerating these structures are not able to handle datasets with more than a few hundred thousand links. However, access to increasingly massive data requires tools to be adapted to larger scales. We then propose an algorithm that scales up the enumeration of maximal cliques to massive real-world temporal networks of up to more than 100 million links. We show experimentally that this algorithm is more efficient than the state-of-the-art by several orders of magnitude.