Earned benefit maximization in social networks under budget constraint

被引:4
作者
Banerjee, Suman [1 ]
Jenamani, Mamata [2 ]
Pratihar, Dilip Kumar [3 ]
机构
[1] Indian Inst Technol Jammu, Dept Comp Sci & Engn, Jammu 181221, Jammu & Kashmir, India
[2] Indian Inst Technol Kharagpur, Dept Ind & Syst Engn, Kharagpur 721302, W Bengal, India
[3] Indian Inst Technol Kharagpur, Dept Mech Engn, Kharagpur 721302, W Bengal, India
关键词
Social network; Earned benefit; Target nodes; Greedy algorithm; Effective nodes; INFORMATION DIFFUSION; MAXIMIZING INFLUENCE; ALGORITHM;
D O I
10.1016/j.eswa.2020.114346
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Given a social network where the users are associated with non-uniform selection cost, the problem of Budgeted Influence Maximization (BIM in short) asks for selecting a subset of the nodes within an allocated budget for initial activation, such that due to the cascading effect, influence in the network is maximized. In this paper, we study this problem with a variation, where a subset of the users are marked as target users, each of them is assigned with a benefit and this can be earned by influencing them. The goal here is to maximize the earned benefit by initially activating a set of nodes within the budget. This problem is referred to as the Earned Benefit Maximization Problem. First, we show that this problem is NP-Hard and the benefit function follows the monotonicity, sub-modularity property under the Independent Cascade Model of diffusion. We propose an incremental greedy strategy for this problem and show, with minor modification it gives (1 - 1 root e)-factor approximation guarantee on the earned benefit. Next, by exploiting the sub-modularity property of the benefit function, we improve the efficiency of the proposed greedy algorithm. Then, we propose a hop-based heuristic method, which works based on the computation of the 'expected earned benefit'. Finally, we perform a series of extensive experiments with four publicly available, real-life social network datasets. From the experiments, we observe that the seed sets selected by the proposed algorithms can achieve more benefit compared to many existing methods. Particularly, the hop-based approach is found to be more efficient than the other ones for solving this problem.
引用
收藏
页数:13
相关论文
共 51 条
[1]  
Abraham A, 2010, COMPUT COMMUN NETW S, P1, DOI 10.1007/978-1-84882-229-0
[2]  
[Anonymous], mizing the Spread of Influence through a Social Network
[3]  
[Anonymous], 2009, P 18 INT C WORLD WID
[4]  
Bagherjeiran Abraham, 2008, 2008 IEEE International Conference on Data Mining Workshops, P837, DOI 10.1109/ICDMW.2008.70
[5]  
Banerjee S., 2018, INT C INT SYST DES A, P717
[6]   Maximizing the Earned Benefit in an Incentivized Social Networking Environment: An Integer Programming-Based Approach [J].
Banerjee, Suman ;
Jenamani, Mamata ;
Pratihar, Dilip Kumar .
PROCEEDINGS OF THE 6TH ACM IKDD CODS AND 24TH COMAD, 2019, :322-325
[7]   A survey on influence maximization in a social network [J].
Banerjee, Suman ;
Jenamani, Mamata ;
Pratihar, Dilip Kumar .
KNOWLEDGE AND INFORMATION SYSTEMS, 2020, 62 (09) :3417-3455
[8]   ComBIM: A community-based solution approach for the Budgeted Influence Maximization Problem [J].
Banerjee, Suman ;
Jenamani, Mamata ;
Pratihar, Dilip Kumar .
EXPERT SYSTEMS WITH APPLICATIONS, 2019, 125 :1-13
[9]   Essential elements regulating HDAC8 inhibition: a classification based structural analysis and enzyme-inhibitor interaction study of hydroxamate based HDAC8 inhibitors [J].
Banerjee, Suvankar ;
Amin, Sk Abdul ;
Adhikari, Nilanjan ;
Jha, Tarun .
JOURNAL OF BIOMOLECULAR STRUCTURE & DYNAMICS, 2020, 38 (18) :5513-5525
[10]   Influence Maximization in Social Networks with Genetic Algorithms [J].
Bucur, Doina ;
Iacca, Giovanni .
APPLICATIONS OF EVOLUTIONARY COMPUTATION, EVOAPPLICATIONS 2016, PT I, 2016, 9597 :379-392