Abstract
With the popularity of location-based information sharing in social networks, more and more businesses are trying to advertise their products online. In reality, users are more likely to choose a shopping location that is affordable in price and near in distance, while businesses hope to maximize the number of potential users through a geo-social network. Here the affordable ability for each user is defined as budget. There is an urgent need to fast find a certain number of influencers, so as to influence as many users as possible, which is called the Budget-Distance-Aware Influence Maximization (BDAIM) problem. To overcome this challenge, we propose a BDAIM model and design four pruning rules that can remove low-influence users to reduce time complexity. Then, we develop an algorithm with a \(1-1/e\) approximation ratio to find high-influence users by combining these pruning rules. Finally, extensive experimental results on real-world datasets have demonstrated the efficiency and effectiveness of proposed methods.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Berman, O., Krass, D., Drezner, Z.: The gradual covering decay location problem on a network. Eur. J. Oper. Res. 151(3), 474–480 (2003)
Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029–1038 (2010)
Chen, X., Zhao, Y., Liu, G., Sun, R., Zhou, X., Zheng, K.: Efficient similarity-aware influence maximization in geo-social network. IEEE Trans. Knowl. Data Eng. 1 (2020). https://doi.org/10.1109/TKDE.2020.3045783
Li, G., Chen, S., Feng, J., Tan, K.l., Li, W.S.: Efficient location-aware influence maximization. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 87–98 (2014)
Li, X., Cheng, X., Su, S., Sun, C.: Community-based seeds selection algorithm for location aware influence maximization. Neurocomputing 275, 1601–1613 (2018)
Nail, J., Charron, C., Baxter, S.: The consumer advertising backlash. Forrester research and intelliseek market research report 137 (2004)
Shi, Q., Wang, C., Chen, J., Feng, Y., Chen, C.: Location driven influence maximization: online spread via offline deployment. Knowl.-Based Syst. 166, 30–41 (2019)
Su, S., Li, X., Cheng, X., Sun, C.: Location-aware targeted influence maximization in social networks. J. Assoc. Inf. Sci. Technol. 69(2), 229–241 (2018)
Wang, X., Zhang, Y., Zhang, W., Lin, X.: Distance-aware influence maximization in geo-social network. In: ICDE, pp. 1–12 (2016)
Wang, Y., Li, Y., Fan, J., Tan, K.L.: Location-aware influence maximization over dynamic social streams. ACM Trans. Inf. Syst. 36(4), 1–35 (2018)
Zhu, W., Yang, W., Xuan, S., Man, D., Wang, W., Lv, J.: Location-aware targeted influence blocking maximization in social networks. In: 2019 28th International Conference on Computer Communication and Networks (ICCCN), pp. 1–9. IEEE (2019)
Acknowledgement
This work is financially supported by the National Key R&D Program of China under Grant No.2017YFB0803002 and National Natural Science Foundation of China under Grant No. 61732022.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Gu, Y., Yao, X., Liang, G., Gu, C., Huang, H. (2021). Efficient Budget-Distance-Aware Influence Maximization in Geo-Social Network. In: Liu, Z., Wu, F., Das, S.K. (eds) Wireless Algorithms, Systems, and Applications. WASA 2021. Lecture Notes in Computer Science(), vol 12939. Springer, Cham. https://doi.org/10.1007/978-3-030-86137-7_31
Download citation
DOI: https://doi.org/10.1007/978-3-030-86137-7_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86136-0
Online ISBN: 978-3-030-86137-7
eBook Packages: Computer ScienceComputer Science (R0)