### 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 | |

Publication status | Published - 2012 |

Event | Joint IAPR international workshops on Structural and Syntactic Pattern Recognition and Statistical techniques in Pattern Recognition - 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 |
---|---|

Abbreviated title | SSPR 2012 / SPR 2012 |

Country | Japan |

City | Hiroshima |

Period | 7/11/12 → 9/11/12 |

### Fingerprint

### Keywords

- complex network
- quantum walk
- symmetry

### Cite this

*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). Berlin (DE): Springer. https://doi.org/10.1007/978-3-642-34166-3_16

}

*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, 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.

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

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 - http://www.scopus.com/inward/record.url?scp=84868124969&partnerID=8YFLogxK

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 contribution

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)

ER -