CN111814006A - Analysis method, device and computer equipment for graph network structure - Google Patents

Abstract

The application relates to the field of artificial intelligence, and discloses an analysis method of a graph network structure, wherein the graph network structure to be analyzed is obtained according to an execution script of a graph analysis task, the graph network structure comprises a vertex set and an edge set, each vertex in the vertex set carries a first type label and a first attribute corresponding to the vertex respectively, each edge in the edge set is formed by connecting two vertexes with an incidence relation, and each edge carries a second type label and a second attribute corresponding to the edge respectively; respectively mapping each vertex and each edge in the graph network structure to a specified data set; acquiring a graph operator corresponding to the graph analysis task according to the execution script; and analyzing and calculating the designated data set corresponding to the graph network structure by utilizing the graph operator to obtain an analysis result. And establishing a graph network structure with extended attributes, converting graph operation into operation of a data set, realizing analysis of a single graph or a graph set, and providing a new function for graph analysis.

Description

Analysis method, device and computer equipment for graph network structure

technical field

The present application relates to the field of artificial intelligence, in particular to the analysis method, apparatus and computer equipment of graph network structure.

Background technique

Graphs can express things and the connections between things more intuitively, but when a computer recognizes a graph, it needs to be modeled according to the graph to identify the information in the graph and calculate the relationship between the things in the graph. Graph analytics plays an important role in research and industry. For example, graphs can represent community relationships in social networks. But complex analytical problems about graphs require a combination of multiple analytical operations, such as ranking websites or analyzing social networks, and a graph data model is a prerequisite for executing graph algorithms. At present, large-scale graph computing is based on the implementation of a library on a data flow framework, such as GraphX on Apache Spark or Gelly on Apache Flink, combined with the general data conversion operators provided by the underlying framework to perform a certain graph computing, but does not support Data sets that cannot solve complex analytical tasks.

SUMMARY OF THE INVENTION

The main purpose of this application is to provide an analysis method for a graph network structure, aiming to solve the technical problem that the existing graph computing does not support data sets and cannot solve complex analysis tasks.

This application proposes a method for analyzing a graph network structure, including:

Obtain the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set carries the first type label and the first type label corresponding to the vertex respectively. attribute, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges carries the second type label and the second attribute corresponding to the edge respectively;

Map each vertex and each edge in the graph network structure to the specified data set respectively;

obtaining a graph operator corresponding to the graph analysis task according to the execution script;

The specified data set corresponding to the graph network structure is analyzed and calculated by using the graph operator, and an analysis result is obtained.

Preferably, the step of obtaining the graph network structure to be analyzed according to the execution script of the graph analysis task includes:

obtaining the graph element of the graph network structure to be analyzed carried in the execution script of the graph analysis task, wherein the graph element includes a graph header;

Extract the image header data set corresponding to the image header from the specified database according to the image header;

judging whether the image header data set includes multiple objects;

If not, it is determined that the graph network structure to be analyzed is a logical graph whose graph header is a single object;

Acquiring vertex data and edge data associated with the logic graph from the data set, respectively forming a vertex set and an edge set;

The logic graph is represented by the vertex set and the edge set, and the graph network structure to be analyzed is obtained.

Preferably, the specified data set includes a Flink data set, and after the step of acquiring the graph operator corresponding to the graph analysis task according to the execution script, the step includes:

Obtain the execution order of each of the graph operators;

According to the execution order, each of the graph operators is linked into operation logic through the Java programming language;

The Flink operation program is formed by associating the operation logic with the trigger of the Flink trigger program.

Preferably, the graph operator includes an exclusion operator, and the graph operator is used to analyze and calculate the specified data set corresponding to the graph network structure, and the steps of obtaining the analysis result include:

obtaining a first vertex set and a first edge set corresponding to the first logical graph, and obtaining a second vertex set and a second edge set corresponding to the second logical graph;

The identifier of the second logic diagram is extracted from the second logic diagram by the function ID_ONLY to form a data set corresponding to the new id object;

The specified vertex and the specified edge are filtered by the exclusion operator to obtain the exclusion result data set corresponding to the exclusion operator, wherein the specified vertex is included in the first vertex set and not included in the second vertex set , the specified edge is really included in the first edge set;

The exclusion result dataset is sent to all nodes of the Apache Flink framework cluster via Flink broadcast.

Preferably, the graph network structure is a social network graph composed of multiple logical graphs, the graph operator includes a relational operator provided by Flink, and the specified data corresponding to the graph network structure is analyzed by using the graph operator. The steps of analyzing and calculating the set to obtain the analysis result include:

Identifying whether the relational operator selected by the user is to find the largest common subgraph between the logical graphs in the social network graph;

If so, aggregate the number of vertices of each of the logical graphs in the social network graph;

according to the number of vertices in each of said logical graphs, selecting a specified logical graph higher than the minimum vertex count;

Based on the specified logic graph, the maximum common subgraph between the logic graphs in the social network graph is obtained through a label propagation algorithm.

Preferably, the graph budget operator includes at least two, and the step of using the graph operator to analyze and calculate the specified data set corresponding to the graph network structure to obtain the analysis result includes:

Get the specified Flink program corresponding to multiple graph budget symbols;

Obtain the current running node of the specified Flink program, and predict the data set that can perform operations concurrently;

Distribute the concurrently executed data sets to designated machines in the Apache Flink framework cluster;

Receive the calculation results obtained by each designated machine executing the distributed data set respectively;

Summarize the calculation results to obtain the analysis results of multiple graph budget symbols;

The analysis results of the multiple graph budget identifiers are sent to all nodes of the Apache Flink framework cluster through Flink broadcast.

Preferably, the specified Flink program includes aggregation operations, transformation budgets and pattern matching budgets for a specific logic graph, and the step of distributing the concurrently executed data set to the specified machines in the Apache Flink framework cluster includes:

acquiring the data set corresponding to the specific logic diagram, the aggregation function corresponding to the aggregation operation, the conversion function corresponding to the transformation operation, and the matching function corresponding to the pattern matching operation;

Distribute the data set corresponding to the specific logic diagram and the aggregation function corresponding to the aggregation operation to the first machine in the cluster, and distribute the data set corresponding to the specific logic diagram and the transformation function corresponding to the transformation operation to the second machine in the cluster. a machine that distributes the data set corresponding to the specific logic diagram and the matching function corresponding to the pattern matching operation to the third machine in the cluster;

The first machine, the second machine and the third machine are controlled to operate concurrently.

The application also provides a graph network structure analysis device, including:

The first acquisition module is used to acquire the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set carries the corresponding A first type label and a first attribute, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges respectively carries the second type label and the second attribute corresponding to the edge;

a mapping module, used to map each vertex and each edge in the graph network structure to the specified data set respectively;

a second obtaining module, configured to obtain a graph operator corresponding to the graph analysis task according to the execution script;

The calculation module is configured to perform analysis and calculation on the specified data set corresponding to the graph network structure by using the graph operator to obtain an analysis result.

The present application also provides a computer device, including a memory and a processor, wherein the memory stores a computer program, and the processor implements the steps of the above method when executing the computer program.

The present application also provides a computer-readable storage medium on which a computer program is stored, and when the computer program is executed by a processor, the steps of the above-mentioned method are implemented.

This application not only establishes a graph network structure with extended attributes, but also has richer semantics of graph representation, supports multiple graphs with different attributes, and provides declarative and composable graph operators based on the graph network structure with extended attributes. It implements the graph network structure with extended attributes, and converts graph operations into data set operations to analyze a single graph or graph collection, provide new functions for graph analysis, and realize the ability to process large-scale data and complex graphs.

Description of drawings

1 is a schematic flowchart of a method for analyzing a graph network structure according to an embodiment of the present application;

2 is a schematic structural diagram of an apparatus for analyzing a graph network structure according to an embodiment of the present application;

FIG. 3 is a schematic diagram of an internal structure of a computer device according to an embodiment of the present application.

Detailed ways

In order to make the purpose, technical solutions and advantages of the present application more clearly understood, the present application will be described in further detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application, but not to limit the present application.

1 , a method for analyzing a graph network structure according to an embodiment of the present application includes:

S1: Obtain the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set carries the first type label corresponding to the vertex and the The first attribute, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges respectively carries the second type label and the second attribute corresponding to the edge;

S2: Map each vertex and each edge in the graph network structure to the specified data set respectively;

S3: Obtain a graph operator corresponding to the graph analysis task according to the execution script;

S4: Use the graph operator to analyze and calculate the specified data set corresponding to the graph network structure to obtain an analysis result.

组成。比如图网络由顶点集V＝{v₀，…，v₉}和边集E＝{e₀，…，e₁₉}组成。顶点可分为多种类型，包括表示人(Person)的顶点、表示论坛(Forum)的顶点和表示兴趣(Tag)的顶点。不同类型的顶点由相应的第一类型标签表示和相应的第一属性进行描述。边描述了顶点之间的关系，也有对应的第二类型标签(如knows)和第二属性进行描述。具有相同类型标签的顶点可能具有不同的属性，例如v0和v1,v1或许包括age属性，但是v0或许没有age属性，这与顶点的类型相关，可通过配置文件配置各顶点的类型标签和属性，以及各边的类型标签和属性，实现了有扩展属性的图网络结构，使网络结构的语义更丰富，可支持多个不同属性的图，信息量更庞大，可表达的关系更加复杂。本申请通过将图网络结构中的各顶点以及各条边分别映射为指定数据类型的指定数据集，比如Flink数据集，以便通过解析指定数据集之间的关系，计算图运算符对应的分析结果，实现对复杂的图网络结构的分析计算，为图形分析提供了新功能领域的应用可能。本申请不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在Apache FLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。The graph network structure in this application has extended attributes, and the graph network structure is composed of a vertex set V and an edge set E, wherein the vertex set V includes various types of vertices, which are described by the first type label and the first attribute corresponding to the point. represents each vertex. For example, the above graph network structure with extended attributes is a graph social network, represented as a directed graph G=<V, E>, consisting of a set of vertices V and a set of edges

composition. For example, a graph network consists of a vertex set V={v ₀ ,...,v ₉ } and an edge set E={e ₀ ,...,e ₁₉ }. Vertices can be classified into various types, including vertices representing people (Person), vertices representing forums (Forum), and vertices representing interests (Tag). Different types of vertices are represented by corresponding first type labels and described by corresponding first attributes. Edges describe the relationship between vertices, and also have corresponding second type labels (such as knows) and second attributes to describe. Vertices with the same type label may have different attributes, such as v0 and v1, v1 may include an age attribute, but v0 may not have an age attribute, which is related to the type of vertex, and the type label and attribute of each vertex can be configured through the configuration file. As well as the type labels and attributes of each side, a graph network structure with extended attributes is realized, which makes the semantics of the network structure richer, supports multiple graphs with different attributes, has a larger amount of information, and can express more complex relationships. In this application, each vertex and each edge in the graph network structure is mapped to a specified data set of a specified data type, such as a Flink data set, so as to analyze the relationship between the specified data sets and calculate the analysis results corresponding to the graph operators , to realize the analysis and calculation of the complex graph network structure, and provide the possibility of application in the new functional field for the graph analysis. This application not only establishes a graph network structure with extended attributes, but also has richer semantics of graph representation, supports multiple graphs with different attributes, and provides declarative and composable graph operators based on the graph network structure with extended attributes. FLink implements a graph network structure with extended attributes, and converts graph operations into data set operations to analyze a single graph or graph set, providing new functions for graph analysis, and realizing the ability to process large-scale data and complex graphs .

Further, the step S1 of acquiring the graph network structure to be analyzed according to the execution script of the graph analysis task includes:

S10: Obtain the graph elements of the graph network structure to be analyzed carried in the execution script of the graph analysis task, wherein the graph elements include graph headers;

S11: Extract the image header data set corresponding to the image header from the specified database according to the image header;

S12: Determine whether the image header data set includes multiple objects;

S13: If not, then determine that the graph network structure to be analyzed is a logical graph whose graph header is a single object;

S14: Obtain vertex data and edge data associated with the logic graph from the data set, and form a vertex set and an edge set respectively correspondingly;

S15: The logic graph is represented by the vertex set and the edge set, and the graph network structure to be analyzed is obtained.

和边集的子集

组成的有序对。图头表示数据与某个逻辑图相关联的关系，如果待分析的图网络结构的图头均只针对一种对象，则整个待分析的图网络结构为数据相通或具有数据关联的逻辑图。本申请的逻辑图带有扩展属性，比如图头的扩展属性包括地址、标签和数据属性，表示为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}>}}。The embodiments of the present application take the graph network structure to be analyzed as a logical graph as an example, and describe in detail the process of acquiring the graph network structure data set from the database to represent the graph network structure. A logic graph is a special case of a graph set. The graph header data set contains only a single object, and all the data information in the graph is the same. Logic graphs also have type labels (eg Community) and attributes, which can be described by either specific metrics (eg vertexCount:3) or general information about the logic graph (eg interest:Databases). The type labels and properties of a logic graph can be explicitly declared in the logic graph, and can also be the output of graph algorithms or used as input to subsequent operators, such as the application of community detection or graph pattern matching. In this application, the predefined database DB=<V,E,L> consists of vertex set V={vi _} , edge set E={ _ek } and a set of logic graph L={G _m }. Logical graph Gm=<V _m ,E _m >, consisting of a subset of vertex set V

and a subset of the edge set

composed of ordered pairs. The graph header represents the relationship between data and a certain logical graph. If the graph headers of the graph network structure to be analyzed are only for one type of object, the entire graph network structure to be analyzed is a logical graph with interconnected data or data association. The logic graph of this application has extended attributes. For example, the extended attributes of the graph header include address, label and data attributes, which are expressed as GraphHead:=<Id, Label, Properties>; the extended attributes of the vertex include address, label, vertex data attribute and The vertex number in the graph, expressed as Vertex:=<Id,Label,Properties,GraphIds>; the extended attributes of the edge include address, label, edge start vertex address, edge end vertex address, edge data attribute and edge number in the graph, Expressed as Edge:=<Id, Label, SrcId, TrgtId, Properties, GraphIds>. For example, the logic graph is 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}>}}.

Further, the specified data set includes a Flink data set, and after the step S3 of acquiring the graph operator corresponding to the graph analysis task according to the execution script, it includes:

S31: Obtain the execution order of each of the graph operators;

S32: link each of the graph operators into operational logic through the Java programming language according to the execution order;

S33: Associate the operation logic with the trigger of the Flink trigger program to form a Flink operation program.

The graph network structure of the embodiment of the present application is a graph representation based on the Apache Flink framework, and three object types are used to represent the graph elements of the graph network structure with extended attributes: graph header, vertex and edge. For datasets representing graph network structures, a dedicated Flink dataset is used for each graph element. The Flink datasets corresponding to the graph elements are converted into their respective dedicated Flink datasets through data mapping conversion. In the Apache Flink framework, programs need to be explicitly triggered to execute, for example, to write results to a file or database. Since none of the processes implemented by the graph operators in the embodiments of the present application include triggers that trigger programs explicitly, in this embodiment, multiple operators are linked into operation logic according to the execution order in the execution script, and then the operation The logic is associated with the trigger of the Flink trigger program to form a Flink operation program, so that the entire operation process is executed as a Flink program.

Further, the graph operator includes an exclusion operator, and the graph operator is used to analyze and calculate the specified data set corresponding to the graph network structure, and the step S4 of obtaining the analysis result includes:

S41: Obtain the first vertex set and the first edge set corresponding to the first logical graph, and obtain the second vertex set and the second edge set corresponding to the second logical graph;

S42: extract the identifier of the second logic diagram from the second logic diagram through the function ID_ONLY to form a data set corresponding to the new id object;

S43: Filter the specified vertex and the specified edge by the exclusion operator to obtain the exclusion result data set corresponding to the exclusion operator, wherein the specified vertex is included in the first vertex set, and is not included in the second vertex set The vertex set, the specified edge is actually contained in the first edge set.

S44: Send the exclusion result dataset to all nodes of the Apache Flink framework cluster through Flink broadcast.

The present application describes the process of obtaining the transformed data set by operating the exclusion operator of graph computation. The implementation process of the exclusion operator includes that the generated logic graph is composed of vertices and edges included in the first logic graph but not included in the second logic graph. The way it is implemented is to filter based on the vertices and edges of the logic graph. First, the identifier of the second logic diagram is extracted by mapping the header data set of the second logic diagram. The conversion is parameterized by calling the user-defined function ID_ONLY, so that the identifier is extracted from the header dataset by the function ID_ONLY. The dataset of the resulting logical graph contains a new id object for filtering vertices that are not included in the second logical graph with this new id object. The user-defined function (NOT_IN_GRAPH_FILTER) is passed as a parameter during the filter transformation, and the function is called for each vertex in the data set of the first and second logic graphs. In order to make the new id object suitable for the filter function, the data set obtained after the operation is sent to all nodes of the Apache Flink framework cluster using Flink's broadcasting concept. Then the generated dataset contains only vertices for which the filter function evaluates to true. The same process is used for edge filtering, but the edge filtering also needs to detect two semi-connected states, i.e. the case where only one end of the source and destination vertices that make up the edge is in the generated dataset needs to be excluded to ensure that the source and destination vertices are are included in the new vertex set. According to the data set generated by the operation, a new logic graph is created, and the graph header of the new logic graph is created by the constructor, including generating a new id. The above process of detecting two semi-connected states means that the source vertex and the target vertex of the edge have one end in another logical graph, that is, the part of one edge of one logical graph is in another logical graph, and the overlapping area needs to be divided. excluded situations.

Further, the graph network structure is a social network graph composed of multiple logical graphs, the graph operator includes a relational operator provided by Flink, and the specified data corresponding to the graph network structure is analyzed by using the graph operator. The step S4 of analyzing and calculating the set to obtain the analysis result includes:

S401: Identify whether the relation operator selected by the user is to find the largest common subgraph between the logic graphs in the social network graph;

S402: If yes, aggregate the number of vertices of each of the logic graphs in the social network graph;

S402: According to the number of vertices in each of the logical graphs, select a specified logical graph higher than the minimum vertex count;

S403: Based on the specified logic graph, obtain the maximum common subgraph between the logic graphs in the social network graph through a label propagation algorithm.

This application uses Flink datasets to represent graphs, so graph analysis is not limited to pre-defined operators, but can also use all data operations provided by Flink, such as relational operators, machine learning operators or graph processing operators. Taking the relationship operator to find the largest common subgraph among larger communities in a social network as an example, the analysis and calculation process is described in detail. Objects represented by graph network structures are often heterogeneous, for example, vertices of a social network graph can represent users, groups, or bands, while relationships can represent friendships, memberships, or interests. That is, entity objects of the same type may have different attributes, that is, different users may provide different attribute information. The above social network diagram includes multiple logic diagrams, including a set of logic diagrams L={G ₀ , G ₁ , G ₂ }, each logic diagram represents a community in the social network diagram, such as a specific interest group, such as Databases . Each logical graph has a corresponding subset of vertices and edges, eg, V(G0)={v0,v1} and E(G0)={e0,e1}. Analyzing the relationship between the logical graphs G0 and G2, it can be obtained from the social network graph with extended attributes of the three logical graphs of the social network graph. The vertices and edges associated with the logical graph G0 are shared with the logical graph G2, and it can be known that G0 and G2 Vertices and edges may overlap because V(G0)∩V(G2)={v0,v1} and E(G0)∩E(G2)={e0,e1}. In this embodiment, by identifying communities and gathering the number of vertices of each community, a community higher than the minimum vertex count is selected, that is, the selected larger community is determined, and the minimum vertex count amount is preset by the user. Finally a label propagation algorithm is applied to find the maximum common subgraph. The above label propagation algorithm is a graph-based semi-supervised learning method. The process is to predict the label information of unlabeled nodes from the label information of labeled nodes, and use the relationship between samples to build a complete graph model. The label of each node is propagated to adjacent nodes according to the similarity. At each step of node propagation, each node updates its label according to the label of the adjacent node. The greater the similarity with the node, the adjacent node will label it. The larger the influence weight is, the more consistent the labels of similar nodes are, and the easier its labels are to propagate. During label propagation, the label of the labeled data is kept unchanged, so that it passes the label to the unlabeled data. Finally, when the iteration ends, the probability distributions of similar nodes tend to be similar and can be divided into one class to find the largest independent set corresponding to the largest common subgraph.

Further, the graph budget operator includes at least two, and the step S4 of using the graph operator to analyze and calculate the specified data set corresponding to the graph network structure to obtain the analysis result includes:

S4001: Obtain the specified Flink programs corresponding to multiple graph budget symbols;

S4002: Obtain the currently running node of the specified Flink program, and predict a data set that can perform operations concurrently;

S4003: Distribute the concurrently executed data set to the designated machine in the Apache Flink framework cluster;

S4004: Receive the calculation result obtained by each designated machine executing the distributed data set respectively;

S4005: Summarize the calculation results to obtain analysis results of multiple graph budget symbols;

S4006: Send the analysis results of the multiple graph budget identifiers to all nodes of the Apache Flink framework cluster through Flink broadcast.

The Apache Flink framework of this application supports declarative definition and distributed execution analysis of data from streaming and batch processing. The supported data includes streaming and batch processing. The basic components of the program are datasets and transformations, which are abstracted through the tasks of defining and executing datasets, that is, forming datasets and the transformation process of datasets. A dataset is a collection of arbitrary data objects, and a transformation describes the conversion of data types from one dataset to another. For example, assuming X, Y are datasets, then the transformation can be seen as a function t: X→Y. For example, the above transformation is a map MAP, for each input data object x _i ∈ X, there is one and only one output data object y _i ∈ Y. For example, when reducing reduce when transforming, all input data objects are aggregated into a dataset of objects. Data transformation in relational databases, including join, groupby, project, union, and distinct. In order to describe the Flink program application logic, this application parameterizes the data conversion process through user-defined functions. Flink programs can be represented as multiple chain transformations. When performing tree transformations, the Flink framework is responsible for program optimization, data distribution, and parallel execution across clusters of machines. That is, a Flink script task can include multiple chained data transformations, and the Flink program will optimize the program, complete data distribution, and execute concurrently on clusters across machines during execution.

