Approximate axial symmetries from continuous time quantum walks

Luca Rossi; Andrea Torsello; Edwin R. Hancock

doi:10.1007/978-3-642-34166-3_16

Approximate axial symmetries from continuous time quantum walks

Luca Rossi^*
, Andrea Torsello
, Edwin R. Hancock

^*Corresponding author for this work

College of Engineering and Physical Sciences

University of York
Università Ca' Foscari Venezia

Research output: Chapter in Book/Published conference output › Conference publication

10 Citations (Scopus)

Abstract

The analysis of complex networks is usually based on key properties such as small-worldness and vertex degree distribution. The presence of symmetric motifs on the other hand has been related to redundancy and thus robustness of the networks. In this paper we propose a method for detecting approximate axial symmetries in networks. For each pair of nodes, we define a continuous-time quantum walk which is evolved through time. By measuring the probability that the quantum walker to visits each node of the network in this time frame, we are able to determine whether the two vertices are symmetrical with respect to any axis of the graph. Moreover, we show that we are able to successfully detect approximate axial symmetries too. We show the efficacy of our approach by analysing both synthetic and real-world data.

Original language	English
Title of host publication	Structural, Syntactic, and Statistical Pattern Recognition
Subtitle of host publication	joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings
Editors	Georgy Gimel’farb, Edwin Hancock, Atsushi Imiya, et al
Place of Publication	Berlin (DE)
Publisher	Springer
Pages	144-152
Number of pages	9
ISBN (Electronic)	978-3-642-34166-3
ISBN (Print)	978-3-642-34165-6
DOIs	https://doi.org/10.1007/978-3-642-34166-3_16
Publication status	Published - 2012
Event	Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012 - Hiroshima, Japan Duration: 7 Nov 2012 → 9 Nov 2012

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	7626
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012
Abbreviated title	SSPR 2012 / SPR 2012
Country/Territory	Japan
City	Hiroshima
Period	7/11/12 → 9/11/12

Keywords

complex network
quantum walk
symmetry

Access to Document

10.1007/978-3-642-34166-3_16

Cite this

Rossi, L., Torsello, A., & Hancock, E. R. (2012). Approximate axial symmetries from continuous time quantum walks. In G. Gimel’farb, E. Hancock, A. Imiya, & et al (Eds.), Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings (pp. 144-152). (Lecture notes in computer science; Vol. 7626). Springer. https://doi.org/10.1007/978-3-642-34166-3_16

Rossi, Luca ; Torsello, Andrea ; Hancock, Edwin R. / Approximate axial symmetries from continuous time quantum walks. Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. editor / Georgy Gimel’farb ; Edwin Hancock ; Atsushi Imiya ; et al. Berlin (DE) : Springer, 2012. pp. 144-152 (Lecture notes in computer science).

@inproceedings{873eecda373d44d1b0b88d2824766028,

title = "Approximate axial symmetries from continuous time quantum walks",

abstract = "The analysis of complex networks is usually based on key properties such as small-worldness and vertex degree distribution. The presence of symmetric motifs on the other hand has been related to redundancy and thus robustness of the networks. In this paper we propose a method for detecting approximate axial symmetries in networks. For each pair of nodes, we define a continuous-time quantum walk which is evolved through time. By measuring the probability that the quantum walker to visits each node of the network in this time frame, we are able to determine whether the two vertices are symmetrical with respect to any axis of the graph. Moreover, we show that we are able to successfully detect approximate axial symmetries too. We show the efficacy of our approach by analysing both synthetic and real-world data.",

keywords = "complex network, quantum walk, symmetry",

author = "Luca Rossi and Andrea Torsello and Hancock, \{Edwin R.\}",

year = "2012",

doi = "10.1007/978-3-642-34166-3\_16",

language = "English",

isbn = "978-3-642-34165-6",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "144--152",

editor = "Georgy Gimel{\textquoteright}farb and Edwin Hancock and Atsushi Imiya and \{et al\}",

booktitle = "Structural, Syntactic, and Statistical Pattern Recognition",

address = "Germany",

note = "Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012, SSPR 2012 / SPR 2012 ; Conference date: 07-11-2012 Through 09-11-2012",

}

Rossi, L, Torsello, A & Hancock, ER 2012, Approximate axial symmetries from continuous time quantum walks. in G Gimel’farb, E Hancock, A Imiya & et al (eds), Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. Lecture notes in computer science, vol. 7626, Springer, Berlin (DE), pp. 144-152, Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012, Hiroshima, Japan, 7/11/12. https://doi.org/10.1007/978-3-642-34166-3_16

Approximate axial symmetries from continuous time quantum walks. / Rossi, Luca; Torsello, Andrea; Hancock, Edwin R.
Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. ed. / Georgy Gimel’farb; Edwin Hancock; Atsushi Imiya; et al. Berlin (DE): Springer, 2012. p. 144-152 (Lecture notes in computer science; Vol. 7626).

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - Approximate axial symmetries from continuous time quantum walks

AU - Rossi, Luca

AU - Torsello, Andrea

AU - Hancock, Edwin R.

PY - 2012

Y1 - 2012

N2 - The analysis of complex networks is usually based on key properties such as small-worldness and vertex degree distribution. The presence of symmetric motifs on the other hand has been related to redundancy and thus robustness of the networks. In this paper we propose a method for detecting approximate axial symmetries in networks. For each pair of nodes, we define a continuous-time quantum walk which is evolved through time. By measuring the probability that the quantum walker to visits each node of the network in this time frame, we are able to determine whether the two vertices are symmetrical with respect to any axis of the graph. Moreover, we show that we are able to successfully detect approximate axial symmetries too. We show the efficacy of our approach by analysing both synthetic and real-world data.

AB - The analysis of complex networks is usually based on key properties such as small-worldness and vertex degree distribution. The presence of symmetric motifs on the other hand has been related to redundancy and thus robustness of the networks. In this paper we propose a method for detecting approximate axial symmetries in networks. For each pair of nodes, we define a continuous-time quantum walk which is evolved through time. By measuring the probability that the quantum walker to visits each node of the network in this time frame, we are able to determine whether the two vertices are symmetrical with respect to any axis of the graph. Moreover, we show that we are able to successfully detect approximate axial symmetries too. We show the efficacy of our approach by analysing both synthetic and real-world data.

KW - complex network

KW - quantum walk

KW - symmetry

UR - https://www.scopus.com/pages/publications/84868124969

UR - http://link.springer.com/chapter/10.1007%2F978-3-642-34166-3_16

U2 - 10.1007/978-3-642-34166-3_16

DO - 10.1007/978-3-642-34166-3_16

M3 - Conference publication

AN - SCOPUS:84868124969

SN - 978-3-642-34165-6

T3 - Lecture notes in computer science

SP - 144

EP - 152

BT - Structural, Syntactic, and Statistical Pattern Recognition

A2 - Gimel’farb, Georgy

A2 - Hancock, Edwin

A2 - Imiya, Atsushi

A2 - et al,

PB - Springer

CY - Berlin (DE)

T2 - Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition 2012

Y2 - 7 November 2012 through 9 November 2012

ER -

Rossi L, Torsello A, Hancock ER. Approximate axial symmetries from continuous time quantum walks. In Gimel’farb G, Hancock E, Imiya A, et al, editors, Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. Berlin (DE): Springer. 2012. p. 144-152. (Lecture notes in computer science). doi: 10.1007/978-3-642-34166-3_16

Approximate axial symmetries from continuous time quantum walks

Abstract

Publication series

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Information theoretic prototype selection for unattributed graphs

Cite this