CN111506833A - A friend recommendation method based on the exact solution of single-source SimRank - Google Patents

Abstract

The invention discloses a friend recommendation method based on a single-source SimRank accurate solution, which comprises the following steps of: converting the target user, the user and the relationship among the users into a graph structure G; compute source node v_iConstructing a personalized Pepper rank vector with respect to the personalized Pepper ranks for all nodes on the graph

Calculating the probability of no-meeting of all nodes on the graph structure G to form a probability matrix of no-meeting

According to n-dimensional vectors

And no longer meeting probability matrix

Computing on a source node v_iObtaining n-dimensional vector according to the SimRank similarity

L rounds of SimRank similarity calculation are repeatedly performed and the n-dimensional vector is subjected to

Updating is carried out; finding n-dimensional vectors

And recommending the user corresponding to the t-dimension with the largest value as a result to the target user. The friend recommendation method based on the single-source SimRank accurate solution can ensure that the accurate solution of the single-source SimRank similarity on a large-scale user group can be obtained within effective time, and the quality and effect of a friend recommendation function are improved.

Description

A friend recommendation method based on the exact solution of single-source SimRank

technical field

The present invention relates to a recommendation method, in particular to a friend recommendation method based on a single-source SimRank exact solution.

Background technique

With the accelerated penetration of China's mobile Internet among citizens, there has been a massive growth in mobile social users. The "2019 China Mobile Social Industry Special Report" released by iiMedia Research shows that in 2018, the scale of China's mobile social networking users reached 737 million, and it is expected to continue to grow steadily in the next two years. It is expected to exceed 800 million in 2020. The group highlights the huge market space and also stimulates the emergence of various social software. According to the functions of social software, mainstream software can be roughly divided into instant messaging social applications represented by WeChat and QQ; media social applications represented by Weibo; interest social applications represented by Douban and Zhihu; and Dating social apps represented by Momo and Tantan.

Different types of social software have different functions, but they all generally support the friend recommendation function, that is, calculating the similarity between specified users according to the existing friend relationship network, and recommending users with high similarity but not yet friends to the specified users, so as to help Users find friends who share their interests.

In the process of friend recommendation, the accuracy of similarity calculation between users will directly affect the quality of recommendation results. Reasonable similarity measurement methods and accurate similarity calculation results are necessary conditions for accurate friend recommendation. Among them, SimRank similarity stands out among many similarity calculation methods with its intuitive design idea, practical recursive definition method, and high-quality calculation results, and has gradually become a widely used similarity measurement method. Therefore, in the application scenario of friend recommendation, people generally use the SimRank similarity result to measure the similarity between users.

At present, the algorithms of the prior art can achieve an accurate solution of SimRank similarity on a small-scale user group, but cannot calculate an accurate solution on a large graph.

Based on this, the inventors of the present application found that the algorithm of the prior art can implement SimRank similarity friend recommendation on a small-scale user group. With the rapid expansion of the user scale, the calculation time of SimRank similarity also increases. In the face of super-large user groups (such as Twitter, Weibo and other social applications with tens of millions of users), the existing methods cannot be used effectively. To accurately calculate the SimRank similarity between the user to be recommended and all users in time, only a certain degree of accuracy can be sacrificed to obtain the estimated value of the SimRank similarity, which greatly affects the quality and effect of the friend recommendation function.

The information disclosed in this Background section is only for enhancement of understanding of the general background of the invention and should not be taken as an acknowledgement or any form of suggestion that this information forms the prior art already known to a person of ordinary skill in the art.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a friend recommendation method based on a single-source SimRank accurate solution, which can improve the quality and effect of the friend recommendation function.

其中，

是n维向量，

的第k维存储的数为从源节点v_i出发的随机游走最终停止在节点v_k的概率，v_k为图结构中的任一节点，所述随机游走在每步游走时都以

的概率停止，以

的概率随机走向当前节点的任意入邻居节点；计算图结构G上所有节点的不再相遇概率，形成不再相遇概率矩阵

所述不再相遇概率矩阵

对角线上的第k个元素存储的数值为节点v_k的不再相遇概率

根据n维向量

以及不再相遇概率矩阵

计算关于源节点v_i的单源SimRank相似度，得到n维向量

重复执行L轮SimRank相似度的计算并对n维向量

进行更新，得到更新L轮后的n维向量

其中，

c为衰减系数，c∈[0，1]，ε为SimRank计算结果的绝对误差；找到n维向量

所有维中值最大的t维对应的节点，将这t个节点对应的用户作为结果推荐给目标用户。In order to achieve the above object, the present invention provides a method for recommending friends based on the exact solution of single-source SimRank, including: converting the relationship between target users, users and users into a graph structure G, wherein the graph structure G includes and The node corresponding to the user and the edge corresponding to the relationship between the users, the target user is the source node v _i of the graph structure, and the graph structure G includes n nodes; in the graph structure G, calculate The personalized page ranking of the source node v _i about all nodes on the graph, which constitutes the personalized page ranking vector

in,

is an n-dimensional vector,

The number stored in the kth dimension is the probability that the random walk starting from the source node v _i finally stops at the node v _k , v _k is any node in the graph structure, and the random walk starts at each step. by

the probability of stopping to

The probability of randomly going to any incoming neighbor node of the current node; calculating the no longer encounter probability of all nodes on the graph structure G, and forming the no longer encounter probability matrix

the no longer encounter probability matrix

The value stored in the kth element on the diagonal is the probability of no longer encountering the node v _k

According to the n-dimensional vector

and the no longer encounter probability matrix

Calculate the single-source SimRank similarity about the source node v _i to get an n-dimensional vector

Repeat L rounds of SimRank similarity computations for n-dimensional vectors

Update to get the n-dimensional vector after updating L rounds

in,

