一种基于候选顶点合并技术的极大二分团枚举方法

摘要

本发明公开了一种基于候选顶点合并技术的极大二分团枚举方法，获取二分图G(U,V,E),其中U和V是二分图中的两个不相交顶点集，E是边集；有选择地对顶点集U和V进行互换，并有选择地对顶点进行重排序；以U,V为函数初始参数，递归调用计算函数；输出所有极大二分团或极大二分团的计数结果给用户。本发明利用枚举树节点内候选顶点可合并的特性，减少了计算过程中的无效分支与无效计算，提升了极大二分团枚举的效率。同时，本发明所提出的顶点合并技术适用于其他图枚举算法，能够提升如极大团枚举、子图挖掘等算法的计算效率。

说明书

技术领域

本发明属于计算机图计算领域与数据挖掘领域，尤其是涉及一种基于候选顶点合并技术的极大二分团枚举方法。

背景技术

二分图上的极大二分团枚举是数据挖掘领域中的基础问题和研究热点。它在电子商务、基因分析、重叠社区检测、GNN信息聚合以及社交关系推荐等领域具有广泛的应用。以电子商务领域为例，用户与商品构成了二分图的两个顶点集，用户购买商品的关系构成了二分图的边。一批用户同时购买一批商品的行为构成了二分团。其中极大二分团是二分图中不被其他任何二分团完全包含的二分团，能够最大程度地描述用户群体对同组商品的购买行为。通过枚举二分图中的所有极大二分团，可以帮助发现可疑的交易，例如刷单行为。

目前的极大二分团枚举方法主要采用递归算法，基于枚举树实现。具体而言，对于二分图G(U,V,E)，现有方法首先递归地生成V集合的幂集作为右部顶点集R，然后将右部顶点集R扩展为对应的二分团(L,R)。算法会枚举所有的极大二分团并裁剪其中的非极大二分团。近年来，针对极大二分团枚举方法的优化主要包括顶点排序、裁剪无效分支和提升并行性等。iMBEA(improved maximal biclique enumeration algorithm)方法结合回溯法与分支定界法，将每个节点内顶点按照运行时邻居数量升序排列。ParMBE(parallel maximalbiclique enumeration)方法通过共享内存的方式，实现多CPU核并行计算的极大二分团枚举算法。PMBE(pivot-based maximal biclique enumeration)方法采用基于枢纽的搜索策略，在每个节点选定一个枢纽顶点用于减少无效分支。OoMBEA(order optimized maximalbiclique enumeration algorithm)方法按照单边顺序对顶点的搜索顺序进行重排序。公开号为CN110175172A的中国专利文献公开了一种基于稀疏二分二图的极大二分团并行枚举方法，包括：均匀的初始化任务分配和高效的任务迁移，以及对单个任务的信息量做了去冗余操作，让冗余重复的信息存储在一个公共区域，每个任务只有执行的时候，才会去查询并获得所有参数信息等具体内容。然而上述方法忽略了枚举树节点内候选顶点可合并的特性，因此仍具有很大提升空间。

发明内容

针对现有技术忽略了枚举树节点内候选可合并特性的不足，本发明提供了一种基于候选顶点合并技术的极大二分团枚举方法，通过合并枚举树节点内具有相同运行时邻居的顶点，减少无效分支与无效计算，提升极大二分团枚举效率。

一种基于候选顶点合并技术的极大二分团枚举方法，包括：

获取待处理的二分图G(U,V,E),其中U和V是二分图中的两个不相交顶点集，E是边集；所述二分图为在电子商务场景下由用户和商品所组成的二分图，在社交网络场景下由用户和兴趣爱好组成的二分图或在基因分析场景下基因与性状的二分图；

以U,

3-1.获取当前枚举树节点对应的L,R,C三个参数；

3-2.判断C集合是否为空集，是则函数退出，否则执行步骤3-3；

3-3.创建当前枚举树节点(L,R,C)的副本(L’,R’,C’)；

3-4.从C集合中选择一个顶点v，计算集合L与顶点v邻居集合的交集，将计算结果赋值给L’；

3-5.将L’集合中每个元素的邻居集合求交集，将计算结果赋值给R’；

3-6.判断R’是否是R∪C的子集，是则执行步骤3-7，否则执行步骤3-11；

3-7.将C集合中全部顶点划分到一个组中；

3-8.以步骤3-7划分获得的组作为初始组别，依次用L’集合中的元素u对对应的每一个组进行划分；每个组内顶点根据其是否与u相连进行划分；

3-9.将C集合中顶点邻居与L’交集不为空集且不为L’的顶点赋值给C’，保留分组关系；

3-10.输出极大二分团(L’，R’)。递归地执行函数BicliqueFind(L’，R’，C’)，其中，在赋值L’的副本L”时，从C’集合中按照C’保留的分组关系，选择一个顶点v或一个组别的顶点，计算集合L与顶点v或一个组别的顶点邻居集合的交集，将计算结果赋值给L’；

3-11.基于步骤3-8的分组结果，从C集合中删除与顶点v同组的全部顶点，执行步骤3-2；

