1. Computing the Number of Loop-Free k-hop Paths of Networks
- Author
-
Hefei Che, Qin Liu, Chunlei Han, Jianshe Wu, Nan Cheng, and Chaojie Zhou
- Subjects
Information Systems and Management ,Computer Networks and Communications ,Computer science ,Word error rate ,Service provider ,Computer Science Applications ,Hop (networking) ,Tree traversal ,Trustworthiness ,Hardware and Architecture ,Cascade ,Search algorithm ,Adjacency matrix ,Algorithm - Abstract
Computing the number of loop-free k-hop paths is crucial for selecting services in social networks, for example a service consumer require to evaluate the trustworthiness of a service provider along the social trust paths, there are usually many social trust paths between two unconnected participants, we need know the number of loop-free k-hop trust propogation paths; other applications include the similarity computation for services recommendation, information diffusion, etc. Previously, the number of k-hop paths is roughly estimated by the elements in the k multiplications of the network adjacency matrix. This method calculates much more k-hop paths with loops, counted as loop-free k-hop paths, which may result in obvious errors in applications. Accurate mathematical formulas for counting loop-free paths are obtained in this paper for paths with 5 or less hops, an approximate method is provided for larger hops. Based on the proposed loop removing algorithm (LRA), the typical method for predicting trust between any two people is improved, the error rate is dramatically reduced; the traditional path based similarity indices are improved, which are much accurate than their antecedent counterparts; and a method for computing the spreading probability for information spreading in the famous independent cascade model is also obtained. To reveal the effectiveness of the proposed LRA, this paper also provide a traversal depth-first search algorithm (DFSA) for finding the true number of k-hop loop-free paths.
- Published
- 2022