c is the attenuation coefficient, c∈[0, 1], ε is the absolute error of the SimRank calculation result; find the n-dimensional vector

For the node corresponding to the t dimension with the largest value among all dimensions, the user corresponding to the t node is recommended to the target user as the result.

包括：根据源节点v_i到节点v_k的出邻居节点的个性化佩奇排名向量，计算源节点v_i到节点v_k的个性化佩奇排名向量，其中，节点v_k为图结构G中的任一节点。In a possible implementation, in the graph structure G, the personalized Page rank of the source node v _i with respect to all nodes on the graph is calculated to form an n-dimensional vector

Including: according to the personalized page ranking vector of the outgoing neighbor nodes from the source node v _i to the node v _k , calculate the personalized page ranking vector from the source node v _i to the node v _k , wherein, the node v _k is in the graph structure G of any node.

进行更新，并对向量

进行存储，所述公式一包括：In a possible implementation manner, according to the personalized page ranking vector of the outgoing neighbor nodes from the source node v _i to the node v _k , calculating the personalized page ranking vector from the source node v _i to the node v _k includes: Obtain the probability transition matrix P of the graph structure G, where P is an n×n-dimensional matrix, and the value recorded at the jth row and the ith column is the probability of transferring from node v _i to node v _j one step along the incoming edge; according to the formula a pair

make an update and update the vector

For storage, the formula one includes:

均为n维向量，0≤i≤n-1，

及

初始化为

为除了第i维为1其余维均为0的n维向量，Among them, l is an intermediate variable, l=0, 1, ..., L; right

Both are n-dimensional vectors, 0≤i≤n-1,

and

initialized as

is an n-dimensional vector whose other dimensions are 0 except that the i-th dimension is 1,

进行更新的过程，获得更新后的n维向量

Repeat L times according to the formula for a pair

The update process is performed to obtain the updated n-dimensional vector

以及不再相遇概率矩阵

计算关于源节点v_i的单源SimRank相似度，得到n维向量

重复执行L轮SimRank相似度的计算并对n维向量

进行更新，得到更新L轮后的n维向量

包括：当进行第一轮计算时，根据以下公式计算SimRank相似度：In a possible implementation, the n-dimensional vector

and the no longer encounter probability matrix

Calculate the single-source SimRank similarity about the source node v _i to get an n-dimensional vector

Repeat L rounds of SimRank similarity computations for n-dimensional vectors

Update to get the n-dimensional vector after updating L rounds

Including: When the first round of calculation is performed, SimRank similarity is calculated according to the following formula:

进行更新，重复更新过程直至第L轮的计算，得到更新L轮后的n维向量

所述公式二为：When the calculation from the second round to the Lth round is carried out, according to the formula two pairs of n-dimensional vectors

Update, repeat the update process until the calculation of the Lth round, and obtain the n-dimensional vector after updating the L round

The second formula is:

为所述不再相遇概率矩阵，l为中间变量，l＝0，1，...，L；对

为n维向量。in,

is the no longer encounter probability matrix, l is an intermediate variable, l=0, 1, ..., L;

is an n-dimensional vector.

包括：获取图结构中的节点v_k；判断节点v_k的入度是否属于预设情况，所述预设情况包括节点v_k的入度为0或1；若属于，则根据所述预设情况返回节点v_k的不再相遇概率，当v_k的入度为0时，节点v_k的不再相遇概率

当v_k的入度为1时，节点v_k的不再相遇概率

若不属于，则计算从节点v_k出发的两条随机游走在第l步首次相遇于节点v_q的概率Z_l(k，q)，重复计算Z_l(k，q)直至从节点v_k延伸出的所有路径的长度之和E_k大于等于预设值，其中，所述预设值为

R(k)为需要从节点v_k处产生的随机游走的次数，

为所述n维向量

的第k维的值；获取从节点v_k延伸出的所有路径的长度之和E_k大于等于预设值时，两条随机游走走过的总层数l(k)；计算从节点v_k出发的两条产生随机游走在l(k)步之后相遇的概率，重复R(k)次上述产生随机游走在l(k)步之后相遇的概率的计算，所述产生随机游走为从节点v_k出发产生两条随机游走，在前l(k)步不停止，从第l(k)+1步起，每步游走时都以

的概率停止，以

的概率随机走向当前节点的任意入邻居；根据R(k)次产生随机游走的计算结果以及从节点v_k延伸出的所有路径的长度之和E_k大于等于预设值时上述Z_l(k，q)的计算结果计算节点v_k的不再相遇概率

并将节点v_k的不再相遇概率

存储至不再相遇矩阵

对角线上的第k个元素；更新k的值，并重复上述计算，直至节点v_k遍历图结构中所有节点。In a possible implementation manner, the no-meeting probability of all nodes in the graph structure G is calculated to form a no-meeting probability matrix

Including: acquiring the node v _k in the graph structure; judging whether the in-degree of the node v _k belongs to a preset situation, and the preset situation includes that the in-degree of the node v _k is 0 or 1; if so, according to the preset The situation returns the no longer encounter probability of node v _k , when the in-degree of v _k is 0, the no longer encounter probability of node v _k

When the in-degree of v _k is 1, the no longer encounter probability of node v _k

If not, calculate the probability Z _l (k, q) that the two random walks from node v _k meet for the first time at node v _q at the lth step, and repeat the calculation of Z _l (k, q) until the node v The sum E _k of the lengths of all paths extended by _k is greater than or equal to a preset value, wherein the preset value is

R(k) is the number of random walks that need to be generated from node v _k ,

for the n-dimensional vector

The value of the k-th dimension of ; obtain the sum of the lengths of all paths extending from node v _k E _k is greater than or equal to the preset value, the total number of layers l(k) traveled by two random walks; calculate from node v The probability that the two random walks starting from _k meet after l(k) steps, repeat R(k) times the above calculation of the probability that the random walks meet after l(k) steps. In order to generate two random walks starting from node v _k , it does not stop in the first l(k) steps, starting from the l(k)+1 step, each walk starts with

the probability of stopping to

The probability of randomly walking to any incoming neighbor of the current node; according to the calculation result of R(k) random walks and the sum of the lengths of all paths extending from the node v _k E _k is greater than or equal to the preset value when the above Z _l ( The calculation result of k, q) calculates the no longer encounter probability of node v _k

and set the no longer encounter probability of node v _k

Store to Never Encounter Matrix

The kth element on the diagonal; update the value of k, and repeat the above calculation until node v _k traverses all nodes in the graph structure.

In a possible implementation manner, the probability Z _l (k, q) that two random walks starting from node v _k first meet at node v _q in the lth step are calculated, and Z _l (k, q) is repeatedly calculated. _q ) Until the sum of the lengths E _k of all paths extending from the node v _k is greater than or equal to the preset value, including: according to the probability (P ^T ) ^l ( _k , q), calculate the probability Z _l (k, q) that two random walks starting from node v _k meet at node v _q for the first time at the lth step; for all (P ^T ) ^ll′ (k, q′)> 0 node v _q' , update (P ^T ) ^l'+1 (q', q), E _k and l' until l'=l, where (P ^T ) ^ll' (k, q' ) represents the probability that node v _k is transferred to node v _q' through 1' steps, (P ^T ) ^l'+1 (q', q) represents the probability that node v _k is transferred to node v _q' through l'+1 steps probability; update the value of l; repeat the above steps until E _k is greater than or equal to the preset value.

In a possible implementation manner, according to the probability (P ^T ) ^l (k, q) of the node v _k to transfer to the node v _q after l steps along the incoming edge, calculate the two paths starting from the node v _k The probability Z _l (k, q) that a random walk encounters node v _q for the first time at step l consists of:

Execute the calculation process of Z _l (k, q) according to formula three, and the formula three is:

为从节点v_k出发的两条随机游走在第l步之前相遇于节点v_q并且在达到节点v_q前已经相遇过的概率，(P^T)^l(k，q)表示节点v_k沿入边经过l步转移至节点v_q的概率，(P^T)⁰(k，k)被初始化为1，对

(P^T)⁰(k，x)被初始化为0，对

(P^T)^l(k，x)被初始化为0；l为中间变量，初始化为0。Among them, c ^l ((P ^T ) ^l (k, q)) ² is the probability that two random walks starting from node v _k meet at node v _q at the lth step,

is the probability that two random walks starting from node v _k meet at node v _q before the lth step and have already met before reaching node v _q , (P ^T ) ^l (k, q) represents node v _k along the The probability that the incoming edge transfers to the node v _q after l steps, (P ^T ) ⁰ (k, k) is initialized to 1, and the

(P ^T ) ⁰ (k, x) is initialized to 0, for

(P ^T ) ^l (k, x) is initialized to 0; l is an intermediate variable, initialized to 0.

In one possible implementation, for all nodes v _q' where (P ^T ) ^11' (k, q')>0, for (P ^T ) ^l'+1 (q', q), E _k and l' to update includes:

According to formula 4, all nodes v _q , where (P ^T ) ^11′ (k, q′)>0 are updated, and (P ^T ) ^l′+1 (q′, q), E _k and l′ are updated, so The fourth formula is:

(P ^T ) ^l'+1 (q', q)=(P ^T ) ^l'+1 (q', q)+(P ^T ) ^l' (q', x)/d _in (v _x )

E _k =E _k +1

l'=l'+1

Among them, the node v _x represents all nodes with (P ^T ) ^l′ (q′, x)>0.

包括：In a possible implementation manner, the above _{Z l (} The calculation result of k, q) calculates the no longer encounter probability of node v _k

include:

所述公式五为：Calculate the no longer encounter probability of node k according to formula 5

The formula five is:

表示从节点vk出发的两条产生随机游走在l(k)步之后相遇的概率，c^l(k)表示两条随机游走在前l步不停止的概率，l(k)为E_k大于等于预设值时变量l的值，Z_l(k，q)为从节点v_k出发的两条随机游走在第l步首次相遇于节点v_q的概率；I(w)为指示器变量，用于计数第w次产生随机游走的过程中随机游走是否相遇，w小于等于R(k)，当第w次产生的两条随机游走相遇时I(w)＝1，否则I(w)＝0。in,

represents the probability that two random walks from node vk meet after l(k) steps, c ^l(k) represents the probability that the two random walks do not stop in the first l steps, and l(k) is E _k The value of variable l when it is greater than or equal to the preset value, Z _l (k, q) is the probability that two random walks starting from node v _k meet at node v _q for the first time at step l; I(w) is the indicator A variable used to count whether random walks meet during the wth generation of random walks, w is less than or equal to R(k), I(w)=1 when two random walks generated at the wth generation meet, otherwise I(w)=0.

In a possible implementation manner, the recommending the users corresponding to the t nodes as a result to the target user includes: the found t nodes correspond to users in the social network; excluding the users who already have friend relationships with the users to be recommended users, and recommend the remaining users to the target users.

进行更新，找到n维向量

所有维中值最大的t维对应的节点，将这t个节点对应的用户作为结果推荐给目标用户，可以在O(logn/ε²+m log(1/ε))的时间复杂度下得到所有用户与待推荐用户间的SimRank相似度估计值，并且用户与待推荐用户间SimRank相似度的估计值与真实值之间的绝对误差不超过ε。当设置ε＝10^-7并使用Float变量类型存储SimRank结果时，可以保证在有效时间内得到SimRank相似度的精确解，提高好友推荐功能的质量和效果。Compared with the prior art, the method for friend recommendation based on the exact solution of single-source SimRank provided by this embodiment repeatedly performs L rounds of single-source SimRank similarity calculation and compares the n-dimensional vector

make an update to find an n-dimensional vector

The node corresponding to the t dimension with the largest median value in all dimensions, and the user corresponding to the t node is recommended to the target user as the result, which can be obtained under the time complexity of O(logn/ε ² +m log(1/ε)) The estimated value of SimRank similarity between all users and the user to be recommended, and the absolute error between the estimated value of the SimRank similarity between the user and the user to be recommended and the real value does not exceed ε. When setting ε=10 ^-7 and using the Float variable type to store the SimRank results, the accurate solution of the SimRank similarity can be obtained within the effective time, and the quality and effect of the friend recommendation function can be improved.

Further, the method for recommending friends based on the exact solution of single-source SimRank provided by this embodiment does not require preprocessing of graph structure, and can accurately calculate dynamically changing groups (such as the appearance of new users, the logout of existing users, and the relationship between friends. Changes, etc.) of the single-source SimRank similarity, to achieve friend recommendation for dynamically changing user groups.

Description of drawings

1 is a flowchart of a friend recommendation method based on a single-source SimRank accurate solution provided according to an embodiment of the present invention;

FIG. 2 is a flowchart of an implementation manner of step S3 provided according to an embodiment of the present invention.

Detailed ways

The specific embodiments of the present invention will be described in detail below with reference to the accompanying drawings, but it should be understood that the protection scope of the present invention is not limited by the specific embodiments.

Unless expressly stated otherwise, throughout the specification and claims, the term "comprising" or its conjugations such as "comprising" or "comprising" and the like will be understood to include the stated elements or components, and Other elements or other components are not excluded.

As shown in FIG. 1 , it is a flowchart of a friend recommendation method based on a single-source SimRank exact solution according to a preferred embodiment of the present invention, including steps S1-S5.

In step S1, the relationship between the target user, the user and the user is converted into a graph structure G, wherein the graph structure G includes a node corresponding to the user and an edge corresponding to the relationship between the users, so The target user is the source node v _i of the graph structure, and the graph structure G includes n nodes.

The users in this embodiment refer to all registered users on the platform, and the relationship between users may specifically be a follow relationship between users. For example, all registered friends and friends network on facebook.

Specifically, for social networks such as Weibo, Facebook, and Instagram that have following relationships, we map the users of the social network to nodes on the graph structure, and the attention relationships between users correspond to the edges on the graph structure. Specifically, if user A follows user B, a directed edge from user B to user A needs to be established in the graph structure. (Example B->A), where B is the incoming neighbor node of A, A is the outgoing neighbor node of B, this edge is the outgoing edge of node B and the incoming edge of node A. We call the number of outgoing edges a node has as "out-degree" and the number of incoming edges it has as "in-degree".

For social networks with friend relationships such as WeChat and QQ, we map users on the social network to graph nodes, and friend relationships to edges on the graph structure. Specifically, if there is a friend relationship between user A and user B (that is, A and B are friends with each other), a directed edge from user A to user B and a directed edge from user B to user B are established on the graph structure. A directed edge of user node.

其中，

是n维向量，

的第k维存储的数为从源节点v_i出发的随机游走最终停止在节点v_k的概率，v_k为图结构中的任一节点，所述随机游走在每步游走时都以

的概率停止，以

的概率随机走向当前节点的任意入邻居节点；In step S2, in the graph structure G, the personalized page ranking of the source node v _i with respect to all nodes on the graph is calculated to form the personalized page ranking vector

in,

is an n-dimensional vector,

The number stored in the kth dimension is the probability that the random walk starting from the source node v _i finally stops at the node v _k , v _k is any node in the graph structure, and the random walk starts at each step. by

the probability of stopping to

The probability of randomly going to any incoming neighbor node of the current node;

所述不再相遇概率矩阵

对角线上的第k个元素存储的数值为节点v_k的不再相遇概率

In step S3, the no longer encounter probability of all nodes on the graph structure G is calculated to form a no longer encounter probability matrix

the no longer encounter probability matrix

The value stored in the kth element on the diagonal is the probability of no longer encountering the node v _k

以及不再相遇概率矩阵

计算关于源节点vi的单源SimRank相似度，得到n维向量

重复执行L轮SimRank相似度的计算并对n维向量

进行更新，得到更新L轮后的n维向量

其中，

c为衰减系数，c∈[0，1]，ε为SimRank计算结果的绝对误差；In step S4, according to the n-dimensional vector

and the no longer encounter probability matrix

Calculate the single-source SimRank similarity about the source node vi to get an n-dimensional vector

Repeat L rounds of SimRank similarity computations for n-dimensional vectors

Update to get the n-dimensional vector after updating L rounds

in,

c is the attenuation coefficient, c∈[0, 1], ε is the absolute error of the SimRank calculation result;

所有维中值最大的t维对应的节点，将这t个节点对应的用户作为结果推荐给目标用户。In step S5, find the n-dimensional vector

For the node corresponding to the t dimension with the largest value among all dimensions, the user corresponding to the t node is recommended to the target user as the result.

It should be noted that the value stored in each dimension of the SimRank vector corresponds to the estimated value of the SimRank similarity between a node on the graph structure and the source node v _i , and then obtains the SimRank between a user in the social network and the target user. An estimate of similarity.

进行更新，找到n维向量

所有维中值最大的t维对应的节点，将这t个节点对应的用户作为结果推荐给目标用户，可以在O(log n/ε²+m log(1/ε))的时间复杂度下得到所有用户与待推荐用户间的SimRank相似度估计值，并且用户与待推荐用户间SimRank相似度的估计值与真实值之间的绝对误差不超过ε。当设置ε＝10^-7并使用Float变量类型存储SimRank结果时，可以保证在有效时间内得到大规模用户群体上的单源SimRank相似度的精确解，提高好友推荐功能的质量和效果。Therefore, through the method for friend recommendation based on the exact solution of single-source SimRank provided in this embodiment, L rounds of SimRank similarity calculation are repeatedly performed and the n-dimensional vector

make an update to find an n-dimensional vector

For the node corresponding to the t dimension with the largest median value among all dimensions, the user corresponding to the t node is recommended to the target user as the result, which can be done in the time complexity of O(log n/ε ² +m log(1/ε)) Obtain the estimated value of SimRank similarity between all users and the user to be recommended, and the absolute error between the estimated value of SimRank similarity between the user and the user to be recommended and the real value does not exceed ε. When ε=10 ^-7 is set and the SimRank result is stored in the Float variable type, it can ensure that the accurate solution of the single-source SimRank similarity on a large-scale user group can be obtained within an effective time, and the quality and effect of the friend recommendation function can be improved.

相比，本方法的复杂度避免了较大的n和较小的ε²同时出现在分子分母使得复杂度结果较大的情况出现，因此可以在有效时间内计算ε＝10^-7的单源SimRank结果。The recommended method provided in this embodiment has a complexity of O(log n/ε ² +m log(1/ε)), which is different from the complexity of most other algorithms.

In contrast, the complexity of this method avoids the situation that a large n and a small ε ² appear in the numerator and denominator at the same time, which makes the complexity result larger, so the single source of ε = 10 ^-7 can be calculated in effective time. SimRank results.

In addition, the recommendation method provided in this embodiment does not require preprocessing of the graph structure, and can accurately calculate the SimRank similarity of dynamically changing groups (such as the emergence of new users, the logout of existing users, and the change of friendship relationships, etc.). Implement friend recommendation for dynamically changing user groups.

In an implementation manner, step S5 may include: the found t nodes correspond to users in the social network; excluding users who have friends with the user to be recommended, and recommending the remaining users to the target user.

In an implementation manner, step S2 may further include:

According to the personalized page ranking vector of the outgoing neighbor nodes from the source node v _i to the node v _k , the personalized page ranking vector from the source node v _i to the node v _k is calculated, wherein the node v _k is any node in the graph structure G. a node.

Specifically, it can be achieved in the following ways:

Obtain the probability transition matrix P of the graph structure G, where P is an n×n-dimensional matrix, and the value recorded at the j-th row and the i-th column is the probability of transitioning from node v _i to node v _j along the incoming edge in one step;

进行更新，并对向量

进行存储，所述公式(1)包括：According to formula (1),

make an update and update the vector

For storage, the formula (1) includes:

均为n维向量，0≤i≤n-1，

及

初始化为

为除了第i维为1其余维均为0的n维向量，Among them, l is an intermediate variable, l=0, 1, ..., L; right

Both are n-dimensional vectors, 0≤i≤n-1,

and

initialized as

is an n-dimensional vector whose other dimensions are 0 except that the i-th dimension is 1,

进行更新的过程，得到更新后的n维向量

Repeat L times according to the formula for a pair

The update process is performed to obtain the updated n-dimensional vector

As shown in FIG. 2 , which is a flowchart of an implementation manner of step S3 in this embodiment, including steps S31 to S38 .

In step S31, the node v _k in the graph structure is acquired.

In step S32, it is determined whether the in-degree of the node v _k belongs to a preset situation, and the preset situation includes that the in-degree of the node v _k is 0 or 1;

当d_in(v_k)＝1时，节点v_k的不再相遇概率

d_in(v_k)表示图结构上节点v_k的入度。In step S33, if it belongs to, return the no longer encounter probability of node v _k according to the preset situation, when d _in (v _k )=0, the no longer encounter probability of node v _k

When d _in (v _k )=1, the no longer encounter probability of node v _k

d _in (v _k ) represents the in-degree of node v _k on the graph structure.

R(k)为需要从节点v_k处产生的随机游走的次数，

为所述n维向量

的第k维的值；In step S34, if not, then calculate the probability Z _l (k, q) that the two random walks starting from node v _k meet at node v _q for the first time in the first step, and repeat the calculation of Z _l (k, q ) until the sum of the lengths of all paths extending from the node v _k E _k is greater than or equal to a preset value, wherein the preset value is

R(k) is the number of random walks that need to be generated from node v _k ,

for the n-dimensional vector

The value of the kth dimension of ;

In step S35, when the sum of the lengths of all paths extending from the node v _k E _k is greater than or equal to a preset value, the total number of layers l(k) traveled by the two random walks is obtained;

的概率停止，以

的概率随机走向当前节点的任意入邻居；In step S36, calculate the probability that the two random walks from node v _k meet after l(k) steps, and repeat the above-mentioned random walks for R(k) times to meet the probability after l(k) steps The calculation of the random walk is to generate two random walks starting from the node v _k , which does not stop in the first l(k) steps, and starts from the l(k)+1th step.

the probability of stopping to

The probability of randomly walking to any incoming neighbor of the current node;

并将节点v_k的不再相遇概率

存储至不再相遇矩阵

对角线上的第k个元素；In step S37, according to the calculation result of generating random walks R(k) times and the above-mentioned calculation of Z _l (k, q) when the sum of the lengths of all paths extending from node v _k E _k is greater than or equal to a preset value The result calculates the no longer encounter probability of node v _k

and set the no longer encounter probability of node v _k

Store to Never Encounter Matrix

the kth element on the diagonal;

所述公式(5)为：The implementation manner of step S34-step S37 may include: calculating the no longer encounter probability of node k according to formula (5)

The formula (5) is:

表示从节点v_k出发的两条产生随机游走在l(k)步之后相遇的概率，c^l(k)表示两条随机游走在前l步不停止的概率；l(k)为E_k大于等于预设值时变量l的值，Z_l(k，q)为从节点v_k出发的两条随机游走在第l步首次相遇于节点v_q的概率；I(w)为指示器变量，当第w次产生的两条随机游走相遇时I(w)＝1，否则I(w)＝0。in,

Represents the probability that two random walks from node v _k meet after l(k) steps, c ^l(k) represents the probability that the two random walks do not stop in the first l steps; l(k) is E The value of variable l when _k is greater than or equal to the preset value, Z _l (k, q) is the probability that two random walks starting from node v _k meet at node v _q for the first time at step l; I(w) is the indicator variable, I(w)=1 when the two random walks generated at the wth meet, otherwise I(w)=0.

In step S38, the value of k is updated, and the above calculation is repeated until the node v _k traverses all nodes in the graph structure.

的计算分成了两部分，前l(k)层的不再相遇概率由步骤S34确定性地算出(即公式(5)中含有Z_l(k，q)的一项)，l(k)到L层的不再相遇概率由步骤S36通过产生随机游走的方法得到。确定性的计算过程结果准确但费时，随机游走的计算方法省时但会引入误差，将

拆成两部分的目的是平衡二者的优缺点，通过l(k)的选取找到时间最短、结果最准确的平衡点。l(k) is the value of the variable l when E _k is greater than or equal to the preset value, indicating the number of layers with the probability of no longer encountering after deterministic calculation. After step S34 is executed, the value of l(k) is also determined, so it can be used in the calculation of formula (5). As can be seen from equation (5), we will no longer meet the probability

The calculation of , is divided into two parts, and the no longer encounter probability of the first l(k) layer is deterministically calculated by step S34 (that is, the item containing Z _l (k, q) in formula (5)), l(k) to The no longer encounter probability of the L layer is obtained by generating a random walk in step S36. The deterministic calculation process results are accurate but time-consuming, while the random walk calculation method saves time but introduces errors.

The purpose of splitting it into two parts is to balance the advantages and disadvantages of the two, and find the balance point with the shortest time and the most accurate result through the selection of l(k).

的估计值，进而得到不再相遇概率矩阵

矩阵

是一个对角矩阵，即只有对角线上的元素非0，矩阵

对角线上的第k个元素存储的数值即为节点v_k的不再相遇概率

矩阵

的估计值会被用于SimRank相似度的计算中。It should be noted that the above steps calculate the no longer encounter probability of each node v _k on the graph

The estimated value of , and then the probability matrix of no longer encounters is obtained

matrix

is a diagonal matrix, that is, only the elements on the diagonal are non-zero, the matrix

The value stored in the kth element on the diagonal is the probability of no longer encountering the node v _k

matrix

The estimated value of is used in the calculation of SimRank similarity.

In an implementation manner, step S34 may include: step S341-step S344.

Step S341, according to the probability (P ^T ) ^l (k, q) that the node v _k is transferred to the node v _q through l steps along the incoming edge, calculate that the two random walks starting from the node v _k meet for the first time at the lth step. The probability Z _l (k, q) of the node v _q .

Among them, P ^T is the transpose of the matrix P, P is an n×n-dimensional matrix, and the value recorded at the j-th row and the i-th column is the probability of transferring from the node v _i to the node v _j one step along the incoming edge”, P ^T (i, j)=P(j, i), the value recorded at the i-th row and the j-th column of P ^T is the probability of transferring from node v _i to node v _j one step along the incoming edge.

的概率停止，而步骤S341中的转移是指从节点v_k沿入边不停止地走到节点v_q的概率。It should be noted that, in this embodiment, the random walk is from v _k along the incoming edge to the node v _q through l steps, which means that in each step of the walk, the

The probability of stopping, and the transition in step S341 refers to the probability of going from node v _k to node v _q along the incoming edge without stopping.

The calculation process of Z _l (k, q) is performed according to formula (3), and the formula (3) is:

Z₀(k，x)初始化为0；c^l((P^T)^l(k，q))²为从节点v_k出发的两条随机游走在第l步相遇于节点v_q的概率，

为从节点v_k出发的两条随机游走在第l步之前相遇于节点v_q并且在达到节点v_q前已经相遇过的概率，(P^T)^l(k，q)表示节点v_k沿入边经过l步转移至节点v_q的概率，(P^T)⁰(k，k)被初始化为1，对

(P^T)⁰(k，x)被初始化为0，对

(P^T)^l(k，x)被初始化为0；l为中间变量，初始化为0。Among them, Z _l (k, q) represents the probability that two random walks starting from node v _k meet at node v _q for the first time in the lth step, Z ₀ (k, k) is initialized to 1, and

Z ₀ (k, x) is initialized to 0; c ^l ((P ^T ) ^l (k, q)) ² is the probability that two random walks starting from node v _k meet at node v _q at the lth step,

is the probability that two random walks starting from node v _k meet at node v _q before the lth step and have already met before reaching node v _q , (P ^T ) ^l (k, q) represents node v _k along the The probability that the incoming edge transfers to the node v _q after l steps, (P ^T ) ⁰ (k, k) is initialized to 1, and the

(P ^T ) ⁰ (k, x) is initialized to 0, for

(P ^T ) ^l (k, x) is initialized to 0; l is an intermediate variable, initialized to 0.

Equation (3) indicates that for the current l, Z _l (k) is calculated from the values of (P ^T ) ^l (k, q), (P ^T ) ^l′ (q′, q) and Z _11′ (k, q′) , q).

Step S342, update (P ^T ) ^l'+1 (q', q), E _k and l' for all nodes v _q' with (P ^T ) ^11' (k, q')>0, until l'=l, where (P ^T ) ^11' (k, q') represents the probability that node v _k is transferred to node v _q' after 11' steps, and P ^l'+1 (q', q) represents node v _q' is the probability of transitioning to node v _k after l'+1 steps.

Update (P ^T ) ^l'+1 (q', q), E _k and l' for all nodes v _q' where (P ^T ) ^11' (k, q')>0 according to formula (4) , the formula (4) is:

(P ^T ) ^l'+1 (q', q)=(P ^T ) ^l'+1 (q', q)+(P ^T ) ^l' (q', x)/d _in (v _x )

(P ^T ) ^ll′ (k, q′) represents the probability that node v _k is transferred to node v _q′ along the incoming edge through ll′ steps. (P ^T ) ^l' (q', x) represents the probability that node v _g' transfers to node v _x through l' steps along the incoming edge. In the update process, the (P ^T ) ^11′ (k, q′) of each point is different, where (P ^T ) ^11′ (k, q′)>0 means to select (P ^T ) ^11′ (k, q')>0 point. (P ^T ) ^l'+1 (q', q) represents the probability that the node v _q ' is transferred to the node v _q' through l'+1 steps along the incoming edge, and the node v _x represents all (P ^T ) ^l' (q ', x)>0 nodes.

Step S343, update the value of l, l=l+1;

Step S344, repeating the above steps until E _k is greater than or equal to the preset value.

In an implementation manner, step S4 may include:

When the first round of calculations is performed, the SimRank similarity is calculated according to the following formula:

进行更新，重复更新过程直至第L轮的计算，得到更新L轮后的n维向量

所述公式(2)为：When the calculation from the second round to the Lth round is carried out, according to the formula two pairs of n-dimensional vectors

Update, repeat the update process until the calculation of the Lth round, and obtain the n-dimensional vector after updating the L round

The formula (2) is:

为所述不再相遇概率矩阵，l为中间变量，l＝0，1，...，L；对

为n维向量。

为步骤2的计算过程中存储的值。in,

is the no longer encounter probability matrix, l is an intermediate variable, l=0, 1, ..., L;

is an n-dimensional vector.

The value stored during the calculation of step 2.

Formula (2) needs to be repeated for L rounds to ensure that the finally obtained SimRank vector is below the absolute error of ε. Denote the SimRank vector obtained after l rounds of calculation as

Thus, the estimation result of the SimRank vector under the absolute error of ε can be obtained, and the value stored in each dimension of the SimRank vector corresponds to the estimated value of the SimRank similarity between a node on the graph structure and the source node v _i , and then obtain An estimate of the SimRank similarity between a user in a social network and a target user.

As will be appreciated by those skilled in the art, the embodiments of the present application may be provided as a method, a system, or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the present application. It will be understood that each flow and/or block in 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 the processor of a general purpose computer, special purpose computer, embedded processor or other programmable data processing device to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing device produce Means for implementing the functions specified in a flow or flow of a flowchart and/or a block or blocks of a block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions The apparatus implements the functions specified in the flow or flow of the flowcharts and/or the block or blocks of the block diagrams.

These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in the flow or blocks of the flowcharts and/or the block or blocks of the block diagrams.

The foregoing descriptions of specific exemplary embodiments of the present invention have been presented for purposes of illustration and description. These descriptions are not intended to limit the invention to the precise form disclosed, and obviously many changes and modifications are possible in light of the above teachings. The exemplary embodiments were chosen and described for the purpose of explaining certain principles of the invention and their practical applications, to thereby enable others skilled in the art to make and utilize various exemplary embodiments and various different aspects of the invention. Choose and change. The scope of the invention is intended to be defined by the claims and their equivalents.

Claims (10)

1. a friend recommendation method based on single-source SimRank accurate solution, is characterized in that, comprises: Convert the relationship between target users, users and users into a graph structure G, wherein the graph structure G includes nodes corresponding to the users and edges corresponding to the relationship between the users, and the target users are all Describe the source node v _i of the graph structure, and the graph structure G includes n nodes; In the graph structure G, calculate the personalized page ranking of the source node v _i with respect to all nodes on the graph, and form the personalized page ranking vector

in,

is an n-dimensional vector,

The number stored in the kth dimension is the probability that the random walk starting from the source node v _i finally stops at the node v _k , v _k is any node in the graph structure, and the random walk starts at each step. by

the probability of stopping to

The probability of randomly going to any incoming neighbor node of the current node; Calculate the no longer encounter probability of all nodes on the graph structure G, and form a no longer encounter probability matrix

the no longer encounter probability matrix

The value stored in the kth element on the diagonal is the probability of no longer encountering the node v _k

According to the n-dimensional vector

and the no longer encounter probability matrix

Calculate the single-source SimRank similarity about the source node v _i to get an n-dimensional vector

Repeat L rounds of SimRank similarity computations for n-dimensional vectors

Update to get the n-dimensional vector after updating L rounds

in,

c is the attenuation coefficient, c∈[0, 1], ε is the absolute error of the SimRank calculation result; find n-dimensional vector

For the node corresponding to the t dimension with the largest value among all dimensions, the user corresponding to the t node is recommended to the target user as the result. 2. The friend recommendation method according to claim 1, characterized in that, in the graph structure G, the personalized Page rank of the source node v _i with respect to all nodes on the graph is calculated to form an n-dimensional vector

include: According to the personalized page ranking vector of the outgoing neighbor nodes from the source node v _i to the node v _k , the personalized page ranking vector from the source node v _i to the node v _k is calculated, wherein the node v _k is any node in the graph structure G. a node. 3. The friend recommendation method according to claim 2, characterized in that, according to the personalized Page rank vector of the outgoing neighbor nodes from the source node v _i to the node v _k , the calculation from the source node v _i to the node v _k is performed. Personalized page ranking vectors include: Obtain the probability transition matrix P of the graph structure G, where P is an n×n-dimensional matrix, and the value recorded at the j-th row and the i-th column is the probability of transitioning from node v _i to node v _j along the incoming edge in one step; According to the formula a pair

make an update and update the vector

For storage, the formula one includes:

Among them, l is an intermediate variable, l=0, 1, ..., L; right

Both are n-dimensional vectors, 0≤i≤n-1,

and

initialized as

is an n-dimensional vector whose other dimensions are 0 except that the i-th dimension is 1,

Repeat L times according to the formula for a pair

The update process is performed to obtain the updated n-dimensional vector

4. The friend recommendation method according to claim 3, wherein the method is based on an n-dimensional vector

and the no longer encounter probability matrix

Calculate the single-source SimRank similarity about the source node v _i to get an n-dimensional vector

Repeat L rounds of SimRank similarity computations for n-dimensional vectors

Update to get the n-dimensional vector after updating L rounds

include: When the first round of calculations is performed, the SimRank similarity is calculated according to the following formula:

When the calculation from the second round to the Lth round is performed, according to the formula two, the n-dimensional vector is paired

Update, repeat the update process until the calculation of the Lth round, and obtain the n-dimensional vector after updating the L round

The second formula is:

in,

is the no longer encounter probability matrix, l is an intermediate variable, l=0, 1, ..., L;

is an n-dimensional vector. 5. friend recommendation method as claimed in claim 2 is characterized in that, the no longer encounter probability of all nodes in the described calculation graph structure G, forms no longer encounter probability matrix

include: Get the node v _k in the graph structure; Determine whether the in-degree of the node v _k belongs to a preset situation, and the preset situation includes that the in-degree of the node v _k is 0 or 1; If it is, return the no longer encounter probability of node v _k according to the preset situation, when the in-degree of v _k is 0, the no longer encounter probability of node v _k

When the in-degree of v _k is 1, the no longer encounter probability of node v _k

If not, calculate the probability Z _l (k, q) that the two random walks from node v _k meet for the first time at node v _q at the lth step, and repeat the calculation of Z _l (k, q) until the node v The sum E _k of the lengths of all paths extended by _k is greater than or equal to a preset value, wherein the preset value is

R(k) is the number of random walks that need to be generated from node v _k ,

for the n-dimensional vector

The value of the kth dimension of ; Obtain the total number of layers l(k) traveled by two random walks when the sum of the lengths of all paths extending from node v _k E _k is greater than or equal to the preset value; Calculate the probability that the two random walks generated from node v _k meet after l(k) steps, and repeat the above calculation of the probability that the random walks meet after l(k) steps for R(k) times. To generate random walks, two random walks are generated from the node v _k , which do not stop in the first l(k) steps, and start from the l(k)+1 step.

the probability of stopping to

The probability of randomly walking to any incoming neighbor of the current node; Calculate the node v _k according to the calculation result of generating random _walks R(k) times and the sum of the lengths E _k of all paths extending from the node v _k is greater than or equal to the preset value. probability of never meeting again

and set the no longer encounter probability of node v _k

Store to Never Encounter Matrix

the kth element on the diagonal; Update the value of k and repeat the above calculation until node v _k traverses all nodes in the graph structure. 6. The method for recommending friends as claimed in claim 5, characterized in that, said calculating the probability Z _l (k, q) that two random walks starting from node v _k meet at node v _q for the first time in the lth step , and repeatedly calculate Z _l (k, q until the sum of the lengths of all paths extending from node v _k E _k is greater than or equal to the preset value, including: According to the probability that node v _k is transferred to node v _q in l steps along the incoming edge

Calculate the probability Z _l (k, q) that two random walks starting from node v _k meet at node v _q for the first time at step l; to all

the node v _q′ , right

E _k and l' are updated until l'=l, where,

represents the probability that node v _k is transferred to node v _q' after ll' steps,

Represents the probability that node v _k is transferred to node v _q' after l'+1 steps; update the value of l; Repeat the above steps until E _k is greater than or equal to the preset value. 7. The friend recommendation method according to claim 6, characterized in that, according to the probability that node v _k transfers to node v _q through 1 steps along the incoming edge

Calculating the probability Z _l (k, q) that two random walks from node v _k meet for the first time at node v _q at step l include: Execute the calculation process of Z _l (k, q) according to formula three, and the formula three is:

in,

is the probability that two random walks from node v _k meet at node v _q at step l,

is the probability that two random walks from node v _k meet at node v _q at step l and have already met before reaching node v _q ,

represents the probability that the node v _k is transferred to the node v _q along the incoming edge after l steps,

is initialized to 1, for

is initialized to 0, for

is initialized to 0; l is an intermediate variable, initialized to 0. 8. The friend recommendation method according to claim 6, characterized in that, for all

the node v _q′ , right

Updating E _k and l′ includes: According to formula four for all

the node v _q′ , right

E _k and l' are updated, and the formula 4 is:

E _k =E _k +1 l'=l'+1 Among them, the node v _x represents all

node. 9. The friend recommendation method according to claim 5, wherein the calculation result of generating random walks according to R(k) times and the _{sum of the lengths of all paths extending from the node vk E k is} greater than or equal to When the preset value is used, the calculation result of the above Z _l (k, q) calculates the probability of no longer encountering the node v _k

include: Calculate the no longer encounter probability of node k according to formula 5

The formula five is:

in,

Represents the probability that two random walks from node v _k meet after l(k) steps, c ^l(k) represents the probability that the two random walks do not stop in the first l steps, and l(k) is E The value of variable l when _k is greater than or equal to the preset value, Z _l (k, q) is the probability that two random walks starting from node v _k meet at node v _q for the first time at step l; I(w) is the indicator The controller variable is used to count whether the random walks meet during the wth generation of random walks, w is less than or equal to R(k), and I(w)=1 when the two random walks generated by the wth generation meet, Otherwise I(w)=0. 10. The friend recommendation method according to claim 1, wherein the recommending the users corresponding to the t nodes as a result to the target user comprises: The found t nodes correspond to users in the social network; Eliminate users who already have friends with the user to be recommended, and recommend the remaining users to the target user.

Images