A novel entropy-based graph signature from the average mixing matrix

Lu Bai, Luca Rossi, Lixin Cui*, Edwin R. Hancock

*Corresponding author for this work

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

Abstract

In this paper, we propose a novel entropic signature for graphs, where we probe the graphs by means of continuous-time quantum walks. More precisely, we characterise the structure of a graph through its average mixing matrix. The average mixing matrix is a doubly-stochastic matrix that encapsulates the time-averaged behaviour of a continuous-time quantum walk on the graph, i.e., the ij-th element of the average mixing matrix represents the time-averaged transition probability of a continuous-time quantum walk from the vertex vi to the vertex vj. With this matrix to hand, we can associate a probability distribution with each vertex of the graph. We define a novel entropic signature by concatenating the average Shannon entropy of these probability distributions with their Jensen-Shannon divergence. We show that this new entropic measure can encaspulate the rich structural information of the graphs, thus allowing to discriminate between different structures. We explore the proposed entropic measure on several graph datasets abstracted from bioinformatics databases and we compare it with alternative entropic signatures in the literature. The experimental results demonstrate the effectiveness and efficiency of our method.

Original languageEnglish
Title of host publication2016 23rd International Conference on Pattern Recognition, ICPR
PublisherIEEE
Pages1339-1344
Number of pages6
ISBN (Electronic)978-1-5090-4847-2
DOIs
Publication statusPublished - 13 Apr 2017
Event23rd International Conference on Pattern Recognition: ICPR 2016 - Cancun, Mexico
Duration: 4 Dec 20168 Dec 2016

Conference

Conference23rd International Conference on Pattern Recognition
CountryMexico
CityCancun
Period4/12/168/12/16

Bibliographical note

-© 2016 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Fingerprint Dive into the research topics of 'A novel entropy-based graph signature from the average mixing matrix'. Together they form a unique fingerprint.

  • Research Output

    • 2 Conference publication

    A novel text structure feature extractor for Chinese scene text detection and recognition

    Ren, X., Chen, K., Yang, X., Zhou, Y., He, J. & Sun, J., 13 Apr 2017, 2016 23rd International Conference on Pattern Recognition, ICPR. IEEE, p. 3380-3385 6 p.

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

  • A transitive aligned Weisfeiler-Lehman subtree kernel

    Bai, L., Rossi, L., Cui, L. & Hancock, E. R., 13 Apr 2017, 2016 23rd International Conference on Pattern Recognition, ICPR. IEEE, p. 396-401 6 p.

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

    Open Access
    File
  • Cite this

    Bai, L., Rossi, L., Cui, L., & Hancock, E. R. (2017). A novel entropy-based graph signature from the average mixing matrix. In 2016 23rd International Conference on Pattern Recognition, ICPR (pp. 1339-1344). IEEE. https://doi.org/10.1109/ICPR.2016.7899823