Target set selection in social networks with tiered influence and activation thresholds

Zhecheng Qiang, Eduardo L. Pasiliao and Qipeng P. Zheng ()
Additional contact information
Zhecheng Qiang: University of Central Florida
Eduardo L. Pasiliao: Air Force Research Laboratory
Qipeng P. Zheng: University of Central Florida

Journal of Combinatorial Optimization, 2023, vol. 45, issue 5, No 7, 27 pages

Abstract: Abstract Thanks to the mass adoption of internet and mobile devices, users of the social media can seamlessly and spontaneously connect with their friends, followers and followees. Consequently, social media networks have gradually become the major venue for broadcasting and relaying information, and is casting great influences on the people in many aspects of their daily lives. Thus locating those influential users in social media has become crucially important for the successes of many viral marketing, cyber security, politics, and safety-related applications. In this study, we address the problem through solving the tiered influence and activation thresholds target set selection problem, which is to find the seed nodes that can influence the most users within a limited time frame. Both the minimum influential seeds and maximum influence within budget problems are considered in this study. Besides, this study proposes several models exploiting different requirements on seed nodes selection, such as maximum activation, early activation and dynamic threshold. These time-indexed integer program models suffer from the computational difficulties due to the large numbers of binary variables to model influence actions at each time epoch. To address this challenge, this paper designs and leverages several efficient algorithms, i.e., Graph Partition, Nodes Selection, Greedy algorithm, recursive threshold back algorithm and two-stage approach in time, especially for large-scale networks. Computational results show that it is beneficial to apply either the breadth first search or depth first search greedy algorithms for the large instances. In addition, algorithms based on node selection methods perform better in the long-tailed networks.

Keywords: Networks; Integer programming; Target set selection; Greedy algorithm; Influence maximization; Social media; Linear threshold model (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01023-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:45:y:2023:i:5:d:10.1007_s10878-023-01023-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01023-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().