Research On Algorithms Of Finding Minimum Positive Influence Dominating Set In Social Networks

The positive influence dominating set(PIDS)problem in social network is a current research hotpot and a challenging problem.The PIDS plays an important role in many realistic scenarios.Finding a PIDS and influencing the individuals who are in the PIDS can have a positive impact on the whole network.For a subset of all nodes in a network,if at least half of the neighbors of each node in the network are included in the subset,then this subset is a PIDS of the network.Recently,there are many studies on PIDS,but the size of each PIDS found by these studies is relatively large.In order to make the cost as low as possible,it is necessary to find a minimum positive influence dominating set(MPIDS),that is,a PIDS with minimum cardinality.To find a MPIDS,some algorithms have been proposed such as a memetic algorithm(MA),a fast greedy algorithm(FGA)and so on.However,these algorithms cannot achieve both satisfactory results and high efficiency.We studied the problem in this thesis and the main contributions of our research are as followsDue to the shortcomings of the existing algorithms,this thesis proposed a meta-heuristic named iterated carousel greedy(ICG)algorithm for finding a MPIDS.The algorithm starts with constructing an initialization solution quickly.Then generates a sequence of solutions by iterating destruction,carousel and reconstruction phases.After that,an acceptance criterion is designed to decide whether the new solution is accepted or not.Finally,a high-quality solution is obtained when the convergence condition is satisfied.The ICG algorithm uses random destruction process to increase disturbance.In addition,the ICG algorithm creatively applies the carousel process,guides the algorithm to the better solution space,and combines the carousel process with iterative greedy method to iteratively improve the solution.The experimental results on real-word networks show that the ICG algorithm proposed in this thesis can achieve better results and efficiency compared with other heuristic and meta-heuristic methods.Social networks are usually modeled as undirected networks,but real-word networks are complicated.In recent years,directed networks are used to represent social networks.Directed edges in a directed network can express concern,support,or approval among users.The existing researches on MPIDS are mostly based on undirected networks,and few researches are based on directed networks.In this thesis,we proposed an improved iterated carousel greedy(IICG)algorithm for finding a MPIDS in directed networks.The algorithm first generates an initial solution,then perturbs the current solution in the disturbance stage to improve the diversity of the search space,and finally adopts the reception criteria based on simulated annealing algorithm to avoid the algorithm falling into local optimum as far as possible.In addition,the existing classical algorithms for finding PIDSs in undirected networks are modified to adapt to directed networks.The experiment exerts on real-world networks and artificial networks.The experimental results show that the proposed IICG algorithm can obtain higher quality solutions compared with other algorithms involved in the comparison.Moreover,it has good stability.