New Algorithms On Multiplex PageRank And KCCA For Information Retrieval

In the network analysis of information retrieval,PageRank is one of the most popular methods to measure centrality.Classical PageRank assumes there is only a single link between network nodes,but current scholars have found the links between network nodes are heterogeneous,so mulitplex PageRank models have been introduced.In this paper,we are interested in the large-scale sparse linear equation and the corresponding incremental and decremental problems converted from the multiplex PageRank problem.As far as we know,there is no effective algorithm for it till now.We first use three classic block iterative algorithms to solve the equation,including block Jacobi algorithm,block Gauss-Seidel algorithm,and block SOR algorithm,and analyze the convergence of the algorithms.However,the classic block iterative algorithms require inner and outer iterations whose computing speed is slow.Based on the three classic block iterative algorithms,we propose three Inverse-Free algorithms,named the block Inverse-Free-Jacobi algorithm,the block Inverse-Free-GS algorithm and the block Inverse-Free-SOR algorithm,and analyze the convergence of these three algorithms.In addition,in the block Inverse-Free-SOR algorithm,we find the choice of relaxation factor ? is quite important.According to the necessary condition for the algorithm to converge,we propose a search algorithm to select the “optimal” ?.Since the layers of mulitplex network may be constantly changing,in order to make full use of the information obtained,we propose the incremental and decremental algorithms,as well as the hybrid algorithm to speed up the calculation.A large number of numerical experiments on real data and artificially generated data show the effectiveness of the new methods.The classical kernel canonical correlation analysis suffers from the problems of small-sample-size and overfitting.A common scheme is to use regularized technique.At present,the cross-validation method is a commonly used technique for selecting regularization parameters,but the amount of calculation of this algorithm is often very huge.Based on the search algorithm proposed in the block Inverse-Free-SOR algorithm,we propose a strategy for selecting the regularization parameter of kernel canonical correlation analysis.Numerical experiments on real data with different backgrounds verify the effectiveness of the strategy we propose.