A Study Of The Minimum Positive Influence Dominating Set Problem

Social networks are social structures composed of individuals and social relationships among individuals.Online social networks,which have rapidly accumulated a large amount of users in recent years,are typical representatives of such social structures.Various information is disseminated and spread efficiently through these social networks.It should be noted that some users may spread negative information through social networks,such as touting negative escapism and advocating unhealthy behaviors.The wide dissemination of such information will inevitably hinder the stable and harmonious development of society.Given a social network,it is an issue to find a set of key users with minimum scale as a positive source of information so that each user in the social network receives more positive influence than negative impact.Normally,this issue is called the Minimum Positive Influence Dominating Set problem(MPIDS in short).This paper focuses on the greedy algorithms used to solve the problem.By re-recognizing the nature of the problem,a new greedy algorithm is designed with high efficiency.Main contributions of this paper are as follows:·Algorithm for solving positive influence dominating set based on individual demand To reduce the search cost in the node selection process,which arises in the traditional algorithms for solving MPIDS problem,this paper proposes an algorithm Locally Greedy based on individual needs.Locally Greedy adopts the principle of preferentially satisfying the demands of low-degree nodes to narrow the search range of the node selection process,thereby improving the solution efficiency.This paper proves the correctness of the algorithm and analyzes the efficiency of the algorithm.·Comparison of algorithm performances This paper reimplements other algorithms for solving MPIDS problem and has carried out a large number of experiments on data sets of public data sources such as Stanford Large Network Dataset Collection,Network Repository,and Network data.The experimental results show that the Locally Greedy algorithm has higher solution efficiency and better solution quality than existing works,which verifies the effectiveness of the algorithm on MPIDS problem.·Algorithms for solving positive influence dominating sets in other types of networks This paper proposes various algorithms based on Locally Greedy for solving MPIDS problem in directed unweighted networks and undirected weighted networks.Experiments on the opensource datasets verify the effectiveness of the proposed algorithm in the corresponding network to complete the task of solving MPIDS problem.