Life-like network automata descriptor based on binary patterns for network classification. (English) Zbl 1457.68253
Summary: We propose a descriptor based on binary patterns extracted from network-automata time-evolution patterns (TEP) aiming to characterize networks. More, in particular, we explore TEPs descriptors from the Life-Like Network Automata (LLNA), a cellular automaton inspired by the rules of the “Life-Like” family that uses a network as tessellation, and based on its dynamics to extract features for network characterization. In recent work, the LLNA has been introduced as a pattern recognition tool that uses a descriptor based on the histograms of complexity measures such as the entropy, word length, and Lempel-Ziv complexity. However, these descriptors correspond to continuous values, and consequently, their histograms lack of an optimal number of bins, which therefore turns out to be a parametric issue. To overcome this disadvantage, we propose a new descriptor that computes feature vectors formed by discrete binary patterns histograms with different lengths \(D\). Furthermore, we show a statistical improvement of the proposed method compared to earlier approaches such as the original LLNA and classical network structural measurements. Our experimental results show the performance improvement of the proposed method in six synthetic network databases and eight real network databases.
Software:
SNAPReferences:
| [1] | Akimushkin, C.; Amancio, D. R.; Oliveira, O. N., Text authorship identified using the dynamics of word co-occurrence networks, PLoS ONE, 12, 1, 1-15 (2017) |
| [2] | Arii, K.; Parrott, L., Examining the colonization process of exotic species varying in competitive abilities using a cellular automaton model, Ecol. Modell., 199, 3, 219-228 (2006) |
| [3] | Banerjee, A.; Jost, J., Spectral plot properties: towards a qualitative classification of networks, NHM, 3, 2, 395-411 (2008) · Zbl 1171.05399 |
| [4] | Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223 |
| [5] | Bullmore, E.; Sporns, O., Complex brain networks: graph theoretical analysis of structural and functional systems, Nat. Rev. Neurosci., 10, 3, 186-198 (2009) |
| [6] | Chopard, B.; Luthi, P.; Droz, M., Reaction-diffusion cellular automata model for the formation of leisegang patterns, Phys. Rev. Lett., 72, 9, 1384-1387 (1994) |
| [7] | Costa, L.; Boas, P. R.V.; Silva, F.; Rodrigues, F., A pattern recognition approach to complex networks, J. Stat. Mech., 2010, 11, P11015 (2010) |
| [8] | Costa, L.; Rodrigues, F.; Travieso, G.; Boas, P. R.V., Characterization of complex networks: a survey of measurements, Adv. Phys., 56, 1, 167-242 (2007) |
| [9] | Czaran, T.; Bartha, S., Spatiotemporal dynamic models of plant populations and communities, Trends Ecol. Evol., 7, 2, 38-42 (1992) |
| [10] | Silva, N. R.; Baetens, J.; Oliveira, M.; Baets, B.; Bruno, O., Classification of cellular automata through texture analysis, Inf. Sci., 370-371, 33-49 (2016) |
| [11] | Dodds, P. S.; Muhamad, R.; Watts, D. J., An experimental study of search in global social networks, Science, 301, 5634, 827-829 (2003) |
| [12] | Dorogovtsev, S. N.; Mendes, J. F., Evolution of networks, Adv. Phys., 51, 4, 1079-1187 (2002) |
| [13] | Erdös, P.; Rényi, A., On random graphs, Publicationes Mathematicae Debrecen, 6, 290-297 (1959) · Zbl 0092.15705 |
| [14] | Filho, H. A.; Machicao, J.; Bruno, O. M., A hierarchical model of metabolic machinery based on the kcore decomposition of plant metabolic networks, PLoS ONE, 13, 5, e0195843 (2018) |
| [15] | Gomez, J. M.; Verdu, M.; Perfectti, F., Ecological interactions are evolutionarily conserved across the entire tree of life, Nature, 465, 918-â921 (2010) |
| [16] | Hearst, M.; Dumais, S.; Osuna, E.; Platt, J.; Scholkopf, B., Support vector machines, IEEE Intell. Syst. Appl., 13, 4, 18-28 (1998) |
| [17] | Jeong, H.; Tombor, B.; Albert, R.; Oltvai, Z. N.; Barabási, A. L., The large-scale organization of metabolic networks, Nature, 407, 6804, 651-654 (2000) |
| [18] | Kanehisa, M.; Sato, Y.; Kawashima, M.; Furumichi, M.; Tanabe, M., KEGG as a reference resource for gene and protein annotation, Nucl. Acids Res., 44, D1, D457-D462 (2015) |
| [19] | J. Leskovec, A. Krevl, SNAP Datasets: stanford large network dataset collection, 2014, (http://snap.stanford.edu/data). |
| [20] | Machicao, J.; Baetens, J. M.; Marco, A. G.; Baets, B. D.; Bruno, O. M., A dynamical systems approach to the discrimination of the modes of operation of cryptographic systems, Commun. Nonlinear Sci. Numer. Simul., 29, 1-3, 102-115 (2015) |
| [21] | Machicao, J.; Corrêa, E. A.; Miranda, G. H.B.; Amancio, D. R.; Bruno, O. M., Authorship attribution based on life-like network automata, PLOS ONE, 13, 3, e0193703 (2018) |
| [22] | Machicao, J.; Filho, H. A.; Lahr, D. J.G.; Buckeridge, M.; Bruno, O. M., Topological assessment of metabolic networks reveals evolutionary information, Sci. Rep., 8, 1 (2018) |
| [23] | Machicao, J.; Marco, A. G.; Bruno, O. M., Chaotic encryption method based on life-like cellular automata, Expert Syst. Appl., 39, 16, 12626-12635 (2012) |
| [24] | Machicao, J.; Ribas, L. C.; Scabini, L. F.; Bruno, O. M., Cellular automata rule characterization and classification using texture descriptors, Physica A, 497, 109-117 (2018) · Zbl 1514.68151 |
| [25] | Marr, C.; Hütt, M., Outer-totalistic cellular automata on graphs, Phys. Lett. A, 373, 5, 546-549 (2009) · Zbl 1227.37006 |
| [26] | Mehri, A.; Darooneh, A. H.; Shariati, A., The complex networks approach for authorship attribution of books, Physica A, 391, 7, 2429-2437 (2012) |
| [27] | Miranda, G. H.B.; Machicao, J.; Bruno, O. M., An optimized shape descriptor based on structural properties of networks, Digit. Signal Process., 82, 216-229 (2018) |
| [28] | Miranda, G. H.B.; Machicao, J.; Bruno, O. M., Exploring spatio-temporal dynamics of cellular automata for pattern recognition in networks, Sci. Rep., 6, Article 37329 pp. (2016) |
| [29] | Newman, M. E., The structure of scientific collaboration networks, Proc. Natl. Acad. Sci., 98, 2, 404-409 (2001) · Zbl 1065.00518 |
| [30] | Palla, G.; Derényi, I.; Farkas, I.; Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society, Nature, 435, 7043, 814-818 (2005) |
| [31] | Poleszczuk, J.; Enderling, H., A high-performance cellular automaton model of tumor growth with dynamically growing domains, Appl. Math., 5, 1, 144-152 (2014) |
| [32] | Rain, J.-C.; Selig, L.; De Reuse, H.; Battaglia, V.; Reverdy, C.; Simon, S.; Lenzen, G.; Petel, F.; Wojcik, J.; Schächter, V., The protein-protein interaction map of helicobacter pylori, Nature, 409, 6817, 211-215 (2001) |
| [33] | L.C. Ribas, J.J. Junior, L.F. Scabini, O.M. Bruno, Fusion of complex networks and randomized neural networks for texture analysis, 2018 arXiv:1806.09170 |
| [34] | Ribas, L. C.; Neiva, M. B.; Bruno, O. M., Distance transform network for shape analysis, Inf. Sci., 470, 28-42 (2019) |
| [35] | ISBN 978-3-319-25751-8 |
| [36] | Rosin, P., Training cellular automata for image processing, IEEE Trans. Image Process., 15, 7, 2076-2087 (2006) |
| [37] | Sirakoulis, G.; Karafyllidis, I.; Thanailakis, A., A cellular automaton model for the effects of population movement and vaccination on epidemic propagation, Ecol. Modell., 133, 3, 209-223 (2000) |
| [38] | Smith, D.; Onnela, J.; Lee, C.; Fricker, M.; Johnson, N., Network automata: coupling structure and function in dynamic networks, Adv. Complex Syst., 14, 3, 317-339 (2011) |
| [39] | Stelzl, U.; Worm, U.; Lalowski, M.; Haenig, C.; Brembeck, F. H.; Goehler, H.; Stroedicke, M.; Zenkner, M.; Schoenherr, A.; Koeppen, S., A human protein-protein interaction network: a resource for annotating the proteome, Cell, 122, 6, 957-968 (2005) |
| [40] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ’small-world’ networks, Nature, 393, 6684, 440-442 (1998) · Zbl 1368.05139 |
| [41] | Waxman, B. M., Routing of multipoint connections, IEEE J. Sel. Areas Commun., 6, 9, 1617-1622 (1988) |
| [42] | Wolfram, S., Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 3, 601-644 (1983) · Zbl 1174.82319 |
| [43] | Wolfram, S., Cellular automata as models of complexity, Nature, 311, 5985, 419-424 (1984) |
| [44] | Wu, A.-C.; Xu, X.-J.; Wang, Y. H., Excitable greenberg-hastings cellular automaton model on scale-free networks, Phys. Rev. E, 75, 3, 32901 (2007) |
| [45] | R. Xin, J. Zhang, Y. Shao, Complex network classification with convolutional neural network, CoRR arXiv:1802.00539. |
| [46] | Zhao, J.; Yu, H.; Luo, J.; Cao, Z. W.; Li, Y., Complex networks theory for analyzing metabolic networks, Chin. Sci. Bull., 51, 13, 1529-1537 (2006) |
| [47] | Zhao, Y.; Billings, S.; Coca, D., Cellular automata modelling of dendritic crystal growth based on moore and von neumann neighbourhoods, Int. J. Model. Ident. Control, 6, 2, 119 (2009) |
| [48] | Zhou, H.; Lipowsky, R., Dynamic pattern evolution on scale-free networks, Proc. Natl. Acad. Sci. USA, 102, 29, 10052-10057 (2005) |
| [49] | Zinovieva, O.; Zinoviev, A.; Ploshikhin, V.; Romanova, V.; Balokhonov, R., A solution to the problem of the mesh anisotropy in cellular automata simulations of grain growth, Comput. Mater. Sci., 108, 168-176 (2015) |
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.
