Fast streaming small graph canonization

Pedro Paredes; Pedro Ribeiro

doi:10.1007/978-3-319-73198-8_3

Fast streaming small graph canonization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper, we introduce the streaming graph canonization problem. Its goal is finding a canonical representation of a sequence of graphs in a stream. Our model of a stream fixes the graph’s vertices and allows for fully dynamic edge changes, meaning it permits both addition and removal of edges. Our focus is on small graphs, since small graph isomorphism is an important primitive of many subgraph-based metrics, like motif analysis or frequent subgraph mining. We present an efficient data structure to approach this problem, namely a graph isomorphism discrete finite automaton and showcase its efficiency when compared to a non-streaming-aware method that simply recomputes the isomorphism information from scratch in each iteration.

Original language	English (US)
Title of host publication	Springer Proceedings in Complexity
Editors	Sean Cornelius, Kate Coronges, Bruno Goncalves, Roberta Sinatra, Alessandro Vespignani
Publisher	Springer Science and Business Media B.V.
Pages	27-40
Number of pages	14
ISBN (Print)	9783319731971
DOIs	https://doi.org/10.1007/978-3-319-73198-8_3
State	Published - 2018
Externally published	Yes
Event	9th International Conference on Complex Networks, CompleNet 2018 - Boston, United States Duration: Mar 5 2018 → Mar 8 2018

Publication series

Name	Springer Proceedings in Complexity
Volume	0
ISSN (Print)	2213-8684
ISSN (Electronic)	2213-8692

Conference

Conference	9th International Conference on Complex Networks, CompleNet 2018
Country/Territory	United States
City	Boston
Period	3/5/18 → 3/8/18

All Science Journal Classification (ASJC) codes

Applied Mathematics
Modeling and Simulation
Computer Science Applications

Access to Document

10.1007/978-3-319-73198-8_3

Cite this

@inproceedings{053b664bf49d41e28aaf5993e2fa582c,

title = "Fast streaming small graph canonization",

abstract = "In this paper, we introduce the streaming graph canonization problem. Its goal is finding a canonical representation of a sequence of graphs in a stream. Our model of a stream fixes the graph{\textquoteright}s vertices and allows for fully dynamic edge changes, meaning it permits both addition and removal of edges. Our focus is on small graphs, since small graph isomorphism is an important primitive of many subgraph-based metrics, like motif analysis or frequent subgraph mining. We present an efficient data structure to approach this problem, namely a graph isomorphism discrete finite automaton and showcase its efficiency when compared to a non-streaming-aware method that simply recomputes the isomorphism information from scratch in each iteration.",

author = "Pedro Paredes and Pedro Ribeiro",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018.; 9th International Conference on Complex Networks, CompleNet 2018 ; Conference date: 05-03-2018 Through 08-03-2018",

year = "2018",

doi = "10.1007/978-3-319-73198-8_3",

language = "English (US)",

isbn = "9783319731971",

series = "Springer Proceedings in Complexity",

publisher = "Springer Science and Business Media B.V.",

pages = "27--40",

editor = "Sean Cornelius and Kate Coronges and Bruno Goncalves and Roberta Sinatra and Alessandro Vespignani",

booktitle = "Springer Proceedings in Complexity",

address = "Germany",

}

Paredes, P & Ribeiro, P 2018, Fast streaming small graph canonization. in S Cornelius, K Coronges, B Goncalves, R Sinatra & A Vespignani (eds), Springer Proceedings in Complexity. Springer Proceedings in Complexity, vol. 0, Springer Science and Business Media B.V., pp. 27-40, 9th International Conference on Complex Networks, CompleNet 2018, Boston, United States, 3/5/18. https://doi.org/10.1007/978-3-319-73198-8_3

Fast streaming small graph canonization. / Paredes, Pedro; Ribeiro, Pedro.
Springer Proceedings in Complexity. ed. / Sean Cornelius; Kate Coronges; Bruno Goncalves; Roberta Sinatra; Alessandro Vespignani. Springer Science and Business Media B.V., 2018. p. 27-40 (Springer Proceedings in Complexity; Vol. 0).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fast streaming small graph canonization

AU - Paredes, Pedro

AU - Ribeiro, Pedro

N1 - Publisher Copyright: © Springer International Publishing AG 2018.

PY - 2018

Y1 - 2018

N2 - In this paper, we introduce the streaming graph canonization problem. Its goal is finding a canonical representation of a sequence of graphs in a stream. Our model of a stream fixes the graph’s vertices and allows for fully dynamic edge changes, meaning it permits both addition and removal of edges. Our focus is on small graphs, since small graph isomorphism is an important primitive of many subgraph-based metrics, like motif analysis or frequent subgraph mining. We present an efficient data structure to approach this problem, namely a graph isomorphism discrete finite automaton and showcase its efficiency when compared to a non-streaming-aware method that simply recomputes the isomorphism information from scratch in each iteration.

AB - In this paper, we introduce the streaming graph canonization problem. Its goal is finding a canonical representation of a sequence of graphs in a stream. Our model of a stream fixes the graph’s vertices and allows for fully dynamic edge changes, meaning it permits both addition and removal of edges. Our focus is on small graphs, since small graph isomorphism is an important primitive of many subgraph-based metrics, like motif analysis or frequent subgraph mining. We present an efficient data structure to approach this problem, namely a graph isomorphism discrete finite automaton and showcase its efficiency when compared to a non-streaming-aware method that simply recomputes the isomorphism information from scratch in each iteration.

UR - http://www.scopus.com/inward/record.url?scp=85054766623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85054766623&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73198-8_3

DO - 10.1007/978-3-319-73198-8_3

M3 - Conference contribution

AN - SCOPUS:85054766623

SN - 9783319731971

T3 - Springer Proceedings in Complexity

SP - 27

EP - 40

BT - Springer Proceedings in Complexity

A2 - Cornelius, Sean

A2 - Coronges, Kate

A2 - Goncalves, Bruno

A2 - Sinatra, Roberta

A2 - Vespignani, Alessandro

PB - Springer Science and Business Media B.V.

T2 - 9th International Conference on Complex Networks, CompleNet 2018

Y2 - 5 March 2018 through 8 March 2018

ER -

Fast streaming small graph canonization

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this