RECORD
Subgraph Isomorphism in Temporal Networks
Social and Information Networks · Submitted 7 May 2016
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We empirically demonstrate the hybrid approach to be more efficient than the others, over a range of network data sets.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Temporal information is increasingly available as part of large network data sets. This information reveals sequences of link activations between network entities, which can expose underlying processes in the data. Examples include the dissemination of information through a social network, the propagation of musical ideas in a music sampling network, and the spread of a disease via contacts between infected and susceptible individuals. The search for these more meaningful patterns may be formulated as a time-respecting subgraph isomorphism problem. Our set of query graphs include an enumeration of small random graphs and fan-out-fan-in structures, all composed of time-respecting paths. We explore three methods of solving the problem, which differ in how they exploit temporal and topological information. One approach extracts all subgraphs that have the temporal properties we require and then performs subgraph isomorphism testing on each subgraph. Another approach performs subgraph isomorphism testing first with temporal post-filtering, while the other is a hybrid approach that uses temporal information during the search. We empirically demonstrate the hybrid approach to be more efficient than the others, over a range of network data sets. These data come from communication and social networks, up to interactions in size.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Temporal information is increasingly available as part of large network data sets. | background 1.00 | 0.04 | 0.01 | asserted 1.00 |
| s1 | This information reveals sequences of link activations between network entities, which can expose underlying processes in the data. | background 0.96 | 0.07 | 0.02 | asserted 0.82 |
| s2 | Examples include the dissemination of information through a social network, the propagation of musical ideas in a music sampling network, and the spread of a disease via contacts between infected and susceptible individuals. | background 1.00 | 0.05 | 0.01 | asserted 0.96 |
| s3 | The search for these more meaningful patterns may be formulated as a time-respecting subgraph isomorphism problem. | background 0.91 | 0.11 | 0.04 | hedged possibility 0.97 |
| s4 | Our set of query graphs include an enumeration of small random graphs and fan-out-fan-in structures, all composed of time-respecting paths. | method 0.86 | 0.87 | 0.02 | asserted 0.99 |
| s5 | We explore three methods of solving the problem, which differ in how they exploit temporal and topological information. | method 0.68 | 0.81 | 0.04 | asserted 0.88 |
| s6 | One approach extracts all subgraphs that have the temporal properties we require and then performs subgraph isomorphism testing on each subgraph. | method 0.99 | 0.77 | 0.03 | asserted 0.94 |
| s7 | Another approach performs subgraph isomorphism testing first with temporal post-filtering, while the other is a hybrid approach that uses temporal information during the search. | method 0.99 | 0.75 | 0.04 | asserted 0.83 |
| s8 | We empirically demonstrate the hybrid approach to be more efficient than the others, over a range of network data sets. | result 1.00 | 0.96 | 0.81 | asserted 1.00 |
| s9 | These data come from communication and social networks, up to interactions in size. | method 0.95 | 0.55 | 0.02 | asserted 0.86 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Temporal information is increasingly available as part of large network data sets. This information reveals sequences of link activations between network entities, which can expose underlying processes in the data. Examples include the dissemination of information through a social network, the propagation of musical ideas in a music sampling network, and the spread of a disease via contacts between infected and susceptible individuals. The search for these more meaningful patterns may be formulated as a time-respecting subgraph isomorphism problem. Our set of query graphs include an enumeration of small random graphs and fan-out-fan-in structures, all composed of time-respecting paths. We explore three methods of solving the problem, which differ in how they exploit temporal and topological information. One approach extracts all subgraphs that have the temporal properties we require and then performs subgraph isomorphism testing on each subgraph. Another approach performs subgraph isomorphism testing first with temporal post-filtering, while the other is a hybrid approach that uses temporal information during the search. We empirically demonstrate the hybrid approach to be more efficient than the others, over a range of network data sets. These data come from communication and social networks, up to interactions in size.
Human review
How the literature uses it
3 arXiv papers cite this in 3 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 2 papers
-
There has been extensive research on the efficient analysis of temporal graphs such as graph mining [ref] , graph simulation [ref] , motif counting [ref] , subgraph matching [ref] , and network clustering [ref] .
Time-Constrained Continuous Subgraph Matching Using Temporal Information for Filtering and Backtracking · Introduction · 1.00
-
Redmond and Cunningham first introduced the problem to find a query subgraph with temporal constraints in a given temporal network [ref] .
Temporal Network Motifs: Models, Limitations, Evaluation · Related Work · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.