Further, the specified Flink program includes aggregate operations, transformation budgets and pattern matching budgets for a specific logic graph, and the step S4003 of distributing the data set of concurrent execution operations to the specified machines in the Apache Flink framework cluster includes:

S40031: Obtain the data set corresponding to the specific logic diagram, the aggregation function corresponding to the aggregation operation, the conversion function corresponding to the transformation operation, and the matching function corresponding to the pattern matching operation;

S40032: Distribute the data set corresponding to the specific logic diagram and the aggregation function corresponding to the aggregation operation to the first machine in the cluster, and distribute the data set corresponding to the specific logic diagram and the transformation function corresponding to the transformation operation to the cluster. The second machine distributes the data set corresponding to the specific logic diagram and the matching function corresponding to the pattern matching operation to the third machine in the cluster;

S40033: Control the first machine, the second machine, and the third machine to run concurrently.

模式匹配运算应用在特定逻辑图G上，返回包含所有匹配的图集合

In this embodiment, the process of concurrent execution by machines in the Apache Flink framework cluster is described in detail by taking the graph operator including the aggregation operator, the transformation operator, and the pattern matching operator as an example. The above aggregation operator refers to mapping the input specific logic graph G to the output graph G'. By executing a user-defined aggregation function α:L→A, where L is the logic graph and A is the value domain, the output graph G' is a modified version of the input specific logic graph G with a new attribute k, such that κ (G ', k)→α(G), κ is the mapping relationship, which maps the attribute k of the logic diagram to a value. For example vertex count: alpha=(g=>gVcount());outGraph=inGraph.agregate('vertexCount', alpha). The above transformation operator performs a user-defined transformation function γ: L→L, ν: V→V and ∈: E→E on the input specific logical graph G, and obtains the output graph G′=γ(G), where V( G')={ν(v):v∈V(G)}, E(G')={∈(e):e∈E(G)}. The above pattern matching operator takes two parameters, the pattern graph G ^* and the predicate

The pattern matching operation is applied to a specific logical graph G and returns a set of graphs containing all matches

2, an apparatus for analyzing a graph network structure according to an embodiment of the present application includes:

The first acquisition module 1 is used to acquire the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set carries the corresponding vertex The first type label and the first attribute of the edge set, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges respectively carries the second type label and the second attribute corresponding to the edge;

The mapping module 2 is used to map each vertex and each edge in the graph network structure to the specified data set respectively;

A second obtaining module 3, configured to obtain a graph operator corresponding to the graph analysis task according to the execution script;

The calculation module 4 is configured to analyze and calculate the specified data set corresponding to the graph network structure by using the graph operator to obtain an analysis result.

组成。比如图网络由顶点集V＝{v₀，…，v₉}和边集E＝{e₀，…，e₁₉}组成。顶点可分为多种类型，包括表示人(Person)的顶点、表示论坛(Forum)的顶点和表示兴趣(Tag)的顶点。不同类型的顶点由相应的第一类型标签表示和相应的第一属性进行描述。边描述了顶点之间的关系，也有对应的第二类型标签(如knows)和第二属性进行描述。具有相同类型标签的顶点可能具有不同的属性，例如v0和v1,v1或许包括age属性，但是v0或许没有age属性，这与顶点的类型相关，可通过配置文件配置各顶点的类型标签和属性，以及各边的类型标签和属性，实现了有扩展属性的图网络结构，使网络结构的语义更丰富，可支持多个不同属性的图，信息量更庞大，可表达的关系更加复杂。本申请通过将图网络结构中的各顶点以及各条边分别映射为指定数据类型的指定数据集，比如Flink数据集，以便通过解析指定数据集之间的关系，计算图运算符对应的分析结果，实现对复杂的图网络结构的分析计算，为图形分析提供了新功能领域的应用可能。本申请不仅建立有扩展属性的图网络结构，图表示的语义更丰富，支持多个不同属性的图，且基于有扩展属性的图网络结构，提供声明性和可组合的图运算符，在Apache FLink上实现了扩展属性的图网络结构，并将图运算转换为数据集的运算，实现分析单个图或图集合，为图形分析提供了新的功能，实现对大规模数据和复杂图形处理的能力。The graph network structure in this application has extended attributes, and the graph network structure is composed of a vertex set V and an edge set E, wherein the vertex set V includes various types of vertices, which are described by the first type label and the first attribute corresponding to the point. represents each vertex. For example, the above graph network structure with extended attributes is a graph social network, represented as a directed graph G=<V, E>, consisting of a set of vertices V and a set of edges

composition. For example, a graph network consists of a vertex set V={v ₀ ,...,v ₉ } and an edge set E={e ₀ ,...,e ₁₉ }. Vertices can be classified into various types, including vertices representing people (Person), vertices representing forums (Forum), and vertices representing interests (Tag). Different types of vertices are represented by corresponding first type labels and described by corresponding first attributes. Edges describe the relationship between vertices, and also have corresponding second type labels (such as knows) and second attributes to describe. Vertices with the same type label may have different attributes, such as v0 and v1, v1 may include an age attribute, but v0 may not have an age attribute, which is related to the type of vertex, and the type label and attribute of each vertex can be configured through the configuration file, As well as the type labels and attributes of each side, a graph network structure with extended attributes is realized, which makes the semantics of the network structure richer, supports multiple graphs with different attributes, has a larger amount of information, and can express more complex relationships. In this application, each vertex and each edge in the graph network structure is mapped to a specified data set of a specified data type, such as a Flink data set, so as to analyze the relationship between the specified data sets and calculate the analysis results corresponding to the graph operators , to realize the analysis and calculation of the complex graph network structure, and provide the possibility of application in the new functional field for the graph analysis. This application not only establishes a graph network structure with extended attributes, but also has richer semantics of graph representation, supports multiple graphs with different attributes, and provides declarative and composable graph operators based on the graph network structure with extended attributes. FLink implements a graph network structure with extended attributes, and converts graph operations into data set operations to analyze a single graph or graph set, providing new functions for graph analysis, and realizing the ability to process large-scale data and complex graphs .

Further, the first acquisition module 1 includes:

a first obtaining unit, configured to obtain the graph elements of the graph network structure to be analyzed carried in the execution script of the graph analysis task, wherein the graph elements include graph headers;

an extraction unit, used for extracting a picture header data set corresponding to the picture header from a specified database according to the picture header;

a judging unit for judging whether the image header data set includes multiple objects;

a determining unit, configured to determine that the graph network structure to be analyzed is a logical graph whose graph header is a single object if it does not include multiple objects;

a second acquiring unit, configured to acquire vertex data and edge data associated with the logic graph from the data set, and form a vertex set and an edge set respectively;

The first obtaining unit is used to represent the logic graph through the vertex set and the edge set, and obtain the graph network structure to be analyzed.

和边集的子集

组成的有序对。图头表示数据与某个逻辑图相关联的关系，如果待分析的图网络结构的图头均只针对一种对象，则整个待分析的图网络结构为数据相通或具有数据关联的逻辑图。本申请的逻辑图带有扩展属性，比如图头的扩展属性包括地址、标签和数据属性，表示为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}>}}。The embodiments of the present application take the graph network structure to be analyzed as a logical graph as an example, and describe in detail the process of acquiring the graph network structure data set from the database to represent the graph network structure. A logic graph is a special case of a graph set. The graph header data set contains only a single object, and all the data information in the graph is the same. Logic graphs also have type labels (eg Community) and attributes, which can be described by either specific metrics (eg vertexCount:3) or general information about the logic graph (eg interest:Databases). The type labels and properties of a logic graph can be explicitly declared in the logic graph, and can also be the output of graph algorithms or used as input to subsequent operators, such as the application of community detection or graph pattern matching. In this application, the predefined database DB=<V, E, L> consists of a vertex set V={vi _} , an edge set E={ _ek } and a set of logic graphs L={G _m }. Logical graph Gm=<V _m , _Em >, consisting of a subset of vertex set V

