日前，深圳计算科学研究院（以下简称“研究院”）1篇论文《Graph Algorithms with Partition Transparency》被国际顶级期刊IEEE TKDE正式收录。此次发表的论文开创性地提出了分区透明度的概念，解决了图算法不能在不同的分区下正常工作的难点问题，并能够进一步提升图分区算法的计算速度，彰显了研究院在图计算领域全面领先的科研实力。

目前，为了处理现实生活中的大型图，我们常常需要对分区图进行并行计算。于是，人们提出了各种图分区算法，包括边切割、点切割，以及混合分区。然而，针对特定图分区方法开发的图算法不能在其他图分区下正常工作，导致如需切换到其他图分区方法，可能不得不重写算法。

为了解决这一问题，研究院科研团队及其合作者开创性地提出了分区透明度的概念，这样图算法就能够在不同的分区下正常工作而无需更改，同时还能进一步提升混合分区算法的计算速度。实验证明：

（1）以图为中心模型和以点为中心模型的透明算法在边切割、点切割和混合分区下都能正确工作，不需要任何修改。

（2）在混合分区下的透明算法，比在边切割和点切割下的算法平均快2.3-21.2倍；同样的，比在边切割和点切割下的定制算法平均快2.8和1.6倍。

（3）即使所有算法都在点切割或边切割的情况下运行，透明算法与为单个分区量身定制的算法之间的性能差距也很小，不超过5.8%。

（4）在混合分区下，透明算法具有较好的扩展性，还能较快地处理大型图。当处理器数量n从32变为160时，平均快2.5倍。透明的WCC（weakly connected component）和PR（PageRank）算法在使用90个处理器对具有500M顶点和6B边的图进行计算时，平均花费66.5秒。

论文链接：

https://ieeexplore.ieee.org/document/9495146

数读研究院科研成果：

截至2021年8月23日，研究院共发表/录用高水平论文54篇，其中CCF A类44篇；申请专利/PCT共26项，授权发明专利3项。科研成果比肩全球任何一支大数据学术团队。