TY - GEN
T1 - A novel entropy-based graph signature from the average mixing matrix
AU - Bai, Lu
AU - Rossi, Luca
AU - Cui, Lixin
AU - Hancock, Edwin R.
N1 - Funding Information:
This work is supported by the National Natural Science Foundation of China (Grant no. 61503422 and 61602535), and the Open Projects Program of National Laboratory of Pattern Recognition. Lu Bai is supported by the program for innovation research in Central University of Finance and Economics. Edwin R. Hancock is supported by a Royal Society Wolfson Research Merit Award.
Publisher Copyright:
© 2016 IEEE.
PY - 2016/1/1
Y1 - 2016/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85019065209&partnerID=8YFLogxK
U2 - 10.1109/ICPR.2016.7899823
DO - 10.1109/ICPR.2016.7899823
M3 - Conference article published in proceeding or book
AN - SCOPUS:85019065209
T3 - Proceedings - International Conference on Pattern Recognition
SP - 1339
EP - 1344
BT - 2016 23rd International Conference on Pattern Recognition, ICPR 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 23rd International Conference on Pattern Recognition, ICPR 2016
Y2 - 4 December 2016 through 8 December 2016
ER -