Computing maximal cliques in link streams

Tiphaine Viard; Matthieu Latapy; Clémence Magnien

doi:10.1016/j.tcs.2015.09.030

Computing maximal cliques in link streams

Tiphaine Viard
, Matthieu Latapy
, Clémence Magnien

Sorbonne Université

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	245-252
Number of pages	8
Journal	Theoretical Computer Science
Volume	609
DOIs	https://doi.org/10.1016/j.tcs.2015.09.030
Publication status	Published - 4 Jan 2016

Keywords

Algorithms
Cliques
Graphs
Link streams
Temporal networks
Time-varying graphs

Access to Document

10.1016/j.tcs.2015.09.030

Cite this

@article{23ccd2648e554a24ac9e462fec2a6bca,

title = "Computing maximal cliques in link streams",

abstract = "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.",

keywords = "Algorithms, Cliques, Graphs, Link streams, Temporal networks, Time-varying graphs",

author = "Tiphaine Viard and Matthieu Latapy and Cl{\'e}mence Magnien",

note = "Publisher Copyright: {\textcopyright} 2015 Elsevier B.V.",

year = "2016",

month = jan,

day = "4",

doi = "10.1016/j.tcs.2015.09.030",

language = "English",

volume = "609",

pages = "245--252",

journal = "Theoretical Computer Science",

issn = "0304-3975",

}

TY - JOUR

T1 - Computing maximal cliques in link streams

AU - Viard, Tiphaine

AU - Latapy, Matthieu

AU - Magnien, Clémence

PY - 2016/1/4

Y1 - 2016/1/4

N2 - 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.

AB - 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.

KW - Algorithms

KW - Cliques

KW - Graphs

KW - Link streams

KW - Temporal networks

KW - Time-varying graphs

U2 - 10.1016/j.tcs.2015.09.030

DO - 10.1016/j.tcs.2015.09.030

M3 - Article

AN - SCOPUS:84951810450

SN - 0304-3975

VL - 609

SP - 245

EP - 252

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Computing maximal cliques in link streams

Abstract

Keywords

Access to Document

Fingerprint

Cite this