CN118070327B - Distance query method and device in social graph satisfying differential privacy protection - Google Patents

Abstract

The invention relates to a social graph processing technology, and discloses a distance query method in a social graph meeting differential privacy protection, which comprises the following steps: the client generates an application request for inquiring the distance between nodes in the social graph; the server receives the application request and calculates privacy sensitivity of a corresponding social graph node set in the application request; and calculating the distance between nodes in the social graph according to the privacy sensitivity, adding noise to the distance, and then transmitting the distance to the client. The invention further provides a distance query device, equipment and medium in the social graph which meet the differential privacy protection. The method and the device can improve the accuracy of distance inquiry in the social graph meeting the differential privacy protection.

Description

Distance query method and device in social graph satisfying differential privacy protection

Technical Field

The present invention relates to the technical field of social graph processing, and in particular to a distance query method and device in a social graph that meets differential privacy protection.

Background technique

Social graph is a widely used way to represent social relationships in today's society. It consists of nodes and edges, and can effectively represent various entities and their relationships. The private information in the social graph can be the attributes of the nodes, the weights of the edges, or the structural information of the graph. However, as people's privacy awareness increases, the unprotected disclosure of information in the social graph will lead to privacy leaks and cause ethical and legal problems.

In order to protect the privacy of social graph data, early researchers used traditional data anonymity computing techniques such as k-anonymity, l-diversity, and t-proximity. However, these techniques cannot resist the increasing computing power of attackers and attacks based on background knowledge. Therefore, some researchers have tried to use differential privacy technology to protect the privacy of graph data.

Differential privacy is a popular privacy protection method today, which has won the favor of researchers for its rigorous mathematical definition and robust privacy measurement. Its main idea is to reduce the impact of input changes on output through randomness. Specifically, if the algorithm satisfies differential privacy, the difference between the inputs will not cause the output to leak privacy. Differential privacy has many ideal properties, namely: (1) Maximum background knowledge assumption: it is assumed that the attacker knows all records except the target record; (2) Privacy mechanism synthesis: simple differential privacy mechanisms can be combined into complex differential privacy mechanisms; (3) Privacy loss quantification: the privacy protection ability of the mechanism is specifically quantified. Therefore, differential privacy is regarded as the standard for privacy protection algorithms and is applied by Microsoft, Google, and Apple to collect telemetry data without violating privacy.

The shortest path is a commonly used metric in social graphs and has a wide range of uses, such as friend matching and betweenness centrality calculation in social graphs. At present, there have been inventions or studies that solve the problem of how to publish the shortest path when the weights of the edges in the graph are sensitive (i.e., they are private information and cannot be made public). For the sake of clarity, we use the shortest path to represent the sequence of edges that the shortest path passes through, and the distance to represent the number of edges that the shortest path passes through.

Existing studies have used a weighted sensitive graph assumption, which makes its global sensitivity 1. Global sensitivity is used in differential privacy to measure the maximum difference in the output results of queries under adjacent data sets. The larger the global sensitivity, the more random noise needs to be introduced into the results to protect the privacy of the data set. However, if a distance query is performed on an unweighted graph, which assumes that the private information is the edge itself, then its global sensitivity can reach the size of n, where n is the number of nodes in the graph. This excessive sensitivity requires us to use a larger noise to protect the privacy of the edges in the data set. In order to reduce the damage of global sensitivity to the utility of the results, smooth sensitivity can be used as an alternative, but the computational cost of smooth sensitivity is high.

Consider a social graph, where nodes represent users and edges between nodes represent friendships between them. In this graph, the shortest path can refer to a sequence of interconnected edges from a user A to user B. The distance between nodes A and B represents the length of this shortest path. If there is a shortest path with a small distance between A and B (such as a distance less than a certain threshold), then we can try to recommend A and B to each other and expand their friendship. For example, there is a trusted database (or server) that stores a complete user social graph. A client needs to query the server for the distance between users A and B. If the server does not protect its results, the friendships between other users in the graph may be exposed, which will affect the privacy security between users. Using sensitivity to add noise to the graph to protect the privacy of the graph, but using global sensitivity will easily expose the privacy relationships between users in the social graph, and using global sensitivity will increase the sensitivity value, resulting in the introduction of greater random noise to protect the security of the social graph, resulting in a decrease in the effectiveness of privacy protection.

Summary of the invention

The present invention provides a distance query method and device in a social graph that meets differential privacy protection, which can improve the accuracy of distance query in a social graph that meets differential privacy protection.

To achieve the above object, the present invention provides a distance query method in a social graph that satisfies differential privacy protection, comprising:

The client generates an application request to query the distance between nodes in the social graph;

The server receives the application request and calculates the privacy sensitivity of the social graph node set corresponding to the application request;

The distance between nodes in the social graph is calculated according to the privacy sensitivity, and noise is added to the distance before being sent to the client.

Optionally, before calculating the privacy sensitivity of the query set corresponding to the application request, the method further includes:

Step 1, traversing any node pair in the social graph;

Step 2: when there is a connection edge between the node pairs, extract the connection edge to obtain a first shortest path, and delete the connection edge from the social graph to obtain a social graph after deletion;

