Huawei Technologies Co., Limited

Jiefeng Cheng

Wei Fan

Zhenguo Li

Cheng He

Zhihong Zhao

The method of the present disclosure includes: after a graph partitioning apparatus extracts an edge, first determining whether an aggregation degree between a currently extracted edge and an allocated edge in a first device satisfies a preset condition; then, when the preset condition is satisfied, determining whether a quantity of allocated edges stored in the first device is less than a first preset threshold; and allocating the currently extracted edge to the first device when the quantity is less than the first preset threshold. In this way, an aggregation degree between allocated edges in each device is relatively high and each device has relatively balanced load. When an edge changes and an edge associated with the particular edge needs to be synchronized, a relatively small quantity of devices need to perform synchronization and update, so that costs of communication between devices are reduced, and distributed graph computing efficiency is improved.

Graph partitioning method and apparatus

The present invention discloses a method and apparatus for querying a nondeterministic graph, which are used to implement quick query of a nondeterministic graph, reduce query complexity, and improve query efficiency. The method comprises receiving a query instruction, where the query instruction is used to query a nondeterministic graph for data that satisfies a query condition; determining two vertices in the nondeterministic graph according to the query instruction; determining all possible paths that use one vertex in the two vertices as a start point and the other vertex as an end point; calculate a probability of a first event or a second event corresponding to each of the paths; and obtaining, according to the probability of the first event or the probability of the second event, a query result corresponding to the query instruction.

Method and apparatus for querying nondeterministic graph

A similarity measurement method includes: obtaining a directional relationship between nodes in a network, and determining a transition matrix; calculating a constraint matrix according to the transition matrix and an obtained attenuation factor; constructing a system of linear equations, where a coefficient matrix of the system of linear equations is the constraint matrix, and a variable of the system of linear equations is a correction vector; solving the system of linear equations by means of iteration by using a Jacobi method, and determining the correction vector; and calculating similarities between the nodes according to the transition matrix, the attenuation factor, and a diagonal correction matrix that is generated according to the correction vector. In the method, the correction vector is determined by using the Jacobi method, and further the similarities between the nodes may be calculated.

Growing community of inventors

Shenzhen, China

Jiefeng Cheng