Personalized node ranking method and system using random walk
View Patent ↗Provided is a personalized node ranking (PNR) system and method using random walk. In detail, a personalized ranking method using random walk includes verifying whether propagation of a positive score or a negative score of a currently-visiting node is trustworthy based on an edge sign between a seed node and a next-visiting node predicted by using a classification model, and when the propagation is trustworthy according to the verification, propagating a score by using a first score propagation method based on balance theory, and when the propagation is untrustworthy according to the verification, propagating a score by using a second score propagation method based on a ratio between a balanced triangle and an unbalanced triangle of a signed network.
1 . A personalized ranking method using random walk, the personalized ranking method comprising:
verifying whether propagation of a positive score or a negative score of a currently-visiting node is trustworthy based on an edge sign between a seed node and a next-visiting node predicted by using a classification model, wherein the seed node, the currently-visiting node, and the next-visiting node are included in a signed network; and
when the propagation is trustworthy according to the verification, propagating a score by using a first score propagation method based on balance theory, and when the propagation is untrustworthy according to the verification, propagating a score by using a second score propagation method based on a ratio between a balanced triangle and an unbalanced triangle of the signed network,
wherein each of a plurality of triangles is examined as to whether each of the plurality of triangles follow rules of the balance theory,
wherein, when a first prior sign of a first edge and a second prior sign of a second edge of a first triangle among the plurality of triangles are determined, the first triangle is classified into the balanced triangle or the unbalanced triangle according to a posterior sign of a third edge, and
wherein the verifying whether the propagation of the positive score or the negative score of the currently-visiting node is trustworthy comprises:
when a first condition regarding whether the predicted edge sign is same as a sign of a score propagated from the currently-visiting node to the next-visiting node is satisfied, determining that the score propagation is trustworthy, and
when the first condition is not satisfied, determining that the score propagation is untrustworthy.
2 . The personalized ranking method of claim 1 , wherein the verifying whether the propagation of the positive score or the negative score of the currently-visiting node is trustworthy further comprises,
when the first condition and a second condition regarding whether a confidence score of the predicted edge sign exceeds a threshold value are satisfied, determining that the score propagation is trustworthy, and when the first condition or the second condition is not satisfied, determining that the score propagation is untrustworthy.
3 . The personalized ranking method of claim 1 , wherein the classification model is a logistic regression classifier model,
wherein the logistic regression classifier model is trained by using, as an input, feature vector information comprising values corresponding to a plurality of topological features for a node pair with an edge sign.
4 . The personalized ranking method of claim 1 , wherein the classification model outputs a confidence score of the predicted edge sign.
5 . The personalized ranking method of claim 1 , wherein the first score propagation method comprises,
when an edge sign between the currently-visiting node and the next-visiting node is + and a positive score of the currently-visiting node is propagated, propagating the positive score of the currently-visiting node to a positive score of the next-visiting node,
when an edge sign between the currently-visiting node and the next-visiting node is + and a negative score of the currently-visiting node is propagated, propagating the negative score of the currently-visiting node to a negative score of the next-visiting node,
when an edge sign between the currently-visiting node and the next-visiting node is − and a positive score of the currently-visiting node is propagated, propagating the positive score of the currently-visiting node to a negative score of the next-visiting node, and
when an edge sign between the currently-visiting node and the next-visiting node is − and a negative score of the currently-visiting node is propagated, propagating the negative score of the currently-visiting node to a positive score of the next-visiting node.
6 . The personalized ranking method of claim 1 , wherein the second score propagation method comprises,
when a positive score of the currently-visiting node is propagated, distributing and propagating the positive score of the currently-visiting node to a positive score and a negative score of the next-visiting node according to a distribution ratio, and
when a negative score of the currently-visiting node is propagated, distributing and propagating the negative score of the currently-visiting node to a positive score and a negative score of the next-visiting node according to a distribution ratio.
7 . The personalized ranking method of claim 6 , wherein the distribution ratio is the ratio between the balanced triangle and the unbalanced triangle,
wherein the balanced triangle is a triangle satisfying the balance theory from among triangles satisfying transitivity, and the unbalanced triangle is a triangle not satisfying the transitivity, in the signed network.
8 . The personalized ranking method of claim 7 , wherein prior signs of the triangle comprise four types comprising (+, +), (+, −), (−, +), and (−, −),
wherein the distribution ratio is determined for each of the four types,
wherein, when a type of the prior signs is a type in which a sign of a score which is propagated from the currently-visiting node to the next-visiting node and an edge sign between the currently-visiting node and the next-visiting node are same, a score is propagated based on the distribution ratio.
9 . A personalized node ranking (PNR) system using random walk, the PNR system comprising:
a receiver configured to receive a signed network;
a memory configured to store one or more instructions; and
at least one processor configured to execute the one or more instructions to,
verify whether propagation of a positive score or a negative score of a currently-visiting node is trustworthy based on an edge sign between a seed node and a next-visiting node predicted by using a classification model, and
when the propagation is trustworthy according to the verification, propagate a score by using a first score propagation method based on balance theory, and when the propagation is untrustworthy according to the verification, propagate a score by using a second score propagation method based on a ratio between a balanced triangle and an unbalanced triangle of the signed network,
wherein the seed node, the currently-visiting node, and the next-visiting node are included in the signed network,
wherein each of a plurality of triangles is examined as to whether each of the plurality of triangles follow rules of the balance theory,
wherein, when a first prior sign of a first edge and a second prior sign of a second edge of a first triangle among the plurality of triangles are determined, the first triangle is classified into the balanced triangle or the unbalanced triangle according to a posterior sign of a third edge, and
wherein the at least one processor is further configured to execute the one or more instructions to:
when a first condition regarding whether the predicted edge sign is same as a sign of a score propagated to the next-visiting node from the currently-visiting node is satisfied, determine that the score propagation is trustworthy, and
when the first condition is not satisfied, determine that the score propagation is untrustworthy.
10 . The PNR system of claim 9 , wherein the at least one processor is further configured to execute the one or more instructions to
allow a random surfer starting from the seed node and performing the random walk to walk from the currently-visiting node to the next-visiting node,
repeatedly perform the random walk until positive scores and negative scores of all nodes of the signed network are converged, and
output node ranking from a viewpoint of the seed node based on the converged positive scores and the converged negative scores.
11 . The PNR system of claim 9 , wherein the at least one processor is further configured to execute the one or more instructions to,
when the first condition and a second condition regarding whether a confidence score of the predicted edge sign exceeds a threshold value are satisfied, determine that the score propagation is trustworthy, and when the first condition or the second condition is not satisfied, determine that the score propagation is untrustworthy.
12 . The PNR system of claim 9 , wherein the classification model is a logistic regression classifier model,
wherein the logistic regression classifier model is trained by using, as an input, feature vector information comprising values corresponding to a plurality of topological features for a node pair with an edge sign.
13 . The PNR system of claim 9 , wherein the classification model outputs a confidence score of the predicted edge sign.
14 . The PNR system of claim 9 , wherein the first score propagation method comprises,
when an edge sign between the currently-visiting node and the next-visiting node is + and a positive score of the currently-visiting node is propagated, propagating the positive score of the currently-visiting node to a positive score of the next-visiting node,
when an edge sign between the currently-visiting node and the next-visiting node is + and a negative score of the currently-visiting node is propagated, propagating the negative score of the currently-visiting node to a negative score of the next-visiting node,
when an edge sign between the currently-visiting node and the next-visiting node is − and a positive score of the currently-visiting node is propagated, propagating the positive score of the currently-visiting node to a negative score of the next-visiting node, and
when an edge sign between the currently-visiting node and the next-visiting node is − and a negative score of the currently-visiting node is propagated, propagating the negative score of the currently-visiting node to a positive score of the next-visiting node.
15 . The PNR system of claim 9 , wherein the second score propagation method comprises,
when a positive score of the currently-visiting node is propagated, distributing and propagating the positive score of the currently-visiting node to a positive score and a negative score of the next-visiting node according to a distribution ratio, and
when a negative score of the currently-visiting node is propagated, propagating the negative score of the currently-visiting node to a positive score and a negative score of the next-visiting node according to a distribution ratio.
16 . The PNR system of claim 15 , wherein the distribution ratio is the ratio between the balanced triangle and the unbalanced triangle,
wherein the balanced triangle is a triangle satisfying the balance theory from among triangles satisfying transitivity and the unbalanced triangle is a triangle not satisfying the transitivity, in the signed network.
17 . The PNR system of claim 16 , wherein the at least one processor is further configured to execute the one or more instructions to
determine the distribution ratio for each of four types of prior signs of the triangle, and
when a type of the prior signs is a type in which a sign of a score propagated from the currently-visiting node to the next-visiting node and an edge sign between the currently-visiting node and the next-visiting node are same, propagate a score based on the distribution ratio,
wherein the four types comprise (+, +), (+, −), (−, +), and (−, −).
18 . A non-transitory computer-readable recording medium storing a program for executing:
an operation of verifying whether propagation of a positive score or a negative score of a currently-visiting node is trustworthy based on an edge sign between a seed node and a next-visiting node predicted by using a classification model, wherein the seed node, the currently-visiting node, and the next-visiting node are included in a signed network; and
an operation of, when the propagation is trustworthy according to the verification, propagating a score by using a first score propagation method based on balance theory, and when the propagation is untrustworthy according to the verification, propagating a score by using a second score propagation method based on a ratio between a balanced triangle and an unbalanced triangle of the signed network,
wherein each of a plurality of triangles is examined as to whether each of the plurality of triangles follow rules of the balance theory,
wherein, when a first prior sign of a first edge and a second prior sign of a second edge of a first triangle among the plurality of triangles are determined, the first triangle is classified into the balanced triangle or the unbalanced triangle according to a posterior sign of a third edge, and
wherein the operation of the verifying whether the propagation of the positive score or the negative score of the currently-visiting node is trustworthy comprises:
an operation of, when a first condition regarding whether the predicted edge sign is same as a sign of a score propagated from the currently-visiting node to the next-visiting node is satisfied, determining that the score propagation is trustworthy, and
an operation of, when the first condition is not satisfied, determining that the score propagation is untrustworthy.