and a subset of the edge set

composed of ordered pairs. The graph header represents the relationship between data and a certain logical graph. If the graph headers of the graph network structure to be analyzed are only for one type of object, the entire graph network structure to be analyzed is a logical graph with interconnected data or data association. The logic graph of the present application has extended attributes. For example, the extended attributes of the graph header include address, label and data attributes, which are expressed as GraphHead:=<Id, Label, Properties>; the extended attributes of the vertex include address, label, vertex data attribute and The vertex number in the graph, expressed as Vertex: <Id, Label, Properties, GraphIds>; the extended attributes of the edge include address, label, edge start vertex address, edge end vertex address, edge data attribute and the edge number in the graph, indicating For Edge: <Id, Label, SrcId, TrgtId, Properties, GraphIds>. For example, the logic graph is 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}>}}.

Further, the specified data set includes a Flink data set, an analysis device for a graph network structure, including:

The third acquisition module is used to acquire the execution order of each of the graph operators;

a linking module, configured to link each of the graph operators into operational logic through the Java programming language according to the execution sequence;

The association module is used to associate the operation logic with the trigger of the Flink trigger program to form the Flink operation program.

The graph network structure of the embodiment of the present application is a graph representation based on the Apache Flink framework, and three object types are used to represent the graph elements of the graph network structure with extended attributes: graph header, vertex and edge. For datasets representing graph network structures, a dedicated Flink dataset is used for each graph element. The Flink datasets corresponding to the graph elements are converted into their respective dedicated Flink datasets through data mapping conversion. In the Apache Flink framework, programs need to be explicitly triggered to execute, for example, to write results to a file or database. Since none of the processes implemented by the graph operators in the embodiments of the present application include triggers that trigger programs explicitly, in this embodiment, multiple operators are linked into operation logic according to the execution order in the execution script, and then the operation The logic is associated with the trigger of the Flink trigger program to form a Flink operation program, so that the entire operation process is executed as a Flink program.

Further, the graph operator includes an exclusion operator, and the calculation module 4 includes:

a third obtaining unit, configured to obtain the first vertex set and the first edge set corresponding to the first logical graph, and obtain the second vertex set and the second edge set corresponding to the second logical graph;

An extraction unit, used for extracting the identifier of the second logic diagram from the second logic diagram through the function ID_ONLY, to form a data set corresponding to the new id object;

A screening unit, configured to filter a specified vertex and a specified edge through the exclusion operator, to obtain an exclusion result data set corresponding to the exclusion operator, wherein the specified vertex is included in the first vertex set, and is not included in the the second vertex set, the specified edge is actually contained in the first edge set.

The first sending unit is configured to send the excluded result data set to all nodes of the Apache Flink framework cluster through Flink broadcast.

The present application describes the process of obtaining the transformed data set by operating the exclusion operator of graph computation. The implementation process of the exclusion operator includes that the generated logic graph is composed of vertices and edges included in the first logic graph but not included in the second logic graph. The way it is implemented is to filter based on the vertices and edges of the logic graph. First, the identifier of the second logic diagram is extracted by mapping the header data set of the second logic diagram. The conversion is parameterized by calling the user-defined function ID_ONLY, so that the identifier is extracted from the header dataset by the function ID_ONLY. The dataset of the resulting logical graph contains a new id object for filtering vertices that are not included in the second logical graph with this new id object. The user-defined function (NOT_IN_GRAPH_FILTER) is passed as a parameter during the filter transformation, and the function is called for each vertex in the data set of the first and second logic graphs. In order to make the new id object suitable for the filter function, the data set obtained after the operation is sent to all nodes of the Apache Flink framework cluster using Flink's broadcasting concept. Then the generated dataset contains only vertices for which the filter function evaluates to true. The same process is used for edge filtering, but edge filtering also requires detection of two semi-connected states, i.e. the case where only one end of the source and destination vertices that make up the edge is in the generated dataset needs to be excluded to ensure that the source and destination vertices are are included in the new vertex set. According to the data set generated by the operation, a new logic graph is created, and the graph header of the new logic graph is created by the constructor, including generating a new id. The above process of detecting two semi-connected states means that the source vertex and the target vertex of the edge have one end in another logical graph, that is, the part of one edge of one logical graph is in another logical graph, and the overlapping area needs to be divided. excluded situations.

Further, the graph network structure is a social network graph composed of multiple logical graphs, the graph operators include relational operators provided by Flink, and the calculation module 4 includes:

an identification unit for identifying whether the relation operator selected by the user is to find the largest common subgraph between the logic graphs in the social network graph;

an aggregation unit, configured to aggregate the number of vertices of each of the logical graphs in the social network graph if the largest common subgraph between the logical graphs in the social network graph is to be found;

a selection unit for selecting a specified logical graph higher than the minimum vertex count according to the number of vertices in each of the logical graphs;

The second obtaining unit is configured to obtain the maximum common subgraph between the logic graphs in the social network graph through a label propagation algorithm based on the specified logic graph.

This application uses Flink datasets to represent graphs, so graph analysis is not limited to pre-defined operators, but can also use all data operations provided by Flink, such as relational operators, machine learning operators or graph processing operators. Taking the relationship operator to find the largest common subgraph among larger communities in a social network as an example, the analysis and calculation process is described in detail. Objects represented by graph network structures are often heterogeneous, for example, vertices of a social network graph can represent users, groups, or bands, while relationships can represent friendships, memberships, or interests. That is, entity objects of the same type may have different attributes, that is, different users may provide different attribute information. The above social network diagram includes multiple logic diagrams, including a set of logic diagrams L={G ₀ , G ₁ , G ₂ }, each logic diagram represents a community in the social network diagram, such as a specific interest group, such as Databases . Each logical graph has a corresponding subset of vertices and edges, eg, V(G0)={v0,v1} and E(G0)={e0,e1}. Analyzing the relationship between the logical graphs G0 and G2, it can be obtained from the social network graph with extended attributes of the three logical graphs of the social network graph. The vertices and edges associated with the logical graph G0 are shared with the logical graph G2, and it can be known that G0 and G2 Vertices and edges may overlap because and . In this embodiment, by identifying communities and gathering the number of vertices of each community, a community higher than the minimum vertex count is selected, that is, the selected larger community is determined, and the minimum vertex count amount is preset by the user. Finally a label propagation algorithm is applied to find the maximum common subgraph. The above label propagation algorithm is a graph-based semi-supervised learning method. The process is to predict the label information of unlabeled nodes from the label information of labeled nodes, and use the relationship between samples to build a complete graph model. The label of each node is propagated to adjacent nodes according to the similarity. At each step of node propagation, each node updates its label according to the label of the adjacent node. The greater the similarity with the node, the adjacent node will label it. The larger the influence weight is, the more consistent the labels of similar nodes are, and the easier its labels are to propagate. During label propagation, the label of the labeled data is kept unchanged, so that it passes the label to the unlabeled data. Finally, when the iteration ends, the probability distributions of similar nodes tend to be similar and can be divided into one class to find the largest independent set corresponding to the largest common subgraph.

Further, the graph budget symbol includes at least two, and the calculation module 4 includes:

The fourth obtaining unit is used to obtain the designated Flink programs corresponding to multiple graph budget symbols;

The fifth acquisition unit is used to acquire the currently running node of the specified Flink program, and predict the data set that can perform operations concurrently;

The distribution unit is used to distribute the concurrently executed data sets to the designated machines in the Apache Flink framework cluster;

a receiving unit, configured to receive the calculation results obtained by the respective designated machines executing the distributed data sets;

The summary unit is used for summarizing the calculation results to obtain the analysis results of multiple graph budget symbols;

The second sending unit is configured to send the analysis results of the plurality of graph budget identifiers to all nodes of the Apache Flink framework cluster through Flink broadcast.

The Apache Flink framework of this application supports declarative definition and distributed execution analysis of data from streaming and batch processing. The supported data includes streaming and batch processing. The basic components of the program are datasets and transformations, which are abstracted through the tasks of defining and executing datasets, that is, forming datasets and the transformation process of datasets. A dataset is a collection of arbitrary data objects, and a transformation describes the conversion of data types from one dataset to another. For example, assuming X, Y are datasets, then the transformation can be seen as a function t: X→Y. For example, the above transformation is a map MAP, for each input data object x _i ∈ X, there is one and only one output data object y _i ∈ Y. For example, when reducing reduce when transforming, all input data objects are aggregated into a dataset of objects. Data transformation in relational databases, including join, groupby, project, union, and distinct. In order to describe the Flink program application logic, this application parameterizes the data conversion process through user-defined functions. Flink programs can be represented as multiple chain transformations. When performing tree transformations, the Flink framework is responsible for program optimization, data distribution, and parallel execution across clusters of machines. That is, a Flink script task can include multiple chained data transformations, and the Flink program will optimize the program, complete data distribution, and execute concurrently on clusters across machines during execution.

Further, the specified Flink program includes aggregation operations, transformation budgets and pattern matching budgets for specific logic graphs, and the distribution unit includes:

an acquisition subunit for acquiring the data set corresponding to the specific logic diagram, the aggregation function corresponding to the aggregation operation, the conversion function corresponding to the transformation operation, and the matching function corresponding to the pattern matching operation;

A distribution subunit, configured to distribute the data set corresponding to the specific logic diagram and the aggregation function corresponding to the aggregation operation to the first machine in the cluster, and distribute the data set corresponding to the specific logic diagram and the conversion function corresponding to the transformation operation to the second machine in the cluster, and distribute the data set corresponding to the specific logic diagram and the matching function corresponding to the pattern matching operation to the third machine in the cluster;

A control subunit for controlling the first machine, the second machine and the third machine to run concurrently.

模式匹配运算应用在特定逻辑图G上，返回包含所有匹配的图集合

In this embodiment, the process of concurrent execution by machines in the Apache Flink framework cluster is described in detail by taking the graph operator including the aggregation operator, the transformation operator, and the pattern matching operator as an example. The above aggregation operator refers to mapping the input specific logic graph G to the output graph G'. By executing a user-defined aggregation function α: L→A, where L is the logic graph and A is the value domain, the output graph G' is a modified version of the input specific logic graph G with a new attribute k, such that κ (G ′, k)→α(G), κ is the mapping relationship, which maps the attribute k of the logic diagram to a value. For example, vertex count: alpha=(g=>gVcount());outGraph=inGraph.aggregate('vertexCount', alpha). The above transformation operator performs a user-defined transformation function γ: L→L, v: V→V and ∈: E→E on the input specific logical graph G, and obtains the output graph G′=γ(G), where G′ ={v(v):v∈V(G)}, E(G')={∈(e):e∈E(G)}. The above pattern matching operator takes two parameters, the pattern graph G ^* and the predicate

The pattern matching operation is applied to a specific logical graph G and returns a set of graphs containing all matches

Referring to FIG. 3 , an embodiment of the present application further provides a computer device. The computer device may be a server, and its internal structure may be as shown in FIG. 3 . The computer device includes a processor, memory, a network interface, and a database connected by a system bus. Among them, the processor of the computer design is used to provide computing and control capabilities. The memory of the computer device includes a non-volatile storage medium, an internal memory. The nonvolatile storage medium stores an operating system, a computer program, and a database. The memory provides an environment for the execution of the operating system and computer programs in the non-volatile storage medium. The database of the computer equipment is used to store all the data required for the analysis process of the graph network structure. The network interface of the computer device is used to communicate with an external terminal through a network connection. The computer program, when executed by a processor, implements a method for analyzing a graph network structure.

The above-mentioned processor executes the analysis method of the above-mentioned graph network structure, and obtains the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set is respectively Carrying the first type label and the first attribute corresponding to the vertex, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges carries the second type label and the second attribute corresponding to the edge respectively. ; Map each vertex and each edge in the graph network structure to the specified data set respectively; According to the execution script, obtain the graph operator corresponding to the graph analysis task; Utilize the graph operator to the described graph operator The specified data set corresponding to the graph network structure is analyzed and calculated, and the analysis result is obtained.

The above computer equipment not only establishes a graph network structure with extended attributes, but also has richer semantics of graph representation, supports multiple graphs with different attributes, and provides declarative and composable graph operators based on the graph network structure with extended attributes, The graph network structure with extended attributes is implemented on Apache FLink, and graph operations are converted into data set operations to analyze a single graph or graph collection, provide new functions for graph analysis, and realize large-scale data and complex graph processing. Ability.

In one embodiment, the step of obtaining the graph network structure to be analyzed by the processor according to the execution script of the graph analysis task includes: obtaining the graph elements of the graph network structure to be analyzed carried in the execution script of the graph analysis task , wherein the picture element includes a picture header; extract the picture header data set corresponding to the picture header from the specified database according to the picture header; determine whether the picture header data set includes multiple objects; if not, determine The graph network structure to be analyzed is a logical graph whose graph header is a single object; vertex data and edge data associated with the logical graph are obtained from the data set, and form a vertex set and an edge set respectively; Sets and edge sets represent the logic graph, and the graph network structure to be analyzed is obtained.

In one embodiment, the specified data set includes a Flink data set, and after the step of obtaining the graph operator corresponding to the graph analysis task according to the execution script, the processor includes: obtaining the graph operator of each graph operator. Execution sequence; according to the execution sequence, each of the graph operators is linked into operation logic through the Java programming language; the operation logic is associated with the trigger of the Flink trigger program to form a Flink operation program.

In one embodiment, the graph operator includes an exclusion operator, and the processor uses the graph operator to perform analysis and calculation on a specified data set corresponding to the graph network structure, and the step of obtaining an analysis result includes: obtaining a first The first vertex set and the first edge set corresponding to a logical graph are obtained, and the second vertex set and the second edge set corresponding to the second logical graph are obtained; the function ID_ONLY is used to extract the second logical graph from the second logical graph. identifier to form the data set corresponding to the new id object; filter the specified vertex and the specified edge by the exclusion operator, and obtain the exclusion result data set corresponding to the exclusion operator, wherein the specified vertex is included in the first The vertex set is not included in the second vertex set, and the specified edge is really included in the first edge set; the excluded result data set is sent to all nodes of the Apache Flink framework cluster through Flink broadcast.

In one embodiment, the graph network structure is a social network graph composed of multiple logical graphs, the graph operators include relational operators provided by Flink, and the above-mentioned processor uses the graph operators to analyze the graph network structure. The corresponding designated data set is analyzed and calculated, and the steps of obtaining the analysis result include: identifying whether the relationship operator selected by the user is to find the largest common subgraph between the logic diagrams in the social network diagram; The number of vertices of each of the logical graphs in the social network graph; according to the number of vertices of each of the logical graphs, a specified logical graph higher than the minimum vertex count is selected; based on the specified logical graph, the tag propagation algorithm is used to obtain the The largest common subgraph between logical graphs in a social network graph.

In one embodiment, the graph budget operator includes at least two, and the processor uses the graph operator to perform analysis and calculation on a specified data set corresponding to the graph network structure, and the step of obtaining an analysis result includes: obtaining multiple data sets. The designated Flink program corresponding to each graph budget symbol; obtain the current running node of the designated Flink program, and predict the data set that can execute the operation concurrently; distribute the data set that can execute the operation concurrently to the designated machine in the Apache Flink framework cluster; receive each designated Flink program The machine executes the calculation results obtained from the distributed datasets separately; aggregates the calculation results to obtain the analysis results of multiple graph budget symbols; sends the analysis results of the multiple graph budget symbols to all members of the Apache Flink framework cluster through Flink broadcast node.

In one embodiment, the designated Flink program includes aggregation operations, transformation budgets, and pattern matching budgets on a specific logic graph, and the above-mentioned processor distributes the data sets that perform operations concurrently to the designated machines in the Apache Flink framework cluster. Including: acquiring the data set corresponding to the specific logic diagram, the aggregation function corresponding to the aggregation operation, the conversion function corresponding to the transformation operation, and the matching function corresponding to the pattern matching operation; and the data set corresponding to the specific logic diagram and the aggregation operation. The aggregation function is distributed to the first machine in the cluster, the data set corresponding to the specific logic diagram and the transformation function corresponding to the transformation operation are distributed to the second machine in the cluster, and the data set corresponding to the specific logic diagram is matched with the pattern The matching function corresponding to the operation is distributed to the third machine in the cluster; the first machine, the second machine and the third machine are controlled to run concurrently.

Those skilled in the art can understand that the structure shown in FIG. 3 is only a block diagram of a partial structure related to the solution of the present application, and does not constitute a limitation on the computer equipment to which the solution of the present application is applied.

An embodiment of the present application also provides a computer-readable storage medium on which a computer program is stored. When the computer program is executed by a processor, a method for analyzing a graph network structure is implemented, and a graph to be analyzed is obtained according to an execution script of a graph analysis task. A network structure, wherein the graph network structure includes a vertex set and an edge set, each vertex in the vertex set carries a first type label and a first attribute corresponding to the vertex, and each edge in the edge set is associated with The two vertices of the relationship are connected to form, and each of the edges respectively carries the second type label and the second attribute corresponding to the edge; each vertex and each edge in the graph network structure are mapped to the specified data set respectively; according to the execution A script is used to obtain a graph operator corresponding to the graph analysis task; using the graph operator to perform analysis and calculation on a specified data set corresponding to the graph network structure, an analysis result is obtained.

The above computer-readable storage medium not only establishes a graph network structure with extended attributes, but also has richer semantics of graph representation, supports multiple graphs with different attributes, and provides declarative and composable graphs based on the graph network structure with extended attributes. The operator implements a graph network structure with extended attributes on Apache FLink, and converts graph operations into data set operations, realizing the analysis of a single graph or graph collection, providing new functions for graph analysis, and realizing large-scale data and graph analysis. The capability of complex graphics processing.

In one embodiment, the step of obtaining the graph network structure to be analyzed by the processor according to the execution script of the graph analysis task includes: obtaining the graph elements of the graph network structure to be analyzed carried in the execution script of the graph analysis task , wherein the picture element includes a picture header; extract the picture header data set corresponding to the picture header from the specified database according to the picture header; determine whether the picture header data set includes multiple objects; if not, determine The graph network structure to be analyzed is a logical graph whose graph header is a single object; vertex data and edge data associated with the logical graph are obtained from the data set, and form a vertex set and an edge set respectively; Sets and edge sets represent the logic graph, and the graph network structure to be analyzed is obtained.

In one embodiment, the specified data set includes a Flink data set, and after the step of obtaining the graph operator corresponding to the graph analysis task according to the execution script, the processor includes: obtaining the graph operator of each graph operator. Execution sequence; according to the execution sequence, each of the graph operators is linked into operation logic through the Java programming language; the operation logic is associated with the trigger of the Flink trigger program to form a Flink operation program.

In one embodiment, the graph operator includes an exclusion operator, and the processor uses the graph operator to perform analysis and calculation on a specified data set corresponding to the graph network structure, and the step of obtaining an analysis result includes: obtaining a first The first vertex set and the first edge set corresponding to a logical graph are obtained, and the second vertex set and the second edge set corresponding to the second logical graph are obtained; the function ID_ONLY is used to extract the second logical graph from the second logical graph. identifier to form the data set corresponding to the new id object; filter the specified vertex and the specified edge by the exclusion operator, and obtain the exclusion result data set corresponding to the exclusion operator, wherein the specified vertex is included in the first The vertex set is not included in the second vertex set, and the specified edge is really included in the first edge set; the excluded result data set is sent to all nodes of the Apache Flink framework cluster through Flink broadcast.

In one embodiment, the graph network structure is a social network graph composed of multiple logical graphs, the graph operators include relational operators provided by Flink, and the above-mentioned processor uses the graph operators to analyze the graph network structure. The corresponding designated data set is analyzed and calculated, and the steps of obtaining the analysis result include: identifying whether the relationship operator selected by the user is to find the largest common subgraph between the logic diagrams in the social network diagram; The number of vertices of each of the logical graphs in the social network graph; according to the number of vertices of each of the logical graphs, a specified logical graph higher than the minimum vertex count is selected; based on the specified logical graph, the tag propagation algorithm is used to obtain the The largest common subgraph between logical graphs in a social network graph.

In one embodiment, the graph budget operator includes at least two, and the processor uses the graph operator to perform analysis and calculation on a specified data set corresponding to the graph network structure, and the step of obtaining an analysis result includes: obtaining multiple data sets. The designated Flink program corresponding to each graph budget symbol; obtain the current running node of the designated Flink program, and predict the data set that can execute the operation concurrently; distribute the data set that can execute the operation concurrently to the designated machine in the Apache Flink framework cluster; receive each designated Flink program The machine executes the calculation results obtained from the distributed datasets separately; aggregates the calculation results to obtain the analysis results of multiple graph budget symbols; sends the analysis results of the multiple graph budget symbols to all members of the Apache Flink framework cluster through Flink broadcast node.

In one embodiment, the designated Flink program includes aggregation operations, transformation budgets, and pattern matching budgets on a specific logic graph, and the above-mentioned processor distributes the data sets that perform operations concurrently to the designated machines in the Apache Flink framework cluster. Including: acquiring the data set corresponding to the specific logic diagram, the aggregation function corresponding to the aggregation operation, the conversion function corresponding to the transformation operation, and the matching function corresponding to the pattern matching operation; and the data set corresponding to the specific logic diagram and the aggregation operation. The aggregation function is distributed to the first machine in the cluster, the data set corresponding to the specific logic diagram and the transformation function corresponding to the transformation operation are distributed to the second machine in the cluster, and the data set corresponding to the specific logic diagram is matched with the pattern The matching function corresponding to the operation is distributed to the third machine in the cluster; the first machine, the second machine and the third machine are controlled to run concurrently.

Those of ordinary skill in the art can understand that all or part of the process in the method of the above-mentioned embodiments can be implemented by instructing the relevant hardware through a computer program, and the above-mentioned computer program can be stored in a non-volatile computer-readable storage medium , when the computer program is executed, it may include the processes of the above-mentioned method embodiments. Wherein, any reference to memory, storage, database or other medium provided in this application and used in the embodiments may include non-volatile and/or volatile memory. Nonvolatile memory may include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), or flash memory. Volatile memory may include random access memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in various forms such as static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double-rate SDRAM (SSRSDRAM), enhanced SDRAM (ESDRAM), synchronous Link (Synchlink) DRAM (SLDRAM), memory bus (Rambus) direct RAM (RDRAM), direct memory bus dynamic RAM (DRDRAM), and memory bus dynamic RAM (RDRAM), etc.

