×

Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks. (English) Zbl 1395.68161

Summary: We show that numerical approximations of Kolmogorov complexity (\(K\)) of graphs and networks capture some group-theoretic and topological properties of empirical networks, ranging from metabolic to social networks, and of small synthetic networks that we have produced. That \(K\) and the size of the group of automorphisms of a graph are correlated opens up interesting connections to problems in computational geometry, and thus connects several measures and concepts from complexity science. We derive these results via two different Kolmogorov complexity approximation methods applied to the adjacency matrices of the graphs and networks. The methods used are the traditional lossless compression approach to Kolmogorov complexity, and a normalised version of a Block Decomposition Method (BDM) based on algorithmic probability theory.

MSC:

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90B10 Deterministic network models in operations research

Software:

DIMACS; acss; OACC
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Newman, M., Networks: an introduction, (2010), Oxford University Press, Inc. · Zbl 1195.94003
[2] Newman, M.; Barabasi, A.-L.; Watts, D. J., The structure and dynamics of networks, (2011), Princeton University Press
[3] Bonchev, D.; Buck, G. A., Quantitative measures of network complexity, (Bonchev, Danail; Rouvray, Dennis, Complexity in Chemistry, Biology, and Ecology, Vol. 7(2), (2005)), 191-235 · Zbl 1109.92300
[4] Kim, J.; Wilhelm, T., What is a complex graph?, Physica A, 387, 11, 2637-2652, (2008)
[5] Mowshowitz, A.; Dehmer, M., Entropy and the complexity of graphs revisited, Entropy, 14, 3, 559-570, (2012) · Zbl 1331.94041
[6] Adami, C.; Qian, J.; Rupp, M.; Hintze, A., Information content of colored motifs in complex networks, Artif. Life, 17, 4, 375-390, (2011)
[7] Mowshowitz, A.; Mitsou, V., Entropy, orbits, and spectra of graphs, (Analysis of Complex Networks, (2014))
[8] Xiao, Y.; Xiong, M.; Wang, W.; Wang, H., Emergence of symmetry in complex networks, Phys. Rev. E, 77, 6, 066108, (2008)
[9] Xiao, Y.; MacArthur, B. D.; Wang, H.; Xiong, M.; Wang, W., Network quotients: structural skeletons of complex systems, Phys. Rev. E, 78, 4, 046102, (2008)
[10] Buhrman, H.; Li, M.; Tromp, J.; Vitányi, P., Kolmogorov random graphs and the incompressibility method, SIAM J. Comput., 29, 2, 590-599, (1999) · Zbl 0939.68054
[11] H. Zenil, F. Soler-Toscano, J.-P. Delahaye, N. Gauvrit, Two-dimensional Kolmogorov complexity and validation of the coding theorem method by compressibility, arXiv:1212.6745 [cs.CC]. · Zbl 1286.68252
[12] Hopcroft, J.; Tarjan, R., Efficient planarity testing, J. ACM, 21, 4, 549-568, (1974) · Zbl 0307.68025
[13] Read, R.; Corneil, D., The graph isomorphism disease, J. Graph Theory, 1, 1, 339-363, (1977) · Zbl 0381.05026
[14] Baskerville, K.; Paczuski, M., Subgraph ensembles and motif discovery using an alternative heuristic for graph isomorphism, Phys. Rev. E, 74, 5 Pt 1, 051903, (2006)
[15] Baskerville, K.; Grassberger, P.; Paczuski, M., Graph animals, subgraph sampling, and motif search in large networks, Phys. Rev. E, 76, 3, 36107, (2007)
[16] Girvan, M.; Newman, M. E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci., 99, 12, 7821-7826, (2002) · Zbl 1032.91716
[17] Kolmogorov, A. N., Three approaches to the quantitative definition of information, Probl. Inf. Transm., 1, 1, 1-7, (1965)
[18] Chaitin, G. J., On the length of programs for computing finite binary sequences: statistical considerations, J. ACM, 16, 1, 145-159, (1969) · Zbl 0187.28303
[19] Li, M.; Vitányi, P., An introduction to Kolmogorov complexity and its applications, (2008), Springer Heidelberg · Zbl 1185.68369
[20] Solomonoff, R. J., A formal theory of inductive inference: parts 1 and 2, Inf. Control, 7, 1-22, 224-254, (1964) · Zbl 0259.68038
[21] Levin, L., Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Probl. Form. Transm., 10, 206-210, (1974)
[22] Cover, T. M.; Thomas, J. A., Information theory, (2014), J. Wiley and Sons
[23] Calude, C. S., Information and randomness, (2002), Springer · Zbl 1055.68058
[24] Delahaye, J.-P.; Zenil, H., On the Kolmogorov-chaitin complexity for short sequences, (Calude, C., Randomness and Complexity: from Leibniz to Chaitin, (2007), World Scientific) · Zbl 1137.68412
[25] Delahaye, J.-P.; Zenil, H., Numerical evaluation of the complexity of short strings: a glance into the innermost structure of algorithmic randomness, Appl. Math. Comput., 219, 63-77, (2012) · Zbl 1448.68250
[26] H. Zenil, Une approche expérimentale à la théorie algorithmique de la complexité, Dissertation in Fulfilment of the Degree of Doctor in Computer Science, Ph.D. Thesis, Université de Lille 1, June 2011.
[27] Delahaye, J.-P.; Zenil, H., Numerical evaluation of the complexity of short strings: a glance into the innermost structure of algorithmic randomness, Appl. Math. Comput., 219, 63-77, (2012) · Zbl 1448.68250
[28] Zenil, H.; Delahaye, J.-P., On the algorithmic nature of the world, (Dodig-Crnkovic, G.; Burgin, M., Information and Computation, (2010), World Scientific Publishing Company)
[29] F. Soler-Toscano, H. Zenil, J.-P. Delahaye, N. Gauvrit, Calculating Kolmogorov complexity from the frequency output distributions of small Turing machines, arXiv:1211:1302 [cs.IT]. · Zbl 1286.68252
[30] Soler-Toscano, F.; Zenil, H.; Delahaye, J.-P.; Gauvrit, N., Correspondence and independence of numerical evaluations of algorithmic information measures, Computability, 2, 2, 125-140, (2014) · Zbl 1286.68252
[31] Zenil, H.; Villarreal-Zapata, E., Asymptotic behaviour and ratios of complexity in cellular automata rule spaces, J. Bifur. Chaos, 13, 9, (2013) · Zbl 1277.37026
[32] Radò, T., On non-computable functions, Bell Syst. Tech. J., 41, 3, 877-884, (1962) · Zbl 1497.68176
[33] Brady, A. H., The determination of the value of rado’s noncomputable function \(S i g m a(k)\) for four-state Turing machines, Math. Comp., 40, 162, 647-665, (1983) · Zbl 0518.03013
[34] Langton, C., Studying artificial life with cellular automata, Physica D, 22, 1-3, 120-149, (1986)
[35] Gell-Mann, M., The quark and the jaguar: adventures in the simple and the complex, (1995), Abacus Paris · Zbl 0833.00010
[36] Dehmer, M.; Mowshowitz, A., A history of graph entropy measures, Inform. Sci., 181, 57-78, (2011) · Zbl 1204.94050
[37] Dehmer, M.; Sivakumar, L., Recent developments in quantitative graph theory: information inequalities for networks, PLoS One, 7, 2, 57-78, (2012)
[38] Standish, R. K., Complexity of networks, (Abbass, H. A.; etal., Recent Advances in Artificial Life, (2005), World Scientific Publishing Company), 253 · Zbl 1464.68297
[39] H. Katebi, K.A. Sakallah, I.L. Markov, Conflict anticipation in the search for graph automorphisms, in: Int’l Conf. on Logic for Programming, LPAR, Merida, Venezuela, 2012. · Zbl 1352.68223
[40] Albert, R.; Barabási, A.-L., Statistical mechanics of complex networks, Rev. Modern Phys., 74, 1, 47, (2002) · Zbl 1205.82086
[41] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 6684, 409-410, (1998) · Zbl 1368.05139
[42] Jeong, H.; Tombor, B.; Albert, R.; Oltvai, Z.; Barabási, A.-L., The large-scale organization of metabolic networks, Nature, 407, 651, (2000)
[43] (Johnson, D.; Trick, M., Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Vol. 26, (1996), AMS Providence, RI, USA)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.