(4)输出所有极大二分团或极大二分团的计数结果给用户。

进一步地，获取待处理的二分图G(U,V,E)后，还包括有选择地对顶点集U和V进行互换，并有选择地对顶点进行重排序步骤，其中顶点集U,V的互换方法选择顶点集顶点个数较小的集合作为V，选择顶点数较大的集合作为U；重排序具体为将V中顶点按照顶点的邻居数量由小到大的方式进行重排序。

进一步地，每次调用BicliqueFind(L,R,C)函数，对应生成一个集合枚举树节点，其中(L,R)构成节点对应的二分团，C是候选顶点集合用于扩展R集合产生新节点，其中

与现有技术相比，本发明具有以下有益效果：

1.本发明利用枚举树节点内候选顶点可合并的特性，提出了一种基于候选顶点合并技术的极大二分团枚举方法，减少了计算过程中的无效分支与无效计算，提升了极大二分团枚举的效率，进而提升电子商务中的刷单行为检出率及检出速度、社交网络中的推荐速度、基因分析、重叠社区检测速度等。

2.本发明所提出的顶点合并技术适用于其他图枚举算法，能够提升如极大团枚举、子图挖掘等算法的计算效率。

附图说明

图1为本发明的流程图；

图2为本发明中BicliqueFind(L,R,C)函数执行流程图；

图3为本发明实施例中的二分图G0；

图4为本发明实施例中采用顶点合并技术对应生成的枚举树；

图5为本发明实施例中生成节点p的计算过程；

图6为本发明实施例中不采用顶点合并技术对应生成的枚举树。

具体实施方式

如图1所示，一种基于候选顶点合并技术的极大二分团枚举方法，包括以下步骤：

(1)获取二分图G(U,V,E),其中，所述二分图为在电子商务场景下由用户和商品所组成的二分图，在社交网络场景下由用户和兴趣爱好组成的二分图或在基因分析场景下基因与性状的二分图等；U和V是二分图中的两个不相交顶点集，E是边集；

(2)有选择地对顶点集U和V进行互换，并有选择地对顶点进行重排序。

(3)以U,

3-1.获取当前枚举树节点对应的L,R,C三个参数；

3-2.判断C集合是否为空集，是则函数退出，否则执行步骤3-3；

3-3.创建当前枚举树节点(L,R,C)的副本(L’,R’,C’)；

3-4.从C集合中选择一个顶点v，计算集合L与顶点v邻居集合的交集，将计算结果赋值给L’；

3-5.将L’集合中每个元素的邻居集合求交集，将计算结果赋值给R’；

3-6.判断R’是否是R∪C的子集，是则执行步骤3-7，否则执行步骤3-11；

3-7.将C集合中全部顶点划分到一个组中；

3-8.以步骤3-7划分获得的组作为初始组别，依次用L’集合中的元素u对对应的每一个组进行划分；每个组内顶点根据其是否与u相连进行划分；

3-9.将C集合中顶点邻居与L’交集不为空集且不为L’的顶点赋值给C’，保留分组关系；

3-10.输出极大二分团(L’，R’)。递归地执行函数BicliqueFind(L’，R’，C’)，其中，在赋值L’的副本L”时，从C’集合中按照C’保留的分组关系，选择一个顶点v或一个组别的顶点，计算集合L与顶点v或一个组别的顶点邻居集合的交集，将计算结果赋值给L’；

3-11.基于步骤3-8的分组结果，从C集合中删除与顶点v同组的全部顶点，执行步骤3-2；

(4)输出所有极大二分团或极大二分团的计数结果给用户。

下面结合附图和实施例对本发明做进一步详细描述，需要指出的是，以下所述实施例旨在便于对本发明的理解，而对其不起任何限定作用。

实施例1：

以电子商务为例，在如阿里巴巴等企业中，单日的交易次数可突破1亿次，即对应一个由超过1亿条边的二分图，描述了用户对商品的交易行为。极大二分团最大程度地描述了用户群体对同组商品的批量购买行为。然而，一些恶意商家会通过刷单方式，雇佣一批用户同时购买一批商品，以提高目标商品的曝光率。极大二分团能够有效地描述此类刷单行为。因此，通过枚举极大二分团，辅助尽早发现大部分的可疑交易，提升可疑交易的检出率。具体地，利用基于候选顶点合并技术的极大二分团枚举方法的一种可疑交易检测方法，包括以下步骤：

如步骤(1)所示，基于候选顶点合并技术的极大二分团枚举方法获取二分图G0。本实施例中，所述二分图为在电子商务场景下由用户和商品所组成的二分图，如图3所示；