It should be noted that, herein, the terms "comprising", "comprising" or any other variation thereof are intended to encompass non-exclusive inclusion, such that a process, device, article or method comprising a series of elements includes not only those elements, It also includes other elements not expressly listed or inherent to such a process, apparatus, article or method. Without further limitation, an element qualified by the phrase "comprising a..." does not preclude the presence of additional identical elements in the process, apparatus, article, or method that includes the element.

The above are only the preferred embodiments of the present application, and are not intended to limit the scope of the patent of the present application. Any equivalent structure or equivalent process transformation made by using the contents of the description and drawings of the present application, or directly or indirectly applied to other related The technical field is similarly included in the scope of patent protection of this application.

Claims (10)

1. an analysis method of graph network structure, is characterized in that, comprises: Obtain the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set carries the first type label and the first type label corresponding to the vertex respectively. attribute, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges carries the second type label and the second attribute corresponding to the edge respectively; Map each vertex and each edge in the graph network structure to the specified data set respectively; obtaining a graph operator corresponding to the graph analysis task according to the execution script; The specified data set corresponding to the graph network structure is analyzed and calculated by using the graph operator, and an analysis result is obtained. 2. The method for analyzing a graph network structure according to claim 1, wherein the step of obtaining the graph network structure to be analyzed according to the execution script of the graph analysis task, comprises: obtaining the graph element of the graph network structure to be analyzed carried in the execution script of the graph analysis task, wherein the graph element includes a graph header; Extract the image header data set corresponding to the image header from the specified database according to the image header; judging whether the image header data set includes multiple objects; If not, it is determined that the graph network structure to be analyzed is a logical graph whose graph header is a single object; Acquiring vertex data and edge data associated with the logic graph from the data set, respectively forming a vertex set and an edge set; The logic graph is represented by the vertex set and the edge set, and the graph network structure to be analyzed is obtained. 3. The method for analyzing a graph network structure according to claim 1, wherein the specified data set comprises a Flink data set, and according to the execution script, the graph operator corresponding to the graph analysis task is obtained. After the steps, including: Obtain the execution order of each of the graph operators; According to the execution order, each of the graph operators is linked into operation logic through the Java programming language; The Flink operation program is formed by associating the operation logic with the trigger of the Flink trigger program. 4 . The method for analyzing a graph network structure according to claim 1 , wherein the graph operator comprises an exclusion operator, and the graph operator is used to analyze and calculate a specified data set corresponding to the graph network structure. 5 . , the steps to get the analysis result include: obtaining a first vertex set and a first edge set corresponding to the first logical graph, and obtaining a second vertex set and a second edge set corresponding to the second logical graph; The identifier of the second logic diagram is extracted from the second logic diagram by the function ID_ONLY to form a data set corresponding to the new id object; The specified vertex and the specified edge are filtered by the exclusion operator to obtain the exclusion result data set corresponding to the exclusion operator, wherein the specified vertex is included in the first vertex set and not included in the second vertex set , the specified edge is really included in the first edge set; The exclusion result dataset is sent to all nodes of the Apache Flink framework cluster via Flink broadcast. 5. The method for analyzing a graph network structure according to claim 1, wherein the graph network structure is a social network graph composed of a plurality of logical graphs, and the graph operators include relational operators provided by Flink, so Describe the steps of using the graph operator to analyze and calculate the specified data set corresponding to the graph network structure to obtain the analysis result, including: Identifying whether the relational operator selected by the user is to find the largest common subgraph between the logical graphs in the social network graph; If so, aggregate the number of vertices of each of the logical graphs in the social network graph; according to the number of vertices in each of said logical graphs, selecting a specified logical graph higher than the minimum vertex count; Based on the specified logic graph, the maximum common subgraph between the logic graphs in the social network graph is obtained through a label propagation algorithm. 6 . The method for analyzing a graph network structure according to claim 1 , wherein the graph budget operator comprises at least two, and the graph operator is used to perform an analysis on a specified data set corresponding to the graph network structure. 7 . The steps of analyzing and calculating to obtain the analysis result include: Get the specified Flink program corresponding to multiple graph budget symbols; Obtain the current running node of the specified Flink program, and predict the data set that can perform operations concurrently; Distribute the concurrently executed data sets to designated machines in the Apache Flink framework cluster; Receive the calculation results obtained by each designated machine executing the distributed data set respectively; Summarize the calculation results to obtain the analysis results of multiple graph budget symbols; The analysis results of the multiple graph budget identifiers are sent to all nodes of the Apache Flink framework cluster through Flink broadcast. 7. The method for analyzing a graph network structure according to claim 6, wherein the specified Flink program includes an aggregate operation, a transformation budget and a pattern matching budget for a specific logic graph, and the data set that will execute the operation concurrently The steps to distribute to specified machines in the Apache Flink framework cluster include: acquiring the data set corresponding to the specific logic diagram, the aggregation function corresponding to the aggregation operation, the conversion function corresponding to the transformation operation, and the matching function corresponding to the pattern matching operation; Distribute the data set corresponding to the specific logic diagram and the aggregation function corresponding to the aggregation operation to the first machine in the cluster, and distribute the data set corresponding to the specific logic diagram and the transformation function corresponding to the transformation operation to the second machine in the cluster. a machine that distributes the data set corresponding to the specific logic diagram and the matching function corresponding to the pattern matching operation to the third machine in the cluster; The first machine, the second machine and the third machine are controlled to operate concurrently. 8. An analysis device of a graph network structure, characterized in that, comprising: The first acquisition module is used to acquire the graph network structure to be analyzed according to the execution script of the graph analysis task, wherein the graph network structure includes a vertex set and an edge set, and each vertex in the vertex set carries the corresponding A first type label and a first attribute, each edge in the edge set is formed by connecting two vertices with an associated relationship, and each of the edges respectively carries the second type label and the second attribute corresponding to the edge; a mapping module, used to map each vertex and each edge in the graph network structure to the specified data set respectively; a second obtaining module, configured to obtain a graph operator corresponding to the graph analysis task according to the execution script; The calculation module is configured to perform analysis and calculation on the specified data set corresponding to the graph network structure by using the graph operator to obtain an analysis result. 9. A computer device comprising a memory and a processor, wherein the memory stores a computer program, wherein the processor implements the steps of the method according to any one of claims 1 to 7 when the processor executes the computer program . 10. A computer-readable storage medium on which a computer program is stored, characterized in that, when the computer program is executed by a processor, the steps of the method according to any one of claims 1 to 7 are implemented.

Images