基于自适应物理模型的量子网络排序算法

Quantum algorithms for ranking nodes of network

对网络节点进行排序是复杂网络分析的核心问题之一.提出了一种改进的SpringRank算法.该算法基于一个把节点之间连接视为静止长度可变的弹簧的自适应物理模型,并基于此定义一个新型罚函数.通过最小化罚函数,该算法可以对有向和加权复杂网络的节点进行排序.为了避免经典算法中计算复杂度随着节点数量的增加而过快增加的情况,使用量子算法加速罚函数最小化过程.罚函数的凸性使我们能够通过求解线性系统的方式找到最小值.当线性系统具有稀疏且条件数较小的性质时,使用量子线性求解器HHL算法找到罚函数的最小值.如果线性系统没有这两个性质,则使用量子虚时演化QITE算法通过迭代方法找到最小值.最后,使用量子模拟器QPanda对多个网络用所提出的两种求最小值算法进行了节点排序测试,实验结果显示两种算法都能给出正确的排序结果.

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.