针对流式图的混合聚类的制作方法

摘要: 背景技术:1、图是表示诸如社交媒体平台和金融系统的真实世界网络的有效方式。图聚类算法标识网络内的相互关联的实体的社区。可以在诸如推荐系统和风险评估的领域中使用聚...
针对流式图的混合聚类的制作方法

背景技术:

1、图是表示诸如社交媒体平台和金融系统的真实世界网络的有效方式。图聚类算法标识网络内的相互关联的实体的社区。可以在诸如推荐系统和风险评估的领域中使用聚类算法的结果。图通常是动态的,其中节点和边由更新的流连续修改,因此必须与图更新并发地处理图查询。改善动态图上的图查询的延迟仍是挑战。

技术实现思路

1、根据本公开的一个方面,提供了一种计算系统,包括处理电路以及存储指令的存储器,所述指令在被执行时使得所述处理电路实现混合图聚类服务。所述混合图聚类服务被配置为从图更新客户端接收事务更新,每个事务更新指示图的子图在状态上的变化,其中所述图是包括多个节点和多个边的流式图,所述多个节点中的每个节点表示网络中的实体。对于事务更新中的每个事务更新,混合图聚类服务被配置为将事务更新发送到全局聚类队列,基于事务更新对子图执行局部聚类,从而生成针对子图中的每个节点的局部聚类更新的社区标识(id),并且利用针对子图中的每个节点的局部聚类更新的社区id来更新社区列表,其中社区列表包括每个相应节点以及由聚类操作指派给相应节点的社区的相关联的社区id。混合图聚类服务还被配置为输出更新的社区列表,该更新的社区列表包括局部聚类更新的社区id。混合图聚类服务还被配置为基于全局聚类队列中的事务更新对图副本执行全局聚类,从而生成针对图中的每个节点的全局聚类更新的社区id,并且利用图中的每个节点的全局聚类更新的社区id来更新社区列表。

2、提供本 技术实现要素: 是为了以简化的形式介绍以下在具体实施方式中进一步描述的一些概念。本发明内容不旨在标识所要求保护的主题的关键特征或必要特征,也不旨在用于限制所要求保护的主题的范围。此外,所要求保护的主题不限于解决本公开的任何部分中指出的任何或所有缺点的实施方式。

1.一种计算系统,包括:

2. 根据权利要求1所述的计算系统,其中所述处理电路还被配置为至少部分地通过以下操作来初始化所述混合图聚类服务:

3.根据权利要求1所述的计算系统,其中所述局部聚类包括:基于所述事务更新更新所述图的所述子图的所述节点和所述边,并且使用louvain社区检测算法基于所述图的所述子图计算所述局部聚类更新的社区标识。

4.根据权利要求1所述的计算系统,其中所述全局聚类包括:基于所述全局聚类队列的所述事务更新对所述图副本的所述节点和所述边执行批量更新,并且使用所述louvain社区检测算法基于所述图副本计算所述全局聚类更新的社区标识。

5.根据权利要求1所述的计算系统,其中所述局部聚类和所述全局聚类被同时执行。

6.根据权利要求1所述的计算系统,其中每个节点具有当所述节点被更新时初始化的定时器或计数器,并且在预设时间届满或计数达标后,所述节点被标记为删除。

7.根据权利要求1所述的计算系统,其中每个节点被映射到相应的存储器容器,并且当所述事务更新指示向所述图添加新节点时,所述新节点被映射到相应节点已被删除的所述存储器容器。

8.根据权利要求1所述的计算系统,其中所述图和所述社区列表被周期性地写入所述分布式文件系统。

9.根据权利要求1所述的计算系统,其中所述处理电路还被配置为至少部分地通过以下操作来从第一图聚类服务转变到第二图聚类服务:

10.根据权利要求1所述的计算系统,其中所述处理电路还被配置为:对更新的所述社区列表执行运行时图查询,计算并输出图查询结果。

11.根据权利要求10所述的计算系统,其中所述运行时图查询包括风险查询,并且所述处理电路还被配置为:

12.一种计算机化的方法,包括:

13.根据权利要求12所述的方法,其中所述图是从分布式文件系统读取的,并且对所述图执行所述聚类操作以生成所述社区列表。

14.根据权利要求12所述的方法,其中所述局部聚类包括:基于所述事务更新更新所述图的所述子图的所述节点和所述边,并且使用louvain社区检测算法基于所述图的所述子图计算所述局部聚类更新的社区标识。

15.根据权利要求12所述的方法,其中所述全局聚类包括:基于所述全局聚类队列的所述事务更新对所述图副本的所述节点和所述边执行批量更新,并且使用所述louvain社区检测算法基于所述图副本计算所述全局聚类更新的社区标识。

16.根据权利要求12所述的方法,其中所述局部聚类和所述全局聚类被同时执行。

17.根据权利要求12所述的方法,其中每个节点具有当所述节点被更新时初始化的定时器或计数器,并且在预设时间届满或计数达标后,所述节点被标记为删除。

18.根据权利要求12所述的方法,其中每个节点被映射到相应的存储器容器,并且当所述事务更新指示向所述图添加新节点时,所述新节点被映射到相应节点已被删除的所述存储器容器。

19.根据权利要求12所述的方法,其中所述图和所述社区列表被周期性地写入所述分布式文件系统。

20.一种计算系统,包括: