# zbMATH — the first resource for mathematics

Depth-based complexity traces of graphs. (English) Zbl 1326.68241
Summary: In this paper we aim to characterize graphs in terms of a structural measure of complexity. Our idea is to decompose a graph into layered substructures of increasing size, and then to measure the information content of these substructures. To locate dominant substructures within a graph, we commence by identifying a centroid vertex which has the minimum shortest path length variance to the remaining vertices. For each graph a family of centroid expansion subgraphs is derived from the centroid vertex in order to capture dominant structural characteristics of the graph. Since the centroid vertex is identified through a global analysis of the shortest path length distribution, the expansion subgraphs provide a fine representation of a graph structure. We then show how to characterize graphs using depth-based complexity traces. Here we explore two different strategies. The first strategy is to measure how the entropies on the centroid expansion subgraphs vary with the increasing size of the subgraphs. The second strategy is to measure how the entropy differences vary with the increasing size of the subgraphs. We perform graph classification in the principal component space of the complexity trace vectors. Experiments on graph datasets abstracted from some bioinformatics and computer vision databases demonstrate the effectiveness and efficiency of the proposed graph complexity traces. Our methods are competitive to state of the art methods.

##### MSC:
 68T10 Pattern recognition, speech recognition 05C81 Random walks on graphs 05C90 Applications of graph theory 62H25 Factor analysis and principal components; correspondence analysis 94A17 Measures of information, entropy
