Maximizing the earned benefit in an incentivized social networking environment: a community-based approach

摘要

Given a social network of users represented as a directed graph with edge weight as diffusion probability, the Social Influence Maximization Problem asks for selecting a set of highly influential users for initial activation to maximize the influence in the network. In this paper, we study a variant of this problem, where nodes are associated with a selection cost signifying the incentive demand; a fixed budget is allocated for the seed set selection process; a subset of the nodes is designated as the target nodes, and each of them is associated with a benefit value that can be earned by influencing the corresponding target user; and the goal is to choose a seed set within the allocated budget for maximizing the earned benefit. Formally, we call this problem as the Earned Benefit Maximization in Incentivized Social Networking Environment or Earned Benefit Maximization Problem (EBM Problem), in short. 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 more benefit compared to the baseline methods. To improve the proposed methodology, we exploit the community structure of the network. Experimental results show that the incorporation of community structure helps the proposed methodology to achieve more benefit without much increase in computational burden.