基于GPS平台的高效k-bisimulation计算算法

计算图的互模划分在许多应用领域中起着至关重要的作用.图中两个点是互模的当且仅当这两点具有相同的特征.随着图数据规模的增大,传统的运行在单机上的互模划分算法面临着越来越大的挑战,分布式算法以及并行算法则成为提高图计算可扩展性的重要途径.最近研究人员提出两种基于MapReduce计算模型的分布式互模划分算法,算法均计算图的局部互模划分.采用MapReduce计算模型的分布式互模划分算法具有网络通讯代价高昂的问题,每次MapReduce迭代操作均会将整个图中所有点边的状态通过网络传输,重新为点边分配计算节点,但实际上计算点的局部互模划分特征仅需要局部信息.以此为研究出发点,本文提出了基于分布式图数据处理平台的互模划分算法,仅使用点的局部信息来计算其特征,进而提升计算效率.经过实验验证,本文算法可以大幅度减少算法执行过程中的网络数据传输量.在包含数亿边大图上的实验表明,在未经图的预处理的情况下,本文算法的时间效率提升了7~16倍,有效的解决了MapReduce计算模型带来的网络通讯代价高昂的问题.

GPS-based algorithms for efficient k-bisimulation computation

Computing the bisimulation partition of a graph plays a key role in various application areas. Two nodes are bisimular if and only if they obtain the same signature. Faced with a big graph, traditional in-memory algorithms can hardly meet practical need. Recently, researchers have proposed two kinds of MapReduce based distributed algorithms to handle bisimulation partition on the big graph, both calculating localized bisimulation. MapReduce based algorithms suffer from huge network communication burden, at the meantime, we only need local information to calculate the signature of a node. Motivated by these observations, we propose an algorithm based on a graph processing system that only uses local information to calculate the signature of a node. We argue that our algorithm can make considerable reduction on the network transportation during computation. In the experiment calculated on the big graph which contains billions of edges, our algorithm can be seven to sixteen times faster even without graph pre-partition.