Research On Influence Maximization Problem In Social Networks Based On Swarm Intelligence

Social networks have become the mainly media for interactional communication among individuals and important platforms for information spread with the rapid development of the Internet and Web 2.0.People are reorganizing their conventional off-line information stream through social networks in more efficient ways at lower costs.The individual nodes tend to exert influence on their neighborhoods and reshape their perception and behaviors,which would lead to the evolution of the network topology.Therefore,it is of great significant to carry out further research on social network analysis to uncover the statistical property of different networks,understand the behaviors of nodes,know the spreading dynamics and ultimately control the evolution of the network topology.As an important research topic,influence maximization problem is targeted to select a subset of influential nodes from a given network as a seed set to maximize the spread of the influence.So it is not only of great theoretical significant to study the influence maximization problem,but also has promising prospects of application in promoting the product adoption,information diffusion and other practical activities through viral marketing.The existing vast majority of influence maximization algorithms always suffer the dilemmas,such as unstable performance and low scalability in networks with different topology structures and highly computational time and huge memory consumption in large-scale social networks.Aiming at the mentioned problems,in this thesis,we firstly present the feasibility analysis and advantages to tackle influence maximization problem in social networks using meta-heuristic algorithms,which are based on swarm intelligence.To explore the solution space broadly and achieve the best seed set,the impact of local search strategy on improving the performance of meta-heuristic algorithms is further studied.Then the bat algorithm is employed to cope with the influence maximization problem.After that,rapid discrete evolutionary mechanisms of meta-heuristic algorithms are explored for large-scale social networks.And by combining the community structure characteristic commonly shared by social networks,an adaptive seed nodes selecting strategy is presented in the last.The experimental results demonstrate that it is a promising way to develop effective meta-heuristic algorithms based on swarm intelligence for the influence maximization problem.The mainly achievements are detailed as follows.(1)We propose an improved discrete particle swarm optimization based on greedy mechanism to enhance the searching ability for influential nodes in the solution space.Greedy algorithms always need to simulate tens-of-thousands Monte-Carlo simulations to estimate the marginal gain of each node approximately,which gives rise to the awkwardness that they cannot be applied to largescale social networks for the highly time complexity.Therefore,we firstly discuss the feasibility to solve influence maximization problem using meta-heuristic algorithms and its superiority to traditional heuristics.To optimize the candidate nodes of each iteration when we adopt the classic particle swarm optimization to select the targeted seed set,an enhanced local search strategy based on greedy mechanism is presented.According to the strategy,each of the candidate node in the temporary optimal seed set is to be replaced with the influential node with the best marginal gain from its direct neighbor set.The experimental results show that the proposed discrete particle swarm optimization performs effectively in improving the accuracy of the optimal seed set.(2)Based on the above efforts,we try to apply the bio-inspired bat algorithm to deal with influence maximization problem by redefining discrete evolutionary rules for the virtual bat population according to the network topology characters.To avoid the algorithm searching blindly in the solution space and enhance the exploitation operation of the discrete bat algorithm,a metric naming contribution rate is conceived by integrating the degree centrality and betweeness centrality to evaluate the importance of the node to the whole network topology structure,and a CandidatesPool is generated according to the metric.The experimental results and statistic tests under independent cascade model demonstrate that DBA achieves competitive influence spread to CELF but has less time computation than CELF.(3)The impact of local search strategy,which is constructed based on network topology,on the time complexity of meta-heuristic algorithms is analyzed prudently,and an efficient discrete shuffled frog-leaping algorithm(DSFLA)is proposed to identify influential nodes for influence maximization.Novel encoding mechanism and discrete evolutionary rules are conceived according to network structure for the virtual frog population.To facilitate the solution of global exploration,a novel local exploitation operation combining deterministic and random walk strategies is put forward to refine the suboptimal meme individual from each memeplex in the population.Then the orthogonal experiment method is introduced to optimize the parameter setting strategy for the discrete algorithm.The experimental results prove that DSFLA performs effectively in selecting targeted influential seed nodes for influence maximization compared to other state-of-theart algorithms.(4)Inspired by the diversity of community structures,which are commonly shared by many real-world social networks,we propose an adaptive discrete particle swarm optimization(ADPSO)based on community detecting to help the algorithm select seed nodes dynamically.For the scale of communities in social networks is diverse,so we construct a dynamic candidate seed nodes selecting mechanism to allocate the required number of candidates for each community reasonably by evaluating the expected influence spread of given potential seed nodes.The experimental results demonstrate that ADPSO performs efficiently and robustly in identifying influential nodes.