一种基于GAS模型的k-Truss分解算法

在大规模网络中发现稠密子图具有极其广泛的应用,如社区发现、垃圾邮件检测等。为了在大规模网络数据中快速、有效地发现稠密子图,本文提出一种基于GAS (Gather-Apply-Scatter)编程模型的分布式k-Truss算法—GASTruss。该算法采用GAS的模式完成数据同步和算法迭代,有效的克服了传统并行算法重复性计算及不能有效处理依赖关系大的数据等问题。本实验选择在GraphLab平台上进行,结果表明：与串行k-Truss算法以及基于MapReduce的GPTruss算法性能相比,GASTruss算法对数据规模具有良好的拓展性,在保持算法效果的同时能有效降低时间复杂度。

A GAS based k-Truss Decomposition Method

Finding dense subgraphs in the large-scale network has the extremely widespread uses, such as community discovery and spam detection, etc. In order to find dense subgraphs rapidly and effectively in the large-scale network, this paper proposed a distributed k-Truss decomposition method based on GAS-- GASTruss. The algorithm adopted the "Gather-Apply-Scatter" programming model to complete the data synchronization and iteration, and effectively overcame the problem of traditional parallel algorithms in overmuch repetitive calculation and incapacity of handling the data with strong dependencies. Experiment was tested on GraphLab platform, the results show that compared with the serial k-Truss algorithm and the MapReduce-based algorithm GPTruss, this method outperforms in terms of running time while maintaining the calculate accuracy.