Efficient Sample Location Selection for Query Zone in Geo-Social Networks
Authors: 
Kejian Tang, Shaohui Zhan, Tao Zhan, Hui Zhu, Qian Zeng, Ming Zhong, Xiaoyu Zhu, Yuanyuan Zhu, Jianxin Li, Tieyun Qian Academic Editor: Rosa M. BenitoAuthors Info & Claims
Abstract
While promoting a business or activity in geo-social networks, the geographical distance between its location and users is critical. Therefore, the problem of Distance-Aware Influence Maximization (DAIM) has been investigated recently. The efficiency of DAIM heavily relies on the sample location selection. Specifically, the online seeding performance is sensitive to the distance between the promoted location and its nearest sample location, and the offline precomputation performance is sensitive to the number of sample locations. However, there is no work to fully study the problem of sample location selection for DAIM in geo-social networks. To do this, we first formalize the problem under a reasonable assumption that a promoted location always adheres to the distribution of users (query zone). Then, we propose two efficient location sampling approaches based on facility location analysis, which is one of the most well-studied areas of operations research, and these two approaches are denoted by Facility Location based Sampling (FLS) and Conditional Facility Location Based Sampling (CFLS), respectively. FLS conducts one-time sample location selection, and CFLS extends the one-time sample location selection to a continuous process, so that an online advertising service can be started immediately without sampling a lot of locations. Our experimental results on two real datasets demonstrate the effectiveness and efficiency of the proposed methods. Specifically, both FLS and CFLS can achieve better performance than the existing sampling methods for the DAIM problem, and CFLS can initialize the online advertising service in a matter of seconds and achieve better objective distance than FLS after sampling a large number of sample locations.
References
[1]
G. Li, S. Chen, J. Feng, K.-l. Tan, and W.-s. Li, “Efficient location-aware influence maximization,” in Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pp. 87–98, ACM Library, New yark, June 2014.
[2]
X. Wang, Y. Zhang, W. Zhang, and X. Lin, “Efficient distance-aware influence maximization in geo-social networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 3, pp. 599–612, 2017.
[3]
A. Wang, A. Zhang, A. Zhang, and A. Lin, “Distance-aware influence maximization in geo-social network,” in Proceedings of the IEEE International Conference on Data Engineering, pp. 1–12, IEEE, Helsinki, Finland, May 2016.
[4]
M. Zhong, Q. Zeng, Y. Zhu, J. Li, and T. Qian, “Sample location selection for efficient distance-aware influence maximization in geo-social networks,” in Proceedings of the Database Systems for Advanced Applications,Lecture Notes in Computer Science, pp. 355–371, Springer, Cham, Switzerland AG, May 2018.
[5]
D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146, ACM Library, New yark, August 2003.
[6]
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420–429, ACM Library, New yark, August 2007.
[7]
W. Chen, C. Wang, and Y. Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social networks,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029–1038, ACM Library, New yark, July 2010.
[8]
E. Cohen, D. Delling, T. Pajor, and R. F. Werneck, “Sketch-based influence maximization and computation,” in Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pp. 629–638, ACM Library, New yark, November 2014.
[9]
W. Chen, Y. Yuan, and L. Zhang, “Scalable influence maximization in social networks under the linear threshold model,” in Proceedings of the IEEE International Conference on Data Mining, pp. 88–97, IEEE, Sydney, NSW, Australia, December 2010.
[10]
J. Li, C. Liu, J. X. Yu, Y. Chen, T. Sellis, and J. S. Culpepper, “Personalized influential topic search via social network summarization,” IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 7, pp. 1820–1834, 2016.
[11]
J. Li, X. Wang, K. Deng, X. Yang, T. Sellis, and J. X. Yu, “Most influential community search over large social networks,” in Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering (ICDE), 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 871–882, IEEE, San Diego, CA, USA, April 2017.
[12]
J. Chen, M. Zhong, J. Li, D. Wang, T. Qian, and H. Tu, “Effective deep attributed network representation learning with topology adapted smoothing,” IEEE Transactions on Cybernetics, pp. 1–12, 2021.
[13]
G. Xue, M. Zhong, J. Li, J. Chen, C. Zhai, and R. Kong, Dynamic Network Embedding Survey, Elsevier, Wuhan China, 2021.
[14]
J. Li, T. Sellis, J. S. Culpepper, Z. He, C. Liu, and J. Wang, “Geo-social influence spanning maximization,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 8, pp. 1653–1666, 2017.
[15]
W.-Y. Zhu, W.-C. Peng, L.-J. Chen, K. Zheng, and X. Zhou, “Modeling user mobility for location promotion in location-based social networks,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1573–1582, ACM Library, New yark, August 2015.
[16]
J. L. Z. Cai, M. Yan, and Y. Li, “Using crowdsourced data in location-based social networks to explore influence maximization,” in Proceedings of the IEEE INFOCOM 2016 - the IEEE International Conference on Computer Communications, pp. 1–9, IEEE, San Francisco, CA, USA, April 2016.
[17]
T. Cai, J. Li, A. S. Mian, R. li, T. Sellis, and J. X. Yu, “Target-aware holistic influence maximization in spatial social networks,” IEEE Transactions on Knowledge and Data Engineering, p. 1, 2020.
[18]
N. A. H. Haldar, M. Reynolds, Q. Shao, C. Paris, J. Li, and Y. Chen, “Activity location inference of users based on social relationship,” World Wide Web, vol. 24, no. 4, pp. 1165–1183, 2021.
[19]
A. Weber, “Ueber den standort der industrieni,” Translated as Alfred Wber's Theory of Location of Industries, vol. 3, 1929.
[20]
A. Boloori Arabani and R. Z. Farahani, “Facility location dynamics: an overview of classifications and applications,” Computers & Industrial Engineering, vol. 62, no. 1, pp. 408–420, 2012.
[21]
C. Irawan and S. Salhi, “Aggregation and non aggregation techniques for large facility location problems: a survey,” Yugoslav Journal of Operations Research, vol. 25, no. 3, pp. 313–341, 2015.
[22]
J. Elzinga and D. W. Hearn, “Geometrical solutions for some minimax location problems,” Transportation Science, vol. 6, no. 4, pp. 379–394, 1972.
[23]
Z. Drezner and G. O. Wesolowsky, “Single facility $l_p $-Distance minimax location,” SIAM Journal on Algebraic and Discrete Methods, vol. 1, no. 3, pp. 315–321, 1980.
[24]
Z. Drezner, “The p-centre problem-heuristic and optimal algorithms,” Journal of the Operational Research Society, vol. 35, no. 8, pp. 741–748, 1984.
[25]
B. Callaghan, S. Salhi, and G. Nagy, “Speeding up the optimal method of Drezner for the p -centre problem in the plane,” European Journal of Operational Research, vol. 257, no. 3, pp. 722–734, 2017.
[26]
E. Minieka, “Conditional centers and medians of a graph,” Networks, vol. 10, no. 3, pp. 265–272, 1980.
[27]
Z. Drezner, “Conditionalp-center problems,” Transportation Science, vol. 23, no. 1, pp. 51–53, 1989.
[28]
O. Berman and Z. Drezner, “A new formulation for the conditional -median and -center problems,” Operations Research Letters, vol. 36, no. 4, pp. 481–483, 2008.
[29]
D. Chen and R. Chen, “A relaxation-based algorithm for solving the conditional -center problem,” Operations Research Letters, vol. 38, no. 3, pp. 215–217, 2010.
[30]
Q. Zeng, M. Zhong, Y. Zhu, T. Qian, and J. Li, “Business location planning based on a novel geo-social influence diffusion model,” Information Sciences, vol. 559, pp. 61–74, 2021.
Recommendations
Sample Location Selection for Efficient Distance-Aware Influence Maximization in Geo-Social Networks
Database Systems for Advanced ApplicationsiGSLR: personalized geo-social location recommendation: a kernel density estimation approach
SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsWith the rapidly growing location-based social networks (LBSNs), personalized geo-social recommendation becomes an important feature for LBSNs. Personalized geo-social recommendation not only helps users explore new places but also makes LBSNs more ...
Exploiting location-aware social networks for efficient spatial query processing
In this paper, we introduce two watchtower-based parameter-tunable frameworks for efficient spatial processing with sparse distributions of Points of Interest (POIs) by exploiting mobile users' check-in data collected from the location-aware social ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2021 Kejian Tang et al.
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Publisher
John Wiley & Sons, Inc.
United States
Publication History
Published: 01 January 2021
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Dec 2024