Algorithm For Computing K Hop No-repetition Paths In Complex Networks And Its Application

As a hot field of current research,complex networks have attracted the interest and attention of many researchers.It is not only because of the breakthrough progress in the research of complex network basic theory,but also because the application of complex networks in life has become more and more extensive.In the real world,complex systems are everywhere,and are closely related to people's lives,such as computer systems connected by computers,neural systems connected by neurons,and virus transmission systems formed by the spread of infectious diseases.These complex systems can be seen as the complex networks.By studying the topology and function of the network model,the characteristics of the complex system can be deeply understood,which provides convenience and support for subsequent transformation and utilization.In the complex network,the research on the number of nonrepetitive paths of k hop is relatively scarce.However,the information dissemination in the network and the analysis of the structural balance are of great significance.In the existing method,the number of paths between nodes is calculated according to the power of the adjacency matrix,and since the loop path and the partial repeat path are included,the result is inaccurate.Therefore,this paper studies the problem of the number of k hop no-repetition paths in complex networks.The main contents of this paper are as follows: 1.K hop no-repetition paths calculation based on node degree.This paper introduces the research background of complex networks.By analyzing the related descriptions of topological structures in the complex network,the concept of availability is proposed.Based on the node degree information,a no-repetitive path calculation method is proposed.In this paper,the local feature information of the complex network is used to take into account the outbound degree of the starting node and the ingress degree of the terminal node.The number of paths between the nodes is verified and analyzed,and a theoretical maximum can be obtained.The experimental results show that the method can quickly give the number of paths based on the node degree information of the network regardless of the node number of the complex network.2.K hop no-repetition paths calculation based on optimal path.In this paper,the k hop path with no-repetition path computation problem in complex networks is studied.After analyzing the path research and real-life demand characteristics in the current complex network,the k hop path with no-repetition algorithm based on the optimal path is proposed.During the processing,key points are selected from the intersections of the starting node and the terminal node to search for the optimal path,and the path is effectively spliced to obtain the k hop path,and the total number of k hop path with no-repetition is obtained through iteration.The experimental results show that the proposed method has a great improvement compared with the traditional algorithm,which shows the potential of the algorithm.3.Trust propagation and similarity calculation based on no-repetition paths.The proposed k hop path with no-repetition algorithm is applied to the propagation of trust values in the network.In this paper,a complex network trust propagation model based on no-repetition path is proposed.Based on the k hop path with no-repetition,the propagation information of the trust value is calculated,and the initial connection state ratio is used as the threshold to calculate the final node credibility.The prediction error rate is used as a criterion for judging the effectiveness of the algorithm.Through the comparison experiments in the e-commerce network dataset,experiments show that the error rate of the algorithm has been significantly reduced on a given network dataset.In solving the similarity of complex network nodes,similarity is the basis for analyzing complex network topology,which is of great significance for community discovery,network evolution and link prediction.The traditional Katz indicator uses the matrix power to estimate the number of paths between nodes.This paper applies the no-repetition path calculation method to the Katz.Through the experiments in the karate networks,the rationality and accuracy is verified.