时 磊 刘 锐 虢 韬 杨 恒 王 伟 陈 玥 张 磊 曹小钰 罗 飞

1(贵州电网有限责任公司输电运行检修分公司 贵州 贵阳 550005)2(国网电力科学研究院武汉南瑞有限责任公司 湖北 武汉 430074)3(电网雷击风险预防湖北省重点实验室 湖北 武汉 430074)4(武汉大学计算机学院 湖北 武汉 430079)

0 引 言

在图理论中，两组对象之间的连接关系可以建模为二分图[1-2]。其中节点表示对象，边表示两组对象节点之间的关系。频繁连接的对象集合，往往是应用背景下有意义的社团群体。边的连接程度是找到这些有意义社团群体的重要特征。二分图中，全连接二分子图称为完全二分子图(biclique)。稠密的、近乎完全连接的二分子图称为准完全二分子图(quasi-biclique)。因为在数据分析中常常存在缺失、假阳性等问题[3]，相对于完全二分子图，准完全二分子图不要求完全连接，使其具备容忍误差的优势，所以它更适合实际建模。

quasi-biclique可定义灵活的结构特征来满足不同应用。例如，Yan[4]提出α-quasi-biclique，要求一组中每个节点至少连接另一组中α%数量的节点。在α-quasi-biclique的基础上，进一步产生了δ-quasi-biclique[5]，要求一组中的每个节点与另一组至少连接(1-δ)的节点。除了限制节点间连接数量，还有一类应用考虑准完全二分子图边的权重。例如Maulik[6]提出在加权二分图中找最大边值的准完全二分子图。

准完全二分子图的结构特征定义了在二分图中搜索的目标，搜索算法用于完成发现目标准完全二分子图。大多数准完全二分子图搜索是NP问题[5]，但是相应工作均给出了近似优化解。……