如步骤(2)所示，枚举树选择顶点数较少的集合{v

如步骤(3)所示，递归调用BicliqueFind(L,R,C)函数生成搜索树；图4展示了本发明实施例中采用顶点合并技术对应生成的搜索树。图4所示的枚举树以U，

3-1.获取根节点对应的参数L＝U，

3-2.判断C集合是否为空集合，否则执行步骤3-3；是则函数退出结束；

3-3.创建当前枚举树节点(L,R,C)的副本(L’,R’,C’)；

3-4.从C集合中选择一个顶点v

3-5.将L’集合中每个元素的邻居的集合求交集，将计算结果赋值给R’。本实施例中用N(*)表示顶点*的邻居，可知R’＝N(u

3-6.判断R’是否是R∪C的子集，是则执行步骤3-7，否则执行步骤3-11；

3-7.如图5所示，将C集合中的全部顶点v

3-8.如图5所示，以步骤3-7划分获得的组作为初始组别，依次用L’集合中的元素u对对应的每一个组进行划分。每个组内顶点根据其是否与u相连进行划分。具体地，按顺序根据C是否与u

3-9.将C集合中顶点邻居与L’交集不为空集且不为L’的顶点v

3-10.输出下一节点p对应的极大二分团(L’,R’)。递归地执行函数BicliqueFind(L’，R’，C’)。其中，在赋值L’的副本L”时，从C’集合中按照C’保留的分组关系，选择一个顶点v或一个组别的顶点，计算集合L与顶点v或一个组别的顶点邻居集合的交集，将计算结果赋值给L’；即在以节点p为根节点的子树中，同组元素v

3-11.基于步骤3-8的分组结果，从C集合中删除与顶点v

如步骤(4)所示，输出所有极大二分团或极大二分团即可疑交易的计数结果给用户。

对比的，图6展示了不采用顶点合并技术的极大二分团枚举过程。通过对比图4可知，基于顶点合并技术的极大二分团枚举方法合并枚举树节点内具有相同运行时邻居的顶点v

实施例2

在社交网络场景下，基于由用户和兴趣爱好组成的二分图的极大二分团最大程度地描述了用户群体的相同兴趣爱好。通过极大二分团枚举，可以更好地辅助社交推荐系统。通过发现用户之间紧密的连接关系，系统可以推荐给用户其他拥有相似兴趣爱好的用户，从而增加社交互动和用户满意度。具体地，利用基于候选顶点合并技术的极大二分团枚举方法的一种社交推荐系统的推荐方法，包括以下步骤：

如步骤(1)所示，基于候选顶点合并技术的极大二分团枚举方法获取二分图G0。本实施例中，社交网络场景下由用户和兴趣爱好组成的二分图；

如步骤(2)所示，有选择地对顶点集U和V进行互换，并有选择地对顶点进行重排序。顶点集U,V的互换方法选择顶点集顶点个数较小的集合作为V，选择顶点数较大的集合作为U；重排序具体为将V中顶点按照顶点的邻居数量由小到大的方式进行重排序。

如步骤(3)所示，以U,

如步骤(4)所示，输出所有极大二分团即具有最大相似兴趣爱好的用户群体及兴趣爱好类别，基于极大二分团进行用户的相互推荐或者当前用户未关注的兴趣爱好推荐。

本发明基于顶点合并技术的极大二分团枚举方法合并枚举树节点内具有相同运行时邻居的顶点，减少对应的无效分支与无效计算，提升了计算效率，提升社交推荐系统的推荐速度和准确度，从而增加社交互动和用户满意度。

实施例3

在基因分析场景下，极大二分团描述了同一组基因对间一组性状的决定作用。枚举极大二分团能够更好地帮助生物学家理解基因与性状之间的关系。通过分析不同基因之间的连接模式，可以揭示基因之间的相互作用以及它们对性状表现的综合景响。这种基于极大二分团的分析方法能够提供更全面和深入的基因功能研究视角，帮助科学家进一步进行蛋白质-蛋白质相互作用网络分析。具体地，利用基于候选顶点合并技术的极大二分团枚举方法的一种基因与性状的关系分析方法，包括以下步骤：

如步骤(1)所示，基于候选顶点合并技术的极大二分团枚举方法获取二分图G0。本实施例中，为在基因分析场景下基因与性状的二分图；

如步骤(2)所示，有选择地对顶点集U和V进行互换，并有选择地对顶点进行重排序。顶点集U,V的互换方法选择顶点集顶点个数较小的集合作为V，选择顶点数较大的集合作为U；重排序具体为将V中顶点按照顶点的邻居数量由小到大的方式进行重排序。

如步骤(3)所示，以U,

如步骤(4)所示，输出所有极大二分团即具有最大连接关系的基因及性状输出给用户。

本发明基于顶点合并技术的极大二分团枚举方法合并枚举树节点内具有相同运行时邻居的顶点，减少对应的无效分支与无效计算，提升了计算效率，提升基因与性状的关系分析的速度和准确度，帮助科学家进一步进行蛋白质-蛋白质相互作用网络分析，有助于准确预测基因变异对性状造成的影响，并为疾病研究、遗传工程等领域提供重要的指导意义。

此外，本发明方法同样适用于重叠社区检测、GNN信息聚合等。

以上所述的实施例对本发明的技术方案和有益效果进行了详细说明，应理解的是以上所述仅为本发明的具体实施例，并不用于限制本发明，凡在本发明的原则范围内所做的任何修改、补充和等同替换，均应包含在本发明的保护范围之内。