Step 3: When there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain a path between the node pairs.

Optionally, deleting the connection edge in the social graph to obtain a deleted social graph further includes:

Performing a path search using the breadth-first search algorithm in the deleted social graph to obtain the second shortest path between the node pairs;

After obtaining the second shortest path between the node pairs, deleting the second shortest path;

The breadth-first search algorithm is used again to perform path search on the social graph after deleting the second shortest path, so as to obtain the third shortest path between the node pairs;

The second shortest path and the third shortest path are stored in the path set.

Optionally, after storing the second shortest path and the third shortest path in the path set, the method further includes:

Identify the distance of the second shortest path, and add the distance of the second shortest path minus the distance of the connecting edge to the first distance set;

The distance of the third shortest path is identified, and the distance difference is obtained by subtracting the distance of the second shortest path from the distance of the third shortest path, and the distance difference is added to the second distance set.

Optionally, when there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain the shortest path between the node pairs, including:

When there is no connecting edge between the node pairs, the breadth-first search algorithm is used to search for paths between the node pairs, and after the search is completed, the second shortest path is obtained;

Identifying the distance of the second shortest path and adding it to the first distance set;

After deleting the second shortest path from the social graph, the breadth-first search algorithm is used to search for a third shortest path between node pairs, and the distance of the third shortest path is identified and then subtracted from the distance of the second shortest path to obtain a path distance difference, and the path distance difference is added to the second distance set.

Optionally, calculating the privacy sensitivity of the set of social graph nodes corresponding to the application request includes:

Obtaining privacy parameters preset in the server;

The privacy sensitivity is calculated according to the preset privacy parameter, the first distance set and the second distance set.

Optionally, the calculating the privacy sensitivity according to the preset privacy parameter, the first distance set, and the second distance set includes:

The privacy sensitivity is calculated using the following formula:

ss=max(max(S),max(R)×e ^-β )

Where max(S) is the maximum value in the first distance set, max(R) is the maximum value in the second distance set, and β is the third privacy parameter. ∈ is the first privacy parameter, and δ is the second privacy parameter.

In order to solve the above problems, the present invention also provides a distance query device in a social graph that satisfies differential privacy protection, and the device includes:

The distance query request module is used by the client to generate an application request for querying the distance between nodes in the social graph;

A sensitivity calculation module, configured to receive the application request at the server end and calculate the privacy sensitivity of the set of social graph nodes corresponding to the application request;

The distance result sending module is used to calculate the distance between nodes in the social graph according to the privacy sensitivity, and send the distance to the client after adding noise.

In order to solve the above problem, the present invention further provides an electronic device, the electronic device comprising:

at least one processor; and,

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

The memory stores a computer program executable by the at least one processor, and the computer program is executed by the at least one processor so that the at least one processor can execute the distance query method in the social graph that satisfies differential privacy protection as described above.

In order to solve the above problems, the present invention also provides a computer-readable storage medium, in which at least one computer program is stored. The at least one computer program is executed by a processor in an electronic device to implement the above-mentioned distance query method in a social graph that meets differential privacy protection.

The embodiment of the present invention queries the distance of the social graph in the client, and can calculate the privacy sensitivity through the distance between the nodes queried in the social graph, thereby increasing privacy security. Furthermore, as an unweighted graph, the social graph can realize distance query in the unweighted graph. In addition, in the distance query application request of the client, the overall sensitivity of the social graph is calculated by calculating the privacy sensitivity of the distance set, and the privacy sensitivity is used instead of the global sensitivity to reduce the error damage of the global sensitivity to the distance calculation result. In addition, the embodiment of the present invention directly calculates the privacy sensitivity in the unweighted graph. Compared with the disadvantage that the existing distance publishing technology based on differential privacy cannot act on the unweighted graph, the present invention can reduce the cost of privacy sensitivity calculation in the unweighted graph.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of a flow chart of a distance query method in a social graph that satisfies differential privacy protection provided by an embodiment of the present invention;

FIG2 is a functional module diagram of a distance query device in a social graph that satisfies differential privacy protection, provided by an embodiment of the present invention;

FIG3 is a schematic diagram of the structure of an electronic device for implementing a distance query method in a social graph satisfying differential privacy protection, provided by an embodiment of the present invention.

The realization of the purpose, functional features and advantages of the present invention will be further explained in conjunction with embodiments and with reference to the accompanying drawings.

Detailed ways

It should be understood that the specific embodiments described herein are only used to explain the present invention, and are not used to limit the present invention.

The embodiment of the present application provides a distance query method in a social graph that satisfies differential privacy protection. The execution subject of the distance query method in a social graph that satisfies differential privacy protection includes but is not limited to at least one of the electronic devices such as a server, a terminal, etc. that can be configured to execute the method provided in the embodiment of the present application. In other words, the distance query method in a social graph that satisfies differential privacy protection can be executed by software or hardware installed on a terminal device or a server device, and the software can be a blockchain platform. The server includes but is not limited to: a single server, a server cluster, a cloud server or a cloud server cluster, etc. The server can be an independent server, or it can be a cloud server that provides basic cloud computing services such as cloud services, cloud databases, cloud computing, cloud functions, cloud storage, network services, cloud communications, middleware services, domain name services, security services, content delivery networks (Content Delivery Network, CDN), and big data and artificial intelligence platforms.

1 is a flow chart of a distance query method in a social graph that satisfies differential privacy protection provided by an embodiment of the present invention. In this embodiment, the distance query method in a social graph that satisfies differential privacy protection includes:

S1. The client generates an application request to query the distance between nodes in the social graph.

In the embodiment of the present invention, the client refers to an individual or entity participating in data analysis, and can be represented as a social user or a social node in a social graph.

In the embodiment of the present invention, the client generates an application request for querying the distance between nodes in the social graph, which can realize data communication from the client to the server.

S2. The server receives the application request and calculates the privacy sensitivity of the social graph node set corresponding to the application request.

In the embodiment of the present invention, the server refers to a central node that collects and processes client data. The purpose of the server is to use the client data to perform some data analysis or machine learning tasks, such as friend recommendations in social networks. In order to protect the privacy of the client, the server cannot directly access the client's original data, but can only receive data processed by a certain privacy protection mechanism. The server needs to minimize the risk of privacy leakage of client data while ensuring data availability.

As an embodiment of the present invention, before calculating the privacy sensitivity of the query set corresponding to the application request, the method further includes:

Step 1, traversing any node pair in the social graph;

Step 2: when there is a connection edge between the node pairs, extract the connection edge to obtain a first shortest path, and delete the connection edge from the social graph to obtain a social graph after deletion;

Step 3: When there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain a path between the node pairs.

In the embodiment of the present invention, the node pair refers to any two nodes in the social graph.

In the embodiment of the present invention, the connecting edge refers to an edge in which a pair of nodes is directly connected by only one edge.

As an embodiment of the present invention, deleting the connection edge in the social graph to obtain a deleted social graph further includes:

Performing a path search using the breadth-first search algorithm in the deleted social graph to obtain the second shortest path between the node pairs;

After obtaining the second shortest path between the node pairs, deleting the second shortest path;

The breadth-first search algorithm is used again to perform path search on the social graph after deleting the second shortest path, so as to obtain the third shortest path between the node pairs;

The second shortest path and the third shortest path are stored in the path set.

Further, after storing the second shortest path and the third shortest path in the path set, the method further includes:

Identify the distance of the second shortest path, and add the distance of the second shortest path minus the distance of the connecting edge to the first distance set;

The distance of the third shortest path is identified, and the distance difference is obtained by subtracting the distance of the second shortest path from the distance of the third shortest path, and the distance difference is added to the second distance set.

In the embodiment of the present invention, the distance refers to the number of connecting edges included in the path between two nodes.

As an embodiment of the present invention, when there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain the shortest path between the node pairs, including:

When there is no connecting edge between the node pairs, the breadth-first search algorithm is used to search for paths between the node pairs, and after the search is completed, the second shortest path is obtained;

Identifying the distance of the second shortest path and adding it to the first distance set;

After deleting the second shortest path from the social graph, the breadth-first search algorithm is used to search for a third shortest path between node pairs, and the distance of the third shortest path is identified and then subtracted from the distance of the second shortest path to obtain a path distance difference, and the path distance difference is added to the second distance set.

In the embodiment of the present invention, the first distance set refers to a set of differences between the distance of the second shortest path and the distance of the first shortest path between node pairs, and is represented by a set S.

In the embodiment of the present invention, the second distance set refers to a set of differences between the distances of all subsequent paths between node pairs and the distance of the second shortest path, and is represented by a set R.

In the embodiment of the present invention, the connection edge distance is an edge directly connecting a pair of nodes, and therefore, the connection edge distance is 1.

Exemplarily, the adopting the breadth-first search algorithm to perform path search between node pairs includes:

Define u∈V,v∈V, where V is the vertex set of graph G, where graph G is a social graph. Traverse any node pair (u,v):

If they have a connecting edge on graph G, represented by e(u,v): then starting from node u, perform a breadth-first search algorithm on graph G\{e(u,v)} to obtain a shortest path p(u,v) between u and v. (graph G\{e(u,v)} means deleting edge e(u,v) from graph G, and the following definition is similar).

Specifically, the breadth-first search process is as follows:

1. Pre-set a blank array A of length n (n is the number of nodes in the graph) and a queue Q (a queue is a first-in-first-out data structure widely used in the computer field).

2. Put the node pair (u,u) into the queue. The first node in the node pair represents the node that was previously visited before the currently visited node, and the second node represents the currently visited node. For the initial node u, a special setting is required so that the two nodes are the same. This setting is to obtain the shortest path p(u,v) when searching for node v.

3. Take the first node pair from the queue and name it (a, b): If b is the target node v, set A[b] = a and stop searching; otherwise, mark node b as visited in the graph, set A[b] = a, and add the node and its unvisited neighbor nodes to form a node pair and add them to the queue.

