Detecting Influential Nodes And The Application In Pinning Complex Networks

Spreading issues,such as computer viruses diffusion,the spread and control of infectious diseases,and the outbreak of public opinion on social media can be abstracted into the spread in the network.Generally speaking,in order to prevent or accelerate such spreading behavior in the network,we could select a small set of influential nodes and apply control strategies to them.The traditional algorithms identify influential nodes from the topology of the network based on the nodes' centrality.However,they fail in large-scale networks.In this paper,we analyze the pinning control problem in large-scale networks and propose an effective algorithm to detect influential nodes.Contribution of the dissertation can be divided into the following two parts:The first part investigates the classical pinning control problem.We demonstrate that the widely used eigenratio metric cannot precisely characterize the pinning controllability and may fail under some extreme conditions.Therefore,we propose a method to describe pinning con-trollability from two perspectives: the coupling range and convergence speed.The former indi-cates the synchronization range of the coupling strength between agents? the latter,derived from the Lyapunov index,characterizes the convergence rate of the pinning control.The coupling range and convergence speed are different metrics,but the eigenratio ignores their difference and characterizes pinning controllability roughly by the ratio of the maximum and minimum eigenvalues.Moreover,we also find that the three metrics cannot reach the optimums at the same time.Simulation in real networks verified the effectiveness of the proposed metrics.The second part focuses on the algorithm to detect influential nodes.In engineering fields,the optimization of controlling a complex network can be divided into two parts: increasing the response speed of the system,or enlarging the range of the coupling strength.The response speed is related to convergence speed.When the fraction of pinning nodes is fixed,we need to select a better set of influential nodes to enlarge the coupling range and improve the convenience of debugging.In order to obtain the optimal set of pinning nodes,based on the perturbation of the coupling range,we propose a greedy algorithm to detect influential nodes.The algorithm has low complexity and can efficiently calculate the optimal control nodes.Experiments on six real networks show that compared with other methods,our proposed method tends to choose those nodes that are ignored by other methods and greatly enhances the pinning controllability.Moreover,we also find that there is a strong correlation between the coupling range and the eigenratio,which suggests that the eigenratio still holds in pinning control and node detection.In conclusion,we mainly study pinning control and detect influential nodes in complex networks.We characterize pinning controllability from two perspectives: the coupling rangeand convergence speed.Then according to the perturbation of the coupling range,we propose an algorithm to detect influential nodes.Our work can deepen our understanding of the pinning control problem and help the pinning control in engineering.