Computing maximal cliques in link streams

DOI10.1016/J.TCS.2015.09.030MaRDI QIDQ897884zbMATH OpenOpenAlexFDO

Authors Jordan Viard, Matthieu Latapy, Clémence Magnien

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00993

zbMATH Keywords

cliquestemporal networkstime-varying graphslink streams

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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 $Delta$, a $Delta$-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 $Delta$. 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 on a real-world contact trace.

Recommendations

• Enumerating maximal cliques in link streams with durations
• Finding all maximal cliques in dynamic graphs
• Temporal matching
• Computing Betweenness Centrality in Link Streams
• Algorithm Theory - SWAT 2004

Cites work

• A note on the problem of reporting maximal cliques
• Algorithm 457: finding all cliques of an undirected graph
• Enumerating all connected maximal common subgraphs in two graphs
• Listing all maximal cliques in large sparse real-world graphs
• On generating all maximal independent sets
• The worst-case time complexity for generating all maximal cliques and computational experiments

Cited in

(35)

• How fast can we reach a target vertex in stochastic temporal graphs?
• scientific article; zbMATH DE number 7559396 (Why is no real title available?)
• Computing parameters of sequence-based dynamic graphs
• Temporal vertex cover with a sliding time window
• Deleting edges to restrict the size of an epidemic in temporal networks
• Sliding window temporal graph coloring
• Deleting edges to restrict the size of an epidemic in temporal networks
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• Temporal interval cliques and independent sets
• On atomic cliques in temporal graphs
• Graph signatures: identification and optimization
• How fast can we reach a target vertex in stochastic temporal graphs?
• A new temporal interpretation of cluster editing
• Community detection in complex networks: from statistical foundations to data science applications
• Temporal matching
• Complex networks and link streams for the empirical analysis of large software
• The complexity of computing optimum labelings for temporal connectivity
• Faster maximal clique enumeration in large real-world link streams
• Efficient temporal core maintenance of massive graphs
• Temporal cliques admit sparse spanners
• Pattern matching in link streams: timed-automata with finite memory
• Cluster editing for multi-layer and temporal graphs
• A new temporal interpretation of cluster editing
• Pattern matching in link streams: a token-based approach
• The temporal explorer who returns to the base
• An information-theoretic framework for the lossy compression of link streams
• Finding conserved low-diameter subgraphs in social and biological networks
• As Time Goes By: Reflections on Treewidth for Temporal Graphs
• Finding all maximal cliques in dynamic graphs
• Enumerating maximal cliques in link streams with durations
• Challenges in community discovery on temporal networks
• Metrics for temporal text networks
• The complexity of finding small separators in temporal graphs
• Temporal cliques admit sparse spanners

Describes a project that uses

Uses Software

• Algorithm 457
• cliques

This page was built for publication: Computing maximal cliques in link streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897884)