4. Repeat step 3 until the target node v is found. After the target node is found, according to the access order contained in A, a shortest path between u and v can be obtained: p(u,v) = {e(u,s ₁ ), e(s ₁ ,s ₂ ),…, e(s _k ,v)}. Among them, s ₁ ,…,s _k are the nodes passed by the shortest path between virtual nodes u and v.

Similarly, starting from node u, perform a breadth-first search algorithm on the graph G\{p(u,v),e(u,v)} to obtain a shortest path p′(u,v) between u and v. (The graph G\{p(u,v),e(u,v)} represents the graph G with the edge e(u,v) and the edge included in the path p(u,v) deleted.) Add the element |p(u,v)|-1 to the set S (|| represents the length of the path). Add the element |p′(u,v)|-|p(u,v)| to the set R.

Exemplarily, when there is no connecting edge on the social graph G, starting from node u, a breadth-first search algorithm is executed on the graph G to obtain a shortest path p(u, v) between u and v.

Similarly, starting from node u, a breadth-first search algorithm is performed on the graph G\{p(u,v)} to obtain a shortest path p′(u,v) between u and v.

Add the element |p′(u,v)|-|p(u,v)| to the set S.

As an embodiment of the present invention, the calculating the privacy sensitivity of the set of social graph nodes corresponding to the application request includes:

Obtaining privacy parameters preset in the server;

The privacy sensitivity is calculated according to the preset privacy parameter, the first distance set and the second distance set.

Further, the calculating the privacy sensitivity according to the preset privacy parameter, the first distance set and the second distance set includes:

The privacy sensitivity is calculated using the following formula:

ss=max(max(S),max(R)×e ^-β )

Where max(S) is the maximum value in the first distance set, max(R) is the maximum value in the second distance set, and β is the third privacy parameter. ∈ is the first privacy parameter, and δ is the second privacy parameter.

The embodiment of the present invention can efficiently calculate the sensitivity by constructing the set S and the set R.

S3. Calculate the distance between nodes in the social graph according to the privacy sensitivity, and send the distance to the client.

As an embodiment of the present invention, calculating the distance between nodes in the social graph according to the privacy sensitivity includes:

Querying a target node pair from the social graph;

Obtaining the distance between the target node pairs;

The distance between the target node pairs is subjected to unbiased processing after adding noise to obtain the target distance.

In the embodiment of the present invention, the target node pair refers to the corresponding nodes in the client application request.

In the embodiment of the present invention, the unbiased processing is performed for the purpose of standardizing the calculation results, so post-processing is performed to convert the biased calculation results into unbiased calculation results, thereby reducing errors.

Further, the adding noise to the distance between the target node pairs and performing unbiased processing to obtain the target distance includes:

The following formula is used to add noise to the distance between the target node pairs for unbiased processing:

Where D is the target distance, d is the distance between the target node pairs, ss is the privacy sensitivity, α is the fourth privacy parameter, and z is the exponential noise.

In the embodiment of the present invention, z is usually an exponential noise Exp ^- (λ) with a scale λ=1.

Furthermore, the probability density function of the exponential noise Exp ^- (λ) is:

The embodiment of the present invention queries the distance of the social graph in the client, and can calculate the privacy sensitivity through the distance between the nodes queried in the social graph, thereby increasing privacy security. Furthermore, as an unweighted graph, the social graph can realize distance query in the unweighted graph. In addition, in the distance query application request of the client, the overall sensitivity of the social graph is calculated by calculating the privacy sensitivity of the distance set, and the privacy sensitivity is used instead of the global sensitivity to reduce the error damage of the global sensitivity to the distance calculation result. In addition, the embodiment of the present invention directly calculates the privacy sensitivity in the unweighted graph. Compared with the disadvantage that the existing distance publishing technology based on differential privacy cannot act on the unweighted graph, the present invention can reduce the cost of privacy sensitivity calculation in the unweighted graph.

As shown in FIG. 2 , it is a functional module diagram of a distance query device in a social graph that satisfies differential privacy protection provided by an embodiment of the present invention.

The device 100 for querying distance in a social graph meeting differential privacy protection of the present invention can be installed in an electronic device. According to the implemented functions, the device 100 for querying distance in a social graph meeting differential privacy protection can include a distance query request module 101, a sensitivity calculation module 102, and a distance result delivery module 103.

The module described in the present invention may also be referred to as a unit, which refers to a series of computer program segments that can be executed by a processor of an electronic device and can complete fixed functions, and is stored in a memory of the electronic device.

In this embodiment, the functions of each module/unit are as follows:

The distance query request module 101 is used by the client to generate an application request for querying the distance between nodes in the social graph.

In the embodiment of the present invention, the client refers to an individual or entity participating in data analysis, and can be represented as a social user or a social node in a social graph.

In the embodiment of the present invention, the client generates an application request for querying the distance between nodes in the social graph, which can realize data communication from the client to the server.

The sensitivity calculation module 102 is used for receiving the application request at the server end and calculating the privacy sensitivity of the social graph node set corresponding to the application request.

In the embodiment of the present invention, the server refers to a central node that collects and processes client data. The purpose of the server is to use the client data to perform some data analysis or machine learning tasks, such as friend recommendations in social networks. In order to protect the privacy of the client, the server cannot directly access the client's original data, but can only receive data processed by a certain privacy protection mechanism. The server needs to minimize the risk of privacy leakage of client data while ensuring data availability.

