×

Targeted influential nodes selection in location-aware social networks. (English) Zbl 1407.91209

Summary: Given a target area and a location-aware social network, the location-aware influence maximization problem aims to find a set of seed users such that the information spread from these users will reach the most users within the target area. We show that the problem is NP-hard and present an approximate algorithm framework, namely, TarIM-SF, which leverages on a popular sampling method as well as spatial filtering model working on arbitrary polygons. Besides, for the large-scale network we also present a coarsening strategy to further improve the efficiency. We theoretically show that our approximate algorithm can provide a guarantee on the seed quality. Experimental study over three real-world social networks verified the seed quality of our framework, and the coarsening-based algorithm can provide superior efficiency.

MSC:

91D30 Social networks; opinion dynamics
68Q25 Analysis of algorithms and problem complexity

Software:

SIMPATH; CELF++
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kempe, D.; Kleinberg, J.; Tardos, É., Maximizing the spread of influence through a social network, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’03) · doi:10.1145/956750.956769
[2] Chen, W.; Wang, C.; Wang, Y., Scalable influence maximization for prevalent viral marketing in large-scale social networks, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD · doi:10.1145/1835804.1835934
[3] Tang, Y.; Shi, Y.; Xiao, X., Influence maximization in near-linear time: a martingale approach, Proceedings of the ACM SIGMOD International Conference on Management of Data, (SIGMOD ’15) · doi:10.1145/2723372.2723734
[4] Li, G.; Chen, S.; Feng, J.; Tan, K.; Li, W., Efficient location-aware influence maximization, Proceedings of the the 2014 ACM SIGMOD international conference · doi:10.1145/2588555.2588561
[5] Goyal, A.; Lu, W.; Lakshmanan, L. V. S., SIMPATH: An efficient algorithm for influence maximization under the Linear Threshold model, Proceedings of the 11th IEEE International Conference on Data Mining, ICDM 2011
[6] Jung, K.; Heo, W.; Chen, W., IRIE: Scalable and robust influence maximization in social networks, Proceedings of the 12th IEEE International Conference on Data Mining, ICDM 2012
[7] MacKay, D. J. C., Introduction to monte carlo methods, Learning in Graphical Models, 30, 90, 175-204 (1998) · Zbl 0911.65004 · doi:10.1007/978-94-011-5014-9
[8] Leskovec, J.; Krause, A.; Guestrin, C.; Faloutsos, C.; Vanbriesen, J.; Glance, N., Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’07) · doi:10.1145/1281192.1281239
[9] Minoux, M., Accelerated greedy algorithms for maximizing submodular set functions, Optimization Techniques, 234-243 (1978) · Zbl 0372.90128
[10] Goyal, A.; Lu, W.; Lakshmanan, L. V. S., CELF++: optimizing the greedy algorithm for influence maximization in social networks, Proceedings of the 20th International Conference Companion on World Wide Web, (WWW ’11) · doi:10.1145/1963192.1963217
[11] Ohsaka, N.; Akiba, T.; Yoshida, Y.; Kawarabayashi, K. I., Fast and accurate influence maximization on large networks with pruned monte-carlo simulations, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI Press
[12] Cheng, S.; Shen, H.; Huang, J.; Zhang, G.; Cheng, X., StaticGreedy, Proceedings of the the 22nd ACM international conference · doi:10.1145/2505515.2505541
[13] Kimura, M.; Saito, K.; Nakano, R., Extracting influential nodes for information diffusion on a social network, Proceedings of the National Conference on Artificial Intelligence, AAAI Press
[14] Liu, X.; Li, M.; Li, S.; Peng, S.; Liao, X.; Lu, X., IMGPU: GPU-accelerated influence maximization in large-scale social networks, IEEE Transactions on Parallel and Distributed Systems, 25, 1, 136-145 (2014) · doi:10.1109/TPDS.2013.41
[15] Wang, Y.; Cong, G.; Song, G.; Xie, K., Community-based Greedy algorithm for mining top-K influential nodes in mobile social networks, Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’10), ACM · doi:10.1145/1835804.1835935
[16] Borgs, C.; Brautbar, M.; Chayes, J.; Lucier, B., Maximizing social influence in nearly optimal time, Proceedings of the ACM-SIAM, ACM-SIAM · Zbl 1420.68248 · doi:10.1137/1.9781611973402.70
[17] Tang, Y.; Xiao, X.; Shi, Y., Influence maximization: Near-optimal time complexity meets practical efficiency, Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD 2014
[18] Nguyen, H. T.; Thai, M. T.; Dinh, T. N., Stop-and-Stare: Optimal sampling algorithms for viral marketing in billion-scale networks, Proceedings of the 2016 ACM SIGMOD International Conference on Management of Data, SIGMOD 2016
[19] Huang, K.; Wang, S.; Bevilacqua, G.; Xiao, X.; Lakshmanan, L. V. S., Revisiting the Stop-and-Stare algorithms for influence maximization, Proceedings of the 43rd International Conference on Very Large Data Bases, VLDB 2017
[20] Dinh, T.; Nguyen, H.; Ghosh, P.; Mayo, M., Social influence spectrum with guarantees: computing more in less time, Computational Social Networks. Computational Social Networks, Lecture Notes in Computer Science, 9197, 84-103 (2015), Cham: Springer International Publishing, Cham · doi:10.1007/978-3-319-21786-4_8
[21] Nguyen, H. T.; Dinh, T. N.; Thaip, M. T., Cost-aware Targeted Viral Marketing in billion-scale networks, Proceedings of the IEEE INFOCOM 2016 - IEEE Conference on Computer Communications · doi:10.1109/INFOCOM.2016.7524377
[22] Liu, Y.; Pi, D.; Cui, L., Mining community-Level influence in microblogging network: A case study on sina weibo, Complexity, 2017 (2017) · Zbl 1382.91068
[23] Li, J.; Wang, X.; Deng, K., Most influential commuity search over large social networks, ICDE, IEEE, 871-882 (2017)
[24] Alduaiji, N.; Datta, A.; Li, J., Influence propagation model for clique-based community detection in social networks, IEEE Transactions on Computational Social Systems, 5, 2, 563-575 (2018) · doi:10.1109/TCSS.2018.2831694
[25] Li, Y.; Zhang, D.; Tan, K.-L., Real-time targeted influence maximization for online advertisements, Proceedings of the Vldb Endowment
[26] Chen, S.; Fan, J.; Li, G.; Feng, J.; Tan, K.-L.; Tang, J., Online topic-aware influence maximization, Proceedings of the 41st International Conference on Very Large Data Bases, VLDB 2015
[27] Wang, X.; Zhang, Y.; Zhang, W.; Lin, X., Efficient Distance-Aware Influence Maximization in Geo-Social Networks, IEEE Transactions on Knowledge and Data Engineering, 29, 3, 599-612 (2017) · doi:10.1109/TKDE.2016.2633472
[28] Zhong, M.; Zeng, Q.; Zhu, Y.; Li, J.; Qian, T., Sample location selection for efficient distance-aware influence maximization in geo-social networks, Database Systems for Advanced Applications. Database Systems for Advanced Applications, Lecture Notes in Computer Science, 10827, 355-371 (2018), Cham: Springer International Publishing, Cham · doi:10.1007/978-3-319-91452-7_24
[29] Zhu, W.; Peng, W.; Chen, L.; Zheng, K.; Zhou, X., Exploiting viral marketing for location promotion in location-based social networks, ACM Transactions on Knowledge Discovery from Data (TKDD), 11, 2, 1-28 (2016) · doi:10.1145/3001938
[30] Zhou, T.; Cao, J.; Liu, B.; Xu, S.; Zhu, Z.; Luo, J., Location-based influence maximization in social networks, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management · doi:10.1145/2806416.2806462
[31] Li, J.; Sellis, T.; Culpepper, J. S.; He, Z.; Liu, C.; Wang, J., Geo-social influence spanning maximization, IEEE Transactions on Knowledge and Data Engineering, 29, 8, 1653-1666 (2017) · doi:10.1109/TKDE.2017.2690288
[32] Li, X.; Cheng, X.; Su, S.; Sun, C., Community-based seeds selection algorithm for location aware influence maximization, Neurocomputing, 275, 1601-1613 (2018) · doi:10.1016/j.neucom.2017.10.007
[33] Guo, L.; Zhang, D.; Cong, G.; Wu, W.; Tan, K.-L., Influence maximization in trajectory databases, IEEE Transactions on Knowledge and Data Engineering, 29, 3, 627-641 (2017) · doi:10.1109/TKDE.2016.2621038
[34] Zhang, D.; Guo, L.; Nie, L.; Shao, J.; Wu, S.; Shen, H. T., Targeted advertising in public transportation systems with quantitative evaluation, ACM Transactions on Information and System Security, 35, 3, 1-29 (2017) · doi:10.1145/3003725
[35] Li, J.; Liu, C.; Yu, J. X.; Chen, Y.; Sellis, T.; Culpepper, J. S., Personalized influential topic search via social network summarization, IEEE Transactions on Knowledge and Data Engineering, 28, 7, 1820-1834 (2016) · doi:10.1109/TKDE.2016.2542804
[36] Su, S.; Li, X.; Cheng, X.; Sun, C., Location-aware targeted influence maximization in social networks, Journal of the Association for Information Science and Technology, 69, 2, 229-241 (2018)
[37] Ohsaka, N.; Sonobe, T.; Fujita, S.; Kawarabayashi, K.-I., Coarsening massive influence networks for scalable diffusion analysis, Proceedings of the 2017 ACM SIGMOD International Conference on Management of Data, SIGMOD 2017
[38] Graham, R. L., An efficient algorithm for determining the convex hull of a finite planar set, Information Processing Letters, 1, 4, 132-133 (1972) · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2
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.