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

Asgarali Bouyer and Hamid Ahmadi Beni

Physica A: Statistical Mechanics and its Applications, 2022, vol. 592, issue C

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.

Keywords: Social networks; Influence maximization; Node labeling; Influence spread; Independent cascade model (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437121009973
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

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:592:y:2022:i:c:s0378437121009973

DOI: 10.1016/j.physa.2021.126841

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().