A Priority-Based Ranking Approach for Maximizing the Earned Benefit in an Incentivized Social Network

摘要

Given a social network of users represented as a directed graph with edge weight as diffusion probability, selecting a set of highly influential users for initial activation to maximize the influence in the network is popularly known as the Social Influence Maximization Problem. In this paper, we study a different and more practical variant of this problem, where each node is associated with a selection cost which signifies the incentive demand if it is included in the seed set; a fixed budget that can be spent for the seed set selection process; a subset of the nodes designated as the target nodes and each of them is associated with a benefit value that can be earned by influencing the corresponding user; and the goal is to choose a seed set for maximizing the earned benefit within the allocated budget. For this problem, we develop a priority based ranking methodology having three steps. First, marking the effective nodes for the given target nodes; second, priority computation of the effective nodes and the third is to choose the seed nodes based on this priority value within the budget. We implement the proposed methodology with two publicly available social network datasets and observe that the proposed methodology can achieve 0.03 to 1.14 times more benefit compared to the baseline methods without much increase in computational burden.