AFGen; COIL-20
Full Text:
##### References:
 [1] Bunke, H.; Riesen, K., Improving vector space embedding of graphs through feature selection algorithms, Pattern Recognition, 44, 1928-1940, (2010) [2] Wilson, R. C.; Hancock, E. R.; Luo, B., Pattern vectors from algebraic graph theory, IEEE Transactions on Pattern Analysis and Machine Intelligence, 27, 1112-1124, (2005) [3] Ren, P.; Wilson, R. C.; Hancock, E. R., Graph characterization via ihara coefficients, IEEE Transactions on Neural Networks, 22, 233-245, (2011) [4] R.I. Kondor, J.D. Lafferty, Diffusion kernels on graphs and other discrete input spaces, in: Proceedings of International Conference on Machine Learning, 2002, pp. 315-322. [5] Lafferty, J. D.; Lebanon, G., Diffusion kernels on statistical manifolds, Journal of Machine Learning Research, 6, 129-163, (2005) · Zbl 1222.68240 [6] H. Kashima, K. Tsuda, A. Inokuchi, Marginalized kernels between labeled graphs, in: Proceedings of International Conference on Machine Learning, 2003, pp. 321-328. [7] Gärtner, T., A survey of kernels for structured data, ACM Special Interest Group on Knowledge Discovery and Data Mining, 5, 49-58, (2003) [8] K.M. Borgwardt, H. Kriegel, Shortest-path kernels on graphs, in: IEEE International Conference on Data Mining, 2005, pp. 74-81. [9] Kolmogorov, A. N., Three approaches to the definition of information (in Russian), Problemy Peredachi Informatsii, 1, 3-11, (1965) · Zbl 0271.94018 [10] Mowshowitz, A.; Dehmer, M., Entropy and the complexity of graph revisited, Entropy, 14, 559-570, (2012) · Zbl 1331.94041 [11] (Bonchev, D.; Rouvray, D. H., Complexity in Chemistry, Biology, and Ecology, Mathematical and Computational Chemistry, (2005), Springer New York) · Zbl 1109.92300 [12] Bonchev, D., Complexity analysis of yeast proteome network, Chemistry & Biodiversity, 1, 312-326, (2004) [13] Pudlák, P.; Rödl, V.; Savickiý, P., Graph complexity, Acta Informatica, 25, 515-535, (1988) · Zbl 0681.68070 [14] Feldman, D. P.; Crutchfield, J. P., Measures of statistical complexitywhy?, Physics Letters A, 238, 244252, (1998) [15] Dehmer, M.; Mowshowitz, A., A history of graph entropy measures, Information Sciences, 181, 57-78, (2011) · Zbl 1204.94050 [16] Anand, K.; Bianconi, G.; Severini, S., Shannon and von Neumann entropy of random networks with heterogeneous expected degree, Physical Review E, 83, 036109, (2011) [17] Passerini, F.; Severini, S., Quantifying complexity in networksthe von Neumann entropy, International Journal of Agent Technologies and Systems, 1, 58-67, (2009) [18] Braunstein, S. L.; Ghosh, S.; Severini, S., The Laplacian of a graph as a density matrixa basic combinatorial approach to separability of mixed states, Annals of Combinatorics, 10, 291-317, (2006) · Zbl 1106.05057 [19] Godsil, C. D.; Royle, G.; Godsil, C. D., Algebraic graph theory, (2001), Springer New York · Zbl 1026.05046 [20] Han, L.; Escolano, F.; Hancock, E. R., Graph characterizations from von Neumann entropy, Pattern Recognition Letters, 33, 1958-1967, (2012) [21] Escolano, F.; Hancock, E. R.; Lozano, M. A., Heat diffusionthermodynamic depth complexity of networks, Physical Review E, 85, 206236, (2012) [22] Crutchfield, J. P.; Shalizi, C. R., Thermodynamic depth of causal statesobjective complexity via minimal representations, Physical Review E, 59, 275283, (1999) [23] Dehmer, M., Information processing in complex networkgraph entropy and information functionals, Applied Mathematics and Computing, 201, 82-94, (2008) · Zbl 1152.05361 [24] Jordan, C., Sur LES assemblages des lignes, Journal für die reine und Angewandte Mathematik, 70, 185-190, (1969) · JFM 02.0344.01 [25] Slater, P. J., Centers to centroids in graphs, Journal of Graph Theory, 2, 209-222, (1978) · Zbl 0425.05021 [26] A. Dutot, D. Olivier, G. Savin, Centroids: a decentralized approach, in: Proceedings of Emergent Properties in Natural and Artificial Complex Systems within ECCS, 2011, pp. 23-28. [27] Shervashidze, N.; Schweitzer, P.; Leeuwen, E. J.V.; Mehlhorn, K.; Borgwardt, K. M., Weisfeiler-lehman graph kernels, Journal of Machine Learning Research, 1, 1-48, (2010) [28] K.M. Borgwardt, HP. Kriegel, Shortest-Path Kernels on Graphs, in: Proceedings of IEEE International Conference on Data Mining, 2005, pp. 74-81. [29] Santhakumaran, A. P., Centroid of a graph with respect to edges, Mathemitical Science, 19, 13-23, (2010) · Zbl 1244.05081 [30] Slater, P. J., Centrality of paths vertices in a graphcores and pits, Theory and Applications of Graphs, 529-542, (1981) [31] R. Nock, F. Nielsen, Fitting the smallest enclosing Bregman ball, in: Proceedings of International Conference of Machine Learning, 2005, pp. 649-656. [32] Bersano-Méndez, N. I.; Schaeffer, S. E.; Bustos-Jiménez, J., Metrics and models for social networks, (Abraham, Ajith; Hassanien, Aboul-Ella, Computational Social Networks, (2012), Springer), 115-142 [33] Schomburg, I.; Chang, A.; Ebeling, C.; Gremse, M.; Heldt, C.; Huhn, G.; Schomburg, D., The enzyme databaseupdates and major new developments, Nucleic Acids Research, 32, 431-433, (2004) [34] Borgwardt, K. M.; Ong, C. S.; Schoenauer, S.; Vishwanathan, S. V.N.; Smola, A. J.; Kriegel, H. P., Protein function prediction via graph kernels, Bioinformatics, 21, Suppl. 1, 47-56, (2005) [35] Debnath, A. K.; Lopez de Compadre, R. L.; Debnath, G.; Shusterman, A. J.; Hansch, C., Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds, correlation with molecular orbital energies and hydrophobicity, Journal of Medicinal Chemistry, 34, 786-797, (1991) [36] Dobson, P. D.; Doig, A. J., Distinguishing enzyme structures from non-enzymes without alignments, Journal of Molecular Biology, 330, 771-783, (2003) [37] T. Gärtner, P.A. Flach, S. Wrobel, On graph kernels: hardness results and efficient alternatives, in: Proceedings of the Conference on Computational Learning Theory, 2003, pp. 129-143. · Zbl 1274.68312 [38] N. Wale, G. Karypis, Comparison of descriptor spaces for chemical compound retrieval and classification, in: Proceedings of IEEE International Conference on Data Mining, 2006, pp. 678-689. [39] S.A. Nene, S.K. Nayar, H. Murase, Columbia Object Image library (COIL-20), Technical Report CUCS-005-96, Department of Computer Science, Columbia University, New York, February 1996. [40] C.G. Harris, M.J. Stephens, A combined corner and edge detector, in: Proceedings of Alvey Vision Conference, 1988, pp. 147-151. [41] Platt, J. C., Fast training of support vector machines using sequential minimal optimization, (Schölkopf, B.; Burges, C. J.C.; Smola, A. J., Advances in Kernel Methods, (1999), MIT Press), 185-208 [42] Sanders, W. S.; Johnston, C. I.; Bridges, S. M.; Burgess, S. C.; Willeford, K. O., Prediction of cell penetrating peptides by support vector machines, PLoS Computational Biology, 7, e1002101, (2011) [43] Bunke, H.; Riesen, K., Improving vector space embedding of graphs through feature selection algorithms, Pattern Recognition, 44, 1928-1940, (2011) [44] (Cook, D. J.; Holder, L. B., Mining Graph Data, (2006), Wiley-Interscience New Jersey) · Zbl 1116.68028 [45] (Brandes, U.; Erlebach, T., Network Analysis, (2005), Springer Berlin, Heidelber) · Zbl 1069.68001 [46] Mowshowitz, A., Entropy and the complexity of the graphs ian index of the relative complexity of a graph, Bulletin Mathematical Biophysics, 30, 175-204, (1968) · Zbl 0165.57601 [47] Rashevsky, N., Life, information theory, and topology, Bulletin Mathematical Biophysics, 17, 229-235, (1955) [48] Trucco, E., A note on the information content of graphs, Bulletin Mathematical Biophysics, 18, 129-135, (1956) [49] Johnson, D. B., Efficient algorithms for shortest paths in sparse networks, Journal of the ACM, 24, 1-13, (1977) · Zbl 0343.68028 [50] J. Körner, Coding of an information source having ambiguous alphabet and the entropy of graphs, in: Proceedings of Transactions of the 6th Prague Conference on Information Theory, 1973, pp. 411-425. [51] Bai, L.; Hancock, E. R., Graph kernels from the Jensen-Shannon divergence, Journal of Mathematical Imaging and Vision, 47, 60-69, (2013) · Zbl 1276.68152 [52] Neuhaus, M.; Bunke, H., Bridging the gap between graph edit distance and kernel machines, (2007), World Scientific · Zbl 1140.68473 [53] Majtey, A.; Lamberti, P.; Prato, D., Jensen-Shannon divergence as a measure of distinguishability between mixed quantum states, Physical Review A, 72, 052310, (2005) [54] L. Bai, E.R. Hancock, A. Torsello, L. Rossi, A quantum Jensen-Shannon graph kernel using the continuous-time quantum walk, in: Proceedings of Graph-Based Representations in Pattern Recognition (GbRPR), 2013, pp. 121-131. · Zbl 1382.68160 [55] Martins, A. F.; Smith, N. A.; Xing, E. P.; Aguiar, P. M.; Figueiredo, M. A., Nonextensive information theoretic kernels on measures. Journal of Machine Learning Research, 10, 935-975, (2009) · Zbl 1235.68174
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.