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