Reference : Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics

	Document type :	Scientific journals : Article
	Discipline(s) :	Engineering, computing & technology : Computer science
	Focus Areas :	Computational Sciences
	To cite this reference:	http://hdl.handle.net/10993/34230

Title :	Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics
Language :	English
Author, co-author :	Changaival, Boonyarit [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Rosalie, Martin [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > >]
	Danoy, Grégoire [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Lavangnananda, Kittichai [King Mongkut’s University of Technology Thonburi (Bangkok) > School of information and Technology (SIT)]
	Bouvry, Pascal [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Publication date :	30-Dec-2017
Journal title :	International Journal of Bifurcation and Chaos
Publisher :	World Scientific Pub Co Pte Lt
Volume :	27
Issue/season :	14
Pages :	1750215
Peer reviewed :	Yes (verified by ORBilu)
Audience :	International
ISSN :	0218-1274
e-ISSN :	1793-6551
City :	Singapore
Country :	Singapore
Keywords :	[en] Bifurcation diagram ; chaotic dynamics ; graph traversal ; random walk
Abstract :	[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.
Target :	Researchers ; Students
Permalink :	http://hdl.handle.net/10993/34230
DOI :	10.1142/S0218127417502157
Other URL :	http://www.worldscientific.com/doi/abs/10.1142/S0218127417502157?src=recsys
Mentions required by the publisher for OA :	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): File Commentary Version Size Access Limited access main-1.pdf Author preprint 8.92 MB Request a copy

All documents in ORBi^lu are protected by a user license.

 

University of Luxembourg Library |  Feedback |  Legal notices Site Map