TWI880469B - Incremental drawing division method, device, equipment, medium and product - Google Patents

Abstract

The present invention discloses an incremental graph partitioning method, device, equipment, medium and product, which belongs to the field of data processing technology. The method includes: when a newly added data node is obtained, at least one subgraph with an associated edge with the newly added data node is determined; when at least one subgraph includes a first subgraph and a second subgraph, a target weight gain threshold is obtained, and the newly added data node has a first associated edge with the first subgraph and a second associated edge with the second subgraph; a weight increment is determined based on the weight values of the first associated edge and the second associated edge; when the weight increment is greater than the target weight gain threshold, the first subgraph and the second subgraph are aggregated to obtain a third subgraph, and the newly added data node is partitioned into the third subgraph. According to the embodiment of the present invention, the problem that the incremental graph division time is long and cannot meet the real-time requirements can be improved.

Description

Incremental mapping methods, devices, equipment, media and products

The present invention belongs to the field of data processing technology, and in particular relates to an incremental image segmentation method, device, equipment, medium and product.

With the development and application of Internet technology, in scenarios such as risk control mining and analysis and marketing recommendation analysis, stock data involving a large number of objects can be used to construct a stock graph. Through this stock graph, closely connected objects can be grouped into the same subgraph. Each subgraph is equivalent to a community, and associated edges can be established between different subgraphs. In this way, by calculating and analyzing the stock graph, it is possible to evaluate the risk value of different objects in the risk control mining and analysis scenario, and recommend corresponding marketing content to different objects in the marketing recommendation analysis scenario.

In related technologies, when the latest incremental data is obtained, it is usually necessary to perform graph calculation analysis through a global graph algorithm to complete the incremental graph division. However, the incremental graph division in related technologies requires a large amount of computation and takes a long time to complete, which cannot meet the real-time requirements.

The embodiments of the present invention provide an incremental image division method, device, equipment, medium and product, which can improve the problem that the incremental image division has a large amount of computation, a long division time and cannot meet the real-time requirements.

In the first aspect, an embodiment of the present invention provides an incremental graph segmentation method, the method comprising:

When a new data node is obtained, determine at least one subgraph among N subgraphs that has an edge associated with the new data node, wherein the N subgraphs are obtained by dividing the stock graph based on a community discovery algorithm;

In the case where at least one subgraph includes a first subgraph and a second subgraph, the target weight gain threshold of the first subgraph and the second subgraph is obtained, wherein a first association edge exists between the newly added data node and the first subgraph, and a second association edge exists between the newly added data node and the second subgraph;

Based on the weight values of the first associated edge and the second associated edge, determine the weight increment of the newly added data node;

When the weight increment is greater than the target weight gain threshold, determine that the first subgraph and the second subgraph meet the preset aggregation conditions, aggregate the first subgraph and the second subgraph to obtain the third subgraph, and divide the newly added data nodes into the third subgraph.

In the second aspect, an embodiment of the present invention provides an incremental image segmentation device, which includes:

A determination module is used to determine at least one subgraph among N subgraphs that has an edge associated with the newly added data node when a newly added data node is obtained, wherein the N subgraphs are obtained by dividing the stock graph based on a community discovery algorithm;

An acquisition module is used to acquire the target weight gain threshold of the first subgraph and the second subgraph when at least one subgraph includes the first subgraph and the second subgraph, wherein the newly added data node has a first associated edge with the first subgraph, and the newly added data node has a second associated edge with the second subgraph;

The determination module is also used to determine the weight increment of the newly added data node based on the weight values of the first associated edge and the second associated edge;

The partitioning module is used to determine that the first subgraph and the second subgraph meet the preset aggregation conditions when the weight increment is greater than the target weight gain threshold, aggregate the first subgraph and the second subgraph to obtain the third subgraph, and partition the newly added data nodes to the third subgraph.

In the third aspect, an embodiment of the present invention provides an electronic device, comprising: a processor and a memory storing computer program instructions; when the processor executes the computer program instructions, the steps of the incremental image segmentation method shown in the first aspect are implemented.

In a fourth aspect, an embodiment of the present invention provides a computer-readable storage medium, on which a program or instruction is stored, and when the program or instruction is executed by a processor, the steps of the incremental graph segmentation method shown in the first aspect are implemented.

In a fifth aspect, an embodiment of the present invention provides a computer program product, which is stored in a non-volatile storage medium. When the computer program product is executed by at least one processor, the steps of the incremental graph partitioning method shown in the first aspect are implemented.

In the sixth aspect, an embodiment of the present invention provides a chip, which includes a processor and a communication interface, the communication interface and the processor are coupled, and the processor is used to run programs or instructions to implement the steps of the incremental graph partitioning method of the first aspect.

The embodiment of the present invention provides an incremental graph partitioning method, device, equipment, medium and product. Based on the community discovery algorithm, the existing graph is pre-partitioned to obtain N subgraphs. When a new data node is obtained, at least one subgraph in the N subgraphs that has an associated edge with the new data node is determined. If at least one subgraph includes a first subgraph and a second subgraph, it means that the new data node has an associated relationship with community nodes in more than one community. Based on this, the present invention obtains the target weight gain threshold of the first subgraph and the second subgraph, and determines the weight increment of the new data node based on the weight value of the associated edge between the new data node and the two subgraphs. If the weight increment is greater than the target weight gain threshold, it can be explained that after adding new data nodes between the first subgraph and the second subgraph, the weight increment can increase the modularity gain between the first subgraph and the second subgraph, thereby making the first subgraph and the second subgraph meet the preset aggregation conditions. In this way, by aggregating the first subgraph and the second subgraph, the third subgraph affected by the newly added data node can be obtained. By traversing each newly added data node, all subgraphs that meet the preset aggregation conditions in the N subgraphs can be fused in pairs, realizing the re-division of the graph structure of the original stock graph. The entire division process does not require a large amount of calculation, and only requires offline calculation of the target weight gain threshold in advance. In the scenario where the newly added data node is obtained, the incremental graph can be divided in real time to meet the real-time requirements.

