Extending ACO for fast path search in huge graphs and social networks

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.