Clique network identification method and apparatus, computer device, and computer-readable storage medium

Patent metadata

Field	Value
Publication number	US-10958529-B2
Application number	US-202016903480-A
Country	US
Kind code	B2
Filing date	Jun 17, 2020
Priority date	Apr 4, 2018
Publication date	Mar 23, 2021
Grant date	Mar 23, 2021

Abstract

The present disclosure provides a method for identifying a clique network using a Pregel graph computing framework. The method includes determining, according to a data transfer feature of a target clique, a transmitting direction of attribute values of nodes; transmitting, an edge vector of the edge and an attribute value of the first node to the second node along the transmitting direction in a constructed data transmission relationship network, the edge vector comprising a plurality of data transfer eigenvalues; performing, weighted calculation on the edge vector received by the second node to obtain an optimal weighted edge; iterating, the above operations; and determining, according to attribute values of the nodes after the one or more iterations, nodes in the target clique, and determining attributes of the nodes in the target clique.

First claim

What is claimed is:

1. A method for identifying a clique network using a Pregel graph computing framework, comprising:
determining, according to a data transfer feature of a target clique, a transmitting direction of attribute values of nodes;
transmitting, on an edge connecting a first node and a neighboring second node, an edge vector of the edge and an attribute value of the first node to the second node along the transmitting direction in a constructed data transmission relationship network, the edge vector comprising a plurality of data transfer eigenvalues;
performing, weighted calculation on the edge vector received by the second node according to a preset calculation logic, to obtain an optimal weighted edge, the calculation logic matching the data transfer feature of the target clique;
updating, an attribute value of the second node according to an attribute value of a first node connected to the optimal weighted edge;
iterating, operations of transmitting, on an edge connecting a first node and a neighboring second node, an edge vector of the edge and an attribute value of the first node to the second node along the transmitting direction, performing weighted calculation on the edge vector received by the second node according to the preset calculation logic, to obtain an optimal weighted edge, and updating an attribute value of the second node according to an attribute value of a first node connected to the optimal weighted edge, until the iteration meets a preset stop condition; and
determining, according to attribute values of the nodes after the one or more iterations, nodes in the target clique, and determining attributes of the nodes in the target clique.

2. The method for identifying a clique network according to claim 1 , wherein the attribute value comprises a node identification (ID) and a clique core index, and before the transmitting, on an edge connecting a first node and a neighboring second node, an edge vector of the edge and an attribute value of the first node to the second node along the transmitting direction in a constructed data transmission relationship network, the method further comprises:
using, a node ID of the first node as an initial ID of the first node, using a node ID of the second node as an initial ID of the second node, and initializing clique core indexes of the first node and the second node to a preset value.

3. The method for identifying a clique network according to claim 2 , wherein the updating, an attribute value of the second node according to an attribute value of a first node connected to the optimal weighted edge comprises:
updating, the node ID of the second node to the node ID of the first node connected to the optimal weighted edge, and updating, according to an update rule, the clique core index of the second node to the clique core index of the first node connected to the optimal weighted edge plus or minus a preset update value; and
the determining attributes of the nodes in the target clique comprises:
determining, the attributes of the nodes according to the update rule and clique core indexes of the nodes.

4. The method for identifying a clique network according to claim 3 , wherein the performing weighted calculation on the edge vector received by the second node according to preset calculation logic, to obtain an optimal weighted edge comprises:
comparing, for data transfer eigenvalues in a plurality of edge vectors received by the second node, eigenvalues of the same type in descending order of weights respectively corresponding to the eigenvalues in the preset calculation logic, and using an edge corresponding to a largest eigenvalue as an optimal weighted edge.

5. The method for identifying a clique network according to claim 4 , wherein the plurality of data transfer eigenvalues comprise a number of times that a data transfer keyword matches a keyword in the data transfer feature of the target clique and a transfer frequency, a number of transfers, and a quantity transferred within a preset period, and the comparing, for data transfer eigenvalues in a plurality of edge vectors received by the second node, eigenvalues of the same type in descending order of weights respectively corresponding to the eigenvalues in the preset calculation logic, and using an edge corresponding to a largest eigenvalue as an optimal weighted edge comprises:
performing comparison, based on the quantity of times that the data transfer keyword matches the keyword in the data transfer feature of the target clique and the transfer frequency, the number of transfers, and the quantity transferred within the preset period in descending order of the weights respectively corresponding to the eigenvalues in the preset calculation logic, and using an edge corresponding to a largest eigenvalue as an optimal weighted edge.

6. The method for identifying a clique network according to claim 5 , after the determining, according to attribute values of the nodes after the iteration, nodes in the same target clique, and determining attributes of the nodes in the target clique, further comprising:
generating, a clique network graph according to a connection relationship between the nodes belonging to the same clique in the data transmission relationship network; and
marking, nodes having different clique core indexes in the clique network graph with different preset distinguishing features, and outputting the clique network graph.

7. The method for identifying a clique network according to claim 6 , after the generating a clique network graph, further comprising:
marking, each node in the clique network graph with a node ID and a clique core index of the node, and marking an edge between every two connected nodes with an edge vector.

8. The method for identifying a clique network according to claim 1 , wherein the determining, by a computer device according to a data transfer feature of a target clique, a transmitting direction of attribute values of nodes comprises:
determining, that the transmitting direction of the attribute values of the nodes is a reverse direction of data transfer between the nodes in a case that the data transfer feature of the target clique is a divergent type; and
determining, that the transmitting direction of the attribute values of the nodes is a direction of data transfer between the nodes in a case that the data transfer feature of the target clique is a convergent type.

9. One or more non-transitory storage media storing a computer-readable instruction, the computer-readable instruction, when executed by one or more processors, causing the one or more processors to perform:
determining, according to a data transfer feature of a target clique, a transmitting direction of attribute values of nodes;
transmitting, on an edge connecting a first node and a neighboring second node, an edge vector of the edge and an attribute value of the first node to the second node along the transmitting direction in a constructed data transmission relationship network, the edge vector comprising a plurality of data transfer eigenvalues;
performing, weighted calculation on the edge vector received by the second node according to a preset calculation logic, to obtain an optimal weighted edge, the calculation logic matching the data transfer feature of the target clique;
updating, an attribute value of the second node according to an attribute value of a first node connected to the optimal weighted edge;
iterating, operations of transmitting, on an edge connecting a first node and a neighboring second node, an edge vector of the edge and an attribute value of the first node to the second node along the transmitting direction, performing weighted calculation on the edge vector received b

Assignees

• Tencent Tech Shenzhen Co Ltd

Inventors

• Xia Bin
• Wu Ming

Classifications

• H04L41/12 Primary

  Discovery or management of network topologies · CPC title

• H04L41/149

  for prediction of maintenance · CPC title

• H04L41/142 Primary

  using statistical or mathematical methods · CPC title

• G06Q50/34 Primary

  Betting or bookmaking, e.g. Internet betting · CPC title