Approximate axial symmetries from continuous time quantum walks

Luca Rossi*, Andrea Torsello, Edwin R. Hancock

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationStructural, Syntactic, and Statistical Pattern Recognition
Subtitle of host publicationjoint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings
EditorsGeorgy Gimel’farb, Edwin Hancock, Atsushi Imiya, et al
Place of PublicationBerlin (DE)
PublisherSpringer
Pages144-152
Number of pages9
ISBN (Electronic)978-3-642-34166-3
ISBN (Print)978-3-642-34165-6
DOIs
Publication statusPublished - 2012
EventJoint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition - Hiroshima, Japan
Duration: 7 Nov 20129 Nov 2012

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume7626
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopJoint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition
Abbreviated titleSSPR 2012 / SPR 2012
CountryJapan
CityHiroshima
Period7/11/129/11/12

Keywords

  • complex network
  • quantum walk
  • symmetry

Fingerprint Dive into the research topics of 'Approximate axial symmetries from continuous time quantum walks'. Together they form a unique fingerprint.

  • Research Output

    • 1 Conference contribution

    Information theoretic prototype selection for unattributed graphs

    Han, L., Rossi, L., Torsello, A., Wilson, R. C. & Hancock, E. R., 2012, Structural, Syntactic, and Statistical Pattern Recognition: joint IAPR international workshop, SSPR&SPR 2012, Hiroshima, Japan, November 7-9, 2012. Proceedings. Gimel’farb, G., Hancock, E., Imiya, A. & et al (eds.). Berlin (DE): Springer, p. 33-41 9 p. (Lecture notes in computer science; vol. 7626).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  • 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