110,120,130,140,410,420,430,510,520,530,540,550: Steps

1100: Incremental drawing device

1110: Confirm module

1120: Get module

1130: Divide module

1200: Electronic equipment

1201: Memory

1202: Processor

1203: Communication interface

1204: Bus

A1: Add a new data node

Gi,Gj,Gk,G1,G2,G3,G4,G5: subgraph

I1,J1,A: Node (trading account)

I2,K1: Node

Z: Add a new node

In order to more clearly explain the technical solution of the embodiment of the present invention, the following will briefly introduce the diagrams required for use in the embodiment of the present invention. For ordinary technicians in this field, other diagrams can be obtained based on these diagrams without making any progressive labor.

Figure 1 is a flow chart of an embodiment of the incremental graph segmentation method provided in the first aspect of the present invention;

Figure 2 is a schematic diagram of an example of a stock map provided in the first aspect of the present invention;

Figure 3 is a schematic diagram of an example of the incremental image segmentation effect provided by the first aspect of the present invention;

Figure 4 is a flow chart of another embodiment of the incremental graph segmentation method provided in the first aspect of the present invention;

Figure 5 is a flow chart of another embodiment of the incremental graph segmentation method provided in the first aspect of the present invention;

Figure 6 is a schematic diagram of another example of the inventory map provided in the first aspect of the present invention;

Figure 7 is a schematic diagram of another example of the inventory map provided in the first aspect of the present invention;

Figure 8 is a schematic diagram of another example of the incremental image segmentation effect provided by the first aspect of the present invention;

Figure 9 is a schematic diagram of another example of the incremental image segmentation effect provided by the first aspect of the present invention;

Figure 10 is a schematic diagram of another example of the incremental image segmentation effect provided by the first aspect of the present invention;

Figure 11 is a schematic structural diagram of an embodiment of the incremental image segmentation device provided in the second aspect of the present invention;

Figure 12 is a schematic structural diagram of an embodiment of the electronic device provided in the third aspect of the present invention.

The features and exemplary embodiments of various aspects of the present invention will be described in detail below. In order to make the purpose, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below in combination with drawings and specific embodiments. It should be understood that the specific embodiments described here are only intended to explain the present invention, not to limit the present invention. For those skilled in the art, the present invention can be implemented without some of these specific details. The following description of the embodiments is only to provide a better understanding of the present invention by showing examples of the present invention.

With the development and application of Internet technology, in scenarios such as risk control mining and analysis and marketing recommendation analysis, stock data involving a large number of objects can be used to construct a stock graph. Through this stock graph, closely connected objects can be grouped into the same subgraph. Each subgraph is equivalent to a community, and associated edges can be established between different subgraphs. In this way, by calculating and analyzing the stock graph, it is possible to evaluate the risk value of different objects in the risk control mining and analysis scenario, and recommend corresponding marketing content to different objects in the marketing recommendation analysis scenario. When the latest incremental data is obtained, it is usually necessary to perform graph calculation analysis through a global graph algorithm to complete the incremental graph segmentation. However, the incremental graph segmentation in related technologies requires a large amount of computation and takes a long time to complete, which cannot meet the real-time requirements.

Based on the above-mentioned problems, the embodiments of the present invention provide an incremental graph partitioning method, device, equipment, medium and product, which can obtain the first subgraph and the second subgraph with associated edges with the newly added data node, as well as the target weight gain threshold of the first subgraph and the second subgraph, and determine the weight increment of the newly added data node based on the weight value of the associated edge between the newly added data node and the two subgraphs. If the weight increment is greater than the target weight gain threshold, it can be explained that after adding the newly added data node between the first subgraph and the second subgraph, the weight increment can improve the modularity gain between the first subgraph and the second subgraph, thereby making the first subgraph and the second subgraph meet the preset aggregation conditions. In this way, by aggregating the first subgraph and the second subgraph, the third subgraph affected by the newly added data node can be obtained. By traversing each newly added data node, all subgraphs that meet the preset aggregation conditions in the N subgraphs can be fused in pairs, realizing the re-division of the graph structure of the original stock graph. The entire division process does not require a large amount of calculation, and only requires the pre-offline calculation of the target weight gain threshold. In the scenario where the newly added data node is obtained, the incremental graph can be divided in real time to meet the real-time requirements.

The incremental graph segmentation method in the embodiment of the present invention can be applied to risk control mining and analysis scenarios, marketing content recommendation scenarios, etc. The incremental graph segmentation method provided by the embodiment of the present invention is described in detail below with reference to the diagram through a specific embodiment.

The first aspect of the present invention provides an incremental image segmentation method that can be applied to electronic devices, that is, the incremental image segmentation method can be executed by electronic devices. It should be noted that the above-mentioned execution subject does not constitute a limitation of the present invention.

For example, the electronic device can be a server for a trading platform, a regulatory platform, a financial terminal, or a content recommendation platform.

FIG1 is a flow chart of an embodiment of the incremental image segmentation method provided by the first aspect of the present invention. As shown in FIG1, the incremental image segmentation method may include steps 110 to 140.

Step 110, when a new data node is obtained, determine at least one subgraph among the N subgraphs that has an edge associated with the new data node.

Among them, N subgraphs are obtained by dividing the stock graph based on the community discovery algorithm.

Step 120, when at least one subgraph includes a first subgraph and a second subgraph, obtain the target weight gain threshold of the first subgraph and the second subgraph.

Among them, there is a first associated edge between the newly added data node and the first subgraph, and there is a second associated edge between the newly added data node and the second subgraph.

Step 130, based on the weight values of the first associated edge and the second associated edge, determine the weight increment of the newly added data node.

Step 140, when the weight increment is greater than the target weight gain threshold, determine that the first subgraph and the second subgraph meet the preset aggregation condition, aggregate the first subgraph and the second subgraph to obtain a third subgraph, and divide the newly added data nodes into the third subgraph.

The incremental graph partitioning method provided by the embodiment of the present invention pre-partitions the stock graph based on the community discovery algorithm to obtain N subgraphs. When a new data node is obtained, at least one subgraph in the N subgraphs that has an associated edge with the new data node is determined. If at least one subgraph includes a first subgraph and a second subgraph, it means that the new data node has an associated relationship with community nodes in more than one community. Based on this, the present invention obtains the target weight gain threshold of the first subgraph and the second subgraph, and determines the weight increment of the new data node based on the weight value of the associated edge between the new data node and the two subgraphs. If the weight increment is greater than the target weight gain threshold, it can be explained that after adding new data nodes between the first subgraph and the second subgraph, the weight increment can improve the correlation between the first subgraph and the second subgraph, thereby making the first subgraph and the second subgraph meet the preset aggregation conditions. In this way, by aggregating the first subgraph and the second subgraph, the third subgraph affected by the newly added data node can be obtained. By traversing each newly added data node, all subgraphs that meet the preset aggregation conditions in the N subgraphs can be fused in pairs, realizing the re-division of the graph structure of the original stock graph. The entire division process does not require a large amount of calculation, and only requires offline calculation of the target weight gain threshold in advance. In the scenario where the newly added data node is obtained, the incremental graph can be divided in real time to meet the real-time requirements.

The specific implementation of the above steps is described in detail below in conjunction with an example, as shown below.

Involving step 110, when a new data node is obtained, at least one subgraph among the N subgraphs having an edge associated with the new data node is determined.

Before step 110, the electronic device can pre-establish a stock graph based on the stock data of multiple objects, and divide the stock graph based on the community discovery algorithm to obtain N sub-graphs, where N is a positive integer.

Each object has a corresponding unique node in the N subgraphs. Each subgraph can include multiple nodes. There can be an associated edge between two nodes. Specifically, there can be an associated edge between two nodes in the same subgraph, and there can also be an associated edge between two nodes in different subgraphs. Each associated edge corresponds to a unique weight, which can be determined based on stock data and can be used to characterize the degree of association between two nodes.

For example, as shown in Figure 2, N subgraphs may include Gi, Gj, Gk, etc., and each of the subgraphs Gi, Gj, and Gk includes 4 nodes. Among them, there is an associated edge between node I1 in Gi and node J1 in Gj, there is an associated edge between node I2 in Gi and node K1 in Gk, and node I2 may also have an associated edge with any other node in any subgraph.

In some embodiments of the present invention, step 110 may specifically include the following steps: when the incremental data of the first object is obtained, determining the first object as a newly added data node; based on the incremental data, determining at least one second object having a preset behavior relationship with the first object; establishing an associated edge between the node corresponding to the second object and the newly added data node, and defining the weight value of each associated edge based on the transaction data; determining that at least one subgraph includes at least one subgraph where the second object is located.

Specifically, each subgraph may include multiple nodes, each node has a corresponding object, and the electronic device determines that the first object is a newly added data node only when the N subgraphs do not include the node corresponding to the first object. The above-mentioned default behavior relationship can be, for example, a transaction relationship, a social relationship, etc. that can reflect the association between different objects.

For example, in the risk control mining and analysis scenario, the transaction data is the incremental data. When the transaction data of trading account A is obtained, if there is no corresponding node of trading account A in the N subgraphs, the corresponding node A of trading account A can be added in the N subgraphs, and based on the data content in the transaction data, a new association edge is established for the node A. For example, in the transaction data of trading account A, including the transfer of 100 yuan from trading account A to trading account I1 and the transfer of 50 yuan from trading account A to trading account J1, it can be determined that trading account I1 and trading account J1 have a transaction relationship with trading account A, so as shown in Figure 3, association edges can be established between node A and node I1 and node J1, respectively, so that it can be determined that at least one subgraph with an association edge with node A includes Gi and Gj. In addition, the weight value of the link between node A and node I1 can be defined based on the transaction amount of 100 yuan, and the weight value of the link between node A and node J1 can be defined based on the transaction amount of 50 yuan.

Involving step 120, when at least one subgraph includes a first subgraph and a second subgraph, obtaining the target weight gain threshold of the first subgraph and the second subgraph.

It should be noted that in the present invention, there is an associated edge between the first subgraph and the second subgraph, that is, there is an associated edge between a node in the first subgraph and a node in the second subgraph. The target weight gain threshold is pre-calculated based on the community discovery Louvain algorithm. Any two subgraphs with associated edges in the N subgraphs can be pre-calculated to obtain a target weight gain threshold.

In some embodiments of the present invention, in order to accurately calculate the target weight gain threshold of the first subgraph and the second subgraph, the first subgraph has an associated edge with M1 subgraphs, the second subgraph has an associated edge with M2 subgraphs, the M1 subgraphs include the second subgraph, and the M2 subgraphs include the first subgraph. In some embodiments of the present invention, FIG4 is a flow chart of another embodiment of the incremental graph partitioning method provided by the first aspect of the present invention. Before step 120, the method may also include steps 410 to 430 as shown in FIG4.

Step 410, obtain the weights of the associated edges between the first subgraph and M1 subgraphs, and obtain M1 third weights.

Among them, the first subgraph and each of the M1 subgraphs can calculate a third weight.

In some examples, if there are multiple associated edges between the first subgraph Gi and the subgraph Gk, the third weight is the weight and value of the multiple associated edges.

Step 420, obtain the weights of the associated edges between the second subgraph and M2 subgraphs, and obtain M2 fourth weights.

Among them, M1 and M2 are both positive integers.

Step 430, based on M1 third weights, M2 fourth weights, and the fifth weight, calculate the target weight gain thresholds of the first sub-graph and the second sub-graph.

Among them, the fifth weight is the weight of the connection edge between the first subgraph and the second subgraph.

In some embodiments of the present invention, FIG. 5 is a flow chart of another embodiment of the incremental graph segmentation method provided in the first aspect of the present invention, and step 430 may specifically include: steps 510 to 550 shown in FIG. 5.

Step 510, add M1 third weights to obtain the first parameter, and add M2 fourth weights to obtain the second parameter.

Step 520, add the first parameter and the second parameter to obtain the sixth weight.

