Publication: Extending ACO for fast path search in huge graphs and social networks
Loading...
Identifiers
Publication date
2017-11-15
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
Impact
Export
Abstract
This paper presents the bio-inspired algorithm SoSACO-v2 that is explained as an extension of the Ant Colony Optimization in which the ants are empowered with the sense of smell, directing them straightly to privileged nodes when they are near enough of them. This algorithm is an evolution of a former version which main feature is efficiency through path search task in huge graphs of high connectivity. New requirements regarding this task in most applications include processing vast graphs, immediate comeback, and dealing with dynamicity. The here proposed algorithm gives response to new needs the former approaches cannot fulfill: fast finding of paths between two nodes through vast dynamic graphs. SoSACO-v2 does not provide the optimum path, but it is the quicker algorithm in providing a response. It stands for domains where optimality is not required, and often the path search takes more time than covering the path. The approach is evaluated, both in a generic huge graph and in a small-world type graph from a real social network, showing satisfactory results.
Description
Keywords
Huge Graphs, Aco, Bio inspired algorithms, Path search, Social networks
Bibliographic citation
Calle, J., Rivero, J., Cuadra, D., Isasi, P. (2017). Extending ACO for fast path search in huge graphs and social networks. Expert Systems with Applications, 86, pp. 292-306