论文标题
在所有成对的最短社交网络中，矩阵产品收敛速度的下限
Lower Bounds on Rate of Convergence of Matrix Products in All Pairs Shortest Path of Social Network
论文作者
论文摘要
随着社交网络应用程序的快速发展，社交网络已成为人们互动的重要媒介。对于网络中所有对的最小距离计算，Alon n [4]提出了一种具有矩阵乘法的算法，与距离产品关联法和块矩阵乘法结合，所有对网络上的最短路径长度算法都具有时间绑定O（（2n^3）/b logn）。在实际应用中，考虑到社交网络的无规模特征以及计算机硬件上浮点操作的精确限制，我发现最短的路径算法具有改进的时间限制的O（（14n^3）/b）。基于上述理论，我提出了将稀疏性判断和收敛判断结合在一起的所有最短路径算法，利用距离产品算法与矩阵乘法，距离产品关联法，块矩阵乘法，社交网络的无标度特征以及对硬件的浮点操作的限制。与Alon N算法相比，在具有8508个参与者的社交网络数据集上测试，建议的算法在CPU和GPU上的性能提高了39％至36.2倍。
With the rapid development of social network applications, social network has become an important medium for people to interact. For the minimum distance computation of all pairs in networks, Alon N[4] proposed an algorithm with matrix multiplication, combining with distance product association law and block matrix multiplication, all pairs shortest path length algorithm on networks has time bound O((2n^3)/B logn). In practical applications, considering the scale-free characteristics of social networks and the precision limitations of floating-point operations on computer hardware, I found that the shortest path algorithm has an improved time bound O((14n^3)/B). Based on the above theory, I propose an all pairs shortest path algorithm that combines sparseness judgment and convergence judgment, leveraging the distance product algorithm with matrix multiplication, distance product association law, block matrix multiplication, scale-free characteristics of social networks, and limitation of floating-point operations on hardware. Testing on a social network dataset with 8508 actors, compared to Alon N algorithm, proposed algorithm has a performance improvement of 39% to 36.2 times on CPU and GPU.
