More Web Proxy on the site http://driver.im/

research-article

Efficient Distance-Aware Influence Maximization in Geo-Social Networks

Authors:

Xuemin LinAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 29, Issue 3

Pages 599 - 612

https://doi.org/10.1109/TKDE.2016.2633472

Published: 01 March 2017 Publication History

Abstract

Given a social network $\mathcal {G}$ and a positive integer $k$ , the influence maximization problem aims to identify a set of $k$ nodes in $\mathcal {G}$ that can maximize the influence spread under a certain propagation model. As the proliferation of geo-social networks, location-aware promotion is becoming more necessary in real applications. In this paper, we study the distance-aware influence maximization (DAIM) problem, which advocates the importance of the distance between users and the promoted location. Unlike the traditional influence maximization problem, DAIM treats users differently based on their distances from the promoted location. In this situation, the $k$ nodes selected are different when the promoted location varies. In order to handle the large number of queries and meet the online requirement, we develop two novel index-based approaches, MIA-DA and RIS-DA, by utilizing the information over some pre-sampled query locations. MIA-DA is a heuristic method which adopts the maximum influence arborescence (MIA) model to approximate the influence calculation. In addition, different pruning strategies as well as a priority-based algorithm are proposed to significantly reduce the searching space. To improve the effectiveness, in RIS-DA, we extend the reverse influence sampling (RIS) model and come up with an unbiased estimator for the DAIM problem. Through carefully analyzing the sample size needed for indexing, RIS-DA is able to return a $1 - 1/e -\epsilon$ approximate solution with at least $1 - \delta$ probability for any given query. Finally, we demonstrate the efficiency and effectiveness of proposed methods over real geo-social networks.

References

[1]

Y. Tang, Y. Shi, and X. Xiao, “ Influence maximization in near-linear time: A martingale approach,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2015, pp. 1539–1554.

Digital Library

[2]

Y. Tang, X. Xiao, and Y. Shi, “ Influence maximization: Near-optimal time complexity meets practical efficiency,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2014, pp. 75–86.

Digital Library

[3]

W. Chen, C. Wang, and Y. Wang, “ Scalable influence maximization for prevalent viral marketing in large-scale social networks,” in Proc. 16th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2010, pp. 1029–1038.

Digital Library

[4]

D. Kempe, J. M. Kleinberg, and E. Tardos, “ Maximizing the spread of influence through a social network,” in Proc. 9th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2003, pp. 137–146.

Digital Library

[5]

E. Cohen, D. Delling, T. Pajor, and R. F. Werneck, “ Sketch-based influence maximization and computation: Scaling up with guarantees,” in Proc. 23rd ACM Int. Conf. Conf. Inf. Knowl. Manage., 2014, pp. 629–638.

Digital Library

[6]

I. R. Misner, The World's Best Known Marketing Secret: Building Your Business with Word-of-Mouth Marketing . 2nd ed. Austin, TX, USA: Bard Press, 1999.

[7]

J. Nail, The Consumer Advertising Backlash . Cambridge, MA, USA: Forrester Res. Intelliseek Market Res. Rep., 2004.

[8]

G. Li, S. Chen, J. Feng, K. Tan, and W. Li, “ Efficient location-aware influence maximization,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2014, pp. 87–98.

Digital Library

[9]

W. Zhu, W. Peng, L. Chen, K. Zheng, and X. Zhou, “ Modeling user mobility for location promotion in location-based social networks,” in Proc. 21st ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2015, pp. 1573–1582.

Digital Library

[10]

X. Wang, Y. Zhang, W. Zhang, and X. Lin, “ Distance-aware influence maximization in geo-social network,” in Proc. IEEE 32nd Int. Conf. Data Eng., 2016, pp. 1–12.

[11]

Y. Li, D. Zhang, and K. Tan, “ Real-time targeted influence maximization for online advertisements,” Proc. VLDB Endowment, vol. Volume 8, pp. 1070–1081, 2015.

Digital Library

[12]

S. Chen, J. Fan, G. Li, J. Feng, K. Tan, and J. Tang, “ Online topic-aware influence maximization,” Proc. VLDB Endowment, vol. Volume 8, pp. 666–677, 2015.

Digital Library

[13]

W. Chen, T. Lin, and C. Yang, “ Real-time topic-aware influence maximization using preprocessing,” in CSoNet, 2015, pp. 1–13.

[14]

Ç. Aslay, N. Barbieri, F. Bonchi, and R. A. Baeza-Yates, “ Online topic-aware influence maximization queries,” in Proc. Int. Conf. Extending Database Technol., 2014, pp. 295–306.

[15]

C. Borgs, M. Brautbar, J. Chayes, and B. Lucier, “ Maximizing social influence in nearly optimal time,” in Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms, 2014, pp. 946–957.

[16]

Y. Wu, S. Yang, and X. Yan, “ Ontology-based subgraph querying,” in Proc. IEEE 32nd Int. Conf. Data Eng., 2013, pp. 697–708.

[17]

K. Feng, G. Cong, S. S. Bhowmick, and S. Ma, “ In search of influential event organizers in online social networks,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2014, pp. 63–74.

Digital Library

[18]

C. Borgs, M. Brautbar, J. T. Chayes, and B. Lucier, “ Maximizing social influence in nearly optimal time,” in Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms, 2014, pp. 946–957.

[19]

