Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Computing

21-03-2024 | Regular Paper

Influence maximization in mobile social networks based on RWP-CELF

Authors: Zhenyu Xu, Xinxin Zhang, Mingzhi Chen, Li Xu

Published in: Computing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Influence maximization (IM) problem for messages propagation is an important topic in mobile social networks. The success of the spreading process depends on the mechanism for selection of the influential user. Beside selection of influential users, the computation and running time should be considered in this mechanism to ensure the accurecy and efficient. In this paper, considering that the overhead of exact computation varies nonlinearly with fluctuations in data size, random algorithm with smoother complexity change was designed to solve the IM problem in combination with greedy algorithm. Firstly, we proposed a method named two-hop neighbor network influence estimator to evaluate the influence of all nodes in the two-hop neighbor network. Then, we developed a novel greedy algorithm, the random walk probability cost-effective with lazy-forward (RWP-CELF) algorithm by modifying cost-effective with lazy-forward (CELF) with random algorithm, which uses 25–50 orders of magnitude less time than the state-of-the-art algorithms. We compared the influence spread effect of RWP-CELF on real datasets with a theoretically proven algorithm that is guaranteed to be approximately optimal. Experiments show that the spread effect of RWP-CELF is comparable to this algorithm, and the running time is much lower than this algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Hu X, Chu THS, Leung VCM, Ngai CH, Philippe K, Chan HCB (2015) A survey on mobile social networks: applications, platforms, system architectures, and future research directions. IEEE Commun Surv Tutor 17(3):1557–1581CrossRef
2.
Chen W, Wang C, Wang Y (2010) 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
3.
Budak C, Agrawal D, Abbadi AE (2011) Limiting the spread of misinformation in social networks. In: Proceedings of the 20th international conference on World wide web, pp 665–674
4.
Domingos P, Richardson M (2001) Mining the network value of customers. In: Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining, pp 57–66
5.
Zhang P, Bao Z, Niu Y, Zhang Y, Mo S, Geng F, Peng Z (2019) Proactive rumor control in online networks. World Wide Web 22(4):1799–1818CrossRef
6.
Li Y, Wang Y, Tan KL (2018) Influence maximization on social graphs: a survey. IEEE Trans Knowl Data Eng 30(10):1852–1872CrossRef
7.
Kempe D, Kleinberg J, Tardos É (2003) Maximizing the spread of influence through a social network. In: Proceedings of the 9th international conference on knowledge discovery and data mining, pp 137–146
8.
Banerjee S, Jenamani M, Pratihar DK (2020) A survey on influence maximization in a social network. Knowl Inf Syst 62(9):3417–3455CrossRef
9.
Banerjee S, Jenamani M, Pratihar DK (2022) An approximate marginal spread computation approach for the budgeted influence maximization with delay. Computing 104:657–680MathSciNetCrossRef
10.
Raghavan S, Zhang R R (2015) Weighted target set selection on social networks, Technical report, Working paper, University of Maryland
11.
Azaouzi M, Mnasria W, Romdhane LB (2021) New trends in influence maximization models. Comput Sci Rev 40:100393CrossRef
12.
Zhu T, Wang B, Wu B, Zhu C (2014) Maximizing the spread of influence ranking in social networks. Inform ci 278:535–544MathSciNet
13.
Srivastava A, Chelmis C, Prasanna VK (2014) Influence in social networks: a unified model? In: Proceedings of the IEEE/ACM international conference on advances in social networks analysis and mining, pp 451–454
14.
Mohamadi-Baghmolaei R, Mozafari N, Hamzeh A (2015) Trust based latency aware influence maximization in social networks. Eng Appl Artif Intell 41:195–206CrossRef
15.
Wang F, Wang G, Xie D (2016) Maximizing the spread of positive influence under LT-MLA model. In: Asia-Pacific services computing conference, pp 450–463
16.
Leskovec J, Krause A, Guestrin C, Faloutsos C, Vanbriesen J, Glance N (2007) Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 420–429
17.
Goyal A, Lu W, Lakshmanan LVS (2011) CELF++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference companion on World wide web, pp 47–48
18.
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 199–207
19.
Kundu S, Pal SK (2015) Deprecation based greedy strategy for set selection in large scale social networks. Inf Sci 316:107–122CrossRef
20.
Shang J, Zhou S, Li X, Liu L, Wu H (2017) CoFIM: a community-based framework for influence maximization on large-scale networks. Knowl-Based Syst 117:88–100CrossRef
21.
Lu F, Zhang W, Shao L, Jiang X, Xu P, Jin H (2016) Scalable influence maximization under independent cascade model. J Netw Comput Appl 86:15–23CrossRef
22.
Freeman LC (1978) Centrality in social networks conceptual clarification. Soc Netw 1(3):215–239CrossRef
23.
Newman MJ (2005) A measure of betweenness centrality based on random walks. Soc Netw 27(1):39–54CrossRef
24.
25.
Zhang X, Xu L, Gao M (2020) An efficient influence maximization algorithm based on social relationship priority in mobile social networks. In: International Symposium on Security and Privacy in Social Networks and Big Data. Springer, pp 164–177
26.
Jiang Q, Song G, Cong G, Wang Y, Si W, Xie K (2011) Simulated annealing based influence maximization in social networks. In: Proceeding of the 25th AAAI conference on artificial intelligence, pp 127–132
27.
Cui L, Hu H, Yu S, Yan Q, Ming Z, Wen Z, Lu N (2018) DDSE: a novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks. J Netw Comput Appl 103:119–130CrossRef
28.
Gong M, Yan J, Shen B, Ma L, Cai Q (2016) Influence maximization in social networks based on discrete particle swarm optimization. Inf Sci 367–368(C):600–614CrossRef
29.
Tang J, Zhang R, Wang P, Zhao Z, Fan L, Liu X (2020) A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks. Knowl-Based Syst 187:104833CrossRef
30.
Zhang X, Zhu J, Wang Q, Zhao H (2013) Identifying influential nodes in complex networks with community structure. Knowl-Based Syst 42:74–84CrossRef
31.
Shang J, Zhou S, Li X, Liu L, Wu H (2017) CoFIM: a community-based framework for influence maximization on large-scale networks. Knowl-Based Syst 117:88–100CrossRef
32.
Shang J, Wu H, Zhou S, Zhong J, Feng Y, Qiang B (2018) IMPC: influence maximization based on multi-neighbor potential in community networks. Physica A 512:1085–1103CrossRef
33.
Kazemzadeh F, Safaei AA, Mirzarezaee M, Afsharian S, Kosarirad H (2023) Determination of influential nodes based on the communities structure to maximize influence in social network. Neurocomputing 534:18–28CrossRef
34.
Kim J, Kim SK, Yu H (2013) Scalable and parallelizable processing of influence maximization for large-scale social networks. In: Proceedings of the IEEE 29th international conference on data engineering, pp 266–277
35.
Liu B, Cong G, Zeng Y, Xu D, Chee YM (2014) Influence spreading path and its application to the time constrained social influence maximization problem and beyond. IEEE Trans Knowl Data Eng 26(8):1904–1917CrossRef
36.
Christakis NA, Fowler JH (2009) Connected: the surprising power of our social networks and how they shape our lives. Little, Brown, Boston
37.
Pei S, Muchnik L, Andrade JS Jr, Zheng Z, Makse HA (2014) Searching for superspreaders of information in real-world social media. Sci Rep 4:5547CrossRef
38.
Fu X, Wang C, Wang Z, Ming Z (2013) Threshold random walks for community structure detection in complex networks. J Softw 8(2):286–295CrossRef
39.
Okuda M, Satoh S, Sato Y, Kidawara Y (2021) Community detection using restrained random-walk similarity. IEEE Trans Pattern Anal Mach Intell 43(1):89–103
40.
Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):2-esCrossRef
41.
Leskovec J, Lang KJ, Dasgupta A, Mahoney MW (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math 6(1):29–123MathSciNetCrossRef
42.
Richardson M (2003) Trust management for the semantic web. In: Proceeding of international semantic web conference, pp 351–368
43.
Nguyen HT, Thai MT, Dinh TN (2016) Stop-and-stare: optimal sampling algorithms for viral marketing in billion-scale networks. In: Proceedings of the 2016 international conference on management of data, pp 695–710
Metadata
Title
Influence maximization in mobile social networks based on RWP-CELF
Authors
Zhenyu Xu
Xinxin Zhang
Mingzhi Chen
Li Xu
Publication date
21-03-2024
Publisher
Springer Vienna
Published in
Computing
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI
https://doi.org/10.1007/s00607-024-01276-z

Premium Partner

    Image Credits