Research On Influence Maximization In Social Networks Based On Node Coverage

Influence maximization,i.e.to maximize the influence spread in a social network by finding a group of influential nodes as small as possible,is an important research in social network analysis.Traditional influence maximization algorithms are divided into three categories,i.e.propagation-based algorithms,topology-based algorithms and community-based algorithms.The research direction of propagation-based algorithms is improving greedy strategies that swap increased spread with time consuming,which limits its application on large-scale networks.This paper focus on topology-based algorithms and community-based algorithms.Aiming at the drawback and shortage of its,corresponding improved algorithms are supposed.(1)Influence maximization algorithm based on node coverageSelecting suitable centrality index is the method for topology-based algorithms to avoid the rich-club phenomenon.However,topology-based algorithms fail to resolve the duplicate neighbor problem during propagation process.In this paper,we propose an influence maximization algorithm based on node coverage.To avoid the rich-club phenomenon,this algorithm regard node coverage as centrality index.In addition,this paper develop the CELF strategy to speed up the NCA algorithm.Experimental results show that our approach can significantly outperform other algorithms.Furthermore,this algorithm is efficient,especially suitable for large-scale networks.(2)Influence maximization algorithm combining node coverage and community structureTraditional community-based influence maximization algorithms select candidate seed nodes by community detection results.Then,it uses greedy strategy or genetic algorithm to select the seed nodes from candidate nodes.Actually,it is difficult to set a suitable scale of candidate set in advance.In this paper,we propose an influence maximization algorithm combining node coverage and community structure.This algorithm divided networks into multiple regions by community detection algorithm.Then,it selects seed nodes based on the node coverage gain in their respective communities.The process does not need to select a candidate set.By community detection and node coverage gain,the proposed algorithm avoids the rich-club phenomenon comprehensively.Experimental results under both the IC and WC models show that,under the same scale of seed node,this algorithm significantly outperform other algorithms.And with the change of seed node size and propagation probability,the algorithm shows excellent stability.In this thesis,there are 9 figures,2 tables and 80 references.