P. Domingos and M. Richardson, “ Mining the network value of customers,” in Proc. 7th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2001, pp. 57–66.

Digital Library

[20]

M. Richardson and P. Domingos, “ Mining knowledge-sharing sites for viral marketing,” in Proc. 8th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2002, pp. 61–70.

Digital Library

[21]

J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “ Cost-effective outbreak detection in networks,” in Proc. 13th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2007, pp. 420–429.

Digital Library

[22]

W. Chen, Y. Wang, and S. Yang, “ Efficient influence maximization in social networks,” in Proc. 15th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2009, pp. 199–208.

Digital Library

[23]

W. Chen, Y. Yuan, and L. Zhang, “ Scalable influence maximization in social networks under the linear threshold model,” in Proc. IEEE Int. Conf. Data Mining, 2010, pp. 88–97.

Digital Library

[24]

A. Goyal, W. Lu, and L. V. Lakshmanan, “ CELF++: Optimizing the greedy algorithm for influence maximization in social networks,” in Proc. 20th Int. Conf. Companion World Wide Web, 2011, pp. 47–48.

Digital Library

[25]

Y. S. Brendan Lucier and Joel Oren, “ Influence at scale: Distributed computation of complex contagion in networks,” in Proc. 21st ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, 2015.

Digital Library

[26]

C. Zhang, L. Shou, K. Chen, G. Chen, and Y. Bei, “ Evaluating geo-social influence in location-based social networks,” in Proc. 21st ACM Int. Conf. Inf. Knowl. Manage., 2012, pp. 1442–1451.

Digital Library

Cited By

Wang JWu YWang XZhang YQin LZhang WLin X(2024)Efficient Influence Minimization via Node BlockingProceedings of the VLDB Endowment10.14778/3675034.367504217:10(2501-2513)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.14778/3675034.3675042
Venunath MSujatha PKoti P(2024)Identification of influential users in social media network using golden ratio optimization methodSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09218-128:3(2207-2222)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00500-023-09218-1
Hu ZZheng WLian X(2023)Triangular Stability Maximization by Influence Spread over Social NetworksProceedings of the VLDB Endowment10.14778/3611479.361149016:11(2818-2831)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611490
Show More Cited By

Recommendations

Efficient location-aware influence maximization
SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data

users in a social network to maximize the expected number of users influenced by the selected users (called influence spread), has been extensively studied, existing works neglected the fact that the location information can play an important role in ...
Efficient Similarity-Aware Influence Maximization in Geo-Social Network
With the explosion of GPS-enabled smartphones and social media platforms, geo-social networks are increasing as tools for businesses to promote their products or services. Influence maximization, which aims to maximize the expected spread of influence in ...
Time and value aware influence blocking maximization in geo-social networks
Abstract
The influence blocking maximization (IBM) problem aims to identify the most influential set of positive nodes in a social network to prevent the propagation of negative information throughout the network. However, existing studies have not ... $()$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 29, Issue 3

March 2017

217 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © 2017.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 March 2017

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang JWu YWang XZhang YQin LZhang WLin X(2024)Efficient Influence Minimization via Node BlockingProceedings of the VLDB Endowment10.14778/3675034.367504217:10(2501-2513)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.14778/3675034.3675042
Venunath MSujatha PKoti P(2024)Identification of influential users in social media network using golden ratio optimization methodSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-09218-128:3(2207-2222)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s00500-023-09218-1
Hu ZZheng WLian X(2023)Triangular Stability Maximization by Influence Spread over Social NetworksProceedings of the VLDB Endowment10.14778/3611479.361149016:11(2818-2831)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611490
Xu KFei ZYu JKong YWang XZhang W(2023)IFGNN: An Individual Fairness Awareness Model for Missing Sensitive Information GraphsDatabases Theory and Applications10.1007/978-3-031-47843-7_20(287-300)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/978-3-031-47843-7_20
Wang LYu ZGuo BYang DMa LLiu ZXiong F(2022)Data-driven Targeted Advertising Recommendation System for Outdoor BillboardACM Transactions on Intelligent Systems and Technology10.1145/349515913:2(1-23)Online publication date: 5-Jan-2022
https://dl.acm.org/doi/10.1145/3495159
Chen XZhao YLiu GSun RZhou XZheng K(2022)Efficient Similarity-Aware Influence Maximization in Geo-Social NetworkIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.304578334:10(4767-4780)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/TKDE.2020.3045783
Zhang XWang HYu JChen CWang XZhang W(2022)Polarity-based graph neural network for sign prediction in signed bipartite graphsWorld Wide Web10.1007/s11280-022-01015-425:2(471-487)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11280-022-01015-4
Allimuthu UMahalakshmi K(2022)Efficient Mobile Ad Hoc Route Maintenance Against Social Distances Using Attacker Detection AutomationMobile Networks and Applications10.1007/s11036-022-02040-328:1(128-159)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11036-022-02040-3
Tang KZhan SZhan TZhu HZeng QZhong MZhu XZhu YLi JQian T(2021)Efficient Sample Location Selection for Query Zone in Geo-Social NetworksComplexity10.1155/2021/25812882021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/2581288
Wang LYu ZYang DWang TWang EGuo BZhang D(2021)Task Execution Quality Maximization for Mobile Crowdsourcing in Geo-Social NetworksProceedings of the ACM on Human-Computer Interaction10.1145/34760535:CSCW2(1-29)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3476053
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents