HK1254034B - Cluster-based random walk method, device and equipment for random walk - Google Patents

Description

Random walk, cluster-based random walk method, device and equipment

Technical Field

This specification relates to the field of computer software technology, and in particular to random walks, cluster-based random walk methods, devices, and equipment.

Background Art

With the rapid development of computer and Internet technologies, many businesses can be conducted online. Graph computing is a common method for processing online social businesses.

For example, for account fraud identification in social risk control business: each user is regarded as a node. If there is a transfer relationship between two users, there is an edge between the corresponding two nodes. The edge can be undirected or have a direction defined according to the transfer direction; by analogy, graph data containing multiple nodes and multiple edges can be obtained, and then graph calculations can be performed based on the graph data to achieve risk control.

Random walk algorithms are a fundamental and important part of graph computing, providing support for higher-level complex algorithms. Conventional techniques typically employ a random walk algorithm that randomly reads a node from a database, then randomly reads an adjacent node from the database, and so on, to implement a random walk within the graph.

Based on existing technologies, a more efficient random walk scheme that can be applied to large-scale graph data is needed.

Summary of the Invention

The embodiments of this specification provide random walks, cluster-based random walk methods, devices, and equipment to solve the following technical problems: a more efficient random walk solution that can be applied to large-scale graph data is needed.

To solve the above technical problems, the embodiments of this specification are implemented as follows:

The embodiments of this specification provide a cluster-based random walk method, including:

The cluster obtains information of each node included in the graph data;

Generate a two-dimensional array based on the information of each node, where each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

The embodiments of this specification provide a random walk method, including:

Obtain a two-dimensional array generated according to information of each node included in the graph data, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

An embodiment of this specification provides a cluster-based random walk device, which belongs to the cluster and includes:

The acquisition module obtains the information of each node contained in the graph data;

A first generating module generates a two-dimensional array according to the information of each node, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

The second generating module generates a random sequence according to the two-dimensional array, where the random sequence reflects the random walk in the graph data.

The embodiments of this specification provide a random walk device, comprising:

An acquisition module, which acquires a two-dimensional array generated according to information of each node contained in the graph data, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A generating module generates a random sequence according to the two-dimensional array, where the random sequence reflects a random walk in the graph data.

An embodiment of this specification provides a cluster-based random walk device, wherein the device belongs to the cluster and includes:

at least one processor; and,

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions executable by the at least one processor, the instructions being executed by the at least one processor to enable the at least one processor to:

Get the information of each node contained in the graph data;

Generate a two-dimensional array based on the information of each node, where each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

The embodiments of this specification provide a random walk device, including:

at least one processor; and,

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions executable by the at least one processor, the instructions being executed by the at least one processor to enable the at least one processor to:

Obtain a two-dimensional array generated according to information of each node included in the graph data, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

At least one of the above-mentioned technical solutions adopted in the embodiments of this specification can achieve the following beneficial effects: it is conducive to reducing the access to the database that originally stores the graph data, the two-dimensional array does not need to rely on the database after generation, and the adjacent nodes of the node can be quickly indexed through the two-dimensional array. This solution can be applied to large-scale graph data and is highly efficient. When this solution is implemented based on a cluster, the efficiency can be further improved.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the embodiments of this specification or the technical solutions in the prior art, the following briefly introduces the drawings required for use in the embodiments or the description of the prior art. Obviously, the drawings described below are only some embodiments recorded in this specification. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying any creative labor.

FIG1 is a schematic diagram of an overall architecture of the solution of this specification in a practical application scenario;

FIG2 is a flow chart of a cluster-based random walk method provided in an embodiment of this specification;

FIG3 is a schematic diagram of a cluster-based two-dimensional array generation process in an actual application scenario provided by an embodiment of this specification;

FIG4 is a schematic diagram of a cluster-based random sequence generation process in an actual application scenario provided by an embodiment of this specification;

FIG5 is a schematic diagram of a flow chart of a random walk method provided in an embodiment of this specification;

FIG6 is a schematic structural diagram of a cluster-based random walk device corresponding to FIG2 provided in an embodiment of this specification;

FIG7 is a schematic structural diagram of a random walk device corresponding to FIG5 provided in an embodiment of this specification.

DETAILED DESCRIPTION

The embodiments of this specification provide random walks, cluster-based random walk methods, devices, and equipment.

In order to help those skilled in the art better understand the technical solutions in this specification, the technical solutions in the embodiments of this specification will be clearly and completely described below in conjunction with the drawings in the embodiments of this specification. Obviously, the embodiments described are only part of the embodiments of this application, not all of the embodiments. Based on the embodiments of this specification, all other embodiments obtained by ordinary technicians in this field without making creative efforts should fall within the scope of protection of this application.

The solutions in this specification are applicable to both clusters and single machines. Clusters are more efficient for processing large-scale graph data because tasks (e.g., data reading tasks, data synchronization tasks, etc.) can be split up, allowing multiple machines in the cluster to execute their assigned tasks in parallel. The following embodiments are primarily described based on cluster scenarios.

The solution may involve one or more clusters. For example, Figure 1 involves two clusters.

Figure 1 is a schematic diagram of the overall architecture of the solution described in this specification, in a practical application scenario. This architecture primarily involves three components: a server cluster, a worker cluster, and a database. The database stores graph data for the cluster to access. The server cluster and worker cluster work together to implement random walks within the graph data based on the data read from the database.

The architecture in Figure 1 is illustrative and not exclusive. For example, a solution could involve a cluster consisting of at least one scheduler and multiple workers; another could involve a cluster of workers and a server; and so on. The machines involved in the solution work together to implement random walks on the graph data.

The scheme of this manual is described in detail below.

Figure 2 is a flow chart of a cluster-based random walk method provided by an embodiment of this specification. Each step in Figure 2 is executed by at least one machine in the cluster (or a program on the machine), and different steps may be executed by different entities.

The process in Figure 2 includes the following steps:

S202: The cluster obtains information of each node included in the graph data.

In the embodiments of this specification, the node information may include: the node identifier, the identifier of the node's neighboring nodes (hereinafter referred to as an example), or information other than the identifier that can indicate the node's neighboring nodes, etc. The information of each node may be obtained at once or in multiple times.

Typically, raw graph data is stored in a database. In this case, it is necessary to access the database to retrieve information about each node. To avoid redundant data reads and increasing the database burden, multiple machines in a cluster can each read information about a subset of unique nodes. Furthermore, multiple machines can read the database in parallel to quickly retrieve node information.

For example, each worker in a worker cluster can concurrently read and process a portion of node information from a database, then synchronize the processed data to a server cluster. Alternatively, each worker can synchronize the read node information directly to the server cluster for further processing. This processing at least includes generating a two-dimensional array.

S204: Generate a two-dimensional array according to the information of each node, where each row of the two-dimensional array includes an identifier of an adjacent node of the node.

In the embodiments of this specification, a two-dimensional array can be regarded as a matrix, and each row thereof is a one-dimensional array.

Each row may correspond to a node, and the row may include at least the identifiers of the adjacent nodes of the corresponding node, and the identifier of each adjacent node may be a one-dimensional array element of the row. For the convenience of indexing, the identifier of the corresponding node itself may also be a one-dimensional array element of the row. For example, the identifier of the corresponding node is the 0th one-dimensional array element of the row, and the subsequent one-dimensional array elements are the identifiers of the adjacent nodes of the node in turn. Alternatively, the identifier of the node itself may not be included in the row, but may only have an association relationship with the row, and the row can be indexed using the identifier of the node through the association relationship.

Based on the two-dimensional array and the identifier of any node, the identifier of any adjacent node of the node can be quickly indexed, which is conducive to efficient random walking in the graph data.

For ease of indexing, the identifiers of each node are preferably numbers. For example, the order of each node is defined by the size of the identifiers of each node, starting from 0, with the identifier of the first node being 0, the identifier of the second node being 1, and so on. The following embodiments are described based on the definition in this example.

Of course, if the original identifier of the node is not a number, the original identifier can also be mapped to a number based on a one-to-one mapping rule and used as the node identifier to generate a two-dimensional array.

S208: Generate a random sequence according to the two-dimensional array, where the random sequence reflects a random walk in the graph data.

In the embodiment of this specification, the random sequence is a sequence composed of identifiers of multiple nodes. The order of the identifiers in the random sequence is the random walk order. The maximum length of the random sequence is generally determined by a predetermined number of random walk steps.

After obtaining the two-dimensional array, step S206 can be performed multiple times independently to obtain multiple independent random sequences. For example, each working machine generates one or more random sequences based on the two-dimensional array.

The method of Figure 2 is helpful in reducing the access to the database that originally stores the graph data. After the two-dimensional array is generated, it does not need to rely on the database. The two-dimensional array can quickly index the adjacent nodes of the node. This solution is applicable to large-scale graph data and is highly efficient. Since this method is implemented based on a cluster, it can further improve efficiency.

Based on the method of FIG2 , the embodiments of this specification also provide some specific implementation plans and extension plans of the method, which will be described below using the architecture in FIG1 as an example.

In the embodiment of this specification, as described above, the cluster may include a server cluster and a worker cluster. For step S202, the cluster obtains information of each node included in the graph data, which may specifically include:

The worker cluster reads the identifiers of the neighboring nodes of each node contained in the graph data from the database, wherein each worker reads the identifiers of the neighboring nodes of a portion of the nodes. It should be noted that if the identifier of the node itself is also unknown to the worker cluster, the worker cluster can read the identifier of the node and, based on the identifier of the node (which serves as the primary key in the database), read the identifiers of the neighboring nodes of the node.

For example, assume there are five nodes with IDs 0 to 4. The worker cluster includes worker 0, worker 1, and worker 2. Each worker reads the IDs of some of the nodes' neighboring nodes from the database. For example, worker 0 reads the IDs of node 1's neighboring nodes (0 and 2), and node 2's IDs (1, 3, and 4). Worker 1 reads the ID of node 0's neighboring nodes (1). Worker 2 reads the IDs of node 3's neighboring nodes (2 and 4), and node 4's IDs (2 and 3).

In the embodiment of the present specification, each working machine may generate a non-complete two-dimensional array based on the identifiers of adjacent nodes and their corresponding nodes read by itself.

Furthermore, the worker cluster can synchronize these partial two-dimensional arrays to the server cluster. Thus, the server cluster can obtain a full two-dimensional array composed of these partial two-dimensional arrays. Specifically, the server cluster can obtain a full two-dimensional array by specifically integrating (for example, splitting the two-dimensional array, merging the two-dimensional array, etc.) these partial two-dimensional arrays. Alternatively, the server cluster can simply treat all synchronized data as a whole, i.e., a full two-dimensional array, without specifically integrating them after the worker cluster is synchronized. Each server in the server cluster can store the full two-dimensional array separately, or only a portion of the full two-dimensional array.

The two-dimensional array described in step S204 can be the full two-dimensional array, the incomplete two-dimensional array, or the two-dimensional array obtained by further processing (for example, reordering) the full two-dimensional array. The following embodiments mainly take the third case as an example for explanation. It should be noted that if it is a incomplete two-dimensional array, the subsequent random walk will be carried out accordingly in the nodes involved in the incomplete two-dimensional array (these nodes are only part of the nodes in the graph data). Any working machine can generate a random sequence based on the incomplete two-dimensional array generated by itself, without necessarily relying on the above-mentioned synchronization and server cluster.

Continuing with the post-synchronization actions, the server cluster can further synchronize the full two-dimensional array to each worker machine, allowing each worker machine to generate a random sequence based on the full two-dimensional array. As mentioned in the third scenario above, each worker machine can further process the full two-dimensional array before using it to generate a random sequence.

For example, the rows in the two-dimensional array of the entire amount can be sorted according to the order of node identifiers; and a random sequence can be generated based on the sorted two-dimensional array. For example, the row containing the identifiers of node 0 and its adjacent nodes can be placed in the first row, the row containing the identifiers of node 1 and its adjacent nodes can be placed in the second row, and so on. Furthermore, the identifier of node 0 in the first row can be removed, and only the identifiers of its adjacent nodes can be retained. An association relationship can be established between node 0 and the first row after processing, so that the identifiers of any adjacent nodes in the first row can be indexed based on the identifier of node 0. Similarly, only the identifiers of adjacent nodes can be retained in each row after processing.

In the embodiments of the present specification, in each row after processing, the number of one-dimensional array elements is equal, and the number of elements is generally not less than the number of neighbor nodes of the node with the most neighbor nodes in each node. For rows that are not fully filled with the identifiers of neighbor nodes, empty elements (i.e., "null" elements) can be used to fill the tail of the row. In addition, if only an individual node has a large number of neighbor nodes, while the number of neighbors of other nodes is much less, the number of one-dimensional array elements in each row after processing can also be defined with reference to the other nodes, and for the neighbor nodes of the individual node, only a part of the neighbor nodes can be taken as the elements of the row corresponding to the individual node, so as to avoid wasting a lot of memory unnecessarily.

According to the above description, in an actual application scenario provided by an embodiment of this specification, a schematic diagram of a cluster-based two-dimensional array generation process is shown in FIG3 .

In Figure 3, the database table uses the node ID as the primary key and records the IDs of each node's neighboring nodes. Node 0's neighboring node is Node 1, Node 1's neighboring nodes are Node 0 and Node 2, Node 2's neighboring nodes are Node 1, Node 3, and Node 4, Node 3's neighboring nodes are Node 2 and Node 4, and Node 4's neighboring nodes are Node 2 and Node 3. As described above, workers 0-2 can preferably read the IDs of neighboring nodes of some nodes from the database in parallel.

Each worker generates a partial two-dimensional array based on the identifier it reads. The two-dimensional array generated by worker 0 contains two rows, the two-dimensional array generated by worker 1 contains one row, and the two-dimensional array generated by worker 2 contains two rows. Each row in the partial two-dimensional array includes both the node identifier and the identifiers of each of its neighboring nodes.

The worker cluster synchronizes all generated partial two-dimensional arrays to the server cluster. You can see that the server cluster obtains the full two-dimensional array and saves it in parts on servers 0 to 2.

The server cluster synchronizes the full two-dimensional array to each worker machine. Each worker machine can then independently sort and remove nodes from the full two-dimensional array to obtain an ordered two-dimensional array containing only the identifiers of adjacent nodes, which is used to generate a random sequence.

In the embodiment of this specification, for step S206, generating a random sequence according to the two-dimensional array may specifically include:

The working machine randomly determines an identifier among the identifiers of each node as the identifier of the target node; based on the identifier of the target node, indexes the corresponding row in the two-dimensional array, and the corresponding row includes the identifier of the target node and the identifiers of the adjacent nodes of the target node; determines the number of identifiers of the adjacent nodes included in the corresponding row; randomly determines a non-negative integer that is less than the number, and obtains the identifiers of the non-negative integer number of adjacent nodes included in the corresponding row; and generates a random sequence consisting of the identifiers of the target nodes obtained in sequence by re-using the non-negative integer number of adjacent nodes as the target node for iterative calculation.

The example of Figure 3 is further used for explanation in conjunction with Figure 4. Figure 4 is a schematic diagram of a cluster-based random sequence generation process in an actual application scenario provided by an embodiment of this specification.

Assume that the graph data contains N nodes, the mth node is identified by m, 0≤m≤N-1, the target node is the i-th node, and the corresponding row is the i-th row of the two-dimensional array. The corresponding row is a one-dimensional array, the nth neighboring node of the target node is identified by the nth element of the one-dimensional array, where n starts counting from 0, and the non-negative integer is denoted by j.

In Figure 5, N=5. The working machine processes the full two-dimensional array synchronized by the server cluster, and the resulting two-dimensional array (called the adjacent node array) contains 5 rows, corresponding to nodes 0 to 4. Each row is a one-dimensional array, and the one-dimensional array includes the identifiers of the adjacent nodes of the corresponding node, and the insufficient part is filled with "null" elements.

The working machine randomly generates an integer belonging to [0, N-1=4], that is, the working machine randomly determines the identity of the target node among the identifiers of each node; according to the identifier i of the target node, indexes to the i-th row (a one-dimensional array) in the adjacent node array; determines the number of non-"null" elements contained in the i-th row; randomly determines a non-negative integer j that is less than the number of elements; and obtains the identity of the j-th adjacent node of the target node by reading the j-th element in the i-th row.

Assume the target node's ID is 2, and j = 1. The target node is node 2, and the i-th row is [1, 3, 4]. The ID of the target node's first neighboring node is the first element of the array, 3. This allows a random walk from node 2 to node 3, and then iterative calculations using node 3 as the target node, continuing the random walk. Thus, the IDs of the multiple nodes passed through form a random sequence.

In Figure 4, the number of random walk steps is preset to 8 and the number of batches is preset to 5. Represented by a matrix, the number of random walk steps is, for example, the number of columns of the matrix, and the number of batches is the number of rows of the matrix. Each row of the matrix can store a random sequence.

The number of random walk steps defines the maximum length of a random sequence. Whenever a random sequence reaches the maximum length, the next random sequence can be generated without relying on the current random sequence.

The batch size defines the maximum number of random sequences each worker can generate before writing the generated sequences to the database. When this maximum number is reached, the worker can write its previously generated random sequences (represented by the corresponding matrices) to the database. For example, in Figure 5, if worker 2 has reached the maximum number of generated random sequences (5), it can write the corresponding matrices to the database.

Taking the first random sequence (3, 4, 3, 2, 4, 2, 3, 2) generated by worker machine 0 in Figure 4 as an example, this random sequence represents a random walk process passing through the following nodes in sequence: node 3, node 4, node 3, node 2, node 4, node 2, node 3, node 2.

Furthermore, a threshold value may be pre-set to limit the maximum total number of random sequences generated by the entire worker cluster. When the threshold value is reached, each worker may stop generating random sequences.

Furthermore, in actual applications, some workers in a worker cluster may experience anomalies, resulting in the loss of the two-dimensional array previously used to generate the random sequence. For example, if a worker only stores the two-dimensional array in memory, the data in memory will be lost after the outage. In this case, when these workers return to normal operation, the full two-dimensional array can be retrieved from the server cluster, processed, and used to generate the random sequence. Figure 4 illustrates this situation using worker 2.

The above mainly describes the solution of this specification based on the cluster scenario, and the solution of this specification can also be separated from the cluster scenario. For example, based on the same idea, the embodiment of this specification also provides a flow chart of a random walk method, as shown in Figure 5.

The execution subject of the process in FIG5 can be a single computing device or multiple computing devices. The process includes the following steps:

S502: Obtain a two-dimensional array generated according to information of each node included in the graph data, where each row of the two-dimensional array includes an identifier of an adjacent node of the node.

In step S502, the specific person who generates the two-dimensional array is not limited in this application. Generally, as long as the graph data does not change, the two-dimensional array generated based on the graph data can be reused.

S504: Generate a random sequence according to the two-dimensional array, where the random sequence reflects a random walk in the graph data.

Based on the same idea, the embodiments of this specification also provide corresponding devices for the above methods, as shown in Figures 6 and 7.

FIG6 is a schematic structural diagram of a cluster-based random walk device corresponding to FIG2 provided in an embodiment of this specification. The device belongs to the cluster and includes:

Acquisition module 601, acquiring information of each node contained in the graph data;

A first generating module 602 generates a two-dimensional array based on the information of each node, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

The second generating module 603 generates a random sequence according to the two-dimensional array, where the random sequence reflects the random walk in the graph data.

Optionally, the cluster includes a server cluster and a worker cluster;

The acquisition module 601 acquires information of each node included in the graph data, specifically including:

The worker machine cluster reads the identifiers of the adjacent nodes of each node contained in the graph data from the database, wherein each worker machine reads the identifiers of the adjacent nodes of a portion of the nodes.

Optionally, the first generating module 602 generates a two-dimensional array according to the information of each node, specifically including:

Each of the working machines generates a partial two-dimensional array according to the identification of the adjacent node and its corresponding node read by itself;

The worker cluster synchronizes each of the partial two-dimensional arrays to the server cluster;

The server cluster obtains a full two-dimensional array based on each of the incomplete two-dimensional arrays.

Optionally, before the second generation module 603 generates a random sequence based on the two-dimensional array, the server cluster synchronizes the full two-dimensional array to each of the working machines so that each of the working machines generates a random sequence based on the full two-dimensional array.

Optionally, the second generating module 603 generates a random sequence according to the two-dimensional array, specifically including:

The working machine sorts each row in the two-dimensional array of the full amount according to the order of node identification;

Generate a random sequence based on a sorted two-dimensional array.

Optionally, the second generating module 603 generates a random sequence according to the two-dimensional array, specifically including:

The working machine randomly determines an identifier from the identifiers of the nodes as the identifier of the target node;

According to the identifier of the target node, indexing in the two-dimensional array obtains a corresponding row, wherein the corresponding row includes the identifier of the target node and identifiers of adjacent nodes of the target node;

Determine the number of identifiers of adjacent nodes included in the corresponding row;

Randomly determine a non-negative integer smaller than the number, and obtain the identifiers of the non-negative integer-th adjacent nodes included in the corresponding row;

By re-using the non-negative integer number of adjacent nodes as target nodes for iterative calculation, a random sequence consisting of identifiers of the target nodes obtained in sequence is generated.

Optionally, the total number of nodes is N, the identifier of the mth node is m, 0≤m≤N-1, the target node is the ith node, and the corresponding row is the ith row of the two-dimensional array.

Optionally, the corresponding row is a one-dimensional array, the identifier of the n-th adjacent node of the target node is the n-th element of the one-dimensional array, and n is counted starting from 0;

The non-negative integer is denoted as j, and the working machine obtains the identifier of the non-negative integer-th adjacent node included in the corresponding row, specifically including:

The working machine obtains the identifier of the jth adjacent node of the target node by reading the jth element of the one-dimensional array.

Optionally, the total number of elements in the one-dimensional array is equal to the number of neighbor nodes of the node with the most neighbor nodes among the nodes.

Optionally, the working machine generates a random sequence consisting of identifiers of target nodes obtained in sequence, specifically including:

When the total number of target nodes obtained in sequence reaches a preset number of random walk steps, the working machine generates a random sequence consisting of identifiers of the target nodes obtained in sequence.

Optionally, the second generating module 603 generates a random sequence, specifically including:

Each of the working machines generates a random sequence respectively until the total number of generated random sequences reaches a set threshold.

Optionally, if the two-dimensional array locally on the working machine is lost, it is retrieved from the server cluster again.

FIG7 is a schematic diagram of the structure of a random walk device corresponding to FIG5 provided in an embodiment of this specification, wherein the device includes:

An acquisition module 701 acquires a two-dimensional array generated based on information of each node included in the graph data, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

The generating module 702 generates a random sequence according to the two-dimensional array, where the random sequence reflects a random walk in the graph data.

Based on the same idea, the embodiment of this specification also provides a cluster-based random walk device corresponding to FIG2 , which belongs to the cluster and includes:

at least one processor; and,

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions executable by the at least one processor, the instructions being executed by the at least one processor to enable the at least one processor to:

Get the information of each node contained in the graph data;

Generate a two-dimensional array based on the information of each node, where each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

Based on the same idea, the embodiment of this specification also provides a random walk device corresponding to FIG5 , including:

at least one processor; and,

a memory communicatively connected to the at least one processor; wherein,

The memory stores instructions executable by the at least one processor, the instructions being executed by the at least one processor to enable the at least one processor to:

Obtain a two-dimensional array generated according to information of each node included in the graph data, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

Based on the same idea, an embodiment of this specification further provides a non-volatile computer storage medium corresponding to FIG2 , storing computer-executable instructions, wherein the computer-executable instructions are configured as follows:

Get the information of each node contained in the graph data;

Generate a two-dimensional array based on the information of each node, where each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

Based on the same idea, an embodiment of this specification also provides a non-volatile computer storage medium corresponding to FIG5 , storing computer-executable instructions, wherein the computer-executable instructions are configured as follows:

Obtain a two-dimensional array generated according to information of each node included in the graph data, wherein each row of the two-dimensional array includes an identifier of an adjacent node of the node;

A random sequence is generated based on the two-dimensional array, where the random sequence reflects a random walk in the graph data.

