Research On The Algorithms Of Identifying The Influential Links In Social Networks

Social networks are complex networks in which people interact with each other,and how to control the spread of infectious diseases in social networks has become an important issue in the study of network science.Changing the topology of social networks can be effective in controlling and mitigating the spread of infectious diseases,and it is often easier and less costly to control and mitigate the spread of infectious diseases by simply disrupting important connections between individuals than by isolating them.Therefore,in this thesis,we will focus on studying how to identify the important links in the network from the topology of the network,and improve the epidemic threshold by removing the set of important links.The main contributions of this thesis are as follows.(1)We propose a RW algorithm based on absorbing random walks to identify the important links.Compared with some classical algorithms,the RW algorithm can better reduce the spectral radius of the network while ensuring the connectivity of the network after removing the important set of links,which can improve the epidemic threshold and reduce the fraction of infected individuals to effectively control the spread of infectious diseases.Extensive experimental simulations further demonstrate that the RW algorithm can effectively identify the set of important links that influence the spread of infectious diseases in social networks.(2)We propose an algorithm to identify the importance of nodes and links based on non-backtracking random walks,and derive a higher-order perturbation estimation theory for the spectral radius corresponding to the non-backtracking matrix.Compared with some classical algorithms,this algorithm can better reduce the spectral radius of the non-backtracking matrix and adjacency matrix while ensuring the connectivity of the network after removing the set of important nodes and links.Extensive experimental simulations show that the algorithm can effectively identify the set of important nodes and the set of links that influence the spread of infectious diseases in social networks.Also the time complexity of the algorithm is guaranteed to be low.