Search social networks based on the behavior of ants
Researchers at Carlos III University of Madrid (Universidad Carlos III de Madrid, UC3M) developed an algorithm based on the behavior of ants when searching for food. This algorithm, according to the authors, accelerates the search for links between elements of social networks.
One of the main technical issues in the field of social networks, which are becoming more and more diverse, is the search for a chain of connections that leads from one person to another. The greatest problem here is the huge size of such networks. At the same time, the search result should be received relatively quickly, as the end user expects to receive a quick response to his query. To solve this problem, researchers from UC3M have developed an algorithm SoSACO, accelerating the search for a path between two nodes of the graph representing the selected social network.
The principles of SoSACO are based on the behavior that has been honed over the millennia by the most disciplined of insects on our planet when searching for food. The algorithms used by ant colonies allow them to find a shortcut between the anthill and the food source. Ants mark the path to food with chemicals called pheromones. “In our study,” the authors explain, “in addition to the paths marked with pheromones, we created paths labeled with the smell of food, which allowed ants to find food much faster.” The main results of this study, conducted by Jessica Riviero in the laboratory LABDA (Laboratorio de Bases de Datos Avanzadas) as part of her doctoral dissertation, are given in the article “Using the ACO algorithm for searching in social networks ”), published in the journal Applied Intelligence.
')
"The first results obtained show that the use of this algorithm in real social networks allows you to get the optimal answer in a very short time (tens of milliseconds)", - Jessica Riviero.
Possible applications
Thanks to the developed algorithm, you can quickly find the path (chain of connections) between elements of social networks, without changing the structure of the graph, whose vertices and edges correspond to the elements of a social network and the connections between them, respectively. “This breakthrough will allow us to solve many applied problems, since many systems and situations can be modeled using graphs,” the researchers explain. The developed algorithm can be used, for example, to find the best routes in freight planning systems, or in computer games, or to determine the degree of semantic proximity of two words, or to find out how many common friends two Facebook or Twitter users have.
This research, supported by the authorities of the autonomous community of Madrid (MA2VICMR, S2009 / TIC-1542) and the Spanish Ministry of Education and Science (Ministerio de Educación y Ciencia) began as part of the SOPAT project (TSI-020110-2009-419) creation of a navigation system for hotel guests. Jessica Riviero’s doctoral thesis on this topic is called “Búsqueda Rápida de Caminos en Grafos de Alta Cardinalidad Estáticos y Dinámicos” (“Fast path finding in large static and dynamic graphs”). The work was led by Francisco Javier Calle Dolores Cuadra, one of the professors of the LABDA laboratory. In February 2012, Jessica successfully defended her dissertation work.
Original article: "A search engine for
Links
Source: https://habr.com/ru/post/145567/
All Articles