The foregoing description of this specification describes specific embodiments. Other embodiments are within the scope of the appended claims. In some cases, the actions or steps recited in the claims can be performed in an order different from that described in the embodiments and still achieve the desired results. Furthermore, the processes depicted in the accompanying drawings do not necessarily require the specific order shown or the sequential order to achieve the desired results. In certain embodiments, multitasking and parallel processing are also possible or may be advantageous.

The various embodiments in this specification are described in a progressive manner. Similar portions between the various embodiments can be referenced to each other, and each embodiment focuses on the differences from the other embodiments. In particular, the device, apparatus, and non-volatile computer storage medium embodiments are generally similar to the method embodiments, so their descriptions are relatively simplified. For relevant details, refer to the descriptions of the method embodiments.

The apparatus, device, non-volatile computer storage medium and method provided in the embodiments of this specification correspond to each other. Therefore, the apparatus, device and non-volatile computer storage medium also have similar beneficial technical effects as the corresponding method. Since the beneficial technical effects of the method have been described in detail above, the beneficial technical effects of the corresponding apparatus, device and non-volatile computer storage medium will not be repeated here.

In the 1990s, technological improvements could be clearly distinguished as either hardware improvements (for example, improvements to circuit structures like diodes, transistors, and switches) or software improvements (improvements to process flows). However, with the advancement of technology, many process flow improvements today can now be considered direct improvements to hardware circuit structures. Designers almost always create the corresponding hardware circuit structure by programming the improved process flow into the hardware circuit. Therefore, it cannot be said that a process flow improvement cannot be implemented using hardware modules. For example, a programmable logic device (PLD), such as a field programmable gate array (FPGA), is an integrated circuit whose logical function is determined by user programming. Designers can "integrate" a digital system on a PLD through their own programming, without having to hire a chip manufacturer to design and manufacture a dedicated integrated circuit chip. Moreover, nowadays, instead of manually fabricating integrated circuit chips, this programming is mostly done using "logic compiler" software. This is similar to the software compiler used when developing programs. Before compilation, the original code must also be written in a specific programming language, called a hardware description language (HDL). There is not just one HDL, but many, such as ABEL (Advanced Boolean Expression Language), AHDL (Altera Hardware Description Language), Confluence, CUPL (Cornell University Programming Language), HDCal, JHDL (Java Hardware Description Language), Lava, Lola, MyHDL, PALASM, RHDL (Ruby Hardware Description Language), etc. The most commonly used ones are VHDL (Very-High-Speed Integrated Circuit Hardware Description Language) and Verilog. Those skilled in the art will also understand that by simply programming the method flow in one of these hardware description languages and then programming it into an integrated circuit, a hardware circuit that implements the logic method flow can be easily obtained.

The controller can be implemented in any suitable manner. For example, the controller can take the form of a microprocessor or processor and a computer-readable medium storing computer-readable program code (e.g., software or firmware) executable by the (micro)processor, logic gates, switches, application-specific integrated circuits (ASICs), programmable logic controllers, and embedded microcontrollers. Examples of controllers include, but are not limited to, the following microcontrollers: ARC 625D, Atmel AT91SAM, Microchip PIC18F26K20, and Silicone Labs C8051F320. The memory controller can also be implemented as part of the control logic of the memory. Those skilled in the art will also know that in addition to implementing the controller in a purely computer-readable program code format, the controller can be implemented in the form of logic gates, switches, application-specific integrated circuits, programmable logic controllers, and embedded microcontrollers by logically programming the method steps. Therefore, such a controller can be considered a hardware component, and the devices included therein for implementing various functions can also be considered as structures within the hardware component. Or even, the devices for implementing various functions can be considered as both software modules that implement the method and structures within the hardware component.

The systems, devices, modules, or units described in the above embodiments may be implemented by computer chips or entities, or by products having certain functions. A typical implementation device is a computer. Specifically, the computer may be, for example, a personal computer, a laptop computer, a cellular phone, a camera phone, a smartphone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device, or a combination of any of these devices.

For the convenience of description, the above devices are described as being divided into various units according to their functions. Of course, when implementing this specification, the functions of each unit can be implemented in the same or multiple software and/or hardware.

Those skilled in the art will appreciate that the embodiments of this specification may be provided as methods, systems, or computer program products. Therefore, the embodiments of this specification may take the form of a complete hardware embodiment, a complete software embodiment, or an embodiment combining software and hardware. Furthermore, the embodiments of this specification may take the form of a computer program product implemented on one or more computer-usable storage media (including but not limited to magnetic disk storage, CD-ROM, optical storage, etc.) containing computer-usable program code.

This specification is described with reference to the flowcharts and/or block diagrams of the methods, devices (systems), and computer program products according to the embodiments of this specification. It should be understood that each process and/or box in the flowchart and/or block diagram, as well as the combination of the processes and/or boxes in the flowchart and/or block diagram, can be implemented by computer program instructions. These computer program instructions can be provided to a processor of a general-purpose computer, a special-purpose computer, an embedded processor, or other programmable data processing device to produce a machine, so that the instructions executed by the processor of the computer or other programmable data processing device produce a device for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing device to operate in a specific manner, so that the instructions stored in the computer-readable memory produce a product including an instruction device that implements the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions can also be loaded onto a computer or other programmable data processing device so that a series of operating steps are executed on the computer or other programmable device to produce a computer-implemented process, so that the instructions executed on the computer or other programmable device provide steps for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

