IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v592y2022ics0378437121009973.html
   My bibliography  Save this article

Influence maximization problem by leveraging the local traveling and node labeling method for discovering most influential nodes in social networks

Author

Listed:
  • Bouyer, Asgarali
  • Beni, Hamid Ahmadi

Abstract

The influence maximization problem has gained particular importance in viral marketing for large-scale spreading in social networks. Developing a fast and appropriate algorithm to identify an optimized seed set for the diffusion process on social networks is crucial due to the fast growth of networks. Most fast methods only focus on the degree of nodes while ignoring the strategic position of nodes in the networks. These methods do not have the required quality in finding a seed set in most networks. On the other hand, many other methods have acceptable quality, but their computational overhead is significant. To address these issues, the main concentration of this paper is to propose a fast and accurate method for the influence maximization problem, which uses a local traveling for labeling of nodes based on the influence power, called the LMP algorithm. In the proposed LMP algorithm, first, a travel starts from a node with the lowest influence power to assign a ranking-label for this node and its neighbor nodes in each step based on their diffusion capability and strategic position. The LMP algorithm uses node labeling steps to reduce search space significantly. Three ranking-labels are used in the proposed algorithm, and nodes with the highest ranking-label are selected as candidate nodes. This local and fast step strictly reduces the search space. Finally, the LMP algorithm selects seed nodes based on the topology features and the strategic position of the candidate and connector. The performance of the proposed algorithm is benchmarked with the well-known and recently proposed seed selection algorithms. The experimental results are performed on real-world and synthetic networks to validate the efficiency and effectiveness. The experiments exhibit that the proposed algorithm is the fastest in comparison with other state-of-the-art algorithms, and it has linear time complexity. In addition, it can achieve a good tradeoff between the efficiency and time complexity in the influence maximization problem.

Suggested Citation

  • Bouyer, Asgarali & Beni, Hamid Ahmadi, 2022. "Influence maximization problem by leveraging the local traveling and node labeling method for discovering most influential nodes in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 592(C).
    • Handle: RePEc:eee:phsmap:v:592:y:2022:i:c:s0378437121009973
    DOI: 10.1016/j.physa.2021.126841
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437121009973
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2021.126841?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Samir, Ahmed M. & Rady, Sherine & Gharib, Tarek F., 2021. "LKG: A fast scalable community-based approach for influence maximization problem in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 582(C).
    2. Kai Gong & Ming Tang & Pak Ming Hui & Hai Feng Zhang & Do Younghae & Ying-Cheng Lai, 2013. "An Efficient Immunization Strategy for Community Networks," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-11, December.
    3. Singh, Shashank Sheshar & Kumar, Ajay & Singh, Kuldeep & Biswas, Bhaskar, 2019. "C2IM: Community based context-aware influence maximization in social networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 514(C), pages 796-818.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kazemzadeh, Farzaneh & Safaei, Ali Asghar & Mirzarezaee, Mitra, 2022. "Influence maximization in social networks using effective community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 598(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wu, Tao & Chen, Leiting & Zhong, Linfeng & Xian, Xingping, 2017. "Predicting the evolution of complex networks via similarity dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 465(C), pages 662-672.
    2. Lin Zhang & Kan Li, 2021. "Influence Maximization Based on Backward Reasoning in Online Social Networks," Mathematics, MDPI, vol. 9(24), pages 1-17, December.
    3. Gong Kai & Kang Li, 2018. "A New K-Shell Decomposition Method for Identifying Influential Spreaders of Epidemics on Community Networks," Journal of Systems Science and Information, De Gruyter, vol. 6(4), pages 366-375, August.
    4. Zhong, Li-Xin & Xu, Wen-Juan & Chen, Rong-Da & Qiu, Tian & Shi, Yong-Dong & Zhong, Chen-Yang, 2015. "Coupled effects of local movement and global interaction on contagion," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 436(C), pages 482-491.
    5. Wu, Rui-Jie & Kong, Yi-Xiu & Di, Zengru & Zhang, Yi-Cheng & Shi, Gui-Yuan, 2022. "Analytical solution to the k-core pruning process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 608(P1).
    6. Mishra, Shivansh & Singh, Shashank Sheshar & Kumar, Ajay & Biswas, Bhaskar, 2022. "ELP: Link prediction in social networks based on ego network perspective," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 605(C).
    7. Samuel F Rosenblatt & Jeffrey A Smith & G Robin Gauthier & Laurent Hébert-Dufresne, 2020. "Immunization strategies in networks with missing data," PLOS Computational Biology, Public Library of Science, vol. 16(7), pages 1-21, July.
    8. Huang, He & Yan, Zhijun & Pan, Yaohui, 2014. "Measuring edge importance to improve immunization performance," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 416(C), pages 532-540.
    9. Taghavian, Fatemeh & Salehi, Mostafa & Teimouri, Mehdi, 2017. "A local immunization strategy for networks with overlapping community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 467(C), pages 148-156.
    10. Gupta, Naveen & Singh, Anurag & Cherifi, Hocine, 2016. "Centrality measures for networks with community structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 452(C), pages 46-59.
    11. Kumar, Ajay & Singh, Shashank Sheshar & Singh, Kuldeep & Biswas, Bhaskar, 2020. "Link prediction techniques, applications, and performance: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    12. Chen, Jie & Tan, Xuegang & Cao, Jinde & Li, Ming, 2022. "Effect of coupling structure on traffic-driven epidemic spreading in interconnected networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 607(C).
    13. Devi, Kalyanee & Tripathi, Rohit, 2023. "ASN: A method of optimality for seed identification in the influence diffusion process," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 618(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:592:y:2022:i:c:s0378437121009973. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.