Computing maximal cliques in link streams

DOI10.1016/J.TCS.2015.09.030zbMATH Open1331.68158arXiv1502.00993OpenAlexW1890592509MaRDI QIDQ897884FDOQ897884

Authors: Jordan Viard, Matthieu Latapy, Clémence Magnien 

Publication date: 8 December 2015

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

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.

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

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

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)

Cites Work

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

Cited In (35)

• How fast can we reach a target vertex in stochastic temporal graphs?
• Title not available (Why is that?)
• Computing parameters of sequence-based dynamic graphs
• Deleting edges to restrict the size of an epidemic in temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Temporal vertex cover with a sliding time window
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• Sliding window temporal graph coloring
• Temporal interval cliques and independent sets
• On atomic cliques in temporal graphs
• How fast can we reach a target vertex in stochastic temporal graphs?
• Graph signatures: identification and optimization
• 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
• Challenges in community discovery on temporal networks
• Metrics for temporal text networks
• Enumerating maximal cliques in link streams with durations
• The complexity of finding small separators in temporal graphs
• Temporal cliques admit sparse spanners

Uses Software

• cliques
• Algorithm 457

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)