Reference : Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics
Scientific journals : Article
Engineering, computing & technology : Computer science
Computational Sciences
http://hdl.handle.net/10993/34230
Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics
English
Changaival, Boonyarit mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Rosalie, Martin mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
Danoy, Grégoire mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Lavangnananda, Kittichai mailto [King Mongkut’s University of Technology Thonburi (Bangkok) > School of information and Technology (SIT)]
Bouvry, Pascal mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
30-Dec-2017
International Journal of Bifurcation and Chaos
World Scientific Pub Co Pte Lt
27
14
1750215
Yes (verified by ORBilu)
International
0218-1274
1793-6551
Singapore
Singapore
[en] Bifurcation diagram ; chaotic dynamics ; graph traversal ; random walk
[en] 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.
Researchers ; Students
http://hdl.handle.net/10993/34230
10.1142/S0218127417502157
http://www.worldscientific.com/doi/abs/10.1142/S0218127417502157?src=recsys
Preprint of an article published in [Int J Bifurcation Chaos Appl Sci Eng, 27, 14, 2017, 1750215] [10.1142/S0218127417502157] © [copyright World Scientific Publishing Company] [http://www.worldscientific.com/worldscinet/ijbc]

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
main-1.pdfAuthor preprint8.92 MBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.