Applying Heuristic-Based Greedy Approaches for Influence Maximization-Cost Minimization in Social Networks

Influence maximization in social networks has been an important research issue in the recent decade. This issue is identifying the most influential individuals in a social network who can convey influence to the largest number of the network’s members. However, in influence maximization, the costs of all of the nodes to be selected as seeds are considered the same for the companies that do not hold in the real world. Accordingly, influence maximization-cost minimization has gained attention recently. Available studies have applied multi-objective optimization methods which are time-consuming. Applying the existing approaches of influence maximization for other variants of this problem has been considered in some studies about other multi-objective versions of the influence maximization problem. In this study, extending and well-applying run time-efficient methods of influence maximization are considered to influence maximization-cost minimization. Accordingly, two methods are proposed. The first, Local Lowest Degree Rank (LLDR) is a heuristic-based one which by considering the degree of nodes aims to find the cost-affordable influential nodes with minimum influence overlap among them. The second proposed method, Ratio-aware-CELF-based (RCELF) method, is a Cost Effective Lazy Forward (CELF)-based algorithm which extends CELF as a run-time efficient greedy approach for influence maximization by incorporating the cost function of the nodes into consideration. The proposed methods are evaluated by applying two real-world datasets, Facebook and Last.fm. The results establish the outperformance which in comparison with the most effective benchmark method is between ۴% to ۳۲% for LLDR and between ۳۴% to ۹۶% for RCELF.

کلیدواژه ها:

Social Network ، Influence maximization ، Cost minimization ، Top-K nodes ، Viral marketing