Research On Node Importance Ranking And Influence Maximization Based On The Network Cycle Structure

From ecosystems to human societies,from power systems to transportation systems,the accelerating global information process represented by big data and Internet technology,as well as the continuous improvement of various infrastructures,have provided humans with an intuitive understanding of complex systems in the 21 st century.As a powerful tool for abstractly characterizing real complex systems,complex networks have become inseparable from human life.In complex networks,important nodes are those that have significant impact on the network’s structure and function.Identifying important nodes in the network can deepen our understanding of the network structure and function.Controlling or influencing these important nodes has significant practical significance,and can provide valuable guidance for rumor management,brand promotion,epidemic control,and other areas.In recent years,important node mining has become a popular research topic in the field of network science.Currently,there are numerous methods for identifying important network nodes,with most of them based on chain or star-shaped structures in the network.There is little research on using cycle structures in the network,despite a large number of studies proving the great potential of cycle structures in complex networks in fields such as neuroscience,psychology,and ecology.To address this gap,this thesis proposes a cycle structure-based node importance ranking method,providing a new perspective for identifying key nodes and solving the problem of influence maximizing in complex networks.The main work of this thesis is as follows:(1)This thesis proposes a new universally applicable method for identifying important network nodes based on cycle structures,called the NC method,to address the existing issues in current network node importance ranking methods.The performance of this method is validated on real networks from both functional and structural perspectives,and the computational complexity and potential future applications of this method are also explored.(2)Influence maximization is a key area of research in identifying important nodes,to solve the problem of influence overlap in influence maximization,two measurement methods,node group similarity,and node group distance,are proposed to reveal the underlying mechanisms of influence maximization.It was found that key node sets with low node group similarity and high node group distance can effectively avoid influence overlap,thereby achieving better influence propagation effects.The experiment shows that the NC method proposed in this thesis performs well in preventing the overlap of influence.(3)To address the issue of the initialization cost of spreading sources in influence maximization,a method for measuring propagation source initialization cost is proposed,and the advantages of the proposed method in balancing cost and propagation effectiveness are verified.This provides a new solution for formulating brand marketing,advertising promotion,and other communication strategies.(4)Based on the computing principles of the basic cycle,this thesis further explores the multi-solution of the NC method and finds that different node sequences generated by NC have similar performance in network spreading and network dismantling,providing effective node supplements for the selection of important nodes.