Preprocessing Rules for Target Set Selection in Complex Networks

• Renato Silva Melo UFPR
• André Luís Vignatti UFPR

DOI: https://doi.org/10.5753/brasnam.2020.11167

Resumo

In the Target Set Selection (TSS) problem, we want to find the minimum set of individuals in a network to spread information across the entire network. This problem is NP-hard, so find good strategies to deal with it, even for a particular case, is something of interest. We introduce preprocessing rules that allow reducing the size of the input without losing the optimality of the solution when the input graph is a complex network. Such type of network has a set of topological properties that commonly occurs in graphs that model real systems. We present computational experiments with real-world complex networks and synthetic power law graphs. Our strategies do particularly well on graphs with power law degree distribution, such as several real-world complex networks. Such rules provide a notable reduction in the size of the problem and, consequently, gains in scalability.

Palavras-chave: Influence Propagation, Social Networks, Combinatorial Optimization

Referências

Ackerman, E., Ben-Zwi, O., and Wolfovitz, G. (2010). Combinatorial model and boundsfor target set selection. Theoretical Computer Science, 411(44-46):4017–4022.

Aiello, W., Chung, F., and Lu, L. (2001). A random graph model for power law graphs. Experimental Mathematics, 10(1):53–66.

Bollob ́as, B., Borgs, C., Chayes, J., and Riordan, O. (2003). Directed scale-free graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 132-139. Society for Industrial and Applied Mathematics.

Chen, N. (2009). On the approximability of influence in social networks. SIAM Journalon Discrete Mathematics, 23(3):1400–1415.

Chen, W., Wang, C., and Wang, Y. (2010a). Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACMSIGKDD international conference on Knowledge discovery and data mining, pages1029–1038. ACM.

Chen, W., Wang, Y., and Yang, S. (2009). Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199–208. ACM.

Chen, W., Yuan, Y., and Zhang, L. (2010b). Scalable influence maximization in social networks under the linear threshold model. In Data Mining (ICDM), 2010 IEEE 10th International Conference on, pages 88–97. IEEE.

Choromanski, K., Matuszak, M., and Miekisz, J. (2013). Scale-free graph with preferential attachment and evolving internal vertex structure. J Stat Phys, 151:1782-1789.

Clauset, A., Shalizi, C. R., and Newman, M. E. (2009). Power-law distributions in empirical data. SIAM review, 51(4):661-703.

Domingos, P. and Richardson, M. (2001). Mining the network value of customers. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 57-66. ACM.

Goyal, A., Bonchi, F., and Lakshmanan, L. V. (2011a). A data-based approach to social influence maximization. Proceedings of the VLDB Endowment, 5(1):73–84.

Goyal, A., Lu, W., and Lakshmanan, L. V. (2011b). Simpath: An efficient algorithm for influence maximization under the linear threshold model. In Data Mining (ICDM),2011 IEEE 11th International Conference on, pages 211-220. IEEE.

Granovetter, M. (1978). Threshold models of collective behavior. American journal of sociology, pages 1420–1443.

Kempe, D., Kleinberg, J., and Tardos, ́E. (2003). Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146. ACM.

Leskovec, J. and Krevl, A. (2014). SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data.

Liu, X., Li, S., Liao, X., Peng, S., Wang, L., and Kong, Z. (2014). Know by a handful the whole sack: efficient sampling for top-k influential user identification in large graphs. World Wide Web, 17(4):627.

Melo, R. S. and Vignatti, A. L. (2018). A preselection algorithm for the influence maximization problem in power law graphs. In Proceedings of the 33rd Annual ACM Symposium on Applied Computing, pages 1782–1789. ACM.

Michail, D., Kinable, J., Naveh, B., and Sichi, J. V. (2019). Jgrapht - a java library for graph data structures and algorithms. arXiv preprint arXiv:1904.08355.

Mitzenmacher, M. and Upfal, E. (2005). Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press.

Tang, Y., Xiao, X., and Shi, Y. (2014). Influence maximization: Near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 75-86. ACM.

Wang, F., Du, H., Camacho, E., Xu, K., Lee, W., Shi, Y., and Shan, S.(2011). On positive influence dominating sets in social networks. Theoretical Computer Science, 412(3):265-269.

Zhang, W., Wu, W., Wang, F., and Xu, K. (2012). Positive influence dominating sets in power-law graphs. Social Network Analysis and Mining, 2(1):31-37.