[go: up one dir, main page]

CN111814006A - 图网络结构的分析方法、装置和计算机设备 - Google Patents

图网络结构的分析方法、装置和计算机设备 Download PDF

Info

Publication number
CN111814006A
CN111814006A CN202010733106.8A CN202010733106A CN111814006A CN 111814006 A CN111814006 A CN 111814006A CN 202010733106 A CN202010733106 A CN 202010733106A CN 111814006 A CN111814006 A CN 111814006A
Authority
CN
China
Prior art keywords
graph
network structure
vertex
edge
data set
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN202010733106.8A
Other languages
English (en)
Inventor
刘利
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
OneConnect Smart Technology Co Ltd
OneConnect Financial Technology Co Ltd Shanghai
Original Assignee
OneConnect Financial Technology Co Ltd Shanghai
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by OneConnect Financial Technology Co Ltd Shanghai filed Critical OneConnect Financial Technology Co Ltd Shanghai
Priority to CN202010733106.8A priority Critical patent/CN111814006A/zh
Publication of CN111814006A publication Critical patent/CN111814006A/zh
Pending legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9024—Graphs; Linked lists
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/36—Creation of semantic tools, e.g. ontology or thesauri
    • G06F16/367—Ontology
    • G06Q10/40—

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Animal Behavior & Ethology (AREA)
  • Computational Linguistics (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

本申请涉及人工智能领域，揭示了图网络结构的分析方法，根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；将所述图网络结构中的各顶点以及各条边分别映射指定数据集；根据所述执行脚本，获取与所述图分析任务相对应的图运算符；利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。建立有扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能。

Description

图网络结构的分析方法、装置和计算机设备
技术领域
本申请涉及到人工智能领域，特别是涉及到图网络结构的分析方法、装置和计算机设备。
背景技术
通过图可以更直观地表达事物以及事物之间的联系，但计算机识别图时需要根据图进行建模，以识别图中信息并计算图中各事物之间的关系。图分析在研究和工业中扮演着重要的角色。比如图能够表示社交网络中的社区关系。但关于图的复杂分析问题需要结合多种分析操作，例如对网站进行排名或分析社交网络，图数据模型是执行图算法的先决条件。目前大规模图计算是基于某个数据流框架上的库的实现，如Apache Spark上的GraphX或Apache Flink上的Gelly，结合底层框架提供的通用数据转换运算符执行某个图计算，但不支持数据集，无法解决复杂的分析任务。
发明内容
本申请的主要目的为提供图网络结构的分析方法，旨在解决现有图计算不支持数据集，无法解决复杂的分析任务的技术问题。
本申请提出一种图网络结构的分析方法，包括：
根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；
将所述图网络结构中的各顶点以及各条边分别映射指定数据集；
根据所述执行脚本，获取与所述图分析任务相对应的图运算符；
利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
优选地，所述根据图分析任务的执行脚本，获取待分析的图网络结构的步骤，包括：
获取图分析任务的执行脚本中携带的所述待分析的图网络结构的图元素，其中，所述图元素包括图头；
根据所述图头从指定数据库中抽取所述图头对应的图头数据集；
判断所述图头数据集是否包括多个对象；
若否，则判定所述待分析的图网络结构为图头为单个对象的逻辑图；
从所述数据集中获取与所述逻辑图关联的顶点数据和边数据，分别对应组成顶点集和边集；
通过所述顶点集和边集表示所述逻辑图，得到所述待分析的图网络结构。
优选地，指定数据集包括Flink数据集，所述根据所述执行脚本，获取与所述图分析任务相对应的图运算符的步骤之后，包括：
获取各所述图运算符的执行顺序；
按照所述执行顺序将各所述图运算符，通过Java编程语言链接为运算逻辑；
将所述运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序。
优选地，所述图运算符包括排除运算符，利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：
获取第一逻辑图对应的第一顶点集和第一边集，获取第二逻辑图对应的第二顶点集和第二边集；
通过函数ID_ONLY从第二逻辑图中，提取所述第二逻辑图的标识符，形成新id对象对应的数据集；
通过所述排除运算符筛选指定顶点和指定边，得到所述排除运算符对应的排除结果数据集，其中，所述指定顶点包含于所述第一顶点集，不包含于所述第二顶点集，所述指定边真包含于所述第一边集；
通过Flink广播将所述排除结果数据集发送至Apache Flink框架集群的所有节点。
优选地，所述图网络结构为多个逻辑图组成的社交网络图，所述图运算符包括Flink提供的关系操作符，所述利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：
识别用户选定的关系操作符是否为寻找所述社交网络图中逻辑图之间的最大公共子图；
若是，则聚集所述社交网络图中每个所述逻辑图的顶点数量；
根据每个所述逻辑图的顶点数量，选择高于最小顶点计数的指定逻辑图；
基于所述指定逻辑图，通过标签传播算法得到所述社交网络图中逻辑图之间的最大公共子图。
优选地，所述图预算符至少包括两个，所述利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：
获取多个图预算符对应的指定Flink程序；
获取所述指定Flink程序当前运行节点，预测可并发执行运算的数据集；
将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器；
接收各指定机器分别执行分发的数据集得到的计算结果；
将各计算结果汇总得到多个图预算符的分析结果；
将所述多个图预算符的分析结果，通过Flink广播发送至Apache Flink框架集群的所有节点。
优选地，所述指定Flink程序包括对特定逻辑图的聚合运算、变换预算和模式匹配预算，所述将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器的步骤，包括：
获取所述特定逻辑图对应的数据集、聚合运算对应的聚合函数、变换运算对应的转换函数以及模式匹配运算对应的匹配函数；
将所述特定逻辑图对应的数据集和聚合运算对应的聚合函数分发至集群中的第一机器，将所述特定逻辑图对应的数据集和变换运算对应的转换函数分发至集群中的第二机器，将所述特定逻辑图对应的数据集和模式匹配运算对应的匹配函数分发至集群中的第三机器；
控制所述第一机器、所述第二机器和所述第三机器并发运行。
本申请还提供了一种图网络结构的分析装置，包括：
第一获取模块，用于根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；
映射模块，用于将所述图网络结构中的各顶点以及各条边分别映射指定数据集；
第二获取模块，用于根据所述执行脚本，获取与所述图分析任务相对应的图运算符；
计算模块，用于利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
本申请还提供了一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现上述方法的步骤。
本申请还提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述的方法的步骤。
本申请不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在ApacheFLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。
附图说明
图1本申请一实施例的图网络结构的分析方法流程示意图；
图2本申请一实施例的图网络结构的分析装置结构示意图；
图3本申请一实施例的计算机设备内部结构示意图。
具体实施方式
为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。
参照图1，本申请一实施例的图网络结构的分析方法，包括：
S1：根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；
S2：将所述图网络结构中的各顶点以及各条边分别映射指定数据集；
S3：根据所述执行脚本，获取与所述图分析任务相对应的图运算符；
S4：利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
本申请中的图网络结构带有扩展属性，图网络结构由顶点集V和边集E组成，其中顶点集V中包括各类型顶点，由点对应的第一类型标签和第一属性进行描述和表示各顶点。举例地，上述带扩展属性的图网络结构为图社交网络，表示为有向图G＝<V，E>，由一组顶点V和一组边
Figure BDA0002604023300000051
组成。比如图网络由顶点集V＝{v0，…，v9}和边集E＝{e0，…，e19}组成。顶点可分为多种类型，包括表示人(Person)的顶点、表示论坛(Forum)的顶点和表示兴趣(Tag)的顶点。不同类型的顶点由相应的第一类型标签表示和相应的第一属性进行描述。边描述了顶点之间的关系，也有对应的第二类型标签(如knows)和第二属性进行描述。具有相同类型标签的顶点可能具有不同的属性，例如v0和v1,v1或许包括age属性，但是v0或许没有age属性，这与顶点的类型相关，可通过配置文件配置各顶点的类型标签和属性，以及各边的类型标签和属性，实现了有扩展属性的图网络结构，使网络结构的语义更丰富，可支持多个不同属性的图，信息量更庞大，可表达的关系更加复杂。本申请通过将图网络结构中的各顶点以及各条边分别映射为指定数据类型的指定数据集，比如Flink数据集，以便通过解析指定数据集之间的关系，计算图运算符对应的分析结果，实现对复杂的图网络结构的分析计算，为图形分析提供了新功能领域的应用可能。本申请不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在Apache FLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。
进一步地，所述根据图分析任务的执行脚本，获取待分析的图网络结构的步骤S1，包括：
S10：获取图分析任务的执行脚本中携带的所述待分析的图网络结构的图元素，其中，所述图元素包括图头；
S11：根据所述图头从指定数据库中抽取所述图头对应的图头数据集；
S12：判断所述图头数据集是否包括多个对象；
S13：若否，则判定所述待分析的图网络结构为图头为单个对象的逻辑图；
S14：从所述数据集中获取与所述逻辑图关联的顶点数据和边数据，分别对应组成顶点集和边集；
S15：通过所述顶点集和边集表示所述逻辑图，得到所述待分析的图网络结构。
本申请实施例以待分析的图网络结构为逻辑图为例，详细说明从数据库中获取图网络结构的数据集，表示图网络结构的过程。逻辑图是图集合的一个特殊情形，其图头数据集中只包含单个对象，图中所有的数据信息都是相通的。逻辑图也有类型标签(例如Community)和属性，可以通过用特定的度量(例如vertexCount:3)或关于该逻辑图的一般信息(例如interest:Databases)来描述该逻辑图。逻辑图的类型标签和属性可通过显式声明的方式显示在逻辑图中，也可以是图算法的输出或用作后续运算符的输入，例如社区检测或图模式匹配的应用情况。本申请中，预定义的数据库DB＝<V,E,L>，由顶点集V＝{vi}、边集E＝{ek}和一组逻辑图L＝{Gm}组成。逻辑图Gm＝<Vm,Em>，由顶点集V的子集
Figure BDA0002604023300000061
和边集的子集
Figure BDA0002604023300000062
组成的有序对。图头表示数据与某个逻辑图相关联的关系，如果待分析的图网络结构的图头均只针对一种对象，则整个待分析的图网络结构为数据相通或具有数据关联的逻辑图。本申请的逻辑图带有扩展属性，比如图头的扩展属性包括地址、标签和数据属性，表示为GraphHead:＝<Id,Label,Properties>；顶点的扩展属性包括地址、标签、顶点数据属性和图中顶点编号，表示为Vertex:＝<Id,Label,Properties,GraphIds>；边的扩展属性包括地址、标签、边起始顶点地址、边终止顶点地址、边数据属性和图中的边编号，表示为Edge:＝<Id,Label,SrcId,TrgtId,Properties,GraphIds>。举例地，逻辑图为g0＝{DataSet<GraphHead>graphHead＝{<0，′Community′，{′interest′：′Databases′，...}>}，DataSet<Vertex>vertices＝{<0，′Person′，{′name′：′Alice′，...}，{0，2}>，<，′Person′，{′name′：′Bob′，...}，{0，2}>}，DataSet<Edge>edges＝{<0，′knows′，0，1，{′since′：2014}，{0，2}>，<1，′Person′，1，0，{′snce′：2014}，{0，2}>}}。
进一步地，所述指定数据集包括Flink数据集，所述根据所述执行脚本，获取与所述图分析任务相对应的图运算符的步骤S3之后，包括：
S31：获取各所述图运算符的执行顺序；
S32：按照所述执行顺序将各所述图运算符，通过Java编程语言链接为运算逻辑；
S33：将所述运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序。
本申请实施例的图网络结构，为基于Apache Flink框架的图表示，使用三种对象类型来表示带扩展属性的图网络结构的图元素：图头、顶点和边。为表示图网络结构的数据集合，为每种图元素使用专用的Flink数据集。图元素对应的Flink数据集，通过数据映射转换，转为为各自对应的专属Flink数据集。在Apache Flink框架中，需要显式地触发程序才能执行，例如，将结果写入文件或数据库。由于本申请实施例中的图运算符实现的过程，都不包含显式地触发程序的触发器，因此本实施例将多个运算符按照执行脚本中的执行顺序链接成运算逻辑，然后将运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序，使整个运算过程作为一个Flink程序执行。
进一步地，所述图运算符包括排除运算符，利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤S4，包括：
S41：获取第一逻辑图对应的第一顶点集和第一边集，获取第二逻辑图对应的第二顶点集和第二边集；
S42：通过函数ID_ONLY从第二逻辑图中，提取所述第二逻辑图的标识符，形成新id对象对应的数据集；
S43：通过所述排除运算符筛选指定顶点和指定边，得到所述排除运算符对应的排除结果数据集，其中，所述指定顶点包含于所述第一顶点集，不包含于所述第二顶点集，所述指定边真包含于所述第一边集。
S44：通过Flink广播将所述排除结果数据集发送至Apache Flink框架集群的所有节点。
本申请以对图计算的排除运算符操作，得到转换后的数据集的过程进行说明。排除运算符的实现过程包括，生成的逻辑图由包含在第一逻辑图中但不包含在第二逻辑图中的顶点和边组成。实现的方式是基于逻辑图的顶点和边进行过滤。先通过对第二逻辑图的图头数据集，用映射变换来提取第二逻辑图的标识符。转换时通过调用用户定义的函数ID_ONLY进行参数化，使通过函数ID_ONLY从图头数据集中提取标识符。生成的逻辑图的数据集包含一个新id对象，用于筛选不包含在具有此新id对象的第二逻辑图中的顶点。筛选转换时通过用户定义的函数(NOT_IN_GRAPH_FILTER)作为参数，对第一逻辑图和第二逻辑图的数据集中的每个顶点调用该函数。为了使新id对象适用于过滤filter函数，使用Flink的广播概念将运算后得到的数据集，发送给Apache Flink框架集群所有节点。然后生成的数据集，只包含filter函数计算结果为true的顶点。对于边的过滤具有相同的过程，但边的过滤还需要检测两个半连接状态，即构成边的源顶点和目标顶点只有一端在生成的数据集中的情况需要排除，以确保源顶点和目标顶点均包含在新的顶点集中。根据运算生成的数据集，创建一个新逻辑图，新逻辑图的图头由构造函数创建，包括生成一个新id。上述检测两个半连接状态的过程是指，组成边的源顶点和目标顶点有一端在另一个逻辑图中，即一逻辑图的一条边的部分在另一逻辑图中，需要将重叠的区域排除的情况。
进一步地，所述图网络结构为多个逻辑图组成的社交网络图，所述图运算符包括Flink提供的关系操作符，所述利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤S4，包括：
S401：识别用户选定的关系操作符是否为寻找所述社交网络图中逻辑图之间的最大公共子图；
S402：若是，则聚集所述社交网络图中每个所述逻辑图的顶点数量；
S402：根据每个所述逻辑图的顶点数量，选择高于最小顶点计数的指定逻辑图；
S403：基于所述指定逻辑图，通过标签传播算法得到所述社交网络图中逻辑图之间的最大公共子图。
本申请使用Flink数据集来表示图形，因此图形分析不仅限于预先定义好的运算符，而且还可以使用Flink提供的所有数据运算，如关系操作符、机器学习符或图形处理符。以通过关系操作符，找到社交网络中较大的社区之间的最大公共子图为例，详细说明分析计算过程。图网络结构所表示的对象通常是异构的，例如社交网络图的顶点可以表示用户、组或乐队，而关系可以表示友谊、成员资格或兴趣。即同一类型的实体对象可能具有不同的属性，即不同的用户可能提供不同的属性信息。上述社交网络图包括多个逻辑图，包含一组逻辑图L＝{G0,G1,G2}，每个逻辑图表示社交网络图中的一个社区，比如是特定的兴趣组，例如Databases。每个逻辑图都有一个对应顶点子集和边子集，例如，V(G0)＝{v0,v1}和E(G0)＝{e0,e1}。分析逻辑图G0和G2的关系，从社交网络图的三个逻辑图的带扩展属性的社交网络图可得到，逻辑图G0关联到的顶点和边与逻辑图G2共享，可以得知G0和G2顶点和边可能重叠，因为V(G0)∩V(G2)＝{v0，v1}和E(G0)∩E(G2)＝{e0，e1}。本实施例通过识别社区并聚集每个社区的顶点数量，选择高于最小顶点计数的社区，即确定选定的较大的社区，最小顶点计数额由用户预先设定。最后应用标签传播算法来找到最大公共子图。上述标签传播算法是基于图的半监督学习方法，过程为从已标记的节点的标签信息，预测未标记的节点的标签信息，利用样本间的关系，建立完全图模型。每个节点标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标记的数据的标签不变，使其将标签传给未标注的数据。最终当迭代结束时，相似节点的概率分布趋于相似，可以划分到一类中，找到最大公共子图对应得最大独立集。
进一步地，所述图预算符至少包括两个，所述利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤S4，包括：
S4001：获取多个图预算符对应的指定Flink程序；
S4002：获取所述指定Flink程序当前运行节点，预测可并发执行运算的数据集；
S4003：将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器；
S4004：接收各指定机器分别执行分发的数据集得到的计算结果；
S4005：将各计算结果汇总得到多个图预算符的分析结果；
S4006：将所述多个图预算符的分析结果，通过Flink广播发送至Apache Flink框架集群的所有节点。
本申请的Apache Flink框架，对来自流和批处理的数据，支持声明性定义和分布式执行分析，支持的数据包括流式的和批处理的。程序的基本组成是数据集和转换，通过对数据集进行定义和执行的任务进行抽象，即形成数据集和数据集的转换过程。数据集是任意数据对象的集合，转换描述了一个数据集到另一个数据集的数据类型的转换。例如，假设X，Y是数据集，那么转换可以看作函数t：X→Y。举例说，上述转换是映射MAP，对于每个输入的数据对象xi∈X，有且只有一个输出数据对象yi∈Y。比如，转换时归约reduce，则所有输入数据对象都被聚合到一个对象的数据集。关系型数据库中的数据转换，包括join、groupby、project、union和distinct等。本申请为了描述Flink程序应用逻辑，通过用户自定义的函数对数据转换过程进行参数化。Flink程序可以表示为多个链式转换，执行树转化时Flink框架负责程序优化、数据分发和跨机器的集群并行执行。即一个Flink脚本任务可以包括多个链式的数据变换，Flink程序在执行时会一并优化程序、完成数据分发以及在跨机器的集群上并发执行。
进一步地，所述指定Flink程序包括对特定逻辑图的聚合运算、变换预算和模式匹配预算，所述将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器的步骤S4003，包括：
S40031：获取所述特定逻辑图对应的数据集、聚合运算对应的聚合函数、变换运算对应的转换函数以及模式匹配运算对应的匹配函数；
S40032：将所述特定逻辑图对应的数据集和聚合运算对应的聚合函数分发至集群中的第一机器，将所述特定逻辑图对应的数据集和变换运算对应的转换函数分发至集群中的第二机器，将所述特定逻辑图对应的数据集和模式匹配运算对应的匹配函数分发至集群中的第三机器；
S40033：控制所述第一机器、所述第二机器和所述第三机器并发运行。
本实施例以图运算符同时包括聚合运算符、变换运算符和模式匹配运算符为例，进行详细说明Apache Flink框架集群中的机器并发执行的过程。上述聚合运算符指，将输入的特定逻辑图G映射到输出图G’。通过执行用户事先定义好的聚合函数α∶L→A，L是逻辑图，A是值域，得到输出图G’是输入的特定逻辑图G的具有新属性k的修改版本，使得κ(G’，k)→α(G)，κ是映射关系，把逻辑图的属性k映射到一个值。例如顶点计数：alpha＝(g＝>g.V.count())；outGraph＝inGraph.agregate(′vertexCount′，alpha)。上述变换运算符对输入的特定逻辑图G，执行用户定义的转换函数γ：L→L，ν：V→V和∈：E→E，得到输出图G′＝γ(G)，其中V(G′)＝{ν(v)：v∈V(G)}，E(G′)＝{∈(e)：e∈E(G)}。上述模式匹配运算符包含两个参数，分别是模式图G*和谓词
Figure BDA0002604023300000101
模式匹配运算应用在特定逻辑图G上，返回包含所有匹配的图集合
Figure BDA0002604023300000102
参照图2，本申请一实施例的图网络结构的分析装置，包括：
第一获取模块1，用于根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；
映射模块2，用于将所述图网络结构中的各顶点以及各条边分别映射指定数据集；
第二获取模块3，用于根据所述执行脚本，获取与所述图分析任务相对应的图运算符；
计算模块4，用于利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
本申请中的图网络结构带有扩展属性，图网络结构由顶点集V和边集E组成，其中顶点集V中包括各类型顶点，由点对应的第一类型标签和第一属性进行描述和表示各顶点。举例地，上述带扩展属性的图网络结构为图社交网络，表示为有向图G＝<V，E>，由一组顶点V和一组边
Figure BDA0002604023300000111
组成。比如图网络由顶点集V＝{v0，…，v9}和边集E＝{e0，…，e19}组成。顶点可分为多种类型，包括表示人(Person)的顶点、表示论坛(Forum)的顶点和表示兴趣(Tag)的顶点。不同类型的顶点由相应的第一类型标签表示和相应的第一属性进行描述。边描述了顶点之间的关系，也有对应的第二类型标签(如knows)和第二属性进行描述。具有相同类型标签的顶点可能具有不同的属性，例如v0和v1,v1或许包括age属性，但是v0或许没有age属性，这与顶点的类型相关，可通过配置文件配置各顶点的类型标签和属性，以及各边的类型标签和属性，实现了有扩展属性的图网络结构，使网络结构的语义更丰富，可支持多个不同属性的图，信息量更庞大，可表达的关系更加复杂。本申请通过将图网络结构中的各顶点以及各条边分别映射为指定数据类型的指定数据集，比如Flink数据集，以便通过解析指定数据集之间的关系，计算图运算符对应的分析结果，实现对复杂的图网络结构的分析计算，为图形分析提供了新功能领域的应用可能。本申请不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在Apache FLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。
进一步地，第一获取模块1，包括：
第一获取单元，用于获取图分析任务的执行脚本中携带的所述待分析的图网络结构的图元素，其中，所述图元素包括图头；
抽取单元，用于根据所述图头从指定数据库中抽取所述图头对应的图头数据集；
判断单元，用于判断所述图头数据集是否包括多个对象；
判定单元，用于若未包括多个对象，则判定所述待分析的图网络结构为图头为单个对象的逻辑图；
第二获取单元，用于从所述数据集中获取与所述逻辑图关联的顶点数据和边数据，分别对应组成顶点集和边集；
第一得到单元，用于通过所述顶点集和边集表示所述逻辑图，得到所述待分析的图网络结构。
本申请实施例以待分析的图网络结构为逻辑图为例，详细说明从数据库中获取图网络结构的数据集，表示图网络结构的过程。逻辑图是图集合的一个特殊情形，其图头数据集中只包含单个对象，图中所有的数据信息都是相通的。逻辑图也有类型标签(例如Community)和属性，可以通过用特定的度量(例如vertexCount:3)或关于该逻辑图的一般信息(例如interest:Databases)来描述该逻辑图。逻辑图的类型标签和属性可通过显式声明的方式显示在逻辑图中，也可以是图算法的输出或用作后续运算符的输入，例如社区检测或图模式匹配的应用情况。本申请中，预定义的数据库DB＝<V，E，L>，由顶点集V＝{vi}、边集E＝{ek}和一组逻辑图L＝{Gm}组成。逻辑图Gm＝<Vm，Em>，由顶点集V的子集
Figure BDA0002604023300000121
和边集的子集
Figure BDA0002604023300000122
组成的有序对。图头表示数据与某个逻辑图相关联的关系，如果待分析的图网络结构的图头均只针对一种对象，则整个待分析的图网络结构为数据相通或具有数据关联的逻辑图。本申请的逻辑图带有扩展属性，比如图头的扩展属性包括地址、标签和数据属性，表示为GraphHead：＝<Id，Label，Properties>；顶点的扩展属性包括地址、标签、顶点数据属性和图中顶点编号，表示为Vertex：<Id，Label，Properties，GraphIds>；边的扩展属性包括地址、标签、边起始顶点地址、边终止顶点地址、边数据属性和图中的边编号，表示为Edge：<Id，Label，SrcId，TrgtId，Properties，GraphIds>。举例地，逻辑图为g0＝{DataSet<GraphHead>graphHead＝{<0，′Community′，{′interest′：′Databases′，...}>}，DataSet<Vertex>vertices＝{<0，′Person′，{′name′：′Alice′，...}，{0，2}>，<1，′Person′，{′name′：′Bob′，...}，{0，2}>}，DataSet<Edge>edges＝{<0，′knows′，0，1，{′since：2014}，{0，2}>，<1，′Person′，1，0，{′since′：2014}，{0，2}>}}。
进一步地，所述指定数据集包括Flink数据集，图网络结构的分析装置，包括：
第三获取模块，用于获取各所述图运算符的执行顺序；
链接模块，用于按照所述执行顺序将各所述图运算符，通过Java编程语言链接为运算逻辑；
关联模块，用于将所述运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序。
本申请实施例的图网络结构，为基于Apache Flink框架的图表示，使用三种对象类型来表示带扩展属性的图网络结构的图元素：图头、顶点和边。为表示图网络结构的数据集合，为每种图元素使用专用的Flink数据集。图元素对应的Flink数据集，通过数据映射转换，转为为各自对应的专属Flink数据集。在Apache Flink框架中，需要显式地触发程序才能执行，例如，将结果写入文件或数据库。由于本申请实施例中的图运算符实现的过程，都不包含显式地触发程序的触发器，因此本实施例将多个运算符按照执行脚本中的执行顺序链接成运算逻辑，然后将运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序，使整个运算过程作为一个Flink程序执行。
进一步地，所述图运算符包括排除运算符，计算模块4，包括：
第三获取单元，用于获取第一逻辑图对应的第一顶点集和第一边集，获取第二逻辑图对应的第二顶点集和第二边集；
提取单元，用于通过函数ID_ONLY从第二逻辑图中，提取所述第二逻辑图的标识符，形成新id对象对应的数据集；
筛选单元，用于通过所述排除运算符筛选指定顶点和指定边，得到所述排除运算符对应的排除结果数据集，其中，所述指定顶点包含于所述第一顶点集，不包含于所述第二顶点集，所述指定边真包含于所述第一边集。
第一发送单元，用于通过Flink广播将所述排除结果数据集发送至Apache Flink框架集群的所有节点。
本申请以对图计算的排除运算符操作，得到转换后的数据集的过程进行说明。排除运算符的实现过程包括，生成的逻辑图由包含在第一逻辑图中但不包含在第二逻辑图中的顶点和边组成。实现的方式是基于逻辑图的顶点和边进行过滤。先通过对第二逻辑图的图头数据集，用映射变换来提取第二逻辑图的标识符。转换时通过调用用户定义的函数ID_ONLY进行参数化，使通过函数ID_ONLY从图头数据集中提取标识符。生成的逻辑图的数据集包含一个新id对象，用于筛选不包含在具有此新id对象的第二逻辑图中的顶点。筛选转换时通过用户定义的函数(NOT_IN_GRAPH_FILTER)作为参数，对第一逻辑图和第二逻辑图的数据集中的每个顶点调用该函数。为了使新id对象适用于过滤filter函数，使用Flink的广播概念将运算后得到的数据集，发送给Apache Flink框架集群所有节点。然后生成的数据集，只包含filter函数计算结果为true的顶点。对于边的过滤具有相同的过程，但边的过滤还需要检测两个半连接状态，即构成边的源顶点和目标顶点只有一端在生成的数据集中的情况需要排除，以确保源顶点和目标顶点均包含在新的顶点集中。根据运算生成的数据集，创建一个新逻辑图，新逻辑图的图头由构造函数创建，包括生成一个新id。上述检测两个半连接状态的过程是指，组成边的源顶点和目标顶点有一端在另一个逻辑图中，即一逻辑图的一条边的部分在另一逻辑图中，需要将重叠的区域排除的情况。
进一步地，所述图网络结构为多个逻辑图组成的社交网络图，所述图运算符包括Flink提供的关系操作符，计算模块4，包括：
识别单元，用于识别用户选定的关系操作符是否为寻找所述社交网络图中逻辑图之间的最大公共子图；
聚集单元，用于若为寻找所述社交网络图中逻辑图之间的最大公共子图，则聚集所述社交网络图中每个所述逻辑图的顶点数量；
选择单元，用于根据每个所述逻辑图的顶点数量，选择高于最小顶点计数的指定逻辑图；
第二得到单元，用于基于所述指定逻辑图，通过标签传播算法得到所述社交网络图中逻辑图之间的最大公共子图。
本申请使用Flink数据集来表示图形，因此图形分析不仅限于预先定义好的运算符，而且还可以使用Flink提供的所有数据运算，如关系操作符、机器学习符或图形处理符。以通过关系操作符，找到社交网络中较大的社区之间的最大公共子图为例，详细说明分析计算过程。图网络结构所表示的对象通常是异构的，例如社交网络图的顶点可以表示用户、组或乐队，而关系可以表示友谊、成员资格或兴趣。即同一类型的实体对象可能具有不同的属性，即不同的用户可能提供不同的属性信息。上述社交网络图包括多个逻辑图，包含一组逻辑图L＝{G0,G1,G2}，每个逻辑图表示社交网络图中的一个社区，比如是特定的兴趣组，例如Databases。每个逻辑图都有一个对应顶点子集和边子集，例如，V(G0)＝{v0,v1}和E(G0)＝{e0,e1}。分析逻辑图G0和G2的关系，从社交网络图的三个逻辑图的带扩展属性的社交网络图可得到，逻辑图G0关联到的顶点和边与逻辑图G2共享，可以得知G0和G2顶点和边可能重叠，因为和。本实施例通过识别社区并聚集每个社区的顶点数量，选择高于最小顶点计数的社区，即确定选定的较大的社区，最小顶点计数额由用户预先设定。最后应用标签传播算法来找到最大公共子图。上述标签传播算法是基于图的半监督学习方法，过程为从已标记的节点的标签信息，预测未标记的节点的标签信息，利用样本间的关系，建立完全图模型。每个节点标签按相似度传播给相邻节点，在节点传播的每一步，每个节点根据相邻节点的标签来更新自己的标签，与该节点相似度越大，其相邻节点对其标注的影响权值越大，相似节点的标签越趋于一致，其标签就越容易传播。在标签传播过程中，保持已标记的数据的标签不变，使其将标签传给未标注的数据。最终当迭代结束时，相似节点的概率分布趋于相似，可以划分到一类中，找到最大公共子图对应得最大独立集。
进一步地，所述图预算符至少包括两个，计算模块4，包括：
第四获取单元，用于获取多个图预算符对应的指定Flink程序；
第五获取单元，用于获取所述指定Flink程序当前运行节点，预测可并发执行运算的数据集；
分发单元，用于将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器；
接收单元，用于接收各指定机器分别执行分发的数据集得到的计算结果；
汇总单元，用于将各计算结果汇总得到多个图预算符的分析结果；
第二发送单元，用于将所述多个图预算符的分析结果，通过Flink广播发送至Apache Flink框架集群的所有节点。
本申请的Apache Flink框架，对来自流和批处理的数据，支持声明性定义和分布式执行分析，支持的数据包括流式的和批处理的。程序的基本组成是数据集和转换，通过对数据集进行定义和执行的任务进行抽象，即形成数据集和数据集的转换过程。数据集是任意数据对象的集合，转换描述了一个数据集到另一个数据集的数据类型的转换。例如，假设X，Y是数据集，那么转换可以看作函数t：X→Y。举例说，上述转换是映射MAP，对于每个输入的数据对象xi∈X，有且只有一个输出数据对象yi∈Y。比如，转换时归约reduce，则所有输入数据对象都被聚合到一个对象的数据集。关系型数据库中的数据转换，包括join、groupby、project、union和distinct等。本申请为了描述Flink程序应用逻辑，通过用户自定义的函数对数据转换过程进行参数化。Flink程序可以表示为多个链式转换，执行树转化时Flink框架负责程序优化、数据分发和跨机器的集群并行执行。即一个Flink脚本任务可以包括多个链式的数据变换，Flink程序在执行时会一并优化程序、完成数据分发以及在跨机器的集群上并发执行。
进一步地，所述指定Flink程序包括对特定逻辑图的聚合运算、变换预算和模式匹配预算，分发单元，包括：
获取子单元，用于获取所述特定逻辑图对应的数据集、聚合运算对应的聚合函数、变换运算对应的转换函数以及模式匹配运算对应的匹配函数；
分发子单元，用于将所述特定逻辑图对应的数据集和聚合运算对应的聚合函数分发至集群中的第一机器，将所述特定逻辑图对应的数据集和变换运算对应的转换函数分发至集群中的第二机器，将所述特定逻辑图对应的数据集和模式匹配运算对应的匹配函数分发至集群中的第三机器；
控制子单元，用于控制所述第一机器、所述第二机器和所述第三机器并发运行。
本实施例以图运算符同时包括聚合运算符、变换运算符和模式匹配运算符为例，进行详细说明Apache Flink框架集群中的机器并发执行的过程。上述聚合运算符指，将输入的特定逻辑图G映射到输出图G’。通过执行用户事先定义好的聚合函数α：L→A，L是逻辑图，A是值域，得到输出图G’是输入的特定逻辑图G的具有新属性k的修改版本，使得κ(G′，k)→α(G)，κ是映射关系，把逻辑图的属性k映射到一个值。例如顶点计数：alpha＝(g＝>g.V.count())；outGraph＝inGraph.aggregate(′vertexCount′，alpha)。上述变换运算符对输入的特定逻辑图G，执行用户定义的转换函数γ：L→L，v：V→V和∈：E→E，得到输出图G′＝γ(G)，其中G′＝{v(v)：v∈V(G)}，E(G′)＝{∈(e)：e∈E(G)}。上述模式匹配运算符包含两个参数，分别是模式图G*和谓词
Figure BDA0002604023300000171
模式匹配运算应用在特定逻辑图G上，返回包含所有匹配的图集合
Figure BDA0002604023300000172
参照图3，本申请实施例中还提供一种计算机设备，该计算机设备可以是服务器，其内部结构可以如图3所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口和数据库。其中，该计算机设计的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统、计算机程序和数据库。该内存器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的数据库用于存储图网络结构的分析过程需要的所有数据。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现图网络结构的分析方法。
上述处理器执行上述图网络结构的分析方法，根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；将所述图网络结构中的各顶点以及各条边分别映射指定数据集；根据所述执行脚本，获取与所述图分析任务相对应的图运算符；利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
上述计算机设备，不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在Apache FLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。
在一个实施例中，上述处理器根据图分析任务的执行脚本，获取待分析的图网络结构的步骤，包括：获取图分析任务的执行脚本中携带的所述待分析的图网络结构的图元素，其中，所述图元素包括图头；根据所述图头从指定数据库中抽取所述图头对应的图头数据集；判断所述图头数据集是否包括多个对象；若否，则判定所述待分析的图网络结构为图头为单个对象的逻辑图；从所述数据集中获取与所述逻辑图关联的顶点数据和边数据，分别对应组成顶点集和边集；通过所述顶点集和边集表示所述逻辑图，得到所述待分析的图网络结构。
在一个实施例中，指定数据集包括Flink数据集，上述处理器根据所述执行脚本，获取与所述图分析任务相对应的图运算符的步骤之后，包括：获取各所述图运算符的执行顺序；按照所述执行顺序将各所述图运算符，通过Java编程语言链接为运算逻辑；将所述运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序。
在一个实施例中，所述图运算符包括排除运算符，上述处理器利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：获取第一逻辑图对应的第一顶点集和第一边集，获取第二逻辑图对应的第二顶点集和第二边集；通过函数ID_ONLY从第二逻辑图中，提取所述第二逻辑图的标识符，形成新id对象对应的数据集；通过所述排除运算符筛选指定顶点和指定边，得到所述排除运算符对应的排除结果数据集，其中，所述指定顶点包含于所述第一顶点集，不包含于所述第二顶点集，所述指定边真包含于所述第一边集；通过Flink广播将所述排除结果数据集发送至Apache Flink框架集群的所有节点。
在一个实施例中，所述图网络结构为多个逻辑图组成的社交网络图，所述图运算符包括Flink提供的关系操作符，上述处理器利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：识别用户选定的关系操作符是否为寻找所述社交网络图中逻辑图之间的最大公共子图；若是，则聚集所述社交网络图中每个所述逻辑图的顶点数量；根据每个所述逻辑图的顶点数量，选择高于最小顶点计数的指定逻辑图；基于所述指定逻辑图，通过标签传播算法得到所述社交网络图中逻辑图之间的最大公共子图。
在一个实施例中，所述图预算符至少包括两个，上述处理器利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：获取多个图预算符对应的指定Flink程序；获取所述指定Flink程序当前运行节点，预测可并发执行运算的数据集；将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器；接收各指定机器分别执行分发的数据集得到的计算结果；将各计算结果汇总得到多个图预算符的分析结果；将所述多个图预算符的分析结果，通过Flink广播发送至Apache Flink框架集群的所有节点。
在一个实施例中，所述指定Flink程序包括对特定逻辑图的聚合运算、变换预算和模式匹配预算，上述处理器将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器的步骤，包括：获取所述特定逻辑图对应的数据集、聚合运算对应的聚合函数、变换运算对应的转换函数以及模式匹配运算对应的匹配函数；将所述特定逻辑图对应的数据集和聚合运算对应的聚合函数分发至集群中的第一机器，将所述特定逻辑图对应的数据集和变换运算对应的转换函数分发至集群中的第二机器，将所述特定逻辑图对应的数据集和模式匹配运算对应的匹配函数分发至集群中的第三机器；控制所述第一机器、所述第二机器和所述第三机器并发运行。
本领域技术人员可以理解，图3中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的计算机设备的限定。
本申请一实施例还提供一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现图网络结构的分析方法，根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；将所述图网络结构中的各顶点以及各条边分别映射指定数据集；根据所述执行脚本，获取与所述图分析任务相对应的图运算符；利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
上述计算机可读存储介质，不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在Apache FLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。
在一个实施例中，上述处理器根据图分析任务的执行脚本，获取待分析的图网络结构的步骤，包括：获取图分析任务的执行脚本中携带的所述待分析的图网络结构的图元素，其中，所述图元素包括图头；根据所述图头从指定数据库中抽取所述图头对应的图头数据集；判断所述图头数据集是否包括多个对象；若否，则判定所述待分析的图网络结构为图头为单个对象的逻辑图；从所述数据集中获取与所述逻辑图关联的顶点数据和边数据，分别对应组成顶点集和边集；通过所述顶点集和边集表示所述逻辑图，得到所述待分析的图网络结构。
在一个实施例中，指定数据集包括Flink数据集，上述处理器根据所述执行脚本，获取与所述图分析任务相对应的图运算符的步骤之后，包括：获取各所述图运算符的执行顺序；按照所述执行顺序将各所述图运算符，通过Java编程语言链接为运算逻辑；将所述运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序。
在一个实施例中，所述图运算符包括排除运算符，上述处理器利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：获取第一逻辑图对应的第一顶点集和第一边集，获取第二逻辑图对应的第二顶点集和第二边集；通过函数ID_ONLY从第二逻辑图中，提取所述第二逻辑图的标识符，形成新id对象对应的数据集；通过所述排除运算符筛选指定顶点和指定边，得到所述排除运算符对应的排除结果数据集，其中，所述指定顶点包含于所述第一顶点集，不包含于所述第二顶点集，所述指定边真包含于所述第一边集；通过Flink广播将所述排除结果数据集发送至Apache Flink框架集群的所有节点。
在一个实施例中，所述图网络结构为多个逻辑图组成的社交网络图，所述图运算符包括Flink提供的关系操作符，上述处理器利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：识别用户选定的关系操作符是否为寻找所述社交网络图中逻辑图之间的最大公共子图；若是，则聚集所述社交网络图中每个所述逻辑图的顶点数量；根据每个所述逻辑图的顶点数量，选择高于最小顶点计数的指定逻辑图；基于所述指定逻辑图，通过标签传播算法得到所述社交网络图中逻辑图之间的最大公共子图。
在一个实施例中，所述图预算符至少包括两个，上述处理器利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：获取多个图预算符对应的指定Flink程序；获取所述指定Flink程序当前运行节点，预测可并发执行运算的数据集；将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器；接收各指定机器分别执行分发的数据集得到的计算结果；将各计算结果汇总得到多个图预算符的分析结果；将所述多个图预算符的分析结果，通过Flink广播发送至Apache Flink框架集群的所有节点。
在一个实施例中，所述指定Flink程序包括对特定逻辑图的聚合运算、变换预算和模式匹配预算，上述处理器将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器的步骤，包括：获取所述特定逻辑图对应的数据集、聚合运算对应的聚合函数、变换运算对应的转换函数以及模式匹配运算对应的匹配函数；将所述特定逻辑图对应的数据集和聚合运算对应的聚合函数分发至集群中的第一机器，将所述特定逻辑图对应的数据集和变换运算对应的转换函数分发至集群中的第二机器，将所述特定逻辑图对应的数据集和模式匹配运算对应的匹配函数分发至集群中的第三机器；控制所述第一机器、所述第二机器和所述第三机器并发运行。
本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，上述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的和实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可以包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双速据率SDRAM(SSRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。
需要说明的是，在本文中，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、装置、物品或者方法不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、装置、物品或者方法所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括该要素的过程、装置、物品或者方法中还存在另外的相同要素。
以上所述仅为本申请的优选实施例，并非因此限制本申请的专利范围，凡是利用本申请说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本申请的专利保护范围内。

Claims (10)

1.一种图网络结构的分析方法，其特征在于，包括：
根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；
将所述图网络结构中的各顶点以及各条边分别映射指定数据集；
根据所述执行脚本，获取与所述图分析任务相对应的图运算符；
利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
2.根据权利要求1所述的图网络结构的分析方法，其特征在于，所述根据图分析任务的执行脚本，获取待分析的图网络结构的步骤，包括：
获取图分析任务的执行脚本中携带的所述待分析的图网络结构的图元素，其中，所述图元素包括图头；
根据所述图头从指定数据库中抽取所述图头对应的图头数据集；
判断所述图头数据集是否包括多个对象；
若否，则判定所述待分析的图网络结构为图头为单个对象的逻辑图；
从所述数据集中获取与所述逻辑图关联的顶点数据和边数据，分别对应组成顶点集和边集；
通过所述顶点集和边集表示所述逻辑图，得到所述待分析的图网络结构。
3.根据权利要求1所述的图网络结构的分析方法，其特征在于，指定数据集包括Flink数据集，所述根据所述执行脚本，获取与所述图分析任务相对应的图运算符的步骤之后，包括：
获取各所述图运算符的执行顺序；
按照所述执行顺序将各所述图运算符，通过Java编程语言链接为运算逻辑；
将所述运算逻辑与Flink触发程序的触发器关联，形成Flink运算程序。
4.根据权利要求1所述的图网络结构的分析方法，其特征在于，所述图运算符包括排除运算符，利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：
获取第一逻辑图对应的第一顶点集和第一边集，获取第二逻辑图对应的第二顶点集和第二边集；
通过函数ID_ONLY从第二逻辑图中，提取所述第二逻辑图的标识符，形成新id对象对应的数据集；
通过所述排除运算符筛选指定顶点和指定边，得到所述排除运算符对应的排除结果数据集，其中，所述指定顶点包含于所述第一顶点集，不包含于所述第二顶点集，所述指定边真包含于所述第一边集；
通过Flink广播将所述排除结果数据集发送至Apache Flink框架集群的所有节点。
5.根据权利要求1所述的图网络结构的分析方法，其特征在于，所述图网络结构为多个逻辑图组成的社交网络图，所述图运算符包括Flink提供的关系操作符，所述利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：
识别用户选定的关系操作符是否为寻找所述社交网络图中逻辑图之间的最大公共子图；
若是，则聚集所述社交网络图中每个所述逻辑图的顶点数量；
根据每个所述逻辑图的顶点数量，选择高于最小顶点计数的指定逻辑图；
基于所述指定逻辑图，通过标签传播算法得到所述社交网络图中逻辑图之间的最大公共子图。
6.根据权利要求1所述的图网络结构的分析方法，其特征在于，所述图预算符至少包括两个，所述利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果的步骤，包括：
获取多个图预算符对应的指定Flink程序；
获取所述指定Flink程序当前运行节点，预测可并发执行运算的数据集；
将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器；
接收各指定机器分别执行分发的数据集得到的计算结果；
将各计算结果汇总得到多个图预算符的分析结果；
将所述多个图预算符的分析结果，通过Flink广播发送至Apache Flink框架集群的所有节点。
7.根据权利要求6所述的图网络结构的分析方法，其特征在于，所述指定Flink程序包括对特定逻辑图的聚合运算、变换预算和模式匹配预算，所述将并发执行运算的数据集分发至Apache Flink框架集群中的指定机器的步骤，包括：
获取所述特定逻辑图对应的数据集、聚合运算对应的聚合函数、变换运算对应的转换函数以及模式匹配运算对应的匹配函数；
将所述特定逻辑图对应的数据集和聚合运算对应的聚合函数分发至集群中的第一机器，将所述特定逻辑图对应的数据集和变换运算对应的转换函数分发至集群中的第二机器，将所述特定逻辑图对应的数据集和模式匹配运算对应的匹配函数分发至集群中的第三机器；
控制所述第一机器、所述第二机器和所述第三机器并发运行。
8.一种图网络结构的分析装置，其特征在于，包括：
第一获取模块，用于根据图分析任务的执行脚本，获取待分析的图网络结构，其中，所述图网络结构包括顶点集和边集，所述顶点集中的各顶点分别携带该顶点对应的第一类型标签和第一属性，所述边集中的各条边由具有关联关系的两个顶点相连形成，各所述边分别携带边对应的第二类型标签和第二属性；
映射模块，用于将所述图网络结构中的各顶点以及各条边分别映射指定数据集；
第二获取模块，用于根据所述执行脚本，获取与所述图分析任务相对应的图运算符；
计算模块，用于利用所述图运算符对所述图网络结构对应的指定数据集进行分析计算，得到分析结果。
9.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至7中任一项所述方法的步骤。
10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至7中任一项所述的方法的步骤。
CN202010733106.8A 2020-07-27 2020-07-27 图网络结构的分析方法、装置和计算机设备 Pending CN111814006A (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010733106.8A CN111814006A (zh) 2020-07-27 2020-07-27 图网络结构的分析方法、装置和计算机设备

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010733106.8A CN111814006A (zh) 2020-07-27 2020-07-27 图网络结构的分析方法、装置和计算机设备

Publications (1)

Publication Number Publication Date
CN111814006A true CN111814006A (zh) 2020-10-23

Family

ID=72862680

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010733106.8A Pending CN111814006A (zh) 2020-07-27 2020-07-27 图网络结构的分析方法、装置和计算机设备

Country Status (1)

Country Link
CN (1) CN111814006A (zh)

Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100145771A1 (en) * 2007-03-15 2010-06-10 Ariel Fligler System and method for providing service or adding benefit to social networks
US20160188391A1 (en) * 2014-12-31 2016-06-30 International Business Machines Corporation Sophisticated run-time system for graph processing
US20170116764A1 (en) * 2015-10-23 2017-04-27 International Business Machines Corporation Dynamic interaction graphs with probabilistic edge decay
CN107402745A (zh) * 2017-07-04 2017-11-28 清华大学 数据流图的映射方法及装置
US20180189388A1 (en) * 2017-01-05 2018-07-05 International Business Machines Corporation Representation of a data analysis using a flow graph
CN108351941A (zh) * 2015-11-02 2018-07-31 日本电信电话株式会社 分析装置、分析方法、以及分析程序
US20190057138A1 (en) * 2017-08-18 2019-02-21 Vmware, Inc. Presenting a temporal topology graph of a computing environment at a graphical user interface
CN110110154A (zh) * 2018-02-01 2019-08-09 腾讯科技（深圳）有限公司 一种图文件的处理方法、装置及存储介质
CN111026544A (zh) * 2019-11-06 2020-04-17 中国科学院深圳先进技术研究院 图网络模型的节点分类方法、装置及终端设备
EP3664374A1 (en) * 2018-12-06 2020-06-10 Fujitsu Limited Data stream processing method and data stream processing system

Patent Citations (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20100145771A1 (en) * 2007-03-15 2010-06-10 Ariel Fligler System and method for providing service or adding benefit to social networks
US20160188391A1 (en) * 2014-12-31 2016-06-30 International Business Machines Corporation Sophisticated run-time system for graph processing
US20170116764A1 (en) * 2015-10-23 2017-04-27 International Business Machines Corporation Dynamic interaction graphs with probabilistic edge decay
CN108351941A (zh) * 2015-11-02 2018-07-31 日本电信电话株式会社 分析装置、分析方法、以及分析程序
US20180189388A1 (en) * 2017-01-05 2018-07-05 International Business Machines Corporation Representation of a data analysis using a flow graph
CN107402745A (zh) * 2017-07-04 2017-11-28 清华大学 数据流图的映射方法及装置
US20190057138A1 (en) * 2017-08-18 2019-02-21 Vmware, Inc. Presenting a temporal topology graph of a computing environment at a graphical user interface
CN110110154A (zh) * 2018-02-01 2019-08-09 腾讯科技（深圳）有限公司 一种图文件的处理方法、装置及存储介质
EP3664374A1 (en) * 2018-12-06 2020-06-10 Fujitsu Limited Data stream processing method and data stream processing system
CN111026544A (zh) * 2019-11-06 2020-04-17 中国科学院深圳先进技术研究院 图网络模型的节点分类方法、装置及终端设备

Similar Documents

Publication Publication Date Title
CN111061859B (zh) 基于知识图谱的数据处理方法、装置和计算机设备
JP7344327B2 (ja) アプリケーションプログラミングインターフェイスのメタデータ駆動型外部インターフェイス生成ためのシステムおよび方法
US8655805B2 (en) Method for classification of objects in a graph data stream
WO2020088439A1 (zh) 实现异构图、分子空间结构性质识别的方法、装置和计算机设备
WO2020048058A1 (zh) 基金知识推理方法、系统、计算机设备和存储介质
US20150039611A1 (en) Discovery of related entities in a master data management system
CN104077723B (zh) 一种社交网络推荐系统及方法
US11204707B2 (en) Scalable binning for big data deduplication
CN104809244B (zh) 一种大数据环境下的数据挖掘方法和装置
Marchant et al. d-blink: Distributed end-to-end Bayesian entity resolution
CN106815307A (zh) 公共文化知识图谱平台及其使用办法
CN110020176A (zh) 一种资源推荐方法、电子设备以及计算机可读存储介质
US20180121526A1 (en) Method, apparatus, and computer-readable medium for non-structured data profiling
Belcastro et al. ParSoDA: high-level parallel programming for social data mining
Braun et al. MapReduce-based complex big data analytics over uncertain and imprecise social networks
Carletti et al. Interpretable anomaly detection with diffi: Depth-based isolation forest feature importance
Zhan et al. Identification of top-K influential communities in big networks
CN114493853A (zh) 信用等级评价方法、装置、电子设备及存储介质
Jafarzadegan et al. An agglomerative hierarchical clustering framework for improving the ensemble clustering process
Jovanovič et al. Big-data analytics: a critical review and some future directions
Wei et al. Graph learning and its advancements on large language models: A holistic survey
Venkatesan et al. CI/CD Pipelines for Model Training: Reducing Turnaround Time in Offline Model Training with Hive and Spark
CN117725220A (zh) 文档表征和文档检索的方法、服务器及存储介质
Belcastro et al. A parallel library for social media analytics
CN110941662A (zh) 科研合作关系的图示化方法、系统、存储介质、及终端

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
AD01 Patent right deemed abandoned
AD01 Patent right deemed abandoned

Effective date of abandoning: 20240126