关键词: 网络节点排序, 自适应物理模型, 最小化罚函数, 量子线性方程求解器, 量子虚时演化

Abstract:

Ranking the node of a network is one of the central problems in a complex network. Here, An improved SpringRank method was proposed that builds an adaptive physical model with variable-spring connected between nodes and a novel penalty function. By minimizing the penalty function, the method can rank the nodes of a directed and weighted complex network. To decrease the computation complexity which increases too fast with the number of nodes, quantum algorithms were used to speed up the process of minimizing the penalty functions. The convexity enables us to find the minimum by solving a linear system. When the linear system has the properties of sparsity and a small conditional number, we use the HHL algorithm to find the minimum of the penalty function by solving the linear equation. And we use the QITE algorithm to find the minimum by updating the parameters iteratively when the linear system doesn’ t have those properties. Lastly, using the quantum simulator QPanda, we implemented the algorithms for several networks and gave the right ranking results.

Key words: network ranking, adaptive physical model, penalty function minimizing, quantum linear