CN111694900A - Network graph processing method and device - Google Patents

Abstract

The application provides a network graph processing method and device. Wherein the method comprises the following steps: acquiring a network graph to be processed; acquiring characteristic information of at least two nodes in the network graph; acquiring feature similarity between the at least two nodes according to the feature information of the at least two nodes; and compressing the network graph according to the feature similarity between the at least two nodes. By adopting the method provided by the application, the problem that the compressed network graph cannot accurately reflect the service information due to the loss of the service information in the compression process of the network graph is solved.

Description

A method and device for processing a network graph

technical field

The present application relates to the field of network graph processing, and in particular to a method and device for processing a network graph.

Background technique

Nowadays, with the popularity of mobile devices, various social networks are used by more and more people. It follows that the data scale of the relational network graphs corresponding to these social networks also expands exponentially.

Appropriately compress the relational network graph of these massive data and reduce the data scale, so as to meet the efficiency requirements of relational network visualization and network analysis.

In the prior art, the compression of the network graph is generally based on the structural relationship of the network graph such as the extension path length to compress the network graph. Using this compression method, although the data scale of the network graph can be compressed, a large amount of business information is lost during the compression process, so that the compressed network graph cannot accurately reflect the business information.

SUMMARY OF THE INVENTION

The present application provides a method and device for processing a network graph to solve the problem in the prior art that service information is lost in the process of compressing the network graph, so that the compressed network graph cannot accurately reflect the service information.

The present application provides a method for processing a network graph, including:

Get the network graph to be processed;

acquiring feature information of at least two nodes in the network graph;

According to the feature information of the at least two nodes, obtain the feature similarity between the at least two nodes;

The network graph is compressed according to the feature similarity between the at least two nodes.

Optionally, the feature information of the at least two nodes includes at least one of the following feature information:

Type information of the at least two nodes;

degree information of the at least two nodes;

attribute information of the at least two nodes;

neighbor node information of each of the at least two nodes.

The obtaining the feature similarity between the at least two nodes according to the feature information of the at least two nodes includes:

Obtain at least one similarity among node type similarity, node degree similarity, node attribute similarity, and neighbor similarity between the at least two nodes;

The feature similarity between the at least two nodes is acquired according to at least one similarity among the node type similarity, the node degree similarity, the node attribute similarity, and the neighbor similarity between the two nodes.

The acquiring the node type similarity between the at least two nodes includes: acquiring the node type similarity between the at least two nodes according to the type information of the at least two nodes;

Alternatively, the acquiring the degree similarity of the nodes between the at least two nodes includes: acquiring the degree similarity of the nodes between the at least two nodes according to the degree information of the at least two nodes;

Alternatively, the obtaining the node attribute similarity between the at least two nodes includes: obtaining the node attribute similarity between the at least two nodes according to the attribute information of the at least two nodes;

Alternatively, the obtaining the neighbor similarity between the at least two nodes includes: obtaining the neighbor similarity between the at least two nodes according to the adjacent node information of the at least two nodes.

Optionally, obtaining the degree similarity of nodes between the at least two nodes according to the degree information of the at least two nodes includes:

According to the degree information of the at least two nodes, obtain the node degree difference between the at least two nodes;

Obtain the node degree similarity between the at least two nodes according to the node degree difference between the at least two nodes.

Optionally, obtaining the neighbor similarity between the two nodes according to the neighbor node information of the at least two nodes includes:

Acquire common neighbor node information between the at least two nodes according to the adjacent node information of the at least two nodes;

According to the common neighbor node information, the neighbor similarity between the at least two nodes is obtained.

Optionally, compressing the network graph according to the feature similarity between the at least two nodes includes:

According to the feature similarity between the at least two nodes, determine whether the features of the at least two nodes are the same;

If so, the at least two nodes are merged.

Optionally, compressing the network graph according to the feature similarity between the at least two nodes includes:

Judging whether the feature similarity between the at least two nodes reaches or exceeds a similarity threshold;

If so, the at least two nodes are merged.

Optionally, the processing method of the network graph further includes:

calculating the size of the network graph;

According to the size of the network graph, determine whether it is necessary to compress the nodes of the network graph;

The acquiring feature information of at least two nodes in the network graph includes: acquiring feature information of at least two nodes in the network graph if the nodes in the network graph need to be compressed.

Optionally, the processing method of the network graph further includes:

Get the request from the client to query the network relationship;

For the request for querying the network relationship, obtain the compressed network graph from the electronic device storing the compressed network graph;

Obtain network relationship data from the compressed network graph;

The network relationship data is provided to the client.

Optionally, the processing method of the network graph further includes:

Get a request for client-side network analysis;

For the request of the network analysis, obtain the compressed network graph from the electronic device storing the compressed network graph;

Perform network analysis on the compressed network graph to obtain network analysis results;

The network analysis results are provided to the client.

The present application provides a processing device for a network graph, including:

a network map acquisition unit, used for acquiring the network map to be processed;

a feature acquisition unit, configured to acquire feature information of at least two nodes in the network graph;

a similarity obtaining unit, configured to obtain the feature similarity between the at least two nodes according to the feature information of the at least two nodes;

A compression processing unit, configured to perform compression processing on the network graph according to the feature similarity between the at least two nodes.

Optionally, the feature information of the at least two nodes includes at least one of the following feature information:

Type information of the at least two nodes;

degree information of the at least two nodes;

attribute information of the at least two nodes;

neighbor node information of each of the at least two nodes.

Optionally, the similarity obtaining unit is specifically used for:

Obtain at least one similarity among node type similarity, node degree similarity, node attribute similarity, and neighbor similarity between the at least two nodes;

The feature similarity between the at least two nodes is acquired according to at least one similarity among the node type similarity, the node degree similarity, the node attribute similarity, and the neighbor similarity between the two nodes.

Optionally, the acquiring the node type similarity between the at least two nodes includes: acquiring the node type similarity between the at least two nodes according to the type information of the at least two nodes;

Alternatively, the acquiring the degree similarity of the nodes between the at least two nodes includes: acquiring the degree similarity of the nodes between the at least two nodes according to the degree information of the at least two nodes;

Alternatively, the acquiring the node attribute similarity between the at least two nodes includes: acquiring the node attribute similarity between the at least two nodes according to the attribute information of the at least two nodes;

Alternatively, the obtaining the neighbor similarity between the at least two nodes includes: obtaining the neighbor similarity between the at least two nodes according to the adjacent node information of the at least two nodes.

Optionally, the similarity obtaining unit is further used for:

According to the degree information of the at least two nodes, obtain the node degree difference between the at least two nodes;

Obtain the node degree similarity between the at least two nodes according to the node degree difference between the at least two nodes.

Optionally, the similarity obtaining unit is further used for:

Acquire common neighbor node information between the at least two nodes according to the adjacent node information of the at least two nodes;

According to the common neighbor node information, the neighbor similarity between the at least two nodes is obtained.

Optionally, the compression processing unit is specifically used for:

According to the feature similarity between the at least two nodes, determine whether the features of the at least two nodes are the same;

If so, the at least two nodes are merged.

Optionally, the compression processing unit is specifically used for:

Judging whether the feature similarity between the at least two nodes reaches or exceeds a similarity threshold;

If so, the at least two nodes are merged.

Optionally, the processing device of the network diagram further includes a judgment unit, and the judgment unit is used for:

calculating the size of the network graph;

According to the size of the network graph, determine whether it is necessary to compress the nodes of the network graph;

The acquiring feature information of at least two nodes in the network graph includes: acquiring feature information of at least two nodes in the network graph if the nodes in the network graph need to be compressed.

Optionally, the apparatus for processing the network map further includes a first processing unit, where the first processing unit is configured to:

Get the request from the client to query the network relationship;

For the request for querying the network relationship, obtain the compressed network graph from the electronic device storing the compressed network graph;

Obtain network relationship data from the compressed network graph;

The network relationship data is provided to the client.

Optionally, the apparatus for processing the network graph further includes a second processing unit, where the second processing unit is configured to:

Get a request for client-side network analysis;

For the request of the network analysis, obtain the compressed network graph from the electronic device storing the compressed network graph;

Perform network analysis on the compressed network graph to obtain network analysis results;

The network analysis results are provided to the client.

The application provides an electronic device, the electronic device includes:

processor;

The memory is used to store a program, and when the program is read and executed by the processor, the following operations are performed:

Get the network graph to be processed;

acquiring feature information of at least two nodes in the network graph;

According to the feature information of the at least two nodes, obtain the feature similarity between the at least two nodes;

The network graph is compressed according to the feature similarity between the at least two nodes.

The present application provides a computer-readable storage medium on which a computer program is stored, and when the program is executed by a processor, the following steps are implemented:

Get the network graph to be processed;

acquiring feature information of at least two nodes in the network graph;

According to the feature information of the at least two nodes, obtain the feature similarity between the at least two nodes;

The network graph is compressed according to the feature similarity between the at least two nodes.

The present application provides a method for processing a network graph, including:

get the original network graph;

Output the compressed network diagram;

Wherein, at least one node in the compressed network graph is a node formed by merging at least two nodes in the original network graph;

Wherein, the features of the at least two nodes are the same, or the feature similarity between the at least two nodes reaches or exceeds a similarity threshold.

Compared with the prior art, the present application has the following advantages:

Using the method provided in the present application, the feature similarity between the at least two nodes is obtained according to the feature information of the at least two nodes, and the network is analyzed according to the feature similarity between the at least two nodes. The image is compressed. Since the feature similarity between nodes is considered in the process of compressing the network graph, try to ensure that the compressed network graph does not lose service information, so that the compressed network graph can reflect the service information as accurately as possible.

Description of drawings

1 is a flowchart of a method for processing a network graph provided by a first embodiment of the present application;

2 is a flowchart of a method for processing a network diagram of an application instance involved in the first embodiment of the present application;

3 is a network diagram compression effect diagram of an application example involved in the first embodiment of the present application;

4 is a schematic diagram of an apparatus for processing a network map provided by a second embodiment of the present application;

FIG. 5 is a flowchart of a method for processing a network graph provided by a fifth embodiment of the present application.

Detailed ways

In the following description, numerous specific details are set forth in order to provide a thorough understanding of the present application. However, the present application can be implemented in many other ways different from those described herein, and those skilled in the art can make similar promotions without departing from the connotation of the present application. Therefore, the present application is not limited by the specific implementation disclosed below.

The first embodiment of the present application provides a method for processing a network graph. Please refer to FIG. 1 , which is a flowchart of the first embodiment of the present application. A method for processing a network graph provided by the first embodiment of the present application will be described in detail below with reference to FIG. 1 . The method includes the following steps:

Step S101: Obtain the network graph to be processed.

This step is used to obtain the network graph to be processed.

A network graph is a data structure used to model relationships between entities. It consists of point sets and edge sets, where a point set is a set of entities and an edge set is a set of relationships between entities.

For example, a social network that is widely used by people can be represented using a network graph. After the network diagram is established, operations such as network analysis can be performed to obtain valuable information. For example, by analyzing the social network graph, it is possible to obtain the friendship relationship between people, the sending relationship of e-mails, and so on.

Step S102: Obtain characteristic information of at least two nodes in the network graph.

This step is used to acquire feature information of at least two nodes in the network graph. The feature information in this application includes service feature information.

The feature information of the at least two nodes includes at least one of the following feature information:

Type information of the at least two nodes;

degree information of the at least two nodes;

attribute information of the at least two nodes;

neighbor node information of each of the at least two nodes.

For example, taking an e-commerce network diagram as an example, in the network diagram, the node types of the network diagram nodes may include merchants, users, products, and the like. The attributes of the merchant type node can include information such as the address of the store, the number of visits to the store, and the monthly sales of the store. The attributes of the user type node may include the purchase quantity of the user and the like. The attributes of the commodity type node can include information such as the price of the commodity, the origin of the commodity, and the manufacturer of the commodity. The user realizes the connection of three network types of nodes through the operation of purchasing products at the merchant; in the network graph, different types of edges (the user purchases the item, the user appears in a certain geographical location) describes the structural information of the network graph. The degree of a node refers to the number of nodes that are directly connected to the nodes in the network graph. The neighbor information of the node may include information of the neighbor nodes of the node.

Step S103: Obtain the feature similarity between the at least two nodes according to the feature information of the at least two nodes.

This step is used to obtain the feature similarity between the at least two nodes according to the feature information of the at least two nodes.

The network graph compression method provided in this embodiment proposes the concept of service similarity between nodes in view of the problem that only structural compression is considered when compressing a network graph, and service information is lost. The business similarity between the nodes may be obtained according to the type information of the node, the degree information of the node, the attribute information of the node, the information of the adjacent nodes of the node and other dimensions. The feature similarity obtained in this way is more from the business perspective of the network graph, and then the network graph is compressed according to the feature similarity, which avoids the drawbacks caused by traditional network graph compression.

The obtaining the feature similarity between the at least two nodes according to the feature information of the at least two nodes includes:

Obtain at least one similarity among node type similarity, node degree similarity, node attribute similarity, and neighbor similarity between the at least two nodes;

The feature similarity between the at least two nodes is acquired according to at least one similarity among the node type similarity, the node degree similarity, the node attribute similarity, and the neighbor similarity between the two nodes.

The acquiring the node type similarity between the at least two nodes includes: acquiring the node type similarity between the at least two nodes according to the type information of the at least two nodes;

Alternatively, the acquiring the degree similarity of the nodes between the at least two nodes includes: acquiring the degree similarity of the nodes between the at least two nodes according to the degree information of the at least two nodes;

Alternatively, the obtaining the node attribute similarity between the at least two nodes includes: obtaining the node attribute similarity between the at least two nodes according to the attribute information of the at least two nodes;

Alternatively, the obtaining the neighbor similarity between the at least two nodes includes: obtaining the neighbor similarity between the at least two nodes according to the adjacent node information of the at least two nodes.

The feature similarity between the nodes of the network graph provided in this embodiment can be obtained only according to one of the node type similarity, the node degree similarity, the node attribute similarity, and the neighbor similarity between the two nodes. . The feature similarity here can be selected from the interval [0, 100]. 100 means that the characteristics of the two nodes are the same, and 0 means that the characteristics of the two nodes are completely dissimilar. For example, the node type similarity is taken as the feature similarity, so that the feature similarity between nodes with the same node type is 100.

In addition, the feature similarity between the network graph nodes provided in this embodiment may also be based on a variety of node type similarity, node degree similarity, node attribute similarity, and neighbor similarity between the two nodes. to obtain. For example, the feature similarity between nodes in the network graph can be calculated according to the node type similarity and the node degree similarity between two nodes, or the feature similarity between nodes in the network graph can also be calculated according to the similarity between two nodes. Node type similarity, node degree similarity, node attribute similarity, and neighbor similarity are calculated.

It should be pointed out here that, in the above process of calculating the feature similarity between network graph nodes, different weights may be assigned to the feature similarity of different dimensions. Please refer to the following formula for calculating feature similarity:

Among them, K is the feature similarity between network graph nodes, i is the variable representing the feature dimension, n is the number of feature dimensions, a _i is the weight value of the ith feature dimension, and _ki is the ith feature dimension similarity.

For example, if the feature similarity between network graph nodes only needs to consider the node type similarity and the node degree similarity, then n=2, k ₁ represents the node type similarity, and a ₁ represents the weight value of the node type similarity , k ₂ represents the node degree similarity, and a ₂ represents the weight value of the node degree similarity. At this time, the calculation process of feature similarity between network graph nodes is:

In the above calculation process, the weight value of node degree similarity and the weight value of node type similarity can either be manually given according to experience, or obtained by other methods such as machine learning.

The obtaining, according to the degree information of the at least two nodes, the degree similarity of the nodes between the at least two nodes includes:

According to the degree information of the at least two nodes, obtain the node degree difference between the at least two nodes;

Obtain the node degree similarity between the at least two nodes according to the node degree difference between the at least two nodes.

If there are three or more nodes, the node degree difference between the at least two nodes refers to the difference between any two nodes. For example, there are now four nodes A(8), B(7), C(4), D(1). The capital letters represent the nodes, and the parentheses after the capital letters represent the degree of the node, then get the The node degree difference between at least two nodes, including obtaining the difference AB(1), AC(3), AD(7), BC(3), BD(6), CD(3), where two Consecutive uppercase letters represent the difference between two nodes, and the specific number of the difference is in parentheses after the two letters.

Generally speaking, nodes with the same node degree have relatively high feature similarity. Here, the feature similarity between the nodes can be judged according to the difference between the node degrees of the two nodes. In a specific implementation, the absolute value of the node degree difference between the two nodes can be used to determine the feature similarity between the nodes. The smaller the absolute value is, the closer the features of the two nodes are.

The node type in the network graph is also an important factor in calculating feature similarity. If two nodes are of the same type, the feature similarity between two nodes is considered to be high. If the types of the two nodes are not the same, it needs to be judged according to the similarity between the types of the two nodes.

For example, if there are three types of nodes, namely merchants, users, and products, nodes with the same type have high similarity. The similarity between different types of nodes can be obtained by querying the node type similarity dictionary. The node type similarity dictionary uses a machine learning method to learn distances of different types of nodes from historical data, and establishes a node type similarity dictionary according to the distances between the different types of nodes.

In addition, the node attributes in the network graph are also important factors for calculating feature similarity. If the attributes of the two nodes are the same, the feature similarity between the two nodes is considered to be high. If the attributes of the two nodes are not the same, it needs to be judged according to the similarity between the attributes of the two nodes.

For example, for a node of merchant type, its attributes may include the address of the store, the number of visits to the store, and the monthly sales of the store. If both node A of the merchant type and B of the merchant type have the same three attributes as the address of the store, the number of visits to the store, and the monthly sales volume of the store, it is considered that the merchant A and the merchant B have a high degree of similarity. If the merchant-type node A and the merchant-type node B have mutually different attributes, the similarity between the nodes is obtained by querying the node attribute similarity dictionary. The node attribute similarity dictionary uses a machine learning method to learn distances of different attributes from historical data, and establishes a node attribute similarity dictionary according to the distances between the attributes.

The obtaining the neighbor similarity between the two nodes according to the neighbor node information of the at least two nodes includes:

Acquire common neighbor node information between the at least two nodes according to the adjacent node information of the at least two nodes;

According to the common neighbor node information, the neighbor similarity between the at least two nodes is obtained.

The common neighbor node information may be a set of neighbor nodes of the node. In the specific implementation process, the Jaccard similarity index is generally used to calculate, as shown in the following formula.

Among them, A represents the adjacent node set of node 1, B represents the adjacent node set of node 2, J represents the similarity index between node 1 and node 2, and the similarity index here is the neighbor between node 1 and node 2 similarity. It can be found from this formula that the more identical nodes between A and B, the larger J is.

In the specific implementation process, the Jaccard distance can also be used to represent the calculation formula as follows:

d _j =1-j(A, B)

Among them, d _j represents the Jaccard distance, and j(A, B) is the Jaccard similarity index. Through this formula, it can be found that the more the same nodes between A and B, the smaller the d _j .

Step S104: Compress the network graph according to the feature similarity between the at least two nodes.

This step is used to compress the network graph according to the feature similarity between the at least two nodes.

The performing compression processing on the network graph according to the feature similarity between the at least two nodes includes:

According to the feature similarity between the at least two nodes, determine whether the features of the at least two nodes are the same;

If so, the at least two nodes are merged.

After obtaining the feature similarity between the two nodes according to step S103, it is first necessary to judge whether the features between the two nodes are completely the same, for example, have the same node type, node attribute and so on. If these features are all identical, the two nodes are considered to have identical features. If the characteristics of the two nodes are exactly the same, the two nodes should be combined into one node, and the corresponding relationship should be combined at the same time.

The performing compression processing on the network graph according to the feature similarity between the at least two nodes includes:

Judging whether the feature similarity between the at least two nodes reaches or exceeds a similarity threshold;

If so, the at least two nodes are merged.

In the method for processing a network graph provided in this embodiment, nodes with identical features are merged preferentially. After merging nodes with identical features, if further network graph compression is required, consider merging nodes with similar features. In a specific implementation, a threshold for judging whether the features are similar may be represented by a similarity threshold. If the feature similarity between the two nodes reaches or exceeds the similarity threshold, the at least two nodes are merged.

The method for processing the network graph, further comprising:

calculating the size of the network graph;

According to the size of the network graph, determine whether it is necessary to compress the nodes of the network graph;

The acquiring feature information of at least two nodes in the network graph includes: acquiring feature information of at least two nodes in the network graph if the nodes in the network graph need to be compressed.

In this embodiment, the size of the network graph may be represented by the size of the space occupied by the network graph, or may be represented by the number of nodes in the network graph.

The method for processing the network graph, further comprising:

Get the request from the client to query the network relationship;

For the request for querying the network relationship, obtain the compressed network graph from the electronic device storing the compressed network graph;

Obtain network relationship data from the compressed network graph according to the request for querying network relationships;

The network relationship data is provided to the client.

After the network graph is compressed, various services can be completed according to the user's request. For example, according to the user's request to query the network relationship, the network relationship data is provided to the customer.

The method for processing the network graph, further comprising:

Get a request for client-side network analysis;

For the request of the network analysis, obtain the compressed network graph from the electronic device storing the compressed network graph;

According to the request of the network analysis, network analysis is performed on the compressed network graph to obtain the network analysis result;

The network analysis results are provided to the client.

After the network graph is compressed, the network analysis result can also be provided to the client according to the user's request for network analysis.

FIG. 2 is a flowchart of an application example of the method for processing a network graph provided by this embodiment. The application example first performs step S201 : calculating the size of the network graph. Then, step S202 is executed: judging whether to compress, this step judges whether the network graph needs to be compressed according to the size of the network graph. If no compression is required, end the process. If compression is required, step S203 is performed: the characteristics of each node are calculated according to the type, degree, neighbor, attribute and other characteristics of the nodes in the network graph. Further, step S204 is performed to determine whether the features are the same, and whether the features are the same is determined according to the features of each node. If the features are the same, step S205 is performed to compress nodes with the same features. If the features are not the same, step S206 is performed: compressing nodes with similar features. After the compression is completed, step S207 is executed to calculate the size of the network graph. According to the size of the network graph, step S208 is executed: it is judged whether to further compress. If further compression is required, step S203 is re-entered.

FIG. 3 is a schematic diagram of a compression effect according to the application example of FIG. 2 . In Figure 3, each row is a schematic diagram of the effect of a compression instance.

As can be seen from the first row in Figure 3, nodes 1, 2, and 3 with the same or similar features are compressed into node 4.

In the second row of Figure 3, firstly, nodes 5, 6, 7 with the same or similar features are compressed into node 10, nodes 8 and 9 with the same or similar features are compressed into node 11, and then, the same or similar features are compressed into node 11. Nodes 10 , 11 with similar characteristics are compressed into node 12 .

In the third row of Figure 3, firstly, nodes 13, 14, 15 with the same or similar features are compressed into nodes 18, nodes 16, 17 with the same or similar features are compressed into nodes 19, and then, the same or similar features are compressed into nodes 19. Nodes 18 , 19 with similar characteristics are compressed into node 20 .

As can be seen from Figure 3, nodes with the same or similar features are merged, thereby maximizing the retention of service information.

In the above-mentioned embodiments, a method for processing a network graph is provided, and correspondingly, the present application also provides a device for processing a network graph. Please refer to FIG. 4 , which is a flowchart of an embodiment of an apparatus for processing a network map of the present application. Since this embodiment, that is, the second embodiment, is basically similar to the method embodiment, the description is relatively simple, and reference may be made to the partial description of the method embodiment for related parts. The apparatus embodiments described below are merely illustrative.

A device for processing a network graph in this embodiment includes:

A network map obtaining unit 401, used to obtain a network map to be processed;

A feature obtaining unit 402, configured to obtain feature information of at least two nodes in the network graph;

A similarity obtaining unit 403, configured to obtain the feature similarity between the at least two nodes according to the feature information of the at least two nodes;

The compression processing unit 404 is configured to perform compression processing on the network graph according to the feature similarity between the at least two nodes.

In this embodiment, the feature information of the at least two nodes includes at least one of the following feature information:

Type information of the at least two nodes;

degree information of the at least two nodes;

attribute information of the at least two nodes;

neighbor node information of each of the at least two nodes.

In this embodiment, the similarity obtaining unit is specifically used for:

Obtain the node type similarity between the at least two nodes according to the type information of the at least two nodes;

According to the degree information of the at least two nodes, obtain the degree similarity of the nodes between the at least two nodes;

According to the attribute information of the at least two nodes, obtain the node attribute similarity between the at least two nodes;

Obtain the neighbor similarity between the at least two nodes according to the neighbor node information of the at least two nodes;

The feature similarity between the at least two nodes is acquired according to at least one similarity among the node type similarity, the node degree similarity, the node attribute similarity, and the neighbor similarity between the two nodes.

In this embodiment, the similarity obtaining unit is also used for:

According to the degree information of the at least two nodes, obtain the node degree difference between the at least two nodes;

Obtain the node degree similarity between the at least two nodes according to the node degree difference between the at least two nodes.

In this embodiment, the similarity obtaining unit is also used for:

Acquire common neighbor node information between the at least two nodes according to the adjacent node information of the at least two nodes;

According to the common neighbor node information, the neighbor similarity between the at least two nodes is obtained.

In this embodiment, the compression processing unit is specifically used for:

According to the feature similarity between the at least two nodes, determine whether the features of the at least two nodes are the same;

If so, the at least two nodes are merged.

In this embodiment, the compression processing unit is specifically used for:

Judging whether the feature similarity between the at least two nodes reaches or exceeds a similarity threshold;

If so, the at least two nodes are merged.

In this embodiment, the processing device for the network diagram further includes a judgment unit, and the judgment unit is used for:

calculating the size of the network graph;

According to the size of the network graph, determine whether it is necessary to compress the nodes of the network graph;

The acquiring feature information of at least two nodes in the network graph includes: acquiring feature information of at least two nodes in the network graph if the nodes in the network graph need to be compressed.

In this embodiment, the apparatus for processing the network map further includes a first processing unit, where the first processing unit is configured to:

Get the client's request to query the network relationship;

For the request for querying the network relationship, obtain the compressed network graph from the electronic device storing the compressed network graph;

Obtain network relationship data from the compressed network graph according to the request for querying network relationships;

The network relationship data is provided to the client.

In this embodiment, the device for processing the network map further includes a second processing unit, where the second processing unit is configured to:

Get a request for client-side network analysis;

For the request of the network analysis, obtain the compressed network graph from the electronic device storing the compressed network graph;

According to the request of the network analysis, network analysis is performed on the compressed network graph to obtain the network analysis result;

The network analysis results are provided to the client.

A third embodiment of the present application provides an electronic device, the electronic device comprising:

processor;

The memory is used for storing a program, and when the program is read and executed by the processor, the program executes the method for processing a network graph provided by the first embodiment of the present application.

A fourth embodiment of the present application provides a computer-readable storage medium on which a computer program is stored. When the program is executed by a processor, the method for processing a network graph provided by the first embodiment of the present application is executed.

A fifth embodiment of the present application provides a method for processing a network graph, including:

Step S501: Obtain the original network graph.

Step S502: Output the compressed network graph.

Step S503: wherein, at least one node in the compressed network graph is a node formed by merging at least two nodes in the original network graph.

Step S504: wherein the features of the at least two nodes are the same, or the feature similarity between the at least two nodes reaches or exceeds a similarity threshold.

The method provided in this embodiment is used to output a network graph compressed by the processing method of the network graph provided in the first embodiment of the present application. The description here is relatively simple, and for details, please refer to the first embodiment.

Although the present application is disclosed above with preferred embodiments, it is not intended to limit the present application. Any person skilled in the art can make possible changes and modifications without departing from the spirit and scope of the present application. Therefore, the present application The scope of protection shall be subject to the scope defined by the claims of this application.

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

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

1. Computer readable media includes both persistent and non-permanent, removable and non-removable media. Information storage can be implemented by any method or technology. Information may be computer readable instructions, data structures, modules of programs, 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 tape cartridges, magnetic tape magnetic disk storage or other magnetic storage devices or any other non-transmission medium that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media does not include non-transitory computer-readable media (transitory media,) such as modulated data signals and carrier waves.

2. Those skilled in the art should understand that the embodiments of the present application may be provided as methods, systems or computer program products. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

Claims (15)

1. a processing method of network graph, is characterized in that, comprises: Get the network graph to be processed; acquiring feature information of at least two nodes in the network graph; According to the feature information of the at least two nodes, obtain the feature similarity between the at least two nodes; The network graph is compressed according to the feature similarity between the at least two nodes. 2. The method for processing a network graph according to claim 1, wherein the characteristic information of the at least two nodes comprises at least one of the following characteristic information: Type information of the at least two nodes; degree information of the at least two nodes; attribute information of the at least two nodes; neighbor node information of each of the at least two nodes. 3. The method for processing a network graph according to claim 1, wherein the obtaining the feature similarity between the at least two nodes according to the feature information of the at least two nodes comprises: Obtain at least one similarity among node type similarity, node degree similarity, node attribute similarity, and neighbor similarity between the at least two nodes; The feature similarity between the at least two nodes is acquired according to at least one similarity among the node type similarity, the node degree similarity, the node attribute similarity, and the neighbor similarity between the two nodes. 4 . The method for processing a network graph according to claim 3 , wherein the obtaining the node type similarity between the at least two nodes comprises: obtaining, according to the type information of the at least two nodes, obtaining the node type similarity between the at least two nodes; Alternatively, the acquiring the degree similarity of the nodes between the at least two nodes includes: acquiring the degree similarity of the nodes between the at least two nodes according to the degree information of the at least two nodes; Alternatively, the obtaining the node attribute similarity between the at least two nodes includes: obtaining the node attribute similarity between the at least two nodes according to the attribute information of the at least two nodes; Alternatively, the obtaining the neighbor similarity between the at least two nodes includes: obtaining the neighbor similarity between the at least two nodes according to the adjacent node information of the at least two nodes. 5 . The method for processing a network graph according to claim 4 , wherein the obtaining, according to the degree information of the at least two nodes, the degree similarity of the nodes between the at least two nodes comprises: 5 . According to the degree information of the at least two nodes, obtain the node degree difference between the at least two nodes; Obtain the node degree similarity between the at least two nodes according to the node degree difference between the at least two nodes. 6. The method for processing a network graph according to claim 4, wherein the obtaining the neighbor similarity between the two nodes according to the adjacent node information of the at least two nodes comprises: Acquire common neighbor node information between the at least two nodes according to the adjacent node information of the at least two nodes; According to the common neighbor node information, the neighbor similarity between the at least two nodes is obtained. 7. The method for processing a network graph according to claim 1, wherein the compressing the network graph according to the feature similarity between the at least two nodes comprises: According to the feature similarity between the at least two nodes, determine whether the features of the at least two nodes are the same; If so, the at least two nodes are merged. 8. The method for processing a network graph according to claim 1, wherein the compressing the network graph according to the feature similarity between the at least two nodes comprises: Judging whether the feature similarity between the at least two nodes reaches or exceeds a similarity threshold; If so, the at least two nodes are merged. 9. The processing method of a network graph according to claim 1, characterized in that, further comprising: calculating the size of the network graph; According to the size of the network graph, determine whether it is necessary to compress the nodes of the network graph; The acquiring feature information of at least two nodes in the network graph includes: acquiring feature information of at least two nodes in the network graph if the nodes in the network graph need to be compressed. 10. The method for processing a network graph according to claim 1, further comprising: Get the request from the client to query the network relationship; For the request for querying the network relationship, obtain the compressed network graph from the electronic device storing the compressed network graph; Obtain network relationship data from the compressed network graph; The network relationship data is provided to the client. 11. The method for processing a network graph according to claim 1, further comprising: Get a request for client-side network analysis; For the request of the network analysis, obtain the compressed network graph from the electronic device storing the compressed network graph; Perform network analysis on the compressed network graph to obtain network analysis results; The network analysis results are provided to the client. 12. A device for processing a network graph, comprising: a network map acquisition unit, used for acquiring the network map to be processed; a feature acquisition unit, configured to acquire feature information of at least two nodes in the network graph; a similarity obtaining unit, configured to obtain the feature similarity between the at least two nodes according to the feature information of the at least two nodes; A compression processing unit, configured to perform compression processing on the network graph according to the feature similarity between the at least two nodes. 13. An electronic device, characterized in that the electronic device comprises: processor; The memory is used for storing a program, and when the program is read and executed by the processor, the method according to any one of claims 1-11 is executed. 14. A computer-readable storage medium on which a computer program is stored, characterized in that, when the program is executed by a processor, the method according to any one of claims 1-11 is executed. 15. A method for processing a network graph, comprising: get the original network graph; Output the compressed network diagram; Wherein, at least one node in the compressed network graph is a node formed by merging at least two nodes in the original network graph; Wherein, the features of the at least two nodes are the same, or the feature similarity between the at least two nodes reaches or exceeds a similarity threshold.

Images