对等网络中平均最短路径长度的分析

Analysis of the Shortest Path Length in Peer-to-Peer Networks

对等网络理论上可以将它看成一个大的无向图,图中的顶点表示网络中的每个计算节点,图的边则表示计算节点之间的连接.P2P网络,类似于其他的复杂网络(如Internet、web和社会关系网络),这类网络中的节点的度的概率分布呈现出Pow-er-law的分布特性.传统上对这些网络建模时采用的是随机图模型,然而随机图网络与Power-law(网络的一个本质区别是在随机图网络中节点度的概率分布呈现泊松分布,这种节点度的分布差异将导致对网络的建模分析不能反映实际网络的真实特性.通信网络(如Internet和P2P网络)中任意两点间的最短路径长度是衡量这种网络的一个重要特征量,它直接关系到诸如路由、搜索等相关算法的设计与实现,本文基于Power-law网络模型对P2P网络的最短路径长度进行理论建模与分析,并通过对实际网络的测量来验证理论分析结果的正确性.

Peer-to-Peer（P2P）networks can be represented as graphs, where vertexes represent nodes in networks and edges represent the links between nodes. Like other complex networks such as Internet, web and social network, P2P networks often exhibit power-law degree distribution. Traditionally, communication networks were always modeled as random graphs with Poisson degree distributions, which will lead to mischaracterize real networks. In communication networks, shortest path length between two arbitrary nodes is a very important characteristic, and the design and implementation of many algorithms such as routing and searching is based on it. This paper presened theoretical modeling and analysis in detail to P2P network, and verifies the correctness of theoretical analysis through measuring real Gnutella network.