Step 530, obtain the weights and values of the associated edges between N-2 subgraphs to obtain the seventh weight.

Among them, the seventh weight is used to represent the weights and values of the associated edges between the remaining N-2 subgraphs except the first and second subgraphs in the N subgraphs.

For example, as shown in Figure 6, N is 4, the first subgraph is G1, and the second subgraph is G2, then the seventh weight is the weight value of the associated edge between subgraph G3 and subgraph G4.

Step 540, calculating the difference between the first product and the second product to obtain the second difference, wherein the first product is the product of the first parameter and the second parameter, and the second product is the product of the fifth weight and the sixth weight.

Step 550, calculate the ratio of the second difference to the seventh weight to obtain the target weight gain threshold.

Among them, the target weight gain threshold is the re-threshold corresponding to the first subgraph and the second subgraph. If the weight increment of the newly added data node is greater than the target weight gain threshold, it means that after adding the newly added data node between the first subgraph and the second subgraph, the modularity gain between the first subgraph and the second subgraph can be increased, and the increased modularity gain is greater than zero.

In some embodiments, the present invention may specifically use formula (1) to calculate the target weight gain threshold:

為第一參數，

為第二參數，V _ij-out 為第五權重，ΣV _ij-out 為第六權重，

為第七權重，△V _ij-out | _threshold 為目標權重增益閾值。 Among them, the first subgraph is Gi, the second subgraph is Gj,

is the first parameter,

is the second parameter, V _ij-out is the fifth weight, Σ V _ij-out is the sixth weight,

is the seventh weight, △ V _ij-out | _threshold is the target weight gain threshold.

In some embodiments of the present invention, before step 110, the method may further include: calculating the modularity gain of the first subgraph and the second subgraph based on M1 third weights, M2 fourth weights, the fifth weight and the community discovery algorithm.

Specifically, add M1 third weights to obtain the first parameter, add M2 fourth weights to obtain the second parameter; add the first parameter and the second parameter to obtain the sixth weight; calculate the ratio of the first product and the sixth weight to obtain the first ratio; subtract the fifth weight from the first ratio to obtain the modularity gain.

The present invention may specifically use formula (2) to calculate the modularity _gain Qij of the first sub-graph Gi and the second sub-graph Gk:

In the embodiment of the present invention, since the current stock graphs have been sub-divided by Louvain algorithm, the modularity gain between any two sub-graphs with associated edges is less than or equal to 0. Therefore, for any two sub-graphs with associated edges in the current stock graph, their corresponding target weight gain thresholds can be calculated based on the weight values of the associated edges between them and other sub-graphs. The target weight gain threshold is the graph structure re-division threshold. That is, through the target weight gain threshold, the modularity gain between the first subgraph and the second subgraph affected by the newly added data node can be quickly determined. Since two subgraphs with modularity gain greater than zero can be fused, after determining that the updated modularity gain is greater than zero, the first subgraph and the second subgraph can be directly fused to achieve real-time update of the incremental graph structure.

Involving step 130, based on the weight values of the first associated edge and the second associated edge, determining the weight increment of the newly added data node.

Among them, the weight value corresponding to the first associated edge is the first weight, the weight value corresponding to the second associated edge is the second weight, and the weight increment is used to characterize the influence of the newly added data node.

In some embodiments of the present invention, step 130 may specifically include the following steps: adding the first weight and the second weight to obtain a first sum; calculating the ratio of the first sum to a preset normalized variable to obtain a weight increment.

Specifically, the present invention can calculate the weight increment △ V _new according to formula (3).

△ V _new =( V _new-i + V _new-j )/ V (3)

Among them, V _new-i is the first weight, V _new-j is the second weight, and V is a default normalized variable, which can be set according to specific needs, and the present invention does not make specific limitations on this.

For example, referring to Figure 3, the connection edge between node A and node I1 is the first connection edge, and the connection edge between node A and node J1 is the second connection edge. If the default normalization variable is 2, the first weight is 10, and the second weight is 5, the weight increment is 7.5.

In some embodiments of the present invention, the method may further include: when the weight increment is not greater than the target weight gain, comparing the first weight and the second weight; if the first weight is greater than the second weight, dividing the newly added data node into the first subgraph; if the second weight is greater than the first weight, dividing the newly added data node into the second subgraph.

For example, the association edge between node A and node I1 is the first association edge, the association edge between node A and node J1 is the second association edge, the first weight is 10, the second weight is 5, and the weight increment is 7.5. If the target weight gain is 8, the first weight and the second weight need to be compared. Since the first weight is larger, the newly added data node A is directly divided into the first subgraph Gi shown in Figure 3.

In the embodiment of the present invention, if the weight increment is not greater than the target weight gain, it means that after being affected by the newly added data node, the modularity gain between the first subgraph and the second subgraph is still less than zero. At this time, there is no need to aggregate the first subgraph and the second subgraph, but directly divide the newly added data point into the subgraph that is most affected by it. The subgraph that is most affected by it is the subgraph with the largest weight of the associated edge with the newly added data point. In this way, the newly added data node can be quickly divided, and the division is accurate, and the newly added data node can be divided into the subgraph with the highest degree of correlation with it.

Involving step 140, when the weight increment is greater than the target weight gain threshold, determining that the first subgraph and the second subgraph meet the preset aggregation condition, aggregating the first subgraph and the second subgraph to obtain a third subgraph, and assigning the newly added data nodes to the third subgraph.

In some embodiments of the present invention, the method may further include the following steps: when at least one subgraph includes a first subgraph and a second subgraph, obtaining the modularity gain of the first subgraph and the second subgraph; updating the modularity gain based on the weight values of the first associated edge and the second associated edge and the community discovery algorithm to obtain an updated modularity gain.

Specifically, the subgraph association between the first subgraph and the second subgraph is positively correlated with the modularity gain. After adding a new data node between the first subgraph and the second subgraph, the fifth weight between the first subgraph and the second subgraph can be updated based on the weight values of the first associated edge and the second associated edge. Then, based on the updated fifth weight, the updated modularity gain is calculated using formula (2).

In the above embodiment, step 140 may specifically include the following steps: when the weight increment is greater than the target weight gain threshold, determining that the updated modularity gain is greater than zero; when the updated modularity gain is greater than zero, determining that the first subgraph and the second subgraph meet the preset aggregation condition.

In some embodiments, the derivation process of formula (1) is as follows:

，更新 後的第二參數

，更新後的第六權重ΣV _ij-out ^' =ΣV _ij-out +△V _ij-out ； When the weight value between the first subgraph and the second subgraph increases by △ V _ij-out , the updated fifth weight V _ij-out ^' = V _ij-out +△ V _ij-out , and the updated first parameter

, the updated second parameter

, the updated sixth weight Σ V _ij-out ^' =Σ V _ij-out +△ V _ij-out ;

Therefore, after substituting the above parameters into formula (2), the updated modular gain can be obtained:

From this we can get:

Further simplification yields:

Therefore, the critical value of △ V _ij-out , that is, the target weight gain threshold:

In the embodiment of the present invention, it can be known from the derivation process of the above formula (1) that if the weight increment is greater than the target weight gain threshold, it can be determined that the updated modularity gain is greater than zero. Based on this, the present invention adds a new data node and an associated edge between the first subgraph and the second subgraph on the basis of the current stock graph. If the weight increment of the new data node is greater than the target weight gain threshold, it can be directly determined that the updated modularity gain of the first subgraph and the second subgraph is greater than zero without other forms of calculation. The first subgraph and the second subgraph can be directly aggregated to realize the subgraph division of the current graph structure. It has strong interpretability, small calculation amount, high division efficiency, and can meet the real-time requirements of incremental graph division.

As a specific example, the incremental graph partitioning method of the present invention can be applied to the incremental graph partitioning scenario of an abnormal transfer association network. FIG6 is a stock graph of an abnormal transfer association network, which includes four subgraphs obtained based on the Louvain algorithm, namely G1, G2, G3 and G4. Each subgraph can include at least one node, and the nodes are connected by association edges. Each association edge can correspond to a weight value, which can be determined based on the transfer data between the two users corresponding to the two nodes. The transfer data can include, for example, the transfer frequency, the transfer amount, etc.

If the weight value of each associated edge in Figure 6 is 1, as shown in Figure 7, the weight of the associated edge between subgraph G1 and subgraph G2 is 1, the weight of the associated edge between subgraph G1 and subgraph G3 is 3, the weight of the associated edge between subgraph G1 and subgraph G4 is 1, and the weight of the associated edge between subgraph G2 and subgraph G4 is 3. If subgraph G1 is the first subgraph and subgraph G2 is the second subgraph, then substitute the fifth weight 1, the sixth weight 10, the first parameter 6 and the second parameter 4 into formula (2), and the modularity gain of subgraph G1 and subgraph G2 can be calculated to be 1-6*4/10=-1.4<0.

>0，則將第一參數6、第二參數4、第五權重1、第六權重10、第七權重1代入公式(1)，計算得到子圖G1與子圖G2的目標權重增益閾值△V _ij-out | _threshold =(4*6-1*10)/1=14。 When the weight of the link between subgraph G1 and subgraph G2 increases by △ V _ij-out , in order to make the updated modularity gain (1+△ V _ij-out )-

>0, then substitute the first parameter 6, the second parameter 4, the fifth weight 1, the sixth weight 10, and the seventh weight 1 into formula (1) to calculate the target weight gain threshold △ V _ij-out | _threshold =(4*6-1*10)/1=14 for subgraph G1 and subgraph G2.

As shown in Figure 8, the first weight between the newly added node Z and subgraph G1 is 4+4, and the second weight between the newly added node Z and subgraph G2 is 4+4. If the default normalization variable is 1, the weight increment of the newly added node Z is 16. The weight increment 16 is greater than the target weight gain threshold of 14, which means that after being affected by the newly added node Z, the updated modularity gain between subgraph G1 and subgraph G2 is greater than zero. Based on this, subgraph G1 and subgraph G2 can be merged to obtain subgraph G5, and the newly added node Z can be assigned to subgraph G5.

In some embodiments of the present invention, the method may further include: when there is an associated edge between the newly added data node and the single subgraph, the newly added data node is divided into the single subgraph.

Specifically, the existence of an associated edge between the newly added data node and a single subgraph may include: the existence of a single associated edge between the newly added data node and a single subgraph, that is, the newly added data node is a single associated edge in the existing graph; or, the existence of at least two associated edges between the newly added data node and a single subgraph, that is, the newly added data node is multiple associated edges in the existing graph.

In an example, as shown in Figure 9, the newly added data node A1 has only one associated edge with the subgraph Gi, so the newly added data node A1 can be divided into the subgraph Gi.

In another example, as shown in Figure 10, if there are two associated edges between the newly added data node A1 and the subgraph Gi, the newly added data node A1 can be divided into the subgraph Gi.

In the embodiment of the present invention, by determining that the newly added data node has only an associated edge with a single subgraph, the newly added data node can be directly divided into a single subgraph without calculation, and the newly added data node can be divided in real time.

The embodiment of the present invention can take into account the incremental graph division in a variety of scenarios, such as evaluating the risk value for different objects in the risk control mining analysis scenario, and recommending corresponding marketing content for different objects in the marketing recommendation analysis scenario. It has strong adaptability and a wide range of applications.

Based on the same inventive concept, the second aspect of the present invention provides an incremental image segmentation device. Figure 11 is a structural schematic diagram of an embodiment of the incremental image segmentation device provided by the second aspect of the present invention.

As shown in FIG11 , the incremental image dividing device 1100 may specifically include: a determination module 1110, an acquisition module 1120, and a dividing module 1130.

The determination module is used to determine at least one subgraph among N subgraphs that has an edge associated with the newly added data node when a newly added data node is obtained, wherein the N subgraphs are obtained by dividing the stock graph based on the community discovery algorithm;

The acquisition module 1120 is used to acquire the target weight gain threshold of the first subgraph and the second subgraph when at least one subgraph includes a first subgraph and a second subgraph, wherein the newly added data node has a first associated edge with the first subgraph, and the newly added data node has a second associated edge with the second subgraph;

