基于距离泛化的二分图(α,β)-core高效分解算法

(α,β)-core分解作为图数据管理与分析研究中的热点问题,已经被广泛应用于电商欺诈检测和兴趣群组推荐等实际场景中。然而现有(α,β)-core模型在构建时仅考虑顶点距离为1的邻居,难以刻画出二部图社区中的细粒度信息。针对此问题,提出了基于距离泛化的(α,β,h)-core模型,即由二部图中两个不相交的顶点集构成一个最大子图,满足一个集合中的任何一个顶点至少有α个与它的距离不大于h的邻居顶点,另一个集合中的任何一个顶点至少有β个与它的距离不大于h的邻居顶点。通过引入距离为h的邻居,解决了(α,β)-core模型细粒度刻画能力不足的问题。由于新模型需要考虑距离不大于h的邻居,因此(α,β,h)-core分解变得更为困难。为此,提出了基于计算共享的分解策略,据此设计了高效的(α,β,h)-core分解算法,并分析了算法性能。考虑到确定距离不大于h的邻居顶点非常耗时,还提出一种(α,β,h)-core下界以减少重复计算距离不大于h的邻居顶点,进一步提高计算效率。在8个真实图数据上的对比实验结果验证了新模型的有效性和算法的高效性。