As an embodiment of the present invention,

Before calculating the privacy sensitivity of the query set corresponding to the application request, the method further includes:

Step 1, traversing any node pair in the social graph;

Step 2: when there is a connection edge between the node pairs, extract the connection edge to obtain a first shortest path, and delete the connection edge from the social graph to obtain a social graph after deletion;

Step 3: When there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain a path between the node pairs.

In the embodiment of the present invention, the node pair refers to any two nodes in the social graph.

In the embodiment of the present invention, the connecting edge refers to an edge in which a pair of nodes is directly connected by only one edge.

As an embodiment of the present invention, deleting the connection edge in the social graph to obtain a deleted social graph further includes:

Performing a path search using the breadth-first search algorithm in the deleted social graph to obtain the second shortest path between the node pairs;

After obtaining the second shortest path between the node pairs, deleting the second shortest path;

The breadth-first search algorithm is used again to perform path search on the social graph after deleting the second shortest path, so as to obtain the third shortest path between the node pairs;

The second shortest path and the third shortest path are stored in the path set.

further,

After storing the second shortest path and the third shortest path in the path set, the method further includes:

Identify the distance of the second shortest path, and add the distance of the second shortest path minus the distance of the connecting edge to the first distance set;

The distance of the third shortest path is identified, and the distance difference is obtained by subtracting the distance of the second shortest path from the distance of the third shortest path, and the distance difference is added to the second distance set.

In the embodiment of the present invention, the distance refers to the number of connecting edges included in the path between two nodes.

As an embodiment of the present invention, when there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain the shortest path between the node pairs, including:

When there is no connecting edge between the node pairs, the breadth-first search algorithm is used to search for paths between the node pairs, and after the search is completed, the second shortest path is obtained;

Identifying the distance of the second shortest path and adding it to the first distance set;

After deleting the second shortest path from the social graph, the breadth-first search algorithm is used to search for a third shortest path between node pairs, and the distance of the third shortest path is identified and then subtracted from the distance of the second shortest path to obtain a path distance difference, and the path distance difference is added to the second distance set.

In the embodiment of the present invention, the first distance set refers to a set of differences between the distance of the second shortest path and the distance of the first shortest path between node pairs, and is represented by a set S.

In the embodiment of the present invention, the second distance set refers to a set of differences between the distances of all subsequent paths between node pairs and the distance of the second shortest path, and is represented by a set R.

In the embodiment of the present invention, the connection edge distance is an edge directly connecting a pair of nodes, and therefore, the connection edge distance is 1.

Exemplarily, the adopting the breadth-first search algorithm to perform path search between node pairs includes:

Define u∈V,v∈V, where V is the vertex set of graph G, where graph G is a social graph. Traverse any node pair (u,v):

If they have a connecting edge on graph G, represented by e(u,v): then starting from node u, perform a breadth-first search algorithm on graph G\{e(u,v)} to obtain a shortest path p(u,v) between u and v. (graph G\{e(u,v)} means deleting edge e(u,v) from graph G, and the following definition is similar).

Specifically, the breadth-first search process is as follows:

1. Pre-set a blank array A of length n (n is the number of nodes in the graph) and a queue Q (a queue is a first-in-first-out data structure widely used in the computer field).

2. Put the node pair (u,u) into the queue. The first node in the node pair represents the node that was previously visited before the currently visited node, and the second node represents the currently visited node. For the initial node u, a special setting is required so that the two nodes are the same. This setting is to obtain the shortest path p(u,v) when searching for node v.

3. Take the first node pair from the queue and name it (a, b): If b is the target node v, set A[b] = a and stop searching; otherwise, mark node b as visited in the graph, set A[b] = a, and add the node and its unvisited neighbor nodes to form a node pair and add them to the queue.

4. Repeat step 3 until the target node v is found. After the target node is found, according to the access order contained in A, a shortest path between u and v can be obtained: p(u,v) = {e(u,s ₁ ), e(s ₁ ,s ₂ ),…, e(s _k ,v)}. Among them, s ₁ ,…,s _k are the nodes passed by the shortest path between virtual nodes u and v.

Similarly, starting from node u, perform a breadth-first search algorithm on the graph G\{p(u,v),e(u,v)} to obtain a shortest path p′(u,v) between u and v. (The graph G\{p(u,v),e(u,v)} represents the graph G with the edge e(u,v) and the edge included in the path p(u,v) deleted.) Add the element |p(u,v)|-1 to the set S (|| represents the length of the path). Add the element |p′(u,v)|-|p(u,v)| to the set R.

Exemplarily, when there is no connecting edge on the social graph G, starting from node u, a breadth-first search algorithm is executed on the graph G to obtain a shortest path p(u, v) between u and v.

Similarly, starting from node u, a breadth-first search algorithm is performed on the graph G\{p(u,v)} to obtain a shortest path p′(u,v) between u and v.

Add the element |p′(u,v)|-|p(u,v)| to the set S.

