求解复杂网络PageRank中心度的基于网络结构的并行子空间算法

分析数据网络是大数据时代的重要课题，测量节点中心度是其中重要的子问题。众多度量方式中，PageRank中心度有着从生物系统到网络安全的广泛应用。随着科技发展，数据网络逐渐复杂化。一方面，网络节点的数量激增；另一方面，节点之间的连接路数增加，即网络层数增多。提高复杂网络的PageRank中心度计算效率成为需研究的问题。根据现有文献和申请人前期结果，预处理的Krylov子空间算法是单层PageRank问题下最具潜力的算法之一，利用网络结构特征来简化问题也是极具前景的研究方向。本项目拟深入这两个方向并将它们结合：首先研究如何更充分挖掘网络结构特征来简化PageRank问题；然后为简化后的形式设计高效预处理Krylov子空间法，组成2-阶段算法。针对问题的复杂性，研究2-阶段算法的高效并行方案和计算多层PageRank中心度的方案。这将为复杂网络中心度计算提供新线索和实用算法。

The analysis of data network is an important topic in the era of big data, and the measurement of the centralities of network nodes is a widely concerned sub-problem. Among many measurements, PageRank centrality has a lot of important applications in different fields including biological systems, cyber security and so on. With the development of science and technology, data networks are becoming more and more complicated. On the one hand, the numbers of nodes in networks have soared, e.g. networks with more than 1 billion nodes are not uncommon. On the other hand, the number of connections between nodes increases, that is, the number of network layers considered increases. How to efficiently calculate PageRank centralities of complex networks becomes a valuable problem. Recent domestic and international studies show that the preconditioned Krylov subspace algorithm is one of the most potential algorithms for this problem. Besides, exploiting the network structure and the numerical properties of the transition probability matrix to reduce the solution cost is also a promising research direction. This project combines the above two directions. The first step is to study how to fully exploit some attributes in the network structure (node similarity and entry degree distribution) to benefit the computation of PageRank; The second step is to study how to adapt Krylov subspace algorithms to efficiently compute this problem, focusing on utilizing the characteristics of the problem and improving the parallelism. Finally, this project plans to develop an efficient intelligent algorithm that adapts to different network structures, layers, number of damping factors and different hardware environments.