Development of an Algorithm for Searching Specific Vertices in Networks
Abstract
Many real networks are not immediately available but can be collected through a mining process. However, in some scenarios we are only interested in the discovery of vertices that have certain features. The others vertices are irrelevant. For this problem, classic algorithms (ex. breadth-first search) are inefficient. In this paper we use the homophily inherent in many real networks to propose a mathematical model that determines the probability of an unexplored vertex to have the feature. This model uses the features of the neighbor vertices already explored and global parameters of the network. The probabilities assigned by the model are used to guide an informed search, which at each step makes a greedy choice. We evaluated the algorithm in three real networks comparing different variations of the model and others search algorithms. The results show that none of considered methods is consistently more efficient than the others.
References
Avrachenkov, K., Basu, P., Neglia, G., and Ribeiro, B. (2014). Pay Few, Influence Most: Online Myopic Network Covering. In Computer Communications Workshops (INFO-COM WKSHPS), 2014 IEEE Conference on.
Bnaya, Z., Puzis, R., Stern, R., and Felner, A. (2013). Bandit algorithms for social network queries. In Social Computing (SocialCom), 2013 International Conference on, pages 148–153. IEEE.
Bondy, J. A. and Murty, U. S. R. (1976). Graph Theory with Applications. Macmillan/Elsevier, 5 edition. ISBN 0-44-19451-7.
Garnett, R., Krishnamurthy, Y., Xiong, X., Schneider, J., and Mann, R. (2012). Bayesian optimal active search and surveying. In International Conference on Machine Learning, ACM, pages 1239–1246.
Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. [link].
Ma, Y., Huang, T.-K., and Schneider, J. G. (2015). Active Search and Bandits on Graphs using Sigma-Optimality. In Conference on Uncertainty Artificial Inteligence, pages 542–551.
Murai, F., Renno, D., Ribeiro, B., Gisele, P., Towsley, D., and Gile, K. (2017). Selective Harvesting over Networks. arXiv preprint arXiv:1703.05082.
Netto, P. O. B. (1996). Grafos: teoria, modelos, algoritmos. Edgard Blücher.
Pfeiffer, J. J., Neville, J., and Bennett, P. (2012). Active sampling of networks. In Workshop on Mining and Learning with Graphs.
Russel, S. and Norvig, P. (2003). Artificial intelligence: A modern approach. EUA: Prentice Hall.
Wang, X., Garnett, R., and Schneider, J. (2013). Active Search on Graphs. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 731–738. ACM.
Xie, P., Zhu, J., and Xing, E. P. (2016). Diversity-promoting bayesian learning of latent variable models. In International Conference on Machine Learning.