Determination module 1110 is also used to determine the weight increment of the newly added data node based on the weight values of the first associated edge and the second associated edge;

The partitioning module 1130 is used to determine that the first subgraph and the second subgraph meet the preset aggregation condition when the weight increment is greater than the target weight gain threshold, aggregate the first subgraph and the second subgraph to obtain the third subgraph, and partition the newly added data node to the third subgraph.

The incremental graph partitioning device provided by the embodiment of the present invention pre-partitions the stock graph into N subgraphs based on the community discovery algorithm. When a new data node is obtained, at least one subgraph in the N subgraphs that has an associated edge with the new data node is determined. If at least one subgraph includes a first subgraph and a second subgraph, it means that the new data node has an associated relationship with community nodes in more than one community. Based on this, the present invention obtains the target weight gain threshold of the first subgraph and the second subgraph, and determines the weight increment of the new data node based on the weight value of the associated edge between the new data node and the two subgraphs. If the weight increment is greater than the target weight gain threshold, it can be explained that after adding new data nodes between the first subgraph and the second subgraph, the weight increment can increase the modularity gain between the first subgraph and the second subgraph, thereby making the first subgraph and the second subgraph meet the preset aggregation conditions. In this way, by aggregating the first subgraph and the second subgraph, the third subgraph affected by the newly added data node can be obtained. By traversing each newly added data node, all subgraphs that meet the preset aggregation conditions in the N subgraphs can be fused in pairs, realizing the re-division of the graph structure of the original stock graph. The entire division process does not require a large amount of calculation, and only requires offline calculation of the target weight gain threshold in advance. In the scenario where the newly added data node is obtained, the incremental graph can be divided in real time to meet the real-time requirements.

In some embodiments of the present invention, the device further includes: an acquisition module 1120, which is used to obtain the modularity gain of the first subgraph and the second subgraph when at least one subgraph includes the first subgraph and the second subgraph; an update module, which is used to update the modularity gain based on the weight values of the first associated edge and the second associated edge and the community discovery algorithm to obtain the updated modularity gain.

In some embodiments of the present invention, the partitioning module 1130 is specifically used to: when the weight increment is greater than the target weight gain threshold, determine that the updated modularity gain is greater than zero; when the updated modularity gain is greater than zero, determine that the first subgraph and the second subgraph meet the preset aggregation condition.

In some embodiments of the present invention, the first association edge corresponds to the first weight, the second association edge corresponds to the second weight, and the determination module 1110 is specifically used to: add the first weight and the second weight to obtain a first sum; calculate the ratio of the first sum to a preset normalized variable to obtain a weight increment.

In some embodiments of the present invention, the device further includes: a comparison module for comparing the first weight and the second weight when the weight increment is not greater than the target weight gain; a division module 1130 for dividing the newly added data node into the first subgraph if the first weight is greater than the second weight; and a division module 1130 for dividing the newly added data node into the second subgraph if the second weight is greater than the first weight.

In some embodiments of the present invention, there is an associated edge between the first subgraph and M1 subgraphs, there is an associated edge between the second subgraph and M2 subgraphs, the M1 subgraphs include the second subgraph, and the M2 subgraphs include the first subgraph. The device further includes: an acquisition module 1120, which is used to obtain the weight of the associated edge between the first subgraph and the M1 subgraphs before obtaining the target weight gain threshold of the first subgraph and the second subgraph, and obtain M1 third weights; the acquisition module 1120 is used to obtain the weight of the associated edge between the second subgraph and the M2 subgraphs, and obtain M2 fourth weights; a calculation module is used to calculate the target weight gain threshold of the first subgraph and the second subgraph based on the M1 third weights, the M2 fourth weights, and the fifth weight; wherein the fifth weight is the weight of the associated edge between the first subgraph and the second subgraph.

In some embodiments of the present invention, the calculation module is specifically used to: add M1 third weights to obtain a first parameter, add M2 fourth weights to obtain a second parameter; add the first parameter and the second parameter to obtain a sixth weight; obtain the weight sum of the associated edges between N-2 subgraphs to obtain a seventh weight, wherein the N-2 subgraphs include subgraphs other than the first subgraph and the second subgraph in the N subgraphs; calculate the difference between the first product and the second product to obtain a second difference, wherein the first product is the product of the first parameter and the second parameter, and the second product is the product of the fifth weight and the sixth weight; calculate the ratio of the second difference to the seventh weight to obtain a target weight gain threshold.

In some embodiments of the present invention, each subgraph includes multiple nodes, and the determination module 1110 includes:

The determination unit is used to determine that the first object is a newly added data node when the incremental data of the first object is obtained; the determination unit is also used to determine at least one second object that has a preset behavior relationship with the first object based on the incremental data; the establishment unit is used to establish an association edge between the node corresponding to the second object and the newly added data node, and define the weight value of each association edge based on the transaction data; the determination unit is also used to determine that at least one subgraph includes the subgraph where at least one second object is located.

In some embodiments of the present invention, the partitioning module 1130 is also used to: when there is an associated edge between the newly added data node and a single subgraph, the newly added data node is partitioned into a single subgraph.

The third aspect of the present invention also provides an electronic device. FIG12 is a schematic structural diagram of an embodiment of the electronic device provided in the third aspect of the present invention. As shown in FIG12, the electronic device 1200 includes a memory 1201, a processor 1202, and a computer program stored in the memory 1201 and executable on the processor 1202.

In one example, the processor 1202 may include a central processing unit (CPU), or an application specific integrated circuit (ASIC), or may be configured to implement one or more integrated circuits of the embodiments of the present invention.

The memory 1201 may include a read-only memory (ROM), a random access memory (RAM), a magnetic disk storage medium device, an optical storage medium device, a flash memory device, an electrical, optical or other physical/tangible memory storage device. Therefore, typically, the memory includes one or more tangible (non-transitory) computer-readable storage media (e.g., a memory device) encoded with software including computer-executable instructions, and when the software is executed (e.g., by one or more processors), it is operable to perform the operations described with reference to the incremental graph partitioning method in the embodiment according to the first aspect of the present invention.

The processor 1202 runs the computer program corresponding to the executable program code by reading the executable program code stored in the memory 1201, so as to implement the incremental image segmentation method in the embodiment of the first aspect mentioned above.

In some examples, the electronic device 1200 may also include a communication interface 1203 and a bus 1204. As shown in FIG. 12 , the memory 1201, the processor 1202, and the communication interface 1203 are connected through the bus 1204 and communicate with each other.

The communication interface 1203 is mainly used to realize the communication between the modules, devices, units and/or equipment in the embodiment of the present invention. The input device and/or output device can also be connected through the communication interface 1203.

The bus 1204 includes hardware, software, or both, coupling the components of the electronic device 1200 to each other. By way of example and not limitation, bus 1204 may include an Accelerated Graphics Port (AGP) or other graphics bus, an Enhanced Industry Standard Architecture (EISA) bus, a Front Side Bus (FSB), a Hyper Transport (HT) interconnect, an Industry Standard Architecture (ISA) bus, an InfiniBand interconnect, a Low Pin Count (LPC) bus, a memory bus, a Micro Channel Architecture (MCA) bus, a Peripheral Component Interconnect (PCI) bus, a Peripheral Component Interconnect Express (PCI) bus, or a 10-bit x86 bus. Express, PCI-Express) bus, Serial Advanced Technology Attachment (SATA) bus, Video Electronics Standards Association Local Bus (VLB) bus or other suitable bus or a combination of two or more of the above. Where appropriate, bus 1204 may include one or more buses. Although the embodiments of the present invention describe and illustrate specific buses, the present invention contemplates any suitable bus or interconnect.

The fourth aspect of the present invention provides a computer-readable storage medium, which stores a program or instruction. When the program or instruction is executed by the processor, the incremental image segmentation method shown in the first aspect can be implemented, and the same technical effect can be achieved. To avoid repetition, it will not be repeated here. Among them, the above-mentioned computer-readable storage medium may include a non-transient computer-readable storage medium, such as a read-only memory (ROM), a random access memory (RAM), a disk or an optical disk, etc., which is not limited here.

The fifth aspect of the present invention provides a computer program product, which is stored in a non-volatile storage medium. When the computer program product is executed by at least one processor, the steps of the incremental image division method shown in the first aspect are implemented. The specific content of the incremental image division method can be found in the relevant description in the above embodiment, and will not be repeated here.

The sixth aspect of the present invention provides a chip, which includes a processor and a communication interface, the communication interface and the processor are coupled, and the processor is used to run programs or instructions to implement the various processes of the implementation example of the incremental graph partitioning method shown in the first aspect, and can achieve the same technical effect. To avoid repetition, it will not be repeated here.

It should be understood that the chip mentioned in the embodiments of the present invention can also be called a system-level chip, a system chip, a chip system or a system-on-chip chip, etc.

It should be made clear that each embodiment in this specification is described in a progressive manner, and the same or similar parts between the embodiments can be referred to each other, and each embodiment focuses on the differences from other embodiments. For the device embodiment, user terminal embodiment, equipment embodiment, system embodiment and computer-readable storage medium embodiment, the relevant parts can refer to the description part of the method embodiment. The present invention is not limited to the specific steps and structures described above and shown in the figure. After understanding the spirit of the present invention, technicians in this field can make various changes, modifications and additions, or change the order between the steps. In addition, for the sake of brevity, the detailed description of the known method technology is omitted here.

Aspects of the present invention are described above with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable incremental diagramming device to produce a machine such that execution of the instructions via the processor of the computer or other programmable incremental diagramming device enables performance of the functions/acts specified in one or more blocks of the flowchart and/or block diagrams. Such a processor may be, but is not limited to, a general-purpose processor, a special-purpose processor, a special application processor, or a field-programmable logic circuit. It is also understood that each box in the block diagram and/or flowchart and the combination of boxes in the block diagram and/or flowchart can also be implemented by dedicated hardware that performs the specified function or action, or can be implemented by a combination of dedicated hardware and computer instructions.

Those skilled in the art should understand that the above embodiments are exemplary rather than restrictive. Different technical features appearing in different embodiments can be combined to achieve beneficial effects. Based on studying the drawings, instructions and the scope of the patent application, those skilled in the art should be able to understand and implement other variations of the disclosed embodiments. In the scope of the patent application, the term "including" does not exclude other devices or steps; the quantifier "one" does not exclude multiple; the terms "first" and "second" are used to identify names rather than to indicate any specific order. Any diagrammatic mark in the claim should not be understood as a limitation on the scope of protection. The functions of multiple parts appearing in the claim can be implemented by a single hardware or software module. The fact that certain technical features appear in different dependent claim items does not mean that these technical features cannot be combined to achieve beneficial results.

110,120,130,140: Steps

Claims (11)

A method for incremental graph partitioning is applied to an electronic device, wherein the method comprises: when the electronic device obtains a newly added data node, determining at least one subgraph in N subgraphs that has an associated edge with the newly added data node, wherein the N subgraphs are obtained by partitioning an existing graph based on a community discovery algorithm; when the at least one subgraph includes a first subgraph and a second subgraph, the electronic device obtains a target weight gain threshold of the first subgraph and the second subgraph, wherein the newly added data node has a first associated edge with the first subgraph, and the newly added data node has a first associated edge with the second subgraph. The electronic device determines a weight increment of the newly added data node based on the weight values of the first and second associated edges; when the weight increment is greater than the target weight gain threshold, the electronic device determines that the first subgraph and the second subgraph meet a preset aggregation condition, aggregates the first subgraph and the second subgraph to obtain a third subgraph, and divides the newly added data node into the third subgraph; wherein, the first subgraph has an associated edge with M1 subgraphs, the second subgraph has an associated edge with M2 subgraphs, the M1 subgraphs include the second subgraph, and the The first subgraph is included in the M2 subgraphs. Before obtaining the target weight gain thresholds of the first subgraph and the second subgraph, the method further includes: the electronic device obtains the weights of the associated edges between the first subgraph and the M1 subgraphs to obtain M1 third weights; the electronic device obtains the weights of the associated edges between the second subgraph and the M2 subgraphs to obtain M2 fourth weights; the electronic device adds the M1 third weights to obtain a first parameter, and adds the M2 fourth weights to obtain a second parameter; the electronic device adds the first parameter to the second parameter to obtain a sixth weight; the electronic device obtains N-2 The electronic device calculates the weight and value of the associated edge between the N-2 subgraphs to obtain the seventh weight, wherein the N-2 subgraphs include the subgraphs other than the first subgraph and the second subgraph in the N subgraphs; the electronic device calculates the difference between the first product and the second product to obtain the second difference, wherein the first product is the product of the first parameter and the second parameter, and the second product is the product of the fifth weight and the sixth weight; the electronic device calculates the ratio of the second difference to the seventh weight to obtain the target weight gain threshold; wherein the fifth weight is the weight of the associated edge between the first subgraph and the second subgraph. The method as claimed in claim 1, wherein the method further comprises: the electronic device obtains the modularity gain of the first subgraph and the second subgraph when the at least one subgraph includes the first subgraph and the second subgraph; the electronic device updates the modularity gain based on the weight values of the first associated edge and the second associated edge and the community discovery algorithm to obtain the updated modularity gain. As described in claim 2, the electronic device determines that the correlation between the first subgraph and the second subgraph satisfies a preset aggregation condition when the weight increment is greater than the target weight gain threshold, including: the electronic device determines that the updated modularity gain is greater than zero when the weight increment is greater than the target weight gain threshold; the electronic device determines that the first subgraph and the second subgraph satisfy the preset aggregation condition when the updated modularity gain is greater than zero. The method of claim 1, wherein the first associated edge corresponds to a first weight, the second associated edge corresponds to a second weight, and the electronic device determines the weight increment of the newly added data node based on the weight values of the first associated edge and the second associated edge, comprising: the electronic device adds the first weight and the second weight to obtain a first sum value; the electronic device calculates the ratio of the first sum value to a preset normalization variable to obtain the weight increment. The method of claim 1, wherein the first associated edge corresponds to a first weight, and the second associated edge corresponds to a second weight, and the method further comprises: the electronic device compares the first weight and the second weight when the weight increment is not greater than the target weight gain; If the first weight is greater than the second weight, the electronic device divides the newly added data node into the first subgraph; if the second weight is greater than the first weight, the electronic device divides the newly added data node into the second subgraph. As described in claim 1, each subgraph includes a plurality of nodes, and the electronic device determines at least one subgraph in the N subgraphs that has an associated edge with the newly added data node when the newly added data node is obtained, including: when the electronic device obtains incremental data of a first object, determining the first object as the newly added data node; based on the incremental data, the electronic device determines at least one second object that has a preset behavior relationship with the first object; the electronic device establishes an associated edge between a node corresponding to the second object and the newly added data node, and defines a weight value of each associated edge based on transaction data; the electronic device determines that the at least one subgraph includes the subgraph where the at least one second object is located. The method as claimed in claim 1, wherein the method further comprises: the electronic device divides the newly added data node into the single subgraph when there is an associated edge between the newly added data node and the single subgraph. An incremental graph partitioning device is characterized in that it includes: a determination module, which is used to determine at least one subgraph in N subgraphs that has an associated edge with the newly added data node when a newly added data node is obtained, wherein the N subgraphs are obtained by partitioning the stock graph based on a community discovery algorithm; an acquisition module, which is used to obtain target weight gain thresholds of the first subgraph and the second subgraph when the at least one subgraph includes a first subgraph and a second subgraph, wherein the newly added data node has a first associated edge with the first subgraph, and the newly added data node has a second associated edge with the second subgraph. The determining module is further used to determine the weight increment of the newly added data node based on the weight values of the first associated edge and the second associated edge; the partitioning module is used to, when the weight increment is greater than the target weight gain threshold, determine that the first subgraph and the second subgraph meet the preset aggregation condition, aggregate the first subgraph and the second subgraph to obtain a third subgraph, and partition the newly added data node into the third subgraph; wherein the first subgraph has an associated edge with M1 subgraphs, the second subgraph has an associated edge with M2 subgraphs, and the M1 subgraph includes the second subgraph. The device further comprises: an acquisition module, which is used to acquire the weights of the associated edges between the first subgraph and the M1 subgraphs before acquiring the target weight gain thresholds of the first subgraph and the second subgraph, and obtain M1 third weights; the acquisition module is also used to acquire the weights of the associated edges between the second subgraph and the M2 subgraphs, and obtain M2 fourth weights; a calculation module, which is used to add the M1 third weights to obtain a first parameter, and add the M2 fourth weights to obtain a second parameter; and add the first parameter to the second parameter to obtain a fourth weight. Six weights; obtain the weight sum of the associated edges between N-2 subgraphs to obtain the seventh weight, wherein the N-2 subgraphs include subgraphs other than the first subgraph and the second subgraph in the N subgraphs; calculate the difference between the first product and the second product to obtain the second difference, wherein the first product is the product of the first parameter and the second parameter, and the second product is the product of the fifth weight and the sixth weight; calculate the ratio of the second difference to the seventh weight to obtain the target weight gain threshold; wherein the fifth weight is the weight of the associated edge between the first subgraph and the second subgraph. An electronic device, characterized in that the device comprises: a processor and a memory storing computer program instructions; when the processor executes the computer program instructions, the incremental graph division method as described in any one of claims 1 to 6 is implemented. A computer-readable storage medium, characterized in that a program or instruction is stored on the computer-readable storage medium, and when the program or instruction is executed by a processor, the incremental graph partitioning method as described in any one of claim items 1 to 6 is implemented. A computer program product, characterized in that the computer program product is stored in a non-volatile storage medium, and when the computer program product is executed by at least one processor, the incremental graph partitioning method as described in any one of claims 1 to 6 is implemented.