Caliò, Antonio; Tagarelli, Andrea Attribute based diversification of seeds for targeted influence maximization. (English) Zbl 1479.91278 Inf. Sci. 546, 1273-1305 (2021). This paper studies attribute based diversification of seeds for targeted influence maximization. The emphasis is on the categorical attribute-based diversity of the seeds. The problem of attribute-based diversity-sensitive targeted influence maximization is proposed. The node set is associated with a categorical dataset describing the profiles of nodes. A class of non-decreasing and sub-modular functions are designed to represent the categorical diversity. A solution to the attribute-based diversity-sensitive targeted influence maximization problem is provided under the reverse influence sampling approach. Both the diversity awareness and the targeted nature of the attribute-based diversity-sensitive targeted influence maximization problem have been tackled. Based on the triggering model, a algorithm regarding attribute-based diversity-sensitive targeted influence maximization has been proposed which gives a \(k\)-seed with certain approximation ratio with high probability. Numerical experiments have been conducted to illustrate the proposed method. Reviewer: Yilun Shang (Newcastle) Cited in 5 Documents MSC: 91D30 Social networks; opinion dynamics Keywords:diversity in influence maximization; monotone submodular categorical set functions; reverse influence sampling; viral marketing; social recommendation Software:SIMPATH; CoFIM PDFBibTeX XMLCite \textit{A. Caliò} and \textit{A. Tagarelli}, Inf. Sci. 546, 1273--1305 (2021; Zbl 1479.91278) Full Text: DOI References: [1] Aslay, Ç.; Matakos, A.; Galbrun, E.; Gionis, A., Maximizing the diversity of exposure in a social network, Proc. IEEE Int. Conf. on Data Mining (ICDM), 863-868 (2018) [2] Banerjee, S.; Jenamani, M.; Pratihar, D. K., ComBIM: a community-based solution approach for the Budgeted Influence Maximization Problem, Expert Syst. Appl., 125, 1-13 (2019) [3] Q. Bao, W. K. Cheung, Y. Zhang, Incorporating structural diversity of neighbors in a diffusion model for social networks, in: Proc. IEEE/WIC/ACM Int. Conf. on Web Intelligence, 2013, pp. 431-438. [4] C. Borgs, M. Brautbar, J. Chayes, B. Lucier, Maximizing social influence in nearly optimal time, in: Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2014, pp. 946-957. · Zbl 1420.68248 [5] Bozorgi, A.; Haghighi, H.; Zahedi, M. S.; Rezvani, M., INCIM: a community-based algorithm for influence maximization problem under the linear threshold model, Inf. Process. Manage., 52, 6, 1188-1199 (2016) [6] Caliò, A.; Interdonato, R.; Pulice, C.; Tagarelli, A., Topology-driven diversity for targeted influence maximization with application to user engagement in social networks, IEEE Trans. Knowl. Data Eng., 30, 12, 2421-2434 (2018) [7] Caliò, A.; Tagarelli, A.; Bonchi, F., Cores matter? An analysis of graph decomposition effects on influence maximization problems, (Proc. 12th ACM Conf. on Web Science (WebSci) (2020)), 184-193 [8] Chen, S.; Fan, J.; Li, G.; Feng, J.; Tan, K.; Tang, J., Online topic-aware influence maximization, PVLDB, 8, 6, 666-677 (2015) [9] Chen, W.; Wang, C.; Wang, Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks, (Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD) (2010)), 1029-1038 [10] Chen, W.; Yuan, Y.; Zhang, L., Scalable influence maximization in social networks under the linear threshold model, Proc. IEEE Int. Conf. on Data Mining (ICDM), 88-97 (2010) [11] Y. Chen, W. Zhu, W. Peng, W. Lee, S. Lee, CIM: community-based influence maximization in social networks, ACM TIST, 5(2) (2014) 25:1-25:31 [12] Cover, T. M.; Thomas, J. A., Elements of Information Theory (2006), John Wiley & Sons Inc · Zbl 1140.94001 [13] Deng, X.; Pan, Y.; Shen, H.; Gui, J., Credit distribution for influence maximization in online social networks with node features, J. Intell. Fuzzy Syst., 31, 2, 979-990 (2016) [14] Y.-H. Fu, C.-Y. Huang, C.-T. Sun, Using global diversity and local topology features to identify influential network spreaders, Phys. A Stat. Mech. Appl. 433 (C) (2015) 344-355. [15] Fujishige, S., Polymatroid dependence structure of a set of random variables, Inf. Contr., 39, 55-72 (1978) · Zbl 0388.94006 [16] Goyal, A.; Lu, W.; Lakshmanan, L. V.S., Simpath: an efficient algorithm for influence maximization under the linear threshold model, (2011 IEEE 11th International Conference on Data Mining (2011)), 211-220 [17] Gursoy, F.; Günneç, D., Influence maximization in social networks under deterministic linear threshold model, Knowl.-Based Syst., 161, 111-123 (2018) [18] Huang, H.; Shen, H.; Meng, Z.; Chang, H.; He, H., Community-based influence maximization for viral marketing, Appl. Intell., 49, 6, 2137-2150 (2019) [19] P. Huang, H. Liu, C. Chen, P. Cheng, The impact of social diversity and dynamic influence propagation for identifying influencers in social networks, in: Proc. IEEE/WIC/ACM Int. Conf. on Web Intelligence, 2013, pp. 410-416 [20] R. Interdonato, C. Pulice, A. Tagarelli, Got to have faith!: The DEvOTION algorithm for delurking in social networks, in: Proc. IEEE/ACM Int. Conf. on Advances in Social Networks Analysis and Mining (ASONAM), 2015, pp. 314-319 [21] D. Kempe, J. M. Kleinberg, É. Tardos, Maximizing the spread of influence through a social network, in: Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD), 2003, pp. 137-146 · Zbl 1337.91069 [22] Kim, D.; Hyeon, D.; Oh, J.; Han, W.; Yu, H., Influence maximization based on reachability sketches in dynamic graphs, Inf. Sci., 394, 217-231 (2017) [23] Kumar, S.; Hamilton, W. L.; Leskovec, J.; Jurafsky, D., Community interaction and conflict on the web, (Proceedings of the 2018 World Wide Web Conference on World Wide Web (2018)), 933-943 [24] Lagnier, C.; Denoyer, L.; Gaussier, E.; Gallinari, P., Predicting information diffusion in social networks using content and user’s profiles, Proc. European Conf. on Information Retrieval (ECIR), 74-85 (2013) [25] Lee, J.; Chung, C., A query approach for influence maximization on specific users in social networks, IEEE Trans. Knowl. Data Eng., 27, 2, 340-353 (2015) [26] Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; VanBriesen, J. M.; Glance, N., Cost-effective outbreak detection in networks, (Proc. ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD) (2007)), 420-429 [27] Li, H.; Bhowmick, S.; Sun, A.; Cui, J., Conformity-aware influence maximization in online social networks, VLDB J., 24, 117-141 (2015) [28] Li, X.; Cheng, X.; Su, S.; Sun, C., Community-based seeds selection algorithm for location aware influence maximization, Neurocomputing, 275, 1601-1613 (2018) [29] Li, X.; Smith, J. D.; Dinh, T. N.; Thai, M. T., Why approximate when you can get the exact? Optimal targeted viral marketing at scale, Proc. IEEE Conf. on Computer Communications (INFOCOM), 1-9 (2017) [30] Li, Y.; Fan, J.; Wang, Y.; Tan, K., Influence maximization on social graphs: a survey, IEEE Trans. Knowl. Data Eng., 30, 10, 1852-1872 (2018) [31] Li, Y.; Gan, X.; Fu, L.; Tian, X.; Qin, Z.; Zhou, Y., Conformity-aware influence maximization with user profiles, (Proc. Int. Conf. on Wireless Communications and Signal Processing (WCSP) (2018)), 1-6 [32] Li, Y.; Zhang, D.; Tan, K.-L., Real-time targeted influence maximization for online advertisements, Proc. VLDB Endow., 8, 10, 1070-1081 (2015) [33] Lovász, L., Submodular functions and convexity, (Bachem, A.; Korte, B.; Grötschel, M., Mathematical Programming: The State of the Art (1983), Springer-Verlag: Springer-Verlag Berlin Heidelberg), 235-257 · Zbl 0566.90060 [34] Lu, W.; Chen, W.; Lakshmanan, L. V.S., From competition to complementarity: Comparative influence diffusion and maximization, Proc. VLDB Endow., 9, 2, 60-71 (2015) [35] Lu, W.; Lakshmanan, L. V.S., Profit maximization over social networks, Proc. IEEE Int. Conf. on Data Mining (ICDM), 479-488 (2012) [36] Nemhauser, G. L.; Wolsey, L. A.; Fisher, M. L., An analysis of approximations for maximizing submodular set functions, Math. Program., 14, 1, 265-294 (1978) · Zbl 0374.90045 [37] Nguyen, H. T.; Dinh, T. N.; Thai, M. T., Cost-aware targeted viral marketing in billion-scale networks, Proc. IEEE Conf. on Computer Communications (INFOCOM), 1-9 (2016) [38] Nguyen, H. T.; Thai, M. T.; Dinh, T. N., Stop-and-Stare: optimal sampling algorithms for viral marketing in billion-scale networks, (Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD) (2016)), 695-710 [39] Nguyen, L. N.; Zhou, K.; Thai, M. T., Influence maximization at community level: a new challenge with non-submodularity, Proc. IEEE Int. Conf. on Distributed Computing Systems (ICDCS), 327-337 (2019) [40] Padmanabhan, M. R.; Somisetty, N.; Basu, S.; Pavan, A., Influence maximization in social networks with non-target constraints, Proc. IEEE Int. Conf. on Big Data, 771-780 (2018) [41] A. Prasad, S. Jegelka, D. Batra, Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. arXiv CoRR, abs/1411.1752, 2014. [42] Qiu, L.; Jia, W.; Yu, J.; Fan, X.; Gao, W., PHG: a three-phase algorithm for influence maximization based on community structure, IEEE Access, 7, 62511-62522 (2019) [43] Shang, J.; Zhou, S.; Li, X.; Liu, L.; Wu, H., Cofim: a community-based framework for influence maximization on large-scale networks, Knowl.-Based Syst., 117, 88-100 (2017) [44] Singh, S. S.; Kumar, A.; Singh, K.; Biswas, B., C2im: community based context-aware influence maximization in social networks, Physica A, 514, 796-818 (2019) · Zbl 07562416 [45] A. Stoica, A. Chaintreau, Fairness in social influence maximization, in: Proc. ACM Conf. on World Wide Web (WWW), 2019, pp. 569-574. [46] F. Tang, Q. Liu, H. Zhu, E. Chen, F. Zhu, Diversified social influence maximization, in: Proc. IEEE/ACM Int. Conf. on Advances in Social Networks Analysis and Mining (ASONAM), 2014, pp. 455-459. [47] Tang, J.; Tang, X.; Yuan, J., Profit maximization for viral marketing in online social networks: algorithms and analysis, IEEE Trans. Knowl. Data Eng., 30, 6, 1095-1108 (2018) [48] Y. Tang, Y. Shi, X. Xiao, Influence maximization in near-linear time: a martingale approach, in: Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD), 2015, pp. 1539-1554 [49] Y. Tang, X. Xiao, Y. Shi, Influence maximization: near-optimal time complexity meets practical efficiency, in: Proc. ACM SIGMOD Int. Conf. on Management of Data (SIGMOD), 2014, pp. 75-86. [50] Zhang, K.; Zhang, Z.; Wu, Y.; Xu, J.; Niu, Y., A core theory based algorithm for influence maximization in social networks, (2017 IEEE International Conference on Computer and Information Technology (CIT) (2017)), 31-36 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.