Research On The Initial Node Selection Strategy In The Problem Of Maximizing The Influence Of Network Propagation

We are living a world of networks.We can find online networks such as Webo and WeChat,offline social networks,power grid,and computer communication networks.Even though networks are diverse where nodes and links correspond to essentially different unities,there exists some kind of spreading phenomenon in almost all networks,including rumor spreading in social networks,advertisements forwarded by online social network accounts,computer virus infecting computers over networks,and especially,most recently COVID-19 spreading all over the world.From the academic perspective,a research topic related to spreading phenomenon is which factors affect the spreading.We could investigate this problem from network structure and figure out which kind of network can facilitate the spreading.We could also fix the network structure,and consider how to choose the initial seeds such that the final affected area is maximized.Latter is called influence maximization in network science research community,which is also the focal topic of this thesis.Recent years have witnessed extensive research on influence maximization problem.In the early stage,greedy algorithm and its variants are considered.However,these algorithms could not deal with large-scale networks because of high computational complexity.Then,heuristic algorithms of low computational burden have gradually became the focal topic.This thesis follows the research line,considering both spreading model and network centrality,propose several initial spreading seeds selection strategies.The main content and contributions are listed as follows:(1)The influence of network structure on performance of sequential seeding is investigated.Different from one-time seeding strategy,sequential seeding could effectively take advantage of currently available information and conduct multiple seeding optimization to cover an enlarged area.We assume that Independent Cascade(IC)model is used as the spreading model and the network structure is tunable.By tuning degree distribution and degree assortativity coefficient,we systematically constructed several classic network structures.By simulations on both man-made and natural networks,it is shown that sequential seeding strategy has the best performance in heterogeneous networks,and moreover,smaller average degree and larger assortativity coefficient could also facilitate the spreading under sequential seeding strategy.(2)Persuasiveness weighted cascade(PWC)model is proposed and the sequential seeding strategy using this model is investigated.In the IC model,nodes all have the same influence or persuasiveness on other nodes.However,in the real world nodes usually have different persuasiveness,and this is why companies ask celebrities to promote their products.Inspired by this consideration,in our PWC model,the persuasiveness of a node is proportional to its degree.Based on the PWC model,we develop a heuristic algorithm considering the expected benefits of seeding.The basic idea is to discount the influence of a node if its neighbor is already a seed,such that influence overlapping could be avoided.Simulations by real-world network data show the priority of proposed algorithm over traditional network centralities such as degree and betweenness.