Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics
บทความในวารสาร
ผู้เขียน/บรรณาธิการ
กลุ่มสาขาการวิจัยเชิงกลยุทธ์
ไม่พบข้อมูลที่เกี่ยวข้อง
รายละเอียดสำหรับงานพิมพ์
รายชื่อผู้แต่ง: Changaival B., Rosalie M., Danoy G., Lavangnananda K., Bouvry P.
ผู้เผยแพร่: World Scientific Publishing
ปีที่เผยแพร่ (ค.ศ.): 2017
วารสาร: International Journal of Bifurcation and Chaos in Applied Sciences and Engineering (0218-1274)
Volume number: 27
Issue number: 14
นอก: 0218-1274
eISSN: 1793-6551
ภาษา: English-Great Britain (EN-GB)
ดูในเว็บของวิทยาศาสตร์ | ดูบนเว็บไซต์ของสำนักพิมพ์ | บทความในเว็บของวิทยาศาสตร์
บทคัดย่อ
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. ฉ 2017 World Scientific Publishing Company.
คำสำคัญ
Bifurcation diagram, chaotic dynamics, graph traversal, random walk
ติดต่อสอบถามเพิ่มเติมได้ที่