Windows into relational events: data structures for contiguous subsequences of edges

DOI10.1137/1.9781611973105.61MaRDI QIDQ5741769zbMATH OpenOpenAlexFDO

Authors Michael J. Bannister, Ch. Dubois, David Eppstein, Padhraic Smyth

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Social networks; opinion dynamics (91D30)

Abstract: We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.

Recommendations

• Time windowed data structures for graphs
• Counting subgraphs in relational event graphs
• Querying Relational Event Graphs Using Colored Range Searching Data Structures
• Querying relational event graphs using colored range searching data structures
• A hybrid adjacency and time-based data structure for analysis of temporal networks

Cited in

(9)

• A hybrid adjacency and time-based data structure for analysis of temporal networks
• Using compressed suffix-arrays for a compact representation of temporal-graphs
• Querying relational event graphs using colored range searching data structures
• Window queries for intersecting objects, maximal points and approximations using coresets
• The network-untangling problem: from interactions to activity timelines
• Counting subgraphs in relational event graphs
• Querying Relational Event Graphs Using Colored Range Searching Data Structures
• Time windowed data structures for graphs
• The Most Likely Object to be Seen Through a Window

This page was built for publication: Windows into relational events: data structures for contiguous subsequences of edges

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