As an embodiment of the present invention, the calculating the privacy sensitivity of the set of social graph nodes corresponding to the application request includes:

Obtaining privacy parameters preset in the server;

The privacy sensitivity is calculated according to the preset privacy parameter, the first distance set and the second distance set.

Further, the calculating the privacy sensitivity according to the preset privacy parameter, the first distance set and the second distance set includes:

The privacy sensitivity is calculated using the following formula:

SS=max(max(S),max(R)×e ^-β )

Where max(S) is the maximum value in the first distance set, max(R) is the maximum value in the second distance set, and β is the third privacy parameter. ∈ is the first privacy parameter, and δ is the second privacy parameter.

The embodiment of the present invention can efficiently calculate the sensitivity by constructing the set S and the set R.

The distance result sending module 103 is used to calculate the distance between nodes in the social graph according to the privacy sensitivity, and send the distance to the client after adding noise.

As an embodiment of the present invention, calculating the distance between nodes in the social graph according to the privacy sensitivity includes:

Querying a target node pair from the social graph;

Obtaining the distance between the target node pairs;

The distance between the target node pairs is subjected to unbiased processing after adding noise to obtain the target distance.

In the embodiment of the present invention, the target node pair refers to the corresponding nodes in the client application request.

In the embodiment of the present invention, the unbiased processing is performed for the purpose of standardizing the calculation results, so post-processing is performed to convert the biased calculation results into unbiased calculation results, thereby reducing errors.

Further, the adding noise to the distance between the target node pairs and performing unbiased processing to obtain the target distance includes:

The following formula is used to add noise to the distance between the target node pairs for unbiased processing:

Where D is the target distance, d is the distance between the target node pairs, ss is the privacy sensitivity, α is the fourth privacy parameter, and z is the exponential noise.

In the embodiment of the present invention, z is usually an exponential noise Exp ^- (λ) with a scale λ=1.

Furthermore, the probability density function of the exponential noise Exp ^- (λ) is:

As shown in FIG3 , it is a schematic diagram of the structure of an electronic device for implementing a distance query method in a social graph satisfying differential privacy protection provided by an embodiment of the present invention.

The electronic device may include a processor 10, a memory 11, a communication bus 12, and a communication interface 13, and may also include a computer program stored in the memory 11 and executable on the processor 10, such as a distance query method program in a social graph that satisfies differential privacy protection.

In some embodiments, the processor 10 may be composed of an integrated circuit, for example, a single packaged integrated circuit, or a plurality of integrated circuits with the same or different functions, including one or more central processing units (CPUs), microprocessors, digital processing chips, graphics processors, and combinations of various control chips. The processor 10 is the control core (ControlUnit) of the electronic device, and uses various interfaces and lines to connect various components of the entire electronic device, and executes or executes programs or modules stored in the memory 11 (for example, executing a distance query method program in a social graph that satisfies differential privacy protection, etc.), and calls data stored in the memory 11 to execute various functions of the electronic device and process data.

The memory 11 includes at least one type of readable storage medium, and the readable storage medium includes a flash memory, a mobile hard disk, a multimedia card, a card-type memory (for example, SD or DX memory, etc.), a magnetic memory, a disk, an optical disk, etc. In some embodiments, the memory 11 may be an internal storage unit of an electronic device, such as a mobile hard disk of the electronic device. In other embodiments, the memory 11 may also be an external storage device of an electronic device, such as a plug-in mobile hard disk, a smart memory card (Smart Media Card, SMC), a secure digital (Secure Digital, SD) card, a flash card (Flash Card), etc. equipped on the electronic device. Further, the memory 11 may also include both an internal storage unit of the electronic device and an external storage device. The memory 11 can not only be used to store application software and various types of data installed in the electronic device, such as a code of a distance query method program in a social graph that satisfies differential privacy protection, but can also be used to temporarily store data that has been output or is to be output.

The communication bus 12 may be a Peripheral Component Interconnect (PCI) bus or an Extended Industry Standard Architecture (EISA) bus, etc. The bus may be divided into an address bus, a data bus, a control bus, etc. The bus is configured to realize connection and communication between the memory 11 and at least one processor 10, etc.

The communication interface 13 is used for communication between the above-mentioned electronic device and other devices, including a network interface and a user interface. Optionally, the network interface may include a wired interface and/or a wireless interface (such as a WI-FI interface, a Bluetooth interface, etc.), which is generally used to establish a communication connection between the electronic device and other electronic devices. The user interface may be a display (Display), an input unit (such as a keyboard (Keyboard)), and optionally, the user interface may also be a standard wired interface, a wireless interface. Optionally, in some embodiments, the display may be an LED display, a liquid crystal display, a touch-sensitive liquid crystal display, and an OLED (Organic Light-Emitting Diode, organic light-emitting diode) touch device, etc. Among them, the display may also be appropriately referred to as a display screen or a display unit, which is used to display information processed in the electronic device and to display a visual user interface.

FIG3 merely shows an electronic device with components. Those skilled in the art will appreciate that the structure shown in FIG3 does not limit the electronic device and may include fewer or more components than shown in the figure, or a combination of certain components, or a different arrangement of components.

For example, although not shown, the electronic device may also include a power source (such as a battery) for supplying power to each component. Preferably, the power source may be logically connected to the at least one processor 10 through a power management device, so that the power management device can realize functions such as charging management, discharging management, and power consumption management. The power source may also include any components such as one or more DC or AC power sources, recharging devices, power failure detection circuits, power converters or inverters, power status indicators, etc. The electronic device may also include a variety of sensors, Bluetooth modules, Wi-Fi modules, etc., which will not be repeated here.

It should be understood that the embodiment is for illustration only and the scope of the patent application is not limited to this structure.

The memory 11 in the electronic device stores a distance query method program in a social graph that satisfies differential privacy protection, which is a combination of multiple instructions. When running in the processor 10, the following can be achieved:

The client generates an application request to query the distance between nodes in the social graph;

The server receives the application request and calculates the privacy sensitivity of the social graph node set corresponding to the application request;

The distance between nodes in the social graph is calculated according to the privacy sensitivity, and noise is added to the distance before being sent to the client.

Specifically, the specific implementation method of the processor 10 for the above instructions can refer to the description of the relevant steps in the corresponding embodiment of the accompanying drawings, which will not be repeated here.

Furthermore, if the module/unit integrated in the electronic device 1 is implemented in the form of a software functional unit and sold or used as an independent product, it can be stored in a computer-readable storage medium. The computer-readable storage medium can be volatile or non-volatile. For example, the computer-readable medium can include: any entity or device capable of carrying the computer program code, a recording medium, a USB flash drive, a mobile hard disk, a magnetic disk, an optical disk, a computer memory, and a read-only memory (ROM).

The present invention further provides a computer-readable storage medium, wherein the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor of an electronic device, the computer program can implement:

The client generates an application request to query the distance between nodes in the social graph;

The server receives the application request and calculates the privacy sensitivity of the social graph node set corresponding to the application request;

The distance between nodes in the social graph is calculated according to the privacy sensitivity, and noise is added to the distance before being sent to the client.

In the several embodiments provided by the present invention, it should be understood that the disclosed devices, apparatuses and methods can be implemented in other ways. For example, the device embodiments described above are only illustrative, for example, the division of the modules is only a logical function division, and there may be other division methods in actual implementation.

The modules described as separate components may or may not be physically separated, and the components shown as modules may or may not be physical units, that is, they may be located in one place or distributed on multiple network units. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution of this embodiment.

In addition, each functional module in each embodiment of the present invention may be integrated into one processing unit, or each unit may exist physically separately, or two or more units may be integrated into one unit. The above-mentioned integrated unit may be implemented in the form of hardware or in the form of hardware plus software functional modules.

It is obvious to those skilled in the art that the present invention is not limited to the details of the above exemplary embodiments, and that the present invention can be implemented in other specific forms without departing from the spirit or essential characteristics of the present invention.

Therefore, no matter from which point of view, the embodiments should be regarded as illustrative and non-restrictive, and the scope of the present invention is limited by the appended claims rather than the above description, so it is intended that all changes falling within the meaning and scope of the equivalent elements of the claims are included in the present invention. Any attached figure mark in the claims should not be regarded as limiting the claims involved.

The blockchain referred to in the present invention is a new application model of computer technologies such as distributed data storage, peer-to-peer transmission, consensus mechanism, encryption algorithm, etc. Blockchain is essentially a decentralized database, a string of data blocks generated by cryptographic methods. Each data block contains a batch of network transaction information, which is used to verify the validity of its information (anti-counterfeiting) and generate the next block. Blockchain can include the blockchain underlying platform, platform product service layer, and application service layer.

The embodiments of the present application can acquire and process relevant data based on artificial intelligence technology. Among them, artificial intelligence (AI) is the theory, method, technology and application system that uses digital computers or machines controlled by digital computers to simulate, extend and expand human intelligence, perceive the environment, acquire knowledge and use knowledge to obtain the best results.

In addition, it is clear that the word "comprising" does not exclude other units or steps, and the singular does not exclude the plural. Multiple units or devices stated in the system claim can also be implemented by one unit or device through software or hardware. The words first, second, etc. are used to indicate names, and do not indicate any specific order.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solution of the present invention rather than to limit it. Although the present invention has been described in detail with reference to the preferred embodiments, those skilled in the art should understand that the technical solution of the present invention can be modified or replaced by equivalents without departing from the spirit and scope of the technical solution of the present invention.

Claims (5)

1. A distance query method in a social graph that satisfies differential privacy protection, characterized in that the method comprises: The client generates an application request to query the distance between nodes in the social graph; The server receives the application request and calculates the privacy sensitivity of the social graph node set corresponding to the application request; wherein, before calculating the privacy sensitivity of the query set corresponding to the application request, it also includes: Step 1, traversing any node pair in the social graph; Step 2: when there is a connecting edge between the node pairs, extract the connecting edge to obtain a first shortest path, and delete the connecting edge in the social graph to obtain a social graph after deletion; wherein, deleting the connecting edge in the social graph to obtain the social graph after deletion also includes: using a breadth-first search algorithm to perform a path search in the social graph after deletion to obtain a second shortest path between the node pairs; after obtaining the second shortest path between the node pairs, deleting the second shortest path; using the breadth-first search algorithm again to perform a path search on the social graph after deleting the second shortest path to obtain a third shortest path between the node pairs; storing the second shortest path and the third shortest path in the path set; wherein, after storing the second shortest path and the third shortest path in the path set, it also includes: identifying the distance of the second shortest path, and adding the distance of the second shortest path minus the distance of the connecting edge to the first distance set; identifying the distance of the third shortest path, and using the distance of the third shortest path minus the distance of the second shortest path to obtain a distance difference, and adding the distance difference to the second distance set; Step 3: When there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain a path between the node pairs; The step of calculating the privacy sensitivity of the set of social graph nodes corresponding to the application request includes: Obtaining privacy parameters preset in the server; The privacy sensitivity is calculated according to the preset privacy parameter, the first distance set, and the second distance set; wherein the privacy sensitivity is calculated according to the preset privacy parameter, the first distance set, and the second distance set, including: The privacy sensitivity is calculated using the following formula: ss=max(max(S),max(R)×e ^-β ) Where max(S) is the maximum value in the first distance set, max(R) is the maximum value in the second distance set, and β is the third privacy parameter. ∈ is the first privacy parameter, δ is the second privacy parameter; The distance between nodes in the social graph is calculated according to the privacy sensitivity, and noise is added to the distance before being sent to the client. 2. The distance query method in a social graph that satisfies differential privacy protection according to claim 1, characterized in that when there is no connecting edge between the node pairs, a breadth-first search algorithm is used in the social graph to obtain the shortest path between the node pairs, comprising: When there is no connecting edge between the node pairs, the breadth-first search algorithm is used to search for paths between the node pairs, and after the search is completed, the second shortest path is obtained; Identifying the distance of the second shortest path and adding it to the first distance set; After deleting the second shortest path from the social graph, the breadth-first search algorithm is used to search for a third shortest path between node pairs, and the distance of the third shortest path is identified and then subtracted from the distance of the second shortest path to obtain a path distance difference, and the path distance difference is added to the second distance set. 3. A device for distance query in a social graph that satisfies differential privacy protection, characterized in that the device can implement the distance query method in a social graph that satisfies differential privacy protection as described in any one of claims 1 to 2, and the device comprises: The distance query request module is used by the client to generate an application request for querying the distance between nodes in the social graph; A sensitivity calculation module, configured to receive the application request at the server end and calculate the privacy sensitivity of the set of social graph nodes corresponding to the application request; wherein, before calculating the privacy sensitivity of the query set corresponding to the application request, it also includes: step 1, traversing any node pair in the social graph; step 2, when there is a connecting edge in the node pair, extracting the connecting edge to obtain a first shortest path, and deleting the connecting edge in the social graph to obtain a social graph after deletion; wherein, deleting the connecting edge in the social graph to obtain a social graph after deletion also includes: performing a path search using the breadth-first search algorithm in the social graph after deletion to obtain a second shortest path between the node pairs; after obtaining the second shortest path between the node pairs, deleting the second shortest path; performing a path search using the breadth-first search algorithm again on the social graph after deleting the second shortest path to obtain a third shortest path between the node pairs; and comparing the second shortest path and the third shortest path. The method further comprises: storing the second shortest path and the third shortest path in the path set; wherein, after storing the second shortest path and the third shortest path in the path set, it further comprises: identifying the distance of the second shortest path, and adding the distance of the second shortest path minus the distance of the connecting edge to the first distance set; identifying the distance of the third shortest path, and obtaining the distance difference by subtracting the distance of the second shortest path from the distance of the third shortest path, and adding the distance difference to the second distance set; step 3, when there is no connecting edge between the node pair, a breadth-first search algorithm is used in the social graph to obtain the path between the node pair; wherein, calculating the privacy sensitivity of the social graph node set corresponding to the application request comprises: obtaining a privacy parameter preset in the server; calculating the privacy sensitivity according to the preset privacy parameter, the first distance set and the second distance set; wherein, calculating the privacy sensitivity according to the preset privacy parameter, the first distance set and the second distance set comprises: The privacy sensitivity is calculated using the following formula: ss=max(max(S),max(R)×e ^-β ) Where max(S) is the maximum value in the first distance set, max(R) is the maximum value in the second distance set, and β is the third privacy parameter. ∈ is the first privacy parameter, δ is the second privacy parameter; The distance result sending module is used to calculate the distance between nodes in the social graph according to the privacy sensitivity, and send the distance to the client after adding noise. 4. An electronic device, characterized in that the electronic device comprises: at least one processor; and, a memory communicatively connected to the at least one processor; wherein, The memory stores a computer program executable by the at least one processor, and the computer program is executed by the at least one processor so that the at least one processor can execute the distance query method in a social graph that satisfies differential privacy protection as described in any one of claims 1 to 2. 5. A computer-readable storage medium storing a computer program, characterized in that when the computer program is executed by a processor, the method for distance query in a social graph satisfying differential privacy protection as described in any one of claims 1 to 2 is implemented.