摘要：

二分图中bi-triangle的枚举是局部聚类系数(CC)计算等图分析任务的核心操作。随着实际二分图数据规模不断扩大, 其数据量已超出单机处理能力, 亟需依托分布式算法实现高效枚举。然而, 现有分布式分图枚举算法GP存在子图组合数据量庞大、消息过载及重复枚举等问题。对此, 基于bi-triangle拓扑特性定制分图策略, 提出两种优化算法。方法1将bi-triangle视为由3个wedge结构组成, 以wedge组为基本单位生成子图, 并提出基于A型和V型wedge组拼接的子图组合构造机制, 显著减少子图组合的数量和数据规模, 最终以wedge三元组枚举bi-triangle。此外, 为解决消息过载和重复枚举问题, 方法1提出基于分布式存储系统的子图读取机制和顶点有序性的去重机制。方法2将bi-triangle视为由2个zedge结构组成, 先以wedge组为基本单位执行第一次分图, 再通过"压缩zedge组"的构造与还原机制完成第二次分图, 最终以zedge二元组枚举bi-triangle, 实现比方法1更低阶的计算复杂度。实验结果表明, 与GP算法相比, 方法1平均只需处理0.5%的子图组合数据, 所用时间不到原来的2.2%;方法2平均处理约3.3%的数据量, 时间压缩至原来的1.0%以内。

关键词: 二分图, 6-环, 分布式分图枚举, wedge组, zedge组

Abstract:

Bi-triangle enumeration in bipartite graphs is a core operation for graph analysis tasks such as local Clustering Coefficient (CC) computation. As the scale of real-world bipartite graph data continues to increase, the data volume has exceeded the processing capacity of a single machine, necessitating efficient enumeration through distributed algorithms. However, existing distributed graph partitioning algorithm, called GP, suffer from issues such as large subgraph combination data volume, message overload, and redundant enumeration. To address these problems, two optimization algorithms based on the topological characteristics of bi-triangles are proposed and the graph partitioning strategies are customized accordingly. Method 1 treats a bi-triangle as composed of three wedge structures and generates subgraphs using wedge groups as the basic unit. It introduces a subgraph combination construction mechanism based on the concatenation of A-type and V-type wedge groups, significantly reducing the number and data size of subgraph combinations, and ultimately enumerates bi-triangles via wedge triplets. Additionally, to address message overload and redundant enumeration, Method 1 proposes a subgraph-reading mechanism based on a distributed storage system and a deduplication mechanism based on vertex ordering. Method 2 considers a bi-triangle as composed of two zedge structures. It first performs initial graph partitioning using wedge groups as the basic unit, then completes the second partitioning through a construction and restoration mechanism of "compressed zedge groups", ultimately enumerating bi-triangles via zedge pairs, achieving lower computational complexity than Method 1. Experimental results demonstrate that, compared with the GP algorithm, Method 1 processes only 0.5% of the subgraph combination data on average and the enumeration time is less than 2.2% of the original, whereas Method 2 processes approximately 3.3% of the data on average and the time is compressed to within 1.0% of the original.

Key words: bipartite graph, bi-triangle, distributed graph partitioning enumeration, wedge group, zedge group