In a typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in a computer-readable medium, random access memory (RAM) and/or non-volatile memory in the form of read-only memory (ROM) or flash RAM. Memory is an example of a computer-readable medium.

Computer-readable media includes permanent and non-permanent, removable and non-removable media that can be implemented by any method or technology to store information. The information can be computer-readable instructions, data structures, program modules or other data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disc read-only memory (CD-ROM), digital versatile disc (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices or any other non-transmission media that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media does not include transitory computer-readable media (transitory media), such as modulated data signals and carrier waves.

It should also be noted that the terms "comprises," "includes," or any other variations thereof are intended to encompass non-exclusive inclusion, such that a process, method, commodity, or apparatus that includes a series of elements includes not only those elements but also other elements not explicitly listed, or includes elements inherent to such process, method, commodity, or apparatus. In the absence of further limitations, an element defined by the phrase "comprises a ..." does not exclude the presence of other identical elements in the process, method, commodity, or apparatus that includes the element.

This specification may be described in the general context of computer-executable instructions, such as program modules, executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, and the like that perform specific tasks or implement specific abstract data types. This specification may also be practiced in distributed computing environments where tasks are performed by remote processing devices connected through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media, including storage devices.

The various embodiments in this specification are described in a progressive manner. Similar parts between the various embodiments can be referred to in conjunction with each other. Each embodiment focuses on the differences between the other embodiments. In particular, the system embodiments are generally similar to the method embodiments, so the description is relatively simple. For relevant parts, refer to the description of the method embodiments.

The foregoing is merely an embodiment of the present invention and is not intended to limit the present application. For those skilled in the art, various modifications and variations may be made to the present application. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and principles of the present application should be included within the scope of the claims of the present application.

Claims (15)

1. A cluster-based random walk method, comprising: The cluster acquires information about each node contained in the graph data; the cluster includes a server cluster and a worker cluster; the acquisition of information about each node contained in the graph data by the cluster specifically includes: the worker cluster reads the identifiers of the adjacent nodes of each node contained in the graph data from the database, wherein each worker reads the identifiers of the adjacent nodes of a subset of nodes. Based on the information of each node, a two-dimensional array is generated, and each row of the two-dimensional array includes the identifier of a neighboring node of a given node. Specifically, each worker machine generates a partial two-dimensional array based on the identifiers of its neighboring nodes and their corresponding identifiers. The worker machine cluster synchronizes each partial two-dimensional array to the server cluster. The server cluster obtains a full two-dimensional array based on each partial two-dimensional array. The server cluster then synchronizes the full two-dimensional array to each worker machine. Based on the two-dimensional array, a random sequence is generated, which reflects the random walk in the graph data; specifically, each of the working machines generates a random sequence based on the full two-dimensional array, until the total number of generated random sequences reaches a set threshold. Each server in the server cluster either stores the full two-dimensional array or only a portion of the full two-dimensional array. If the worker machine loses the existing two-dimensional array, it will obtain it again from the server cluster. 2. The method as described in claim 1, wherein generating a random sequence based on the two-dimensional array specifically includes: Sort the rows in the full two-dimensional array according to the node identifier order; Generate a random sequence based on the sorted two-dimensional array. 3. The method as described in claim 1, wherein generating a random sequence based on the two-dimensional array specifically includes: The working machine randomly selects one identifier from the identifiers of each node as the identifier of the target node; Based on the identifier of the target node, the corresponding row is obtained by indexing in the two-dimensional array. The corresponding row includes the identifier of the target node and the identifiers of the neighboring nodes of the target node. Determine the number of identifiers of the adjacent nodes included in the corresponding row; Randomly determine a non-negative integer less than the stated number, and obtain the identifiers of the non-negative integer-th adjacent nodes included in the corresponding row; By iteratively calculating the first set of non-negative integer neighboring nodes as target nodes, a random sequence consisting of the identifiers of each target node obtained in sequence is generated. 4. The method as described in claim 3, wherein the total number of nodes is N, the identifier of the m-th node is m, 0≤m≤N-1, the target node is the i-th node, and the corresponding row is the i-th row of the two-dimensional array. 5. The method as described in claim 3, wherein the corresponding row is a one-dimensional array, and the identifier of the nth neighboring node of the target node is the nth element of the one-dimensional array, where n is counted starting from 0; The non-negative integer is denoted as j, and obtaining the identifier of the non-negative integer-th adjacent node included in the corresponding row specifically includes: The identifier of the j-th neighboring node of the target node is obtained by reading the j-th element of the one-dimensional array. 6. The method as described in claim 5, wherein the total number of elements in the one-dimensional array is equal to the number of neighboring nodes of the node with the most neighboring nodes among all nodes. 7. The method as described in claim 3, wherein generating a random sequence composed of the identifiers of each target node obtained sequentially specifically includes: When the total number of target nodes obtained in sequence reaches the preset number of random walks, a random sequence composed of the identifiers of the target nodes obtained in sequence is generated. 8. A cluster-based random walk device, the device belonging to the cluster, the cluster including a server cluster and a worker cluster; the device comprising: The acquisition module acquires information about each node contained in the graph data; specifically, the worker cluster reads the identifiers of the neighboring nodes of each node contained in the graph data from the database, wherein each worker reads the identifiers of the neighboring nodes of a subset of nodes. The first generation module generates a two-dimensional array based on the information of each node. Each row of the two-dimensional array includes the identifier of a neighboring node of a given node. Specifically, each worker machine generates a partial two-dimensional array based on the identifiers of its neighboring nodes and their corresponding identifiers. The worker machine cluster synchronizes each partial two-dimensional array to the server cluster. The server cluster obtains a full two-dimensional array based on each partial two-dimensional array. The server cluster then synchronizes the full two-dimensional array to each worker machine. The second generation module generates random sequences based on the two-dimensional array, and the random sequences reflect random walks in the graph data; specifically, each of the working machines generates random sequences based on the full two-dimensional array until the total number of generated random sequences reaches a set threshold. Each server in the server cluster either stores the full two-dimensional array or only a portion of the full two-dimensional array. If the worker machine loses the existing two-dimensional array, it will obtain it again from the server cluster. 9. The apparatus of claim 8, wherein the second generation module generates a random sequence based on the two-dimensional array, specifically comprising: The working machine sorts each row in the full two-dimensional array according to the node identifier order; Generate a random sequence based on the sorted two-dimensional array. 10. The apparatus of claim 8, wherein the second generation module generates a random sequence based on the two-dimensional array, specifically comprising: The working machine randomly selects one identifier from the identifiers of each node as the identifier of the target node; Based on the identifier of the target node, the corresponding row is obtained by indexing in the two-dimensional array. The corresponding row includes the identifier of the target node and the identifiers of the neighboring nodes of the target node. Determine the number of identifiers of the adjacent nodes included in the corresponding row; Randomly determine a non-negative integer less than the stated number, and obtain the identifiers of the non-negative integer-th adjacent nodes included in the corresponding row; By iteratively calculating the first set of non-negative integer neighboring nodes as target nodes, a random sequence consisting of the identifiers of each target node obtained in sequence is generated. 11. The apparatus of claim 10, wherein the total number of nodes is N, the identifier of the m-th node is m, 0≤m≤N-1, the target node is the i-th node, and the corresponding row is the i-th row of the two-dimensional array. 12. The apparatus of claim 10, wherein the corresponding row is a one-dimensional array, and the identifier of the nth neighboring node of the target node is the nth element of the one-dimensional array, where n is counted starting from 0; The non-negative integer is denoted as j. The worker obtains the identifiers of the non-negative integer-th adjacent nodes included in the corresponding row, specifically including: The working machine obtains the identifier of the j-th adjacent node of the target node by reading the j-th element of the one-dimensional array. 13. The apparatus of claim 12, wherein the total number of elements in the one-dimensional array is equal to the number of neighboring nodes of the node with the most neighboring nodes among all nodes. 14. The apparatus of claim 10, wherein the worker generates a random sequence composed of the identifiers of each target node obtained sequentially, specifically including: When the total number of target nodes obtained sequentially reaches a preset number of random walks, the machine generates a random sequence composed of the identifiers of the target nodes obtained sequentially. 15. A cluster-based random walk device, the device belonging to the cluster, the cluster including a server cluster and a worker cluster; the device comprising: At least one processor; and, A memory communicatively connected to the at least one processor; wherein, The memory stores instructions executable by the at least one processor, which, when executed by the at least one processor, enable the at least one processor to: Obtaining information about each node contained in the graph data; specifically including: the worker cluster reading the identifiers of the neighboring nodes of each node contained in the graph data from the database, wherein each worker reads the identifiers of the neighboring nodes of a subset of nodes; Based on the information of each node, a two-dimensional array is generated, and each row of the two-dimensional array includes the identifier of a neighboring node of a given node. Specifically, each worker machine generates a partial two-dimensional array based on the identifiers of its neighboring nodes and their corresponding identifiers. The worker machine cluster synchronizes each partial two-dimensional array to the server cluster. The server cluster obtains a full two-dimensional array based on each partial two-dimensional array. The server cluster then synchronizes the full two-dimensional array to each worker machine. Based on the two-dimensional array, a random sequence is generated, which reflects the random walk in the graph data; specifically, each of the working machines generates a random sequence based on the full two-dimensional array, until the total number of generated random sequences reaches a set threshold. Each server in the server cluster either stores the full two-dimensional array or only a portion of the full two-dimensional array. If the worker machine loses the existing two-dimensional array, it will obtain it again from the server cluster.