Research On Influence Maximization Problem In Social Networks Based On Overlapping Community Structure

In recent years,social networks have been developed rapidly,such as Facebook and QQ.In social networks,the interactions among a group of users have a great impact on information spread,news diffusion and product marketing.Therefore,influence maximization problem in social networks has attracted more and more researchers' attention.The main steps of community structure based influence maximization algorithms: The community structure is firstly obtained by community detection algorithm;Secondly,some important communities are selected from the whole communities,and candidate nodes are selected from them;Finally,the final seed nodes are selected from the candidate nodes.This kind of algorithms utilize the characteristic of community structure to reduce the search space,and can achieve a good balance between efficiency and effectiveness.However,the existing community structure based influence maximization problem researches focus on non-overlapping community structure.When selecting seed nodes,they are easy to ignore those important overlapping nodes while overlapping nodes often play a positive role in promoting the influence spread,because they connect multiple communities.Therefore,this thesis studies overlapping community structure based influence maximization problem in social networks.Specifically,by utilizing the overlapping community structure mined from social networks,this thesis firstly designs an evolutionary algorithm based on overlapping community structure to solve the traditional influence maximization problem in social networks,and achieves a better balance between efficiency and effectiveness.However,in the traditional influence maximization problem,the cost of selecting each node is the same,without considering the situation that each node has different employment costs and budget constraint.Therefore,this thesis designs a local-global influence indicator based on overlapping community structure,and proposes a local-global influence indicator based constrained evolutionary algorithm for budgeted influence maximization in social networks to effectively solve the influence maximization problem with budget constraint.The main research works of this thesis are introduced as follows:(1)An overlapping community based evolutionary algorithm OCEA for traditional influence maximization in social networks is proposed.In order to avoid ignoring those important overlapping nodes,this method consider overlapping nodes and non-overlapping nodes separately,and select candidate overlapping nodes and candidate non-overlapping nodes according to different metrics.At the same time,by making full use of overlapping nodes,nonoverlapping nodes and their interactive information,three strategies(i.e.initialization,mutation and local search)are designed,which can not only accelerate the convergence of population,but also improve the final results.Finally,the experimental results on 9 real-world social networks verify not only the effectiveness and efficiency of OCEA,but also the effectiveness of the proposed three strategies.(2)A local-global influence indicator based constrained evolutionary algorithm IICEA for effectively solving budgeted influence maximization problem in social networks is proposed.In IICEA,a new influence indicator is firstly designed,which considers both local neighbor information and global community information.It can better measure the ability of spreading information of nodes in social networks.Based on the proposed influence indicator,a constrained evolutionary framework is proposed,and the influence indicator is used to guide mutation strategy,crossover strategy and repairment strategy to promote the evolution of population.Finally,experimental results on 10 real-world social networks show the efficiency and effectiveness of IICEA and the effectiveness of the proposed local-global influence indicator.