CN115733763B - A method, device and computer-readable storage medium for label propagation of an associated network - Google Patents
A method, device and computer-readable storage medium for label propagation of an associated network Download PDFInfo
- Publication number
- CN115733763B CN115733763B CN202211492068.7A CN202211492068A CN115733763B CN 115733763 B CN115733763 B CN 115733763B CN 202211492068 A CN202211492068 A CN 202211492068A CN 115733763 B CN115733763 B CN 115733763B
- Authority
- CN
- China
- Prior art keywords
- node
- association network
- network
- label
- propagation
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L41/00—Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
- H04L41/14—Network analysis or design
- H04L41/142—Network analysis or design using statistical or mathematical methods
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
- H04L9/40—Network security protocols
Landscapes
- Engineering & Computer Science (AREA)
- Computer Security & Cryptography (AREA)
- Signal Processing (AREA)
- Computer Networks & Wireless Communication (AREA)
- Mathematical Analysis (AREA)
- Mathematical Physics (AREA)
- Probability & Statistics with Applications (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Optimization (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Algebra (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention provides a label propagation method, a device and a computer readable storage medium of an association network, wherein the method comprises the steps of constructing a first association network based on first party data and constructing a second association network based on second party data; the method comprises the steps of obtaining a first association network and a second association network based on a security intersection protocol, obtaining a federation association network, and iteratively executing multiple rounds of label propagation on nodes of the federation association network, wherein each round of label propagation comprises the steps of determining label propagation probability between adjacent nodes in a federation association graph, and determining the round of label of each node according to the round of label of the adjacent nodes and the label propagation probability of the adjacent nodes to the nodes for each node. By using the method, the tag propagation across the platform network can be realized on the premise of ensuring the privacy data.
Description
Technical Field
The invention belongs to the field of computers, and particularly relates to a method and a device for propagating labels of an associated network and a computer readable storage medium.
Background
This section is intended to provide a background or context to the embodiments of the invention that are recited in the claims. The description herein is not admitted to be prior art by inclusion in this section.
With the strictness of privacy protection laws, data cooperation among institutions is increasingly required to consider the problem of data privacy protection. The current privacy computing technology mainly focuses on scenes such as federal learning, safety intersection, trace inquiry and the like, and aims at the combination and aggregation of single-point data. The data sources of the tag propagation algorithm in the current association network are all local. The cross-mechanism data joint application on the premise of privacy protection cannot be realized. The updating of the tag cannot use the associated network data of both parties at the same time, and the data value is not utilized efficiently.
Therefore, how to implement federal network tag propagation under the premise of privacy protection is a problem to be solved urgently.
Disclosure of Invention
In order to solve the problems in the prior art, a method, a device and a computer readable storage medium for propagating labels of a correlation network are provided, and the problems can be solved by using the method, the device and the computer readable storage medium.
The present invention provides the following.
According to the first aspect, a label propagation method of an association network is provided, which comprises the steps of constructing a first association network based on first party data, constructing a second association network based on second party data, associating the first association network and the second association network based on a security traffic protocol to obtain a federal association network, and iteratively executing multiple rounds of label propagation on nodes of the federal association network, wherein each round of label propagation comprises the steps of determining label propagation probability between adjacent nodes in a federal association graph, and determining the round of label of each node according to the round of label of the adjacent nodes and the label propagation probability of the adjacent nodes to the nodes.
In one embodiment, the method comprises the steps of associating a first association network with a second association network based on a security intersection protocol to obtain a federal association network, and further comprises the steps of encrypting and intersection of first party data and second party data, determining public nodes in the first association network and the second association network, and associating the first association network with the second association network according to the public nodes to obtain the federal association network;
In one embodiment, determining the label propagation probability between adjacent nodes in the federation association graph further comprises determining an edge weight w ij of an edge ij between a node i and its neighbor node J in the federation association network, determining an edge weight sum Σ jwij between the node i and all its neighbors J, and determining the label propagation probability P ij of the neighbor node J to the node i according to the ratio of the edge weight w ij to the edge weight sum Σ jwij.
In one embodiment, if node i is a non-common node, all neighbor nodes J represent all neighbor nodes of the graph in which node i is located.
In one embodiment, if node i is a common node, all neighbor nodes J represent a set of all neighbor nodes a of node i in the first associated network and all neighbor nodes b of node i in the second associated network.
In one embodiment, if node i is a common node, the first and second parties interact an edge weight sum between node i and all neighbor nodes a of the first associated network and an edge weight sum between node i and all neighbor nodes b of the second associated network.
In one embodiment, the method further comprises determining an edge weight sum Σ jwij：∑jwij＝∑awia+∑bwib by using the following formula if node i is a common node, wherein Σ awia is the edge weight sum between node i and all neighbor nodes a of the first association network, and Σ bwib is the edge weight sum between node i and all neighbor nodes b of the second association network.
In one embodiment, performing multiple rounds of label propagation iteratively on nodes of the federation associated network further includes determining labeled nodes and unlabeled nodes of the federation associated network, updating labels of the unlabeled nodes round by round until labels of the unlabeled nodes no longer change and/or exceed an update round threshold, and maintaining labels of the labeled nodes unchanged.
In one embodiment, the method comprises the steps of determining, for each node, a round of labels of each neighbor node of the node and label propagation probabilities of each neighbor node to the node according to the round of labels of the neighbor node and label propagation probabilities of the neighbor node to the node, calculating the sum of label propagation probabilities corresponding to each label in all neighbor nodes of the node to obtain label propagation aggregation probabilities corresponding to each label, and updating the round of labels of the node according to the label with the largest label propagation aggregation probability.
In one embodiment, if the node is a non-common node, the method further includes calculating a label propagation aggregation probability corresponding to each neighbor node label of the node by the party where the node is located.
In an implementation mode, if the nodes are common nodes, the method further comprises the steps that a first party calculates first party tag propagation aggregation probabilities corresponding to all neighbor node tags of the nodes in a first association network, a second party calculates second tag propagation aggregation probabilities corresponding to all neighbor node tags of the nodes in a second association network, the first party and the second party interact the first tag propagation aggregation probabilities and the second tag propagation aggregation probabilities, and the first party and the second party conduct tag propagation probability aggregation again based on interaction information respectively to obtain tag propagation aggregation probabilities corresponding to all the tags.
In one embodiment, the method further comprises determining graph weights of the first associated network and the second associated network according to the node relation tightness degree of the first associated network and the second associated network, and introducing the graph weights in the interaction process of the first associated network and the second associated network.
In one embodiment, introducing graph weights in the interaction of the first and second associated networks includes determining an edge weight sum Σ jwij if node i is a common node using the following formula:
Σ jwij＝θa∑awia+θb∑bwib, wherein Σ awia is the edge weight sum between the node i and all the neighbor nodes a of the first association network, Σ bwib is the edge weight sum between the node i and all the neighbor nodes b of the second association network, θ a is the graph weight of the first association network, and θ b is the graph weight of the second association network.
In one embodiment, the method comprises the steps of introducing graph weights in the interaction process of the first association network and the second association network, and further comprises the steps of after the first party and the second party interact the first tag propagation aggregation probability and the second tag propagation aggregation probability, carrying out tag propagation probability aggregation again based on the graph weights of the first association network and the second association network to obtain tag propagation aggregation probabilities corresponding to each tag.
In one embodiment, the method further comprises using only the ingress neighbor node of each node as a neighbor node if the first and second associated networks are directed graph networks.
The label propagation device of the association network comprises a graph construction module, a federation network module and a label propagation module, wherein the graph construction module is used for constructing a first association network based on first party data and constructing a second association network based on second party data, the federation network module is used for associating the first association network with the second association network based on a security intersection protocol to obtain the federation association network, the label propagation module is used for iteratively executing multiple rounds of label propagation on nodes of the federation association network, each round of label propagation comprises the steps of determining label propagation probability between adjacent nodes in a federation association graph, and determining the round of label of each node according to the round of label of the adjacent nodes and the label propagation probability of the adjacent nodes to the nodes.
In a third aspect, there is provided a tag propagating device of an associated network comprising at least one processor and a memory communicatively coupled to the at least one processor, wherein the memory stores instructions executable by the at least one processor to enable the at least one processor to perform the method of the first aspect.
In a fourth aspect, there is provided a computer readable storage medium storing a program which, when executed by a multi-core processor, causes the multi-core processor to perform a method as in the first aspect.
One of the advantages of the above embodiment is that tag propagation across a platform network can be achieved while ensuring private data. .
Other advantages of the present invention will be explained in more detail in connection with the following description and accompanying drawings.
It should be understood that the foregoing description is only an overview of the technical solutions of the present invention, so that the technical means of the present invention may be more clearly understood and implemented in accordance with the content of the specification. The following specific embodiments of the present invention are described in order to make the above and other objects, features and advantages of the present invention more comprehensible.
Drawings
The advantages and benefits described herein, as well as other advantages and benefits, will become apparent to those of ordinary skill in the art upon reading the following detailed description of the exemplary embodiments. The drawings are only for purposes of illustrating exemplary embodiments and are not to be construed as limiting the invention. Also, like reference numerals are used to designate like parts throughout the figures. In the drawings:
Fig. 1 is a schematic structural diagram of a tag propagation apparatus of an association network according to an embodiment of the present invention;
FIG. 2 is a flow chart of a method of tag propagation for an associated network according to an embodiment of the present invention;
FIG. 3 is a schematic diagram of a first association network and a second association network according to an embodiment of the present invention;
FIG. 4 is a schematic diagram of a federal associated network according to an embodiment of the present invention;
FIG. 5 is a schematic diagram of determining tag propagation probabilities for a first associated network and a second associated network in accordance with an embodiment of the present invention;
FIG. 6 is a schematic diagram of determining tag propagation probabilities for a federally associated network in accordance with an embodiment of the present invention;
FIG. 7 is a schematic diagram of tag propagation for an associated network according to an embodiment of the present invention;
FIG. 8 is a schematic diagram of tag propagation for an associated network according to an embodiment of the present invention;
Fig. 9 is a schematic structural diagram of a tag propagating device of an association network according to an embodiment of the present invention.
In the drawings, the same or corresponding reference numerals indicate the same or corresponding parts.
Detailed Description
Exemplary embodiments of the present disclosure will be described in more detail below with reference to the accompanying drawings. While exemplary embodiments of the present disclosure are shown in the drawings, it should be understood that the present disclosure may be embodied in various forms and should not be limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the disclosure to those skilled in the art.
In describing embodiments of the present application, it will be understood that terms, such as "comprises" or "comprising," and the like, are intended to indicate the presence of features, numbers, steps, acts, components, portions, or combinations thereof disclosed in the specification, and are not intended to exclude the possibility of one or more other features, numbers, steps, acts, components, portions, or combinations thereof being present.
Unless otherwise indicated, "/" means or, for example, A/B may represent A or B, and "and/or" herein is merely an association relationship describing an association object, means that there may be three relationships, for example, A and/or B, and that there may be three cases where A alone exists, while A and B exist, and B alone exists.
The terms "first," "second," and the like are used for descriptive purposes only and are not to be construed as indicating or implying relative importance or implicitly indicating the number of technical features indicated. Thus, a feature defining "a first", "a second", etc. may explicitly or implicitly include one or more such feature. In the description of the embodiments of the present application, unless otherwise indicated, the meaning of "a plurality" is two or more.
In order to clearly illustrate embodiments of the present application, concepts that may appear in some of the following embodiments will first be described.
The present invention will be described in detail below with reference to the accompanying drawings in conjunction with embodiments.
Referring first to FIG. 1, a schematic diagram of an environment 100 in which an exemplary implementation according to the present disclosure may be used is schematically illustrated.
Fig. 1 shows a schematic diagram of an example of a computing device 100 according to an embodiment of the disclosure. It should be noted that fig. 1 is a schematic structural diagram of a hardware running environment of a tag propagation method of an association network. The tag propagation method equipment based on the association network in the embodiment of the invention can be terminal equipment such as a PC, a portable computer and the like.
As shown in fig. 1, the tag propagation method device of the associated network may include a processor 1001, e.g., a CPU, a network interface 1004, a user interface 1003, a memory 1005, and a communication bus 1002. Wherein the communication bus 1002 is used to enable connected communication between these components. The user interface 1003 may include a Display, an input unit such as a Keyboard (Keyboard), and the optional user interface 1003 may further include a standard wired interface, a wireless interface. The network interface 1004 may optionally include a standard wired interface, a wireless interface (e.g., WI-FI interface). The memory 1005 may be a high-speed RAM memory or a stable memory (non-volatile memory), such as a disk memory. The memory 1005 may also optionally be a storage device separate from the processor 1001 described above.
It will be appreciated by those skilled in the art that the tag propagation device structure of the associated network shown in fig. 1 does not constitute a limitation of the tag propagation method device of the associated network, and may include more or less components than illustrated, or may combine certain components, or may be a different arrangement of components.
As shown in fig. 1, an operating system, a network communication module, a user interface module, and a tag propagation method program of an associated network may be included in a memory 1005 as one type of computer storage medium. The operating system is a program for managing and controlling the hardware and software resources of the tag propagation device of the associated network, and supports the operation of the tag propagation program and other software or programs of the associated network.
In the tag broadcasting apparatus of the association network shown in fig. 1, the user interface 1003 is mainly used for receiving requests, data, etc. sent by the first terminal, the second terminal, and the supervisory terminal, the network interface 1004 is mainly used for connecting the background server to perform data communication with the background server, and the processor 1001 may be used for calling the tag broadcasting program of the association network stored in the memory 1005 and performing the following operations:
The method comprises the steps of constructing a first association network based on first party data, constructing a second association network based on second party data, associating the first association network and the second association network based on a security intersection protocol to obtain a federation association network, and iteratively executing multiple rounds of label propagation on nodes of the federation association network, wherein each round of label propagation comprises the steps of determining label propagation probability between adjacent nodes in a federation association graph, and determining the round of label of each node according to the round of label of the adjacent nodes and the label propagation probability of the adjacent nodes to the nodes.
Therefore, the two parties can perform cross-organization data association network joint calculation and application schemes on the premise that the original data of the two parties are not out of the library only by the non-privacy data such as the interaction tag propagation probability.
Fig. 2 illustrates a flow chart of a tag propagation method for performing an association network according to an embodiment of the present disclosure. The method may be performed, for example, by a computing device 100 as shown in fig. 1. It should be understood that method 200 may also include additional blocks not shown and/or that the blocks shown may be omitted, the scope of the disclosure being not limited in this respect.
Step 210, constructing a first association network based on the first party data, and constructing a second association network based on the second party data;
For example, referring to fig. 3, the a-party and the B-party form nodes and edges in the associated network based on their own data, respectively. And assuming that the party A is a bank, forming an party A association network as an account transfer association network through account transfer data among users, wherein the mobile phone number of the user is a node in the association network, connecting edges to the nodes with account transfer relationship, and taking account transfer as an edge weight value among the nodes. The B party is an operator, a B party associated network is formed by call data among users and is a call associated network, the mobile phone number of the user is a node in the associated network, the node with the call record is connected with the edge, and the call times are edge weight values among the nodes. Optionally, the edge weight values of the respective associated networks may be normalized.
Step 220, associating the first association network with the second association network based on the security intersection protocol to obtain a federal association network;
In one embodiment, the step 220 further includes performing encryption intersection on the first party data and the second party data, determining a common node in the first association network and the second association network, and associating the first association network and the second association network according to the common node to obtain the federal association network.
For example, referring to fig. 4, a security intersection algorithm (such as a privacy intersection algorithm based on rsa+hash) may be used to perform security intersection on two-party node data, and a common node may be found without exposing the original data, so as to form a virtual federal association network. As shown in fig. 4, the first association network and the second association network in fig. 3 may be associated to obtain the federal association network. Where Va represents the node of the a-party, va represents the node of the B-party, vab represents the node shared by both parties, and Vab1, vab2, vab3 are the nodes shared by both parties. With the example of node Vab1, there are 2 neighbor nodes of Vab1 from the a-party association network alone. While from the global data there are 4 neighbor nodes of Vab 1.
Step 230, iteratively executing a plurality of rounds of tag propagation on nodes of the binding associated network;
in particular, nodes of the federal associated network may include annotated nodes and unlabeled nodes, e.g., a portion of unlabeled nodes may exist in the first associated network and the second associated network, respectively. For another example, the first association network is all marked nodes, and the second association network is all unmarked nodes. And so on.
In one embodiment, for the case that the federal associated network includes both marked nodes and unmarked nodes, the step 230 may further include determining marked nodes and unmarked nodes of the federal associated network, updating the labels of the unmarked nodes round by round until the labels of the unmarked nodes no longer change and/or exceed the threshold of the update round, and maintaining the labels of the marked nodes unchanged. Therefore, the labels of the original samples can be unchanged, and the label propagation accuracy is guaranteed.
Optionally, the labels of the labeling nodes may also be dynamically updated round by round, that is, the labels of all nodes in the federal associated network are updated round by round until the labels of the nodes no longer change and/or exceed the update round threshold. Thus, the original label can be corrected, and the hidden risk label can be mined.
In step 230 described above, each round of tag propagation specifically includes the following steps 231-232:
step 231, determining the label propagation probability between adjacent nodes in the federal associated graph;
In one embodiment, the step 231 may specifically include:
(1) Determining an edge weight w ij of an edge ij between a node i and a neighbor node j in the federation association network;
(2) Determining edge weights and sigma jwij between the node i and all the neighbor nodes J;
in one embodiment, if node i is a non-common node, all neighbor nodes J represent all neighbor nodes of the graph in which node i is located.
In one embodiment, if node i is a common node, all neighbor nodes J represent a set of all neighbor nodes a of node i in the first associated network and all neighbor nodes b of node i in the second associated network.
Further, if the node i is a common node, the first and second parties interact the edge weights and Σ awia between the node i and all the neighboring nodes a of the first association network and the edge weights and Σ bwib between the node i and all the neighboring nodes b of the second association network, so that the first and second parties can each calculate the edge weights and Σ jwij between the node i and all the neighboring nodes J based on the sum of the two side weights interacted by the two parties.
Further, in one embodiment, if node i is a common node, based on the sum of the edge weights of the two parties interacting, the first party and the second party may determine the edge weight sum Σ jwij using the following formula:
∑jwij＝∑awia+∑bwib;
Wherein Σ awia is the edge weight sum between node i and all the neighbor nodes a of the first association network, and Σ bwib is the edge weight sum between node i and all the neighbor nodes b of the second association network.
Optionally, in another embodiment, the impact of the traffic scenario on node relationship affinity may be further considered. For example, in a financial scene, the transfer relationship is a strong relationship, and the call relationship is a weak relationship, so that when the tag propagation probability of the edge is calculated, the edge relationship strengths under different business scenes of the two parties can be considered for weighted aggregation.
In this case, the first and second parties may each determine the weighted edge weights and Σ jwij using the following formula:
∑jwij＝θa∑awia+θb∑bwib;
Wherein θ a is the corresponding graph weight of the first association network, and θ b is the graph weight of the second association network.
(3) The label propagation probability P ij of the neighbor node j to the node i is determined according to the ratio of the edge weight w ij to the edge weight sum sigma jwij.
Specifically, tag propagation probabilities for each edge of the federally associated networkWhere w ij represents the weight value of the edge ij. Here, for non-common nodes, J represents the neighbor node of node i, and for common nodes, J represents all neighbor nodes of node i on both sides A, B, respectively.
The calculation logic of Sigma jwij is that the weight sum of the neighbor nodes of the node i is calculated as Sigma awia by the A side, and the weight sum of the neighbor nodes of the node i is calculated as Sigma bwib by the B side. Both parties interact with Σ awia and Σ bwib to obtain the final weight calculation denominator value of Σ jwij＝∑awia+∑bwib.
Referring to fig. 5, a node Vab2 is taken here as an example. In the local network of the A side, 1 neighbor node of the Vab2 is calculated separately, the tag propagation probability of the separate calculation method is P=0.1/0.1=1, 3 neighbor nodes of the Vab2 are calculated separately, the tag propagation probability of the separate calculation method is P=0.2/(0.2+0.4+0.8) =1/7, P=0.4/(0.2+0.4+0.8) =2/7, P=0.8/(0.2+0.4+0.8) =4/7, further, the weight value of the target node Vab2 and the neighbor nodes is exchanged by the two parties, the A side is 0.1, and the B side is 0.2+0.4+0.8=1.4. And updating the label propagation probability of the target node in combination with the federal associated network.
Referring to fig. 6, through the above calculation, on the a side, the label propagation probability of its neighbor node to the node iOn the B-side, similarly, the label propagation probabilities of its neighbor nodes for this node i are 2/15,4/15,8/15, respectively.
Step 232, for each node, determining the round tag of each node according to the round tag of the neighbor node and the tag propagation probability of the neighbor node for the node.
With reference to fig. 7, here, the federally associated network formed by Vab2 is continued as shown below. Node 5 is a risk node, shown as a white node, the label is set to "1", the remaining nodes are unknown nodes, shown as gray nodes, and the label is set to "0". In the label propagation process, the label of the node 5 is always 1, and the labels of the other nodes are updated round by round until the labels of all the nodes are not changed or exceed the updating round threshold value.
In one embodiment, in the step 232, the method further includes the following steps:
step 2321, for node i, determining the round tag of each neighbor node of node i and the tag propagation probability of each neighbor node for node i;
Step 2322, calculating the sum of the tag propagation probabilities corresponding to each tag in all neighbor nodes of the node i to obtain the tag propagation aggregation probability corresponding to each tag;
specifically, if the node i is a non-common node, the label propagation aggregation probability corresponding to each neighbor node label of the node i is calculated only by the party where the node i is located.
The method comprises the steps of firstly calculating first label propagation aggregation probabilities corresponding to all neighbor node labels of a node i in a first association network by a first party, calculating second label propagation aggregation probabilities corresponding to all neighbor node labels of the node i in a second association network by a second party, secondly, interacting the first label propagation aggregation probabilities and the second label propagation aggregation probabilities by the first party and the second party, and finally, conducting label propagation probability aggregation again by the first party and the second party respectively based on interaction information to obtain label propagation aggregation probabilities corresponding to all labels.
Step 2323, the current round of labels of node i are updated according to the label with the largest label propagation aggregation probability.
The node tag update rule shown in the above steps 2321 to 2323 may include the following specific steps:
First, for the T-th round update of node i, let its neighbor node set be J((J1,L1,Pi1),(J2,L2,Pi2),(Jj,Lj,Pij)...,(Jn,Ln,Pin)>,, where J j is the identity of neighbor node J, L j is the label of neighbor node J, and P ij is the propagation probability of edge < i, J j >.
Secondly, the aggregate propagation probability of all tags of the neighbor node set is calculated. The method specifically comprises the steps of P (L j)＝∑Pij, wherein P ij is the label propagation probability of a neighbor node with a label of L j to a target node i, wherein if the node i is a non-common node, only the propagation probability of the label of the neighbor node is calculated, if the node i is a common node, the A side calculates the probability P (L aj)＝∑Piaj) corresponding to all the labels of the neighbor node, the B side calculates the probability P (L bj)＝∑Pibj) corresponding to the labels of the neighbor node, the A side and the B side interact P (L aj) and P (L bj) respectively, and label propagation probability aggregation is carried out again at the A side to obtain label propagation aggregation probability P (L j)＝P(Laj)+P(Lbj) which is finally combined with the associated network information of the two sides.
Finally, the label L j corresponding to the largest P (L j) is selected as the current round label of the node i. The above steps are repeated until the labels of all nodes no longer change.
In one specific example, a specific calculation example of the tag update is given with reference to fig. 7 and 8.
Referring to fig. 7, for the first round of propagation, for node Vab2, the following calculations are performed:
(1) And calculating the label propagation aggregation probability of the neighbor node of the A party as < "0",1/15>, wherein "0" represents a risk-free label, and 1/15 represents the label propagation aggregation probability corresponding to the label "0". It will be appreciated that since the a-party Vab2 has only one neighbor node 1 and its initial tag value is "0", it has been calculated above that the tag propagation probability of node 1 to node Vab2 is 1/15, so that for the a-party Vab2 node there is only one transmissible tag "0", and the tag propagation aggregation probability corresponding to this transmissible tag "0" is 1/15.
(2) And calculating the label propagation aggregation probability of the neighbor node of the B party to be < "0",6/15>, < "1",8/15>, wherein "0" represents a risk-free label, and 6/15 represents the label propagation aggregation probability corresponding to the label "0". "1" represents a risky tag and 8/15 represents the tag propagation aggregation probability corresponding to tag "1". Since B-party Vab2 has three neighbor nodes (3, 4, 5), and the initial label value of nodes 3,4 is "0" and the initial label value of node 5 is "1". In the above, it has been calculated that the label propagation probability of the node 3 to the node Vab2 is 2/15, the label propagation probability of the node 4 to the node Vab2 is 4/15, and the label propagation probability of the node 5 to the node Vab2 is 8/15, so that for the B-party Vab2 node, there are 2 transmissible labels "0" and "1", and the label propagation aggregation probability corresponding to the transmissible label "0" is 6/15=2/15+4/15, and the label propagation aggregation probability corresponding to the transmissible label "1" is 8/15.
(3) The label propagation aggregation probabilities are exchanged by both parties, and the label propagation aggregation probabilities corresponding to the same label are accumulated, so that the label propagation aggregation probability of the node Vab2 is calculated to be < "0",7/15>, < "1",8/15>, namely the label propagation aggregation probability corresponding to the transmissible label "0" is 7/15, and the label propagation aggregation probability corresponding to the transmissible label "1" is 8/15.
(4) And selecting the label '1' corresponding to the maximum label propagation aggregation probability < '1', 8/15> as the label of the current round of the node Vab 2. The other nodes are similar to the steps described above.
After the first round of propagation, the updated node label distribution diagram of the federally associated network is shown in fig. 8, where nodes Vab1 and Vab2 are each updated with a label of "1". The next round of label propagation is continued until the label of the node no longer changes or the propagation round is greater than a certain threshold.
In one embodiment, a graph weight of the first associated network and the second associated network is determined based on a degree of node relationship closeness of the first associated network and the second associated network, and the graph weight is introduced during interaction of the first associated network and the second associated network.
For example, the first association network and the second association network may be determined to be strongly associated or weakly associated according to the service scenario, and then the graph weights of the first association network and the second association network may be introduced when the tag propagation probability of the edge is calculated. Of course, the graph weights of the first association network and the second association network may be introduced when calculating the tag propagation aggregation probability of each tag, which is not particularly limited by the present application.
In one embodiment, the graph weight is introduced in the interaction process of the first association network and the second association network, which at least comprises the following two introduction modes:
(1) In step 231, if node i is a common node, the edge weight sum Σ jwij is determined using the following formula:
Σ jwij＝θa∑awia+θb∑bwib, wherein Σ awia is the edge weight sum between the node i and all the neighbor nodes a of the first association network, Σ bwib is the edge weight sum between the node i and all the neighbor nodes b of the second association network, θ a is the graph weight of the first association network, and θ b is the graph weight of the second association network.
(2) In step 232, after the first party and the second party interact the first tag propagation aggregation probability and the second tag propagation aggregation probability, the tag propagation probability aggregation is performed again based on the graph weights of the first association network and the second association network, so as to obtain tag propagation aggregation probabilities corresponding to each tag. For example, if the node i is a common node, the a side calculates the probabilities P corresponding to all the neighboring node labels of the present invention (L aj)＝∑Piaj, the B side calculates the probabilities P corresponding to the neighboring node labels of the present invention (L bj)＝∑Pibj, the a side and the B side interact P (L aj) and P (L bj), and perform label propagation probability aggregation again at the present invention, to obtain the label propagation aggregation probability P (L j)＝θaP(Laj)+θbP(Lbj) that is finally combined with the network information associated with both sides.
In one embodiment, the method further comprises using only the ingress neighbor node of each node as a neighbor node if the first and second associated networks are directed graph networks. For example, for a directed graph, only the inflow neighbor nodes of the target node may be considered when calculating the propagation probability of the node. The judgment can be specifically performed by combining the service scene.
In the description of the present specification, reference to the terms "some possible embodiments," "some embodiments," "examples," "specific examples," or "some examples," etc., means that a particular feature, structure, material, or characteristic described in connection with the embodiments or examples is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms are not necessarily directed to the same embodiment or example. Furthermore, the particular features, structures, materials, or characteristics described may be combined in any suitable manner in any one or more embodiments or examples. Furthermore, the various embodiments or examples described in this specification and the features of the various embodiments or examples may be combined and combined by those skilled in the art without contradiction.
With respect to the method flow diagrams of embodiments of the application, certain operations are described as distinct steps performed in a certain order. Such a flowchart is illustrative and not limiting. Some steps described herein may be grouped together and performed in a single operation, may be partitioned into multiple sub-steps, and may be performed in an order different than that shown herein. The various steps illustrated in the flowcharts may be implemented in any manner by any circuit structure and/or tangible mechanism (e.g., by software running on a computer device, hardware (e.g., processor or chip implemented logic functions), etc., and/or any combination thereof).
Based on the same technical concept, the embodiment of the invention also provides a tag propagation device of the association network, which is used for executing the tag propagation method of the association network provided by any embodiment. Fig. 9 is a schematic structural diagram of a tag propagation device of an association network according to an embodiment of the present invention.
As shown in fig. 9, the apparatus 900 includes:
a graph construction module 910, configured to construct a first association network based on the first party data, and construct a second association network based on the second party data;
the federation network module 920 is configured to associate the first association network and the second association network based on a security intersection protocol to obtain a federation association network;
The label propagation module 930 is configured to iteratively perform multiple rounds of label propagation on nodes of the federal associated network, where each round of label propagation includes determining a label propagation probability between neighboring nodes in the federal associated graph, and determining, for each node, a home round label of each node according to a home round label of a neighboring node and the label propagation probability of the neighboring node to the node.
It should be noted that, the device in the embodiment of the present application may implement each process of the embodiment of the foregoing method and achieve the same effects and functions, which are not described herein again.
According to some embodiments of the present application there is provided a non-transitory computer storage medium having stored thereon computer executable instructions for a method of tag propagation in an associated network, the computer executable instructions being arranged, when executed by a processor, to perform the method of the above embodiments.
The embodiments of the present application are described in a progressive manner, and the same and similar parts of the embodiments are referred to each other, and each embodiment is mainly described as a difference from other embodiments. In particular, for apparatus, devices and computer readable storage medium embodiments, the description thereof is simplified as it is substantially similar to the method embodiments, as relevant points may be found in part in the description of the method embodiments.
The apparatus, the device, and the computer readable storage medium provided in the embodiments of the present application are in one-to-one correspondence with the methods, and therefore, the apparatus, the device, and the computer readable storage medium also have similar advantageous technical effects as the corresponding methods, and since the advantageous technical effects of the methods have been described in detail above, the advantageous technical effects of the apparatus, the device, and the computer readable storage medium are not repeated herein.
It will be apparent to those skilled in the art that embodiments of the present invention may be provided as a method, apparatus (device or system), or computer readable storage medium. Accordingly, the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the invention may take the form of a computer-readable storage medium embodied in 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.
The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (devices or systems) and computer-readable storage media according to embodiments of the invention. It will be understood that each flow and/or block of the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.
These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.
In one typical configuration, a computing device includes one or more processors (CPUs), input/output interfaces, network interfaces, and memory.
The memory may include volatile memory in a computer-readable medium, random Access Memory (RAM) and/or nonvolatile memory, such as Read Only Memory (ROM) or flash memory (flash RAM). Memory is an example of computer-readable media.
Computer readable media, including both non-transitory and non-transitory, removable and non-removable media, may implement information storage by any method or technology. The information may be computer readable instructions, data structures, modules of a program, or other data. Examples of storage media for a computer 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 Discs (DVD) or other optical storage, magnetic cassettes, magnetic tape magnetic disk storage or other magnetic storage devices, or any other non-transmission medium, which can be used to store information that can be accessed by a computing device. Furthermore, although the operations of the methods of the present invention are depicted in the drawings in a particular order, this is not required or suggested that these operations must be performed in this particular order or that all of the illustrated operations must be performed in order to achieve desirable results. Additionally or alternatively, certain steps may be omitted, multiple steps combined into one step to perform, and/or one step decomposed into multiple steps to perform.
While the spirit and principles of the present invention have been described with reference to several particular embodiments, it is to be understood that the invention is not limited to the disclosed embodiments nor does it imply that features of the various aspects are not useful in combination, nor are they useful in any combination, such as for convenience of description. The invention is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.
Claims (17)
1. A method of tag propagation for an associated network, comprising:
Constructing a first association network based on the first party data, and constructing a second association network based on the second party data;
associating the first association network with the second association network based on a security intersection protocol to obtain a federal association network;
Iteratively performing multiple rounds of tag propagation on nodes of the federal associated network;
determining an edge weight w ij of an edge ij between a node i and a neighbor node j in the federal associated network;
Determining edge weights and sigma jwij between the node i and all the neighbor nodes J;
Determining a tag propagation probability P ij of the neighbor node j for the node i according to the ratio of the edge weight w ij to the edge weight and sigma jwij;
and for each node, determining the round label of each node according to the round label of the neighbor node and the label propagation probability of the neighbor node to the node.
2. The method of claim 1, wherein associating the first association network and the second association network based on a security intersection protocol results in a federal association network, further comprising:
And encrypting and intersecting the first party data and the second party data, determining public nodes in the first association network and the second association network, and associating the first association network and the second association network according to the public nodes to obtain a federal association network.
3. The method of claim 1, wherein the step of determining the position of the substrate comprises,
And if the node i is a non-common node, the all neighbor nodes J represent all neighbor nodes of the graph where the node i is located.
4. The method of claim 1, wherein the step of determining the position of the substrate comprises,
If the node i is a common node, the all neighbor nodes J represent a set of all neighbor nodes a of the node i in the first association network and all neighbor nodes b of the node i in the second association network.
5. The method of claim 1, wherein the step of determining the position of the substrate comprises,
If the node i is a shared node, the first party and the second party interact edge weight sum between the node i and all neighbor nodes a of the first association network and edge weight sum between the node i and all neighbor nodes b of the second association network.
6. The method as recited in claim 1, further comprising:
If the node i is a common node, the edge weight and Σ jwij are determined using the following formula:
∑jwij＝∑awia+∑bwib;
Wherein Σ awia is the edge weight sum between the node i and all neighbor nodes a of the first association network, and Σ bwib is the edge weight sum between the node i and all neighbor nodes b of the second association network.
7. The method of claim 1, wherein performing multiple rounds of tag propagation iteratively on nodes of the federally associated network, further comprises:
Determining marked nodes and unmarked nodes of the federal associated network;
updating the label of the unlabeled node round by round until the label of the unlabeled node is not changed and/or exceeds the updating round threshold value, and
And keeping the label of the labeling node unchanged.
8. The method of claim 1, wherein determining the current round of labels for each node based on the current round of labels for neighbor nodes and the label propagation probability of the neighbor nodes for the node comprises:
Determining, for each node, a home round tag of each neighbor node of the node, and a tag propagation probability of each neighbor node for the node;
Calculating the sum of tag propagation probabilities corresponding to each tag in all neighbor nodes of the node to obtain tag propagation aggregation probabilities corresponding to each tag;
and updating the current round of labels of the nodes according to the label with the maximum label propagation aggregation probability.
9. The method of claim 8, wherein if the node is a non-common node, the method further comprises:
And the party where the node is located calculates label propagation aggregation probability corresponding to each neighbor node label of the node.
10. The method of claim 8, wherein if the node is a common node, the method further comprises:
the first party calculates first label propagation aggregation probabilities corresponding to all neighbor node labels of the node in a first association network;
The second party calculates second label propagation aggregation probabilities corresponding to all neighbor node labels of the node in a second association network;
the first party and the second party interact the first tag propagation aggregation probability and the second tag propagation aggregation probability;
and the first party and the second party respectively conduct label propagation probability aggregation again based on the interaction information to obtain label propagation aggregation probabilities corresponding to each label.
11. The method as recited in claim 1, further comprising:
Determining the graph weights of the first association network and the second association network according to the node relation tightness degree of the first association network and the second association network, and
The graph weight is introduced in the interaction process of the first association network and the second association network.
12. The method of claim 11, wherein introducing the graph weights during interaction of the first associated network and the second associated network comprises:
If the node i is a common node, the edge weight and Σ jwij are determined using the following formula:
∑jwij＝θa∑awia+θb∑bwib;
Wherein Σ awia is the edge weight sum between the node i and all the neighbor nodes a of the first association network, Σ bwib is the edge weight sum between the node i and all the neighbor nodes b of the second association network, θ a is the graph weight of the first association network, and θ b is the graph weight of the second association network.
13. The method of claim 11, wherein introducing the graph weights during interaction of the first associated network and the second associated network comprises:
after the first party and the second party interact the first tag propagation aggregation probability and the second tag propagation aggregation probability, the tag propagation probability aggregation is performed again based on the graph weights of the first association network and the second association network, and the tag propagation aggregation probability corresponding to each tag is obtained.
14. The method as recited in claim 1, further comprising:
and if the first association network and the second association network are directed graph networks, only the inflow neighbor node of each node is used as the neighbor node.
15. A tag propagation apparatus of an associated network, comprising:
The diagram construction module is used for constructing a first association network based on the first party data and constructing a second association network based on the second party data;
the federation network module is used for associating the first association network with the second association network based on a security intersection protocol to obtain a federation association network;
The label propagation module is used for iteratively executing multiple rounds of label propagation on the nodes of the federal associated network, wherein each round of label propagation comprises the following steps:
Determining an edge weight w ij of an edge ij between a node i and a neighboring node j in the federation association network;
Determining edge weights and sigma jwij between the node i and all the neighbor nodes J;
Determining a tag propagation probability P ij of the neighbor node j for the node i according to the ratio of the edge weight w ij to the edge weight and sigma jwij;
and for each node, determining the round label of each node according to the round label of the neighbor node and the label propagation probability of the neighbor node to the node.
16. A tag propagation apparatus of an associated network, comprising:
The apparatus of claim 1-14, wherein the at least one processor is configured to execute the instructions, and wherein the memory is communicatively coupled to the at least one processor and stores instructions executable by the at least one processor to enable the at least one processor to perform the method.
17. A computer readable storage medium storing a program which, when executed by a multi-core processor, causes the multi-core processor to perform the method of any of claims 1-14.
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211492068.7A CN115733763B (en) | 2022-11-25 | 2022-11-25 | A method, device and computer-readable storage medium for label propagation of an associated network |
| PCT/CN2023/127581 WO2024109454A1 (en) | 2022-11-25 | 2023-10-30 | Label propagation method and apparatus for associated network, and computer readable storage medium |
| TW112144259A TWI895857B (en) | 2022-11-25 | 2023-11-16 | A network-related label propagation method, device, and computer-readable storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211492068.7A CN115733763B (en) | 2022-11-25 | 2022-11-25 | A method, device and computer-readable storage medium for label propagation of an associated network |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN115733763A CN115733763A (en) | 2023-03-03 |
| CN115733763B true CN115733763B (en) | 2025-06-20 |
Family
ID=85298377
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211492068.7A Active CN115733763B (en) | 2022-11-25 | 2022-11-25 | A method, device and computer-readable storage medium for label propagation of an associated network |
Country Status (3)
| Country | Link |
|---|---|
| CN (1) | CN115733763B (en) |
| TW (1) | TWI895857B (en) |
| WO (1) | WO2024109454A1 (en) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115733763B (en) * | 2022-11-25 | 2025-06-20 | 中国银联股份有限公司 | A method, device and computer-readable storage medium for label propagation of an associated network |
| CN118096417B (en) * | 2024-04-28 | 2024-07-19 | 江西求是高等研究院 | A method, system, computer and storage medium for discovering communication network patterns |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113095946A (en) * | 2021-04-28 | 2021-07-09 | 福州大学 | Insurance customer recommendation method and system based on federal label propagation |
| CN113254717A (en) * | 2021-06-10 | 2021-08-13 | 中国人民解放军国防科技大学 | Multidimensional graph network node clustering processing method, apparatus and device |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US9477541B2 (en) * | 2014-02-20 | 2016-10-25 | City University Of Hong Kong | Determining faulty nodes via label propagation within a wireless sensor network |
| CN106991614A (en) * | 2017-03-02 | 2017-07-28 | 南京信息工程大学 | The parallel overlapping community discovery method propagated under Spark based on label |
| US10922609B2 (en) * | 2017-05-17 | 2021-02-16 | Facebook, Inc. | Semi-supervised learning via deep label propagation |
| CN110136016B (en) * | 2019-04-04 | 2021-06-29 | 中国科学院信息工程研究所 | A method and system for multi-label propagation based on implicit association |
| US11514265B2 (en) * | 2019-09-26 | 2022-11-29 | Microsoft Technology Licensing, Llc | Inference via edge label propagation in networks |
| CN111723298B (en) * | 2020-05-11 | 2023-09-29 | 珠海高凌信息科技股份有限公司 | Social network community discovery method, device and medium based on improved tag propagation |
| CN114401134B (en) * | 2022-01-14 | 2023-12-15 | 深圳市兴海物联科技有限公司 | A distributed trusted management method for the Internet of Things with end-side collaboration |
| CN115733763B (en) * | 2022-11-25 | 2025-06-20 | 中国银联股份有限公司 | A method, device and computer-readable storage medium for label propagation of an associated network |
-
2022
- 2022-11-25 CN CN202211492068.7A patent/CN115733763B/en active Active
-
2023
- 2023-10-30 WO PCT/CN2023/127581 patent/WO2024109454A1/en not_active Ceased
- 2023-11-16 TW TW112144259A patent/TWI895857B/en active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113095946A (en) * | 2021-04-28 | 2021-07-09 | 福州大学 | Insurance customer recommendation method and system based on federal label propagation |
| CN113254717A (en) * | 2021-06-10 | 2021-08-13 | 中国人民解放军国防科技大学 | Multidimensional graph network node clustering processing method, apparatus and device |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2024109454A1 (en) | 2024-05-30 |
| TW202423089A (en) | 2024-06-01 |
| TWI895857B (en) | 2025-09-01 |
| CN115733763A (en) | 2023-03-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US10698885B2 (en) | Method and device for writing service data in block chain system | |
| JP7011083B2 (en) | Credit check system, method of storing credit check data, equipment and computer programs | |
| TWI682304B (en) | Abnormal account prevention and control method, device and equipment based on graph structure model | |
| CN112508075B (en) | DBSCAN clustering method based on transverse federation and related equipment thereof | |
| WO2021007863A1 (en) | Integrity auditing for multi-copy storage | |
| CN113297436B (en) | User policy distribution method and device based on relational graph network and electronic equipment | |
| CN113094739B (en) | Data processing method, device and server based on privacy protection | |
| CN107969154A (en) | Privacy management | |
| CN112559635B (en) | Service processing method, device, equipment and medium for Ethernet alliance chain node | |
| CN114896569A (en) | Blockchain-based code copyright registration system, method and platform | |
| TWI895857B (en) | A network-related label propagation method, device, and computer-readable storage medium | |
| CN112417485B (en) | A model training method, system and device based on a trusted execution environment | |
| CN115481440B (en) | Data processing methods, devices, electronic equipment and media | |
| CN116541870A (en) | Method and device for evaluating federal learning model | |
| CN112529102A (en) | Feature expansion method, device, medium, and computer program product | |
| CN114338527B (en) | IPv6 active identifier processing method and system | |
| CN116957112A (en) | Training method, device, equipment and storage medium of joint model | |
| CN116009792B (en) | A device and method for reading and writing data in image processing, and electronic equipment | |
| CN115150092B (en) | Method and device for creating service sub-chain, electronic equipment and computer storage medium | |
| CN117873554A (en) | Software release method, device and equipment | |
| Ji et al. | SEBF: A Single-Chain based Extension Model of Blockchain for Fintech. | |
| CN116842541A (en) | Data encryption and decryption processing method and device, computer equipment and storage medium | |
| CN117176322A (en) | Privacy set intersection system, method and device | |
| CN113722334A (en) | Data processing method and device, electronic equipment and medium | |
| CN119338028B (en) | Data prediction processing method, device, equipment and medium based on artificial intelligence |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |