Network Analysis Using Spatio-Temporal Patterns

Different network models have been proposed along the last years inspired by real-world topologies. The characterization of these models implies the understanding of the underlying network phenomena, which accounts structural and dynamic properties. Several mathematical tools can be employed to characterize such properties as Cellular Automata (CA), which can be defined as dynamical systems of discrete nature composed by spatially distributed units governed by deterministic rules. In this paper, we proposed a method based on the modeling of one specific CA over distinct network topologies in order to perform the classification of the network model. The proposed methodology consists in the modeling of a binary totalistic CA over a network. The transition function that governs each CA cell is based on the density of living neighbors. Secondly, the distribution of the Shannon entropy is obtained from the evolved spatio-temporal pattern of the referred CA and used as a network descriptor. The experiments were performed using a dataset composed of four different types of networks: random, small-world, scale-free and geographical. We also used cross-validation for training purposes. We evaluated the accuracy of classification as a function of the initial number of living neighbors, and, also, as a function of a threshold parameter related to the density of living neighbors. The results show high accuracy values in distinguishing among the network models which demonstrates the feasibility of the proposed method. (paper)