×

Chaotic traversal (CHAT): very large graphs traversal using chaotic dynamics. (English) Zbl 1382.68162

Summary: Graph Traversal algorithms can find their applications in various fields such as routing problems, natural language processing or even database querying. The exploration can be considered as a first stepping stone into knowledge extraction from the graph which is now a popular topic. Classical solutions such as Breadth First Search (BFS) and Depth First Search (DFS) require huge amounts of memory for exploring very large graphs. In this research, we present a novel memoryless graph traversal algorithm, Chaotic Traversal (CHAT) which integrates chaotic dynamics to traverse large unknown graphs via the Lozi map and the Rössler system. To compare various dynamics effects on our algorithm, we present an original way to perform the exploration of a parameter space using a bifurcation diagram with respect to the topological structure of attractors. The resulting algorithm is an efficient and nonresource demanding algorithm, and is therefore very suitable for partial traversal of very large and/or unknown environment graphs. CHAT performance using Lozi map is proven superior than the, commonly known, Random Walk, in terms of number of nodes visited (coverage percentage) and computation time where the environment is unknown and memory usage is restricted.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C81 Random walks on graphs
37D45 Strange attractors, chaotic dynamics of systems with hyperbolic behavior
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adamic, L. A. [1999] “ The small world web,” ECDL, pp. 443-452.
[2] Albers, S. & Henzinger, M. R. [2000] “ Exploring unknown environments,” SIAM J. Comput.29, 1164-1188. · Zbl 0947.68165
[3] Albert, R., Jeong, H. & Barabási, A.-L. [1999] “ Internet: Diameter of the world-wide web,” Nature401, 130-131.
[4] Albert, R. [2005] “ Scale-free networks in cell biology,” J. Cell Sci.118, 4947-4957.
[5] Alon, N., Bruck, J., Naor, J., Naor, M. & Roth, R. M. [1992] “ Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs,” IEEE Trans. Inf. Th.38, 509-516. · Zbl 0744.94023
[6] Araujo, E. & Coelho, L. D. S. [2008] “ Particle swarm approaches using Lozi map chaotic sequences to fuzzy modeling of an experimental thermal-vacuum system,” Appl. Soft. Comput.8, 1354-1364.
[7] Aziz-Alaoui, M., Robert, C. & Grebogi, C. [2001] “ Dynamics of a Hénon-Lozi-type map,” Chaos Solit. Fract.12, 2323-2341. · Zbl 1005.37013
[8] Barabasi, A.-L. & Oltvai, Z. N. [2004] “ Network biology: Understanding the cell’s functional organization,” Nat. Rev. Genet.5, 101.
[9] Botella-Soler, V., Castelo, J., Oteo, J. & Ros, J. [2011] “ Bifurcations in the Lozi map,” J. Phys. A: Math. Th.44, 305101. · Zbl 1223.37063
[10] Bucolo, M., Caponetto, R., Fortuna, L., Frasca, M. & Rizzo, A. [2002] “Does chaos work better than noise?” IEEE Circuits Syst. Mag.2, 4-19.
[11] Chen, G. & Ueta, T. [1999] “ Yet another chaotic attractor,” Int. J. Bifurcation and Chaos09, 1465-1466. · Zbl 0962.37013
[12] Choset, H. [2001] “ Coverage for robotics — A survey of recent results,” Ann. Math. Artif. Intell.31, 113-126. · Zbl 1314.68317
[13] Chua, L., Wu, C., Huang, A. & Zhong, G.-Q. [1993] “ A universal circuit for studying and generating chaos. II. Strange attractors,” IEEE Trans. Circuits Syst.-I: Fund. Th. Appl.40, 745-761. · Zbl 0844.58053
[14] Coppersmith, D., Doyle, P., Raghavan, P. & Snir, M. [1993] “ Random walks on weighted graphs and applications to on-line algorithms,” J. ACM40, 421-453. · Zbl 0785.68071
[15] Dentler, K., Guéret, C. & Schlobach, S. [2009] “ Semantic web reasoning by swarm intelligence,” Proc. Int. Workshop Scalable Semantic Web Knowledge Base Systems (SSWS), p. 1.
[16] Dudek, G., Jenkin, M., Milios, E. & Wilkes, D. [1991] “ Robotic exploration as graph construction,” IEEE Trans. Rob. Autom.7, 859-865.
[17] Erdős, P. & Rényi, A. [1960] “ On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci.5, 17-60. · Zbl 0103.16301
[18] Faloutsos, M., Faloutsos, P. & Faloutsos, C. [1999] “ On power-law relationships of the internet topology,” ACM SIGCOMM Computer Com. Review, pp. 251-262. · Zbl 0889.68050
[19] Fleischer, R. & Trippen, G. [2003] “ Experimental studies of graph traversal algorithms,” Exp. Efficient Algorithms, pp. 120-133. · Zbl 1023.68875
[20] Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A. & Peleg, D. [2005] “ Graph exploration by a finite automaton,” Theor. Comput. Sci.345, 331-344. · Zbl 1081.68045
[21] Fujita, K. A., Ostaszewski, M., Matsuoka, Y., Ghosh, S., Glaab, E., Trefois, C., Crespo, I., Perumal, T. M., Jurkowski, W., Antony, P. M.et al. [2014] “ Integrating pathways of Parkinson’s disease in a molecular interaction map,” Mol. Neurobiol.49, 88-102.
[22] Gandomi, A. H., Yang, X.-S., Talatahari, S. & Alavi, A. [2013a] “ Firefly algorithm with chaos,” Commun. Nonlin. Sci. Numer. Simul.18, 89-98. · Zbl 1254.92089
[23] Gandomi, A. H., Yun, G. J., Yang, X.-S. & Talatahari, S. [2013b] “ Chaos-enhanced accelerated particle swarm optimization,” Commun. Nonlin. Sci. Numer. Simul.18, 327-340. · Zbl 1323.90082
[24] Gaudino, R., Carena, A., Ferrero, V., Pozzi, A., De Feo, V., Gigante, P., Neri, F. & Poggiolini, P. [2001] “ RINGO: A WDM ring optical packet network demonstrator,” Eur. Conf. Optical Com. (ECOC’01), pp. 620-621.
[25] Haenggi, M., Andrews, J. G., Baccelli, F., Dousse, O. & Franceschetti, M. [2009] “ Stochastic geometry and random graphs for the analysis and design of wireless networks,” IEEE J. Sel. Areas Commun.27.
[26] Hagberg, A. A., Schult, D. A. & Swart, P. J. [2008] “ Exploring network structure, dynamics, and function using NetworkX,” Proc. Python in Science Conf. (SciPy2008), pp. 11-15.
[27] Hamaizia, T., Lozi, R. & Hamri, N.-E. [2012] “ Fast chaotic optimization algorithm based on locally averaged strategy and multifold chaotic attractor,” Appl. Math. Comput.219, 188-196. · Zbl 1291.90325
[28] Higashikawa, Y., Katoh, N., Langerman, S. & Tanigawa, S. [2014] “ Online graph exploration algorithms for cycles and trees by multiple searchers,” J. Comb. Opt.28, 480-495. · Zbl 1291.90279
[29] Holme, P. & Kim, B. J. [2002] “ Growing scale-free networks with tunable clustering,” Phys. Rev. E65, 026107.
[30] Hong, S., Oguntebi, T. & Olukotun, K. [2011] “ Efficient parallel graph exploration on multi-core CPU and GPU,” Proc. IEEE Int. Conf. Parallel Architectures and Compilation Techniques, pp. 78-88.
[31] Horvitz, E. & Leskovec, J. [2007] “ Planetary-scale views on an instant-messaging network,” MSR-TR.
[32] Ilcinkas, D. [2008] “ Setting port numbers for fast graph exploration,” Theor. Comput. Sci.401, 236-242. · Zbl 1147.68042
[33] Kalyanasundaram, B. & Pruhs, K. R. [1994] “ Constructing competitive tours from local information,” Theor. Comput. Sci.130, 125-138. · Zbl 0938.68764
[34] Khan, A. & Elnikety, S. [2014] “ Systems for big-graphs,” Proc. VLDB Endow., Vol. 7, pp. 1709-1710.
[35] Koenig, S. & Smirnov, Y. [1996] “ Graph learning with a nearest neighbor approach,” Proc. ACM Ann. Conf. Computational Learning Theory, pp. 19-28.
[36] Koenig, S., Szymanski, B. & Liu, Y. [2001] “ Efficient and inefficient ant coverage methods,” Ann. Math. Artif. Intell.31, 41-76.
[37] Koyuncu, I., Ozcerit, A. T. & Pehlivan, I. [2014] “ Implementation of FPGA-based real time novel chaotic oscillator,” Nonlin. Dyn.77, 49-59.
[38] Kruskal, W. H. & Wallis, W. A. [1952] “ Use of ranks in one-criterion variance analysis,” J. Am. Stat. Assoc.47, 583-621. · Zbl 0048.11703
[39] Kwek, S. [1997] “ On a simple depth-first search strategy for exploring unknown graphs,” Lect. Notes Comput. Sci., pp. 345-353. · Zbl 1509.68278
[40] Li, L., Yang, Y., Peng, H. & Wang, X. [2006] “ An optimization method inspired by “chaotic” ant behavior,” Int. J. Bifurcation and Chaos16, 2351-2364. · Zbl 1192.90251
[41] Liu, B., Wang, L., Jin, Y.-H., Tang, F. & Huang, D.-X. [2005] “ Improved particle swarm optimization combined with chaos,” Chaos Solit. Fract.25, 1261-1271. · Zbl 1074.90564
[42] Liu, D. & Chen, G. [2010] “ Hybrid algorithm for ant colony optimization based on chaos technique,” Proc. IEEE Int. Conf. Natural Computation, pp. 2628-2632.
[43] Lorenz, E. N. [1963] “ Deterministic nonperiodic flow,” J. Atmos. Sci.20, 130-141. · Zbl 1417.37129
[44] Lovász, L. [2012] Large Networks and Graph Limits, Vol. 60 (American Mathematical Society, Providence). · Zbl 1292.05001
[45] Lozi, R. [1978] “ Un attracteur étrange (?) du type attracteur de Hénon,” J. Phys.39, C5-C9.
[46] Lozi, R. [2012] “ Emergence of randomness from chaos,” Int. J. Bifurcation and Chaos22, 1250021-1-15. · Zbl 1270.65002
[47] Mangiarotti, S. & Letellier, C. [2015] “ Topological analysis for designing a suspension of the Hénon map,” Phys. Lett. A379, 3069-3074.
[48] Matsumoto, M. & Nishimura, T. [1998] “ Mersenne twister: A 623-dimensionally equidistributed uniform pseudo-random number generator,” ACM Trans. Model. Comput. Simul.8, 3-30. · Zbl 0917.65005
[49] Mitzenmacher, M. [2004] “ A brief history of generative models for power law and lognormal distributions,” Internet Math.1, 226-251. · Zbl 1063.68526
[50] Moravec, H. & Elfes, A. [1985] “ High resolution maps from wide angle sonar,” Proc. IEEE Int. Conf. Rob. Autom., pp. 116-121.
[51] Murphy, R., Berry, J., McLendon, W., Hendrickson, B., Gregor, D. & Lumsdaine, A. [2006] “ DFS: A simple to write yet difficult to execute benchmark,” Proc. IEEE Int. Symp. Workload Characterization, pp. 175-177.
[52] Newman, M. E., Strogatz, S. H. & Watts, D. J. [2001] “ Random graphs with arbitrary degree distributions and their applications,” Phys. Rev. E64, 026118.
[53] Panaite, P. & Pelc, A. [1999] “ Exploring unknown undirected graphs,” J. Algorithms33, 281-295. · Zbl 0957.68092
[54] Piyatumrong, A., Bouvry, P., Guinand, F. & Lavangnananda, K. [2009a] “ A study of token traversal strategies on tree-based backbones for mobile ad hoc — Delay tolerant networks,” Proc. IEEE Int. Conf. Ultra Modern Telecommunications (ICUMT), pp. 1-8.
[55] Piyatumrong, A., Ruiz, P., Bouvry, P., Guinand, F. & Lavangnananda, K. [2009b] “ Token traversal strategies of a distributed spanning forest algorithm in mobile ad hoc — Delay tolerant networks,” Proc. Int. Conf. Advances in Information Technology (IAIT) (Springer), pp. 96-109.
[56] Pluhacek, M., Senkerik, R. & Zelinka, I. [2015] “ PSO algorithm enhanced with Lozi chaotic map-tuning experiment,” AIP Conf. Proc., p. 550022.
[57] Richter, A., Bock, H., Fischler, W., Leisching, P., Krummrich, P., Mayer, A., Neuhauser, R., Elbers, J. & Glingener, C. [2001] “ Germany-wide DWDM field trial: Transparent connection of a long haul link and a multiclient metro network,” Optical Fiber Com. Conf., p. ML3.
[58] Rosalie, M. & Letellier, C. [2014] “ Toward a general procedure for extracting templates from chaotic attractors bounded by high genus torus,” Int. J. Bifurcation and Chaos24, 1450045-1-12. · Zbl 1296.37026
[59] Rosalie, M. [2016] “ Templates and subtemplates of Rössler attractors from a bifurcation diagram,” J. Phys. A: Math. Theor.49, 315101. · Zbl 1369.37048
[60] Rosalie, M., Danoy, G., Chaumette, S. & Bouvry, P. [2016] “ From random process to chaotic behavior in swarms of UAVs,” Proc. ACM Int. Symp. Design and Analysis of Intelligent Vehicular Networks and Applications (DIVANet 2016), pp. 9-15.
[61] Rössler, O. E. [1976] “ An equation for continuous chaos,” Phys. Lett. A57, 397-398. · Zbl 1371.37062
[62] Sanz-Arigita, E. J., Schoonheim, M. M., Damoiseaux, J. S., Rombouts, S. A., Maris, E., Barkhof, F., Scheltens, P. & Stam, C. J. [2010] “ Loss of ‘small-world’ networks in Alzheimer’s disease: Graph analysis of FMRI resting-state functional connectivity,” PLoS One5, e13788.
[63] Seaton, K. A. & Hackett, L. M. [2004] “ Stations, trains and small-world networks,” Physica A339, 635-644.
[64] Servetto, S. D. & Barrenechea, G. [2002] “ Constrained random walks on random graphs: Routing algorithms for large scale wireless sensor networks,” Proc. ACM Int. Workshop Wireless Sensor Networks and Applications, pp. 12-21.
[65] Shrikhande, K. V., White, I. M., Wonglumsom, D.-R., Gemelos, S. M., Rogge, M. S., Fukashiro, Y., Avenarius, M. & Kazovsky, L. G. [2000] “ HORNET: A packet-over-WDM multiple access metropolitan area ring network,” IEEE J. Sel. Areas Commun.18, 2004-2016.
[66] Sprott, J. & Li, C. [2017] “ Asymmetric bistability in the Rössler system,” Acta Phys. Pol. B48, 97.
[67] Starrett, J. [2012] “ Non-strange chaotic attractors equivalent to their templates,” Dyn. Syst.27, 187-196. · Zbl 1243.37030
[68] Tiddi, I., d’Aquin, M. & Motta, E. [2014] “ Walking linked data: A graph traversal approach to explain clusters,” Proc. Int. Conf. Consuming Linked Data-Volume 1264, pp. 73-84.
[69] Varrette, S., Bouvry, P., Cartiaux, H. & Georgatos, F. [2014] “ Management of an academic HPC cluster: The UL experience,” Proc. Int. Conf. High Performance Computing & Simulation (HPCS 2014), pp. 959-967.
[70] Wagner, I. A., Lindenbaum, M. & Bruckstein, A. M. [1999] “ Distributed covering by ant-robots using evaporating traces,” IEEE Trans. Rob. Autom.15, 918-933.
[71] Wagner, A. & Fell, D. A. [2001] “ The small world inside large metabolic networks,” Proc. Roy. Soc. London, Ser. B268, 1803-1810.
[72] Watts, D. J. & Strogatz, S. H. [1998] “ Collective dynamics of small-world networks,” Nature393, 440-442. · Zbl 1368.05139
[73] Wilcoxon, F. [1945] “ Individual comparisons by ranking methods,” Biometr. Bull.1, 80-83.
[74] Wong, A. K. & You, M. [1985] “ Entropy and distance of random graphs with application to structural pattern recognition,” IEEE Trans. Pattern Anal. Mach. Intell.7, 599-609. · Zbl 0564.05047
[75] Xiang, T., Liao, X. & Wong, K.-W. [2007] “ An improved particle swarm optimization algorithm combined with piecewise linear chaotic map,” Appl. Math. Comput.190, 1637-1645. · Zbl 1122.65363
[76] Yanovski, V., Wagner, I. A. & Bruckstein, A. M. [2001] “ Vertex-ant-walk — A robust method for efficient exploration of faulty graphs,” Ann. Math. Artif. Intell.31, 99-112. · Zbl 1314.68319
[77] Yook, S.-H., Oltvai, Z. N. & Barabási, A.-L. [2004] “ Functional and topological characterization of protein interaction networks,” Proteomics4, 928-942.
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.