一种基于扫帚树采样的二分团近似计数方法及装置

本发明公开了一种基于扫帚树采样的二分团近似计数方法及装置，所述方法包括：获取二分图G(U,V,E)，其中U和V为不相交的顶点集，E为边集，并接收二分团规模参数p和q；对二分图G进行预处理，包括Core‑reduction剪枝和图染色，得到预处理后的二分图G'；构造扫帚树结构，所述扫帚树为满足特定边连接条件的树形结构，用于稀疏化表示二分团；使用动态规划算法计算满足颜色递增约束的扫帚树子图数量B；基于动态规划结果，按概率反向采样扫帚树的边，并统计采样路径中满足二分团约束的路径数量；根据多次采样的结果，计算二分团数量的近似值。本发明提升了二分团计数的效率与精度。