Depth-based complexity traces of graphs
作者：
Highlights：
• We identify a centroid vertex of a graph through its shortest path matrix.
• We establish a family of expansion subgraphs of a graph from its centroid vertex.
• We construct depth-based complexity traces of a graph on its expansion subgraphs.
• We evaluate the performance of our complexity traces on standard graph datasets.
• We demonstrate the effectiveness and efficiency of the graph complexity traces.
摘要
Highlights•We identify a centroid vertex of a graph through its shortest path matrix.•We establish a family of expansion subgraphs of a graph from its centroid vertex.•We construct depth-based complexity traces of a graph on its expansion subgraphs.•We evaluate the performance of our complexity traces on standard graph datasets.•We demonstrate the effectiveness and efficiency of the graph complexity traces.
论文关键词：Depth-based complexity traces,Entropy,Entropy difference,Centroid vertex,Centroid expansion subgraphs,Graph classification
论文评审过程：Received 10 January 2013, Revised 11 September 2013, Accepted 15 September 2013, Available online 24 September 2013.
论文官网地址：https://doi.org/10.1016/j.patcog.2013.09.010
