CN111984832A - A friend recommendation method based on personalized page ranking - Google Patents

Abstract

The present invention provides a method for recommending friends based on personalized page ranking. The method includes: converting target users, users and the relationship between users into a graph structure, and repeating the calculation process of L-layer personalized page ranking for a total of L round to obtain the personalized page ranking of the sink node relative to all other nodes in each layer on the graph structure, and add the personalized page ranking scores of the sink node relative to each other node at each layer to obtain the relative value of the sink node relative to each layer. The personalized page ranking of other nodes, according to the personalized page ranking of the sink node relative to each other node, obtain the users corresponding to the top preset value and other nodes as target users, according to the user to be recommended and the target user Mutual importance measure, friend recommendation. The invention can get rid of the dependence between the calculation time of the single-home personalized page ranking and the density of the social network, and achieve the optimal calculation time, thereby improving the friend recommendation speed.

Description

A friend recommendation method based on personalized page ranking

technical field

The invention relates to the field of computer technology, in particular to a friend recommendation method based on personalized Page ranking.

Background technique

With the rapid development of Internet construction, social networks have integrated a number of functions such as communication, business cooperation, life entertainment, etc., which are rapidly popular among national users and become an important part of Internet applications. According to the in-depth research report on the social network industry released by the Prospective Industry Research Institute, the market size of my country's social network industry is expected to reach 50 billion yuan in 2022, and it will maintain a rapid growth trend and continue to develop, showing huge commercial value.

In the management and development of social networks, content, platform and users are the three dimensions that social applications focus on. High-quality content output, high-quality platform construction and large-scale user binding are the key factors for the sustainable development of social applications. How to attract more users to join a specific social software, how to delineate target users for content promotion and value dissemination, and how to measure the degree of intimacy between users are all issues that social applications will focus on. Among them, user importance evaluation in social applications is widely used in core fields such as friend recommendation, advertisement placement, user similarity calculation, etc. The evaluation results of user importance directly affect the operation effect of many specific applications, such as the quality of friend recommendation, The actual revenue of advertising, the accuracy of user similarity calculation results, etc. Therefore, how to obtain accurate evaluation results of the importance of social users is a common concern of most social applications.

In the evaluation process of user importance, in order to obtain better evaluation results, people tend to convert social networks into abstract graph structures, and complete the user importance evaluation on social networks by calculating the relative importance of graph nodes. Among many graph node importance measures, Personalized PageRank has been widely studied and applied for its intuitive design idea, realistic iterative definition and high-quality user importance evaluation results. According to the evaluation direction of user importance, the calculation method of personalized page ranking can be divided into two types, namely single-source personalized page ranking and single-homed personalized page ranking. For a given user, the single-source personalized ranking calculates the importance of all users relative to the specified user from the perspective of the specified user; the single-homed personalized page ranking hopes to calculate the importance of the specified user relative to other users. Sex rankings. For example: in friend recommendation (such as the friend recommendation function on Facebook), given a user to be recommended, it is necessary to stand in the perspective of the user to be recommended, look for users with high importance to it, and also need to carry out an important response. To evaluate, determine to which users the user to be recommended is important. The two-way importance evaluation ensures the actual function and use effect of friend recommendation. It not only finds users who are highly important to the recommended users, but also ensures that the users to be recommended also have attention value for these highly important users. Only in this way can both parties benefit from the friend relationship to be established, and agree to this friend recommendation to establish a friend relationship. For example, Bill Gates is generally more important to users in the computer industry. If only one-way importance, then Bill Gates' Facebook may receive numerous friend recommendation messages every day. These friend recommendations that only consider the one-way importance are meaningless to Bill Gates, because these users have a lot of respect for Bill Gates. The importance is generally not high, resulting in the inefficiency of friend recommendation.

At present, for the calculation of single-source personalized page ranking, there are methods that can make the time consumption reach the theoretical optimum, but there is still room for improvement in the calculation process of single-homed personalized page ranking.

SUMMARY OF THE INVENTION

The embodiment of the present invention provides a method for recommending friends based on personalized page ranking, so as to solve the problem of long time consumption of friend recommendation in the prior art, and realize fast friend recommendation.

An embodiment of the present invention provides a method for recommending friends based on personalized page ranking, including:

S1, for a target user on any social network platform, convert the target user, the user and the relationship between the users into a graph structure G, wherein the graph structure G includes a node corresponding to the user and a node corresponding to the user. The edge corresponding to the relationship between the users, the target user is the sink node of the graph structure;

S2, for each node in the graph structure, sort the incoming neighbor nodes of each node according to the order of increasing out-degree;

S3, repeating the calculation process of the l-layer personalized page ranking for a total of L rounds, to obtain the personalized page ranking of the sink node at each layer relative to all other nodes on the graph structure, and each other user corresponds to the graph every other node on the structure;

S4, for each other node on the graph structure, add up the personalized page ranking scores of each layer of the sink node relative to each other node to obtain the personalization of the sink node relative to each other node Page ranking;

S5, according to the personalized page ranking of the sink node relative to each other node, obtain a preset number of other nodes that are ranked first;

S6: Obtain the user information corresponding to the preset number of other nodes, as a measure of the importance of the target user to the user to be recommended, and make friend recommendation in combination with the importance ranking of the user to be recommended to the target user .

According to an embodiment of the present invention, the method for recommending friends based on personalized page rankings, the step S3 specifically includes:

S31, for the graph structure, repeat the update process until the update process traverses all nodes on the graph structure with a personalized page ranking score value greater than 0 at the current layer;

S32: Store the personalized page ranking score values of each node on the graph structure at the current layer for subsequent calculation.

According to the method for recommending friends based on personalized page ranking according to an embodiment of the present invention, the update process is specifically:

For the graph structure, according to the storage order of the nodes in the incoming adjacency list of the current node v, judge one by one whether each incoming neighbor node u∈N _in (v) in the incoming adjacency list satisfies the preset condition, and if so, update The personalized page ranking score value of the incoming neighbor nodes that meet the preset conditions in the next layer, N _in (v) is the set composed of all incoming neighbor nodes of the current node v, and the current node is the personality in the current layer. Converts nodes with a Page rank score greater than 0.

According to the method for recommending friends based on personalized page ranking according to an embodiment of the present invention, the step S31 specifically includes:

If the incoming neighbor node u of the current node satisfies the first preset condition, use the first update formula to update the personalized page ranking score π _l+1 (u, t) of the incoming neighbor node u in the next layer ;

The first preset condition is:

The first update formula is:

时，最后得到的各节点个性化佩奇排名的估计分数值与真实分数值之间的绝对误差不超过θ，用户根据实际情况选择λ(u)的取值；Among them, π _l+1 (u, t)' represents the updated personalized page ranking score value, v is the current node, and π _l (v, t) is the personalized page ranking of the current node v in the current layer l Score value, π _l+1 (u, t) is the personalized page ranking score value of incoming neighbor node u in the next layer l+1, θ is the error parameter determined by the user according to the actual situation, α is the α-decay random walk The stopping probability of each step is determined by the user according to the actual situation. The specific value of the parameter α is determined by the user. λ(u) is a value related to the node u. For nodes whose true score value is greater than θ, the estimated score value of the final personalized Page ranking and the true score value do not exceed a constant relative error, when

When , the absolute error between the estimated score value of each node's personalized Page ranking and the real score value does not exceed θ, and the user chooses the value of λ(u) according to the actual situation;

If the incoming neighbor u does not meet the first preset condition, but meets the second preset condition, a random number r∈[0,1) between 0 and 1 is independently and randomly generated, using the second The update formula updates the personalized Page rank score π _l+1 (u, t) of the incoming neighbor node u of the current node in the next layer;

The second preset condition is as follows:

The second update formula is as follows:

If the incoming neighbor node u of the current node does not satisfy the first preset condition nor the second preset condition, the update process of the node v is ended.

According to the method for recommending friends based on personalized page ranking according to an embodiment of the present invention, L is the number of rounds that need to be repeated for the calculation of the l-layer personalized page ranking, and L=log _1-α θ, θ is the user's The error parameter determined by the actual situation, α is the stopping probability of each step in the α-decay random walk, and the specific value of the parameter α is determined by the user according to the actual situation.

An embodiment of the present invention further provides an electronic device, including a memory, a processor, and a computer program stored in the memory and running on the processor, when the processor executes the program, the processor implements any of the above based Steps of a friend recommendation method for personalized Page Ranking.

Embodiments of the present invention also provide a non-transitory computer-readable storage medium, on which a computer program is stored, and when the computer program is executed by a processor, implements the method for recommending friends based on any of the above-mentioned personalized page rankings A step of.

The embodiment of the present invention provides a method for recommending friends based on personalized page ranking, which can get rid of the dependence between the calculation time of single-homed personalized page ranking and the density of social networks, and use relative error to constrain single-homed personalized When estimating the quality of Page's ranking score value, it achieves the optimal calculation time, improves the efficiency of social user importance evaluation, and thus improves the speed of friend recommendation.

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the following briefly introduces the accompanying drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description These are some embodiments of the present invention. For those of ordinary skill in the art, other drawings can also be obtained according to these drawings without creative efforts.

FIG. 1 is a flowchart of a method for recommending friends based on personalized page ranking provided by an embodiment of the present invention;

Fig. 2 is the specific flow chart of step S3 in the embodiment of the present invention;

FIG. 3 is a schematic structural diagram of an electronic device according to an embodiment of the present invention.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

At present, for the calculation of single-source personalized page ranking, there are methods that can make the time consumption reach the theoretical optimum, but there is still room for improvement in the calculation process of single-homed personalized page ranking. However, the time consumption of existing methods for calculating single-homed personalized page ranking generally depends on the density of social networks. For social networks with a large average correlation between users, the calculation speed of the single-home personalized page ranking is slow, and it does not reach the optimal time consumption in theoretical analysis, which limits the efficiency of user importance evaluation to a certain extent. , thus affecting the speed of friend recommendation.

In order to solve the above problems, the embodiment of the present invention provides a method for recommending friends based on personalized page ranking, which can get rid of the dependence between the calculation time of single-home personalized page ranking and the density of social networks, and when using relative error When constraining the estimated quality of the single-homed personalized page ranking score value, the optimal calculation time is achieved, the efficiency of social user importance evaluation is improved, and the friend recommendation speed is improved.

FIG. 1 is a flowchart of a method for recommending friends based on personalized page ranking provided by an embodiment of the present invention. As shown in FIG. 1 , the method includes:

S1, for a target user on any social network platform, convert the target user, the user and the relationship between the users into a graph structure G, wherein the graph structure G includes a node corresponding to the user and a node corresponding to the user. The edge corresponding to the relationship between the users, the target user is the sink node of the graph structure;

First, the relationship between target users, users and users is converted into a graph structure G. The graph structure G includes all social users, namely target users and other users, social users correspond to nodes on the graph structure, and concerns between social users The relationship corresponds to the edge on the graph structure, the target user is the sink node t of the graph structure, and the graph structure G includes n nodes.

In the embodiment of the present invention, users refer to all registered users on the social platform, and the relationship between users may specifically be a follow relationship between users. For example, all registered friends on Facebook and the network of friends.

Specifically, for social networks with following relationships such as Weibo, Facebook, and Instagram, the users of the social network are mapped 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 is established on the graph structure. For example, B—>A, where B is the incoming neighbor node of A, and A is the outgoing neighbor node of B. This edge is the outgoing edge of node B and the incoming edge of node A. The number of out-edges owned by a node is called "out-degree", and the number of in-edges owned by a node is called "in-degree".

For social networks such as WeChat and QQ with friend relationships, users on the social network are mapped to graph nodes, and friend relationships are mapped 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.

When storing the above graph structure, an incoming adjacency table is constructed for each node on the graph to store all incoming neighbors of the node. For any node v on the graph, the length of its corresponding in-adjacency list is d _in (v), and d _in (v) represents the out-degree of node v.

S2, for each node in the graph structure, sort the incoming neighbor nodes of each node according to the order of increasing out-degree;

其对应的入邻接表里存储的节点即为

Sort the nodes stored in the in-adjacency list of all nodes in the graph structure in the order of increasing out-degree. Suppose the incoming neighbor of any node v on the graph is

The corresponding node stored in the adjacency list is

按照其出度递增顺序进行重排，并重构节点v的入邻接表为

其中

表示节点v所有入邻居

的一种排列顺序，且保证

Will

Rearrange in ascending order of its out-degree, and reconstruct the in-adjacency list of node v as

in

represents all incoming neighbors of node v

a sort order of , and guarantees

It should be noted that, in the embodiment of the present invention, the above-mentioned sorting is completed by using the counting sorting method, so that the time consumption of the entire sorting process is the same as the time consumption of the graph structure construction process.

S3, repeating the calculation process of the l-layer personalized page ranking for a total of L rounds, to obtain the personalized page ranking of the sink node at each layer relative to all other nodes on the graph structure, and each other user corresponds to the graph every other node on the structure;

Repeat the calculation process of the l-layer personalized page ranking, and update l according to the following formula until l is greater than the preset value.

l The update formula is: l=l+1.

Wherein, the preset value is L=log _1-α θ, θ is an error parameter determined by the user according to the actual situation, and L is the number of rounds that need to be repeated for the calculation of the l-layer personalized page ranking.

Before step S3 is executed, all nodes on the graph structure maintain (L+1) variables respectively, corresponding to the personalized page ranking score values of the node at each layer. For example, for any node v on the graph, it needs to maintain (L+1) variables: π ₀ (v,t), π ₁ (v,t), ..., π _L (v,t), the corresponding node v is in The score of the personalized page ranking for tiers 0, 1, ..., L. Except that π ₀ (t, t) is initialized to α, the personalized Page rank scores of all nodes v at each layer are initialized to 0. α is a user-specified parameter derived from the α-decay random walk.

In the calculation process of the l-layer personalized page ranking, the personalized page ranking score value of each node in the l-layer is correspondingly updated. l is an intermediate variable, which is used to mark the update layer number of the current personalized page ranking, and determine the stop time of the whole calculation process.

It should be noted that the concept of "L layer" comes from the number of steps of random walks. Given a sink node t, the personalized Page rank score of any node v in the lth layer in the graph structure is π ₁ (v,t) is equal to the probability that an α-decaying random walk from node v stops at destination node t at step l. Among them, the α-decay random walk is a special random walk method. At each step of the walk, the α-decay random walk stops with the probability of α, and randomly walks to the current node with the probability of 1-α. out neighbor nodes. α is a parameter between 0 and 1. The specific value of parameter α is determined by the user according to the actual situation. The step size is shorter.

S4, for each other node on the graph structure, add up the personalized page ranking scores of each layer of the sink node relative to each other node to obtain the personalization of the sink node relative to each other node Page ranking;

For all nodes in the graph structure, add up the personalized page ranking scores of each layer relative to the sink node t to obtain the personalized page ranking of each node relative to the sink node t.

即

For example, for any node v on the graph, add up the variable values of the (L+1) variables π ₀ (v,t), π ₁ (v,t), ..., π _L (v,t) it maintains , as an estimate of the personalized Page rank score π(v,t) for node v

which is

It should be noted that, given the sink node t, the personalized Page rank score π(v, t) of any node v on the graph is equal to the probability that the α-decay random walk starting from the node v finally stops at the sink node t. The personalized page ranking score value π(v,t) of node v is equal to the sum of the personalized page ranking score values of each layer, namely

可以证明的是，

与π(v,t)之间的误差不超过θ，其中θ为用户根据实际情况确定的误差参数。In step S4, the sum of the personalized page ranking scores of the first L layers is used as the estimated value of the node v personalized page ranking score π(v, t)

It can be proved that,

The error with π(v,t) does not exceed θ, where θ is the error parameter determined by the user according to the actual situation.

S5, according to the personalized page ranking of the sink node relative to each other node, obtain a preset number of other nodes that are ranked first;

From all the nodes in the graph structure, find the top t nodes with the highest personalized page ranking relative to the sink node, where t is a preset value, which can be specified by the user, and refers to the number of users recommended to the target user.

S6: Obtain the user information corresponding to the preset number of other nodes, as a measure of the importance of the target user to the user to be recommended, and make friend recommendation in combination with the importance ranking of the user to be recommended to the target user .

Find the user information corresponding to the aforementioned t nodes, and use it as a measure of the importance of the target user relative to the user to be recommended, and make friend recommendation in combination with the importance ranking of other users to be recommended relative to the target user.

Among them, the calculation method of the importance ranking of the user to be recommended to the target user is the single-source personalized ranking calculation method, and the commonly used methods for realizing the single-source personalized page ranking include Monte Carlo sampling and forward search.

To sum up, the embodiment of the present invention provides a method for recommending friends based on personalized page ranking, which gets rid of the dependence of calculation time and social network density when calculating single-home personalized page ranking in the past, and uses relative error When constraining the estimated quality of the single-homed personalized page ranking score value, the optimal calculation time is achieved, the efficiency of social user importance evaluation is improved, and the friend recommendation speed is improved.

的时间复杂度内完成单宿个性化佩奇排名在常数相对误差、δ相对误差约束阈值下的计算，达到了理论证明的最优计算时间；对于绝对误差ε，本发明实施例可以在

的时间复杂度内完成单宿个性化佩奇排名的计算，

为该社交网络对应的图结构上的节点平均度。In addition, for a randomly selected sink node, the embodiment of the present invention may

The calculation of the single-homed personalized page ranking under the constant relative error and the δ relative error constraint threshold is completed within the time complexity of ε, which achieves the optimal calculation time of the theoretical proof; for the absolute error ε, the embodiment of the present invention can be

The calculation of the single-homed personalized page ranking is completed within the time complexity of ,

is the average degree of nodes on the graph structure corresponding to the social network.

的时间内得到常数相对误差、δ相对误差约束阈值下的计算结果，或者在

的时间内得到绝对误差ε的计算结果。However, the existing methods for calculating the single-homed personalized page ranking can only be used in

The calculation results under the constant relative error, the delta relative error constraint threshold, or the

The calculation result of the absolute error ε is obtained within the time.

Fig. 2 is a specific flowchart of step S3 in the embodiment of the present invention. As shown in Fig. 2, on the basis of the above-mentioned embodiment, preferably, the step S3 specifically includes:

S31, for the graph structure, repeat the update process until the update process traverses all nodes on the graph structure with a personalized page ranking score value greater than 0 at the current layer;

The update process is repeated until the update process traverses all nodes in the graph structure whose personalized Page rank score value is greater than 0 at the current layer.

Specifically, the update process is:

For the graph structure, according to the storage order of the nodes in the incoming adjacency list of the current node v, judge one by one whether each incoming neighbor node u∈N _in (v) in the incoming adjacency list satisfies the preset condition, and if so, update The personalized page ranking score value of the incoming neighbor nodes that meet the preset conditions in the next layer, N _in (v) is the set composed of all incoming neighbor nodes of the current node v, and the current node is the personality in the current layer. Converts nodes with a Page rank score greater than 0.

S32: Store the personalized page ranking score values of each node on the graph structure at the current layer for subsequent calculation.

On the basis of the above embodiment, preferably, the step S31 specifically includes:

S311, if the incoming neighbor node u of the current node satisfies the first preset condition, use the first update formula for the personalized page ranking score of the incoming neighbor node u in the next layer π _l+1 (u, t) to update;

The first preset condition is:

The first update formula is:

时，最后得到的各节点个性化佩奇排名的估计分数值与真实分数值之间的绝对误差不超过θ，用户根据实际情况选择λ(u)的取值；Among them, π _l+1 (u, t)' represents the updated personalized page ranking score value, v is the current node, and π _l (v, t) is the personalized page ranking of the current node v in the current layer l Score value, π _l+1 (u, t) is the personalized page ranking score value of incoming neighbor node u in the next layer l+1, θ is the error parameter determined by the user according to the actual situation, α is the α-decay random walk The stopping probability of each step is determined by the user according to the actual situation. The specific value of the parameter α is determined by the user. λ(u) is a value related to the node u. For nodes whose true score value is greater than θ, the estimated score value of the final personalized Page ranking and the true score value do not exceed a constant relative error, when

When , the absolute error between the estimated score value of each node's personalized Page ranking and the real score value does not exceed θ, and the user chooses the value of λ(u) according to the actual situation;

S312, if the incoming neighbor u does not meet the first preset condition but meets the second preset condition, independently and randomly generate a random number r∈[0,1) between 0 and 1, using The second update formula updates the personalized Page rank score π _l+1 (u, t) of the incoming neighbor node u of the current node in the next layer;

The second preset condition is as follows:

The second update formula is as follows:

S313, if the incoming neighbor node u of the current node does not satisfy the first preset condition nor the second preset condition, end the updating process of the node v.

It should be noted that, for the incoming neighbor node u, only when it does not meet the first preset condition, it may satisfy the second preset condition. In addition, in step S2, the in-neighbors of each node have been sorted in an increasing order of their out-degrees. Therefore, if the previous incoming neighbor node in the incoming adjacency table does not meet the first preset condition but meets the second preset condition, the next incoming neighbor node does not need to perform the judgment of step S311 again, and directly executes step S312; If the second preset condition is not satisfied from an incoming neighbor node, the incoming neighbor node directly executes step S313, and ends the update of the personalized page ranking of node v incoming neighbors in the next layer, and subsequent nodes do not need to perform step S311- S313.

FIG. 3 is a schematic diagram of the physical structure of an electronic device provided by an embodiment of the present invention. As shown in FIG. 3 , the electronic device may include: a processor (processor) 310, a communications interface (Communications Interface) 320, and a memory (memory) 330 and a communication bus 340 , wherein the processor 310 , the communication interface 320 , and the memory 330 communicate with each other through the communication bus 340 . The processor 310 may invoke logic instructions in the memory 330 to execute a method for recommending friends based on the personalized page ranking, the method comprising:

S1, for a target user on any social network platform, convert the target user, the user and the relationship between the users into a graph structure G, wherein the graph structure G includes a node corresponding to the user and a node corresponding to the user. The edge corresponding to the relationship between the users, the target user is the sink node of the graph structure;

S2, for each node in the graph structure, sort the incoming neighbor nodes of each node according to the order of increasing out-degree;

S3, repeating the calculation process of the l-layer personalized page ranking for a total of L rounds, to obtain the personalized page ranking of the sink node at each layer relative to all other nodes on the graph structure, and each other user corresponds to the graph every other node on the structure;

S4, for each other node on the graph structure, add up the personalized page ranking scores of each layer of the sink node relative to each other node to obtain the personalization of the sink node relative to each other node Page ranking;

S5, according to the personalized page ranking of the sink node relative to each other node, obtain a preset number of other nodes that are ranked first;

S6: Obtain the user information corresponding to the preset number of other nodes, as a measure of the importance of the target user to the user to be recommended, and make friend recommendation in combination with the importance ranking of the user to be recommended to the target user .

In addition, the above-mentioned logic instructions in the memory 330 may be implemented in the form of software functional units and may be stored in a computer-readable storage medium when sold or used as an independent product. Based on this understanding, the technical solution of the present invention can be embodied in the form of a software product in essence, or the part that contributes to the prior art or the part of the technical solution. The computer software product is stored in a storage medium, including Several instructions are used to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to execute all or part of the steps of the methods described in the various embodiments of the present invention. The aforementioned storage medium includes: U disk, mobile hard disk, Read-Only Memory (ROM, Read-Only Memory), Random Access Memory (RAM, Random Access Memory), magnetic disk or optical disk and other media that can store program codes .

On the other hand, an embodiment of the present invention also provides a computer program product, the computer program product includes a computer program stored on a non-transitory computer-readable storage medium, the computer program includes program instructions, when the program instructions When executed by a computer, the computer can execute a method for recommending friends based on personalized Page rank provided by the above method embodiments, the method includes:

S1, for a target user on any social network platform, convert the target user, the user and the relationship between the users into a graph structure G, wherein the graph structure G includes a node corresponding to the user and a node corresponding to the user. The edge corresponding to the relationship between the users, the target user is the sink node of the graph structure;

S2, for each node in the graph structure, sort the incoming neighbor nodes of each node according to the order of increasing out-degree;

S3, repeating the calculation process of the l-layer personalized page ranking for a total of L rounds, to obtain the personalized page ranking of the sink node at each layer relative to all other nodes on the graph structure, and each other user corresponds to the graph every other node on the structure;

S4, for each other node on the graph structure, add up the personalized page ranking scores of each layer of the sink node relative to each other node to obtain the personalization of the sink node relative to each other node Page ranking;

S5, according to the personalized page ranking of the sink node relative to each other node, obtain a preset number of other nodes that are ranked first;

S6: Obtain the user information corresponding to the preset number of other nodes, as a measure of the importance of the target user to the user to be recommended, and make friend recommendation in combination with the importance ranking of the user to be recommended to the target user .

In yet another aspect, embodiments of the present invention further provide a non-transitory computer-readable storage medium on which a computer program is stored, and the computer program is implemented when executed by a processor to execute a personalization-based storage medium provided by the foregoing embodiments. Page Rank's friend recommendation method, which includes:

S1, for a target user on any social network platform, convert the target user, the user and the relationship between the users into a graph structure G, wherein the graph structure G includes a node corresponding to the user and a node corresponding to the user. The edge corresponding to the relationship between the users, and the target user is the sink node of the graph structure;

S2, for each node in the graph structure, sort the incoming neighbor nodes of each node according to the order of increasing out-degree;

S3, repeating the calculation process of the l-layer personalized page ranking for a total of L rounds, to obtain the personalized page ranking of the sink node at each layer relative to all other nodes on the graph structure, and each other user corresponds to the graph every other node on the structure;

S4, for each other node on the graph structure, add up the personalized page ranking scores of each layer of the sink node relative to each other node to obtain the personalization of the sink node relative to each other node Page ranking;

S5, according to the personalized page ranking of the sink node relative to each other node, obtain a preset number of other nodes that are ranked first;

S6: Obtain the user information corresponding to the preset number of other nodes, as a measure of the importance of the target user to the user to be recommended, and make friend recommendation in combination with the importance ranking of the user to be recommended to the target user .

The device embodiments described above are only illustrative, wherein the units described as separate components may or may not be physically separated, and the components shown as units may or may not be physical units, that is, they may be located in One place, or it can be distributed over multiple network elements. Some or all of the modules may be selected according to actual needs to achieve the purpose of the solution in this embodiment. Those of ordinary skill in the art can understand and implement it without creative effort.

From the description of the above embodiments, those skilled in the art can clearly understand that each embodiment can be implemented by means of software plus a necessary general hardware platform, and certainly can also be implemented by hardware. Based on this understanding, the above-mentioned technical solutions can be embodied in the form of software products in essence or the parts that make contributions to the prior art, and the computer software products can be stored in computer-readable storage media, such as ROM/RAM, magnetic A disc, an optical disc, etc., includes several instructions for causing a computer device (which may be a personal computer, a server, or a network device, etc.) to perform the methods described in various embodiments or some parts of the embodiments.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, but not to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that it can still be The technical solutions described in the foregoing embodiments are modified, or some technical features thereof are equivalently replaced; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the embodiments of the present invention.

Claims (7)

1. A friend recommendation method based on personalized Peltier is characterized by comprising the following steps:

s1, for a target user on any social network platform, converting the target user, the user and the relationship among the users into a graph structure G, wherein the graph structure G comprises a node corresponding to the user and an edge corresponding to the relationship among the users, and the target user is a sink node of the graph structure;

s2, for each node in the graph structure, sorting the neighbor nodes of each node according to the ascending order of out degree;

s3, repeatedly executing the calculation process of the L-layer personalized Peltier ranking for L rounds to obtain personalized Peltier ranking of the host node on the graph structure relative to all other nodes on each layer, wherein each other user corresponds to each other node on the graph structure;

s4, for each other node on the graph structure, adding the personalized Pepper ranking score values of the sink node relative to each other node to obtain the personalized Pepper ranking of the sink node relative to each other node;

s5, acquiring other nodes with preset numerical values ranked in the front according to the personalized Peltier ranking of the host node relative to each other node;

and S6, acquiring user information corresponding to other nodes with the preset value, taking the user information as an importance measurement standard of the target user for the user to be recommended, and performing friend recommendation by combining the importance ranking of the user to be recommended for the target user.

2. The friend recommendation method based on personalized paget' S ranking according to claim 1, wherein the step S3 specifically comprises:

s31, repeating the updating process for the graph structure until the updating process traverses all nodes of the graph structure with the personalized Peppe ranking score value of the current layer being more than 0;

and S32, storing the personalized Peppe ranking score value of each node on the graph structure at the current layer for subsequent calculation.

3. The friend recommendation method based on personalized paget's rank according to claim 2, wherein the update process specifically comprises:

for the graph structure, according to the node storage sequence in the adjacent entry table of the current node v, judging each adjacent entry node u e N in the adjacent entry table one by one_in(v) Whether a preset condition is met, if so, updating the personalized Pepper ranking score value, N, of the next layer of the neighbor-entering nodes meeting the preset condition_in(v) And the current node is a set formed by all the neighbor nodes of the current node v, and the current node is a node with the personalized Pepper ranking score value of more than 0 at the current layer.

4. The friend recommendation method based on personalized paget' S ranking according to claim 3, wherein the step S31 specifically comprises:

if the neighbor node u of the current node meets the first preset condition, the personalized Pecify ranking score value pi of the neighbor node u at the next layer is updated by the first updating formula_l+1(u, t) updating;

the first preset condition is as follows:

the first update formula is:

wherein, pi_l+1(u, t)' represents the updated personalized peclet ranking score value, v is the current node, π_l(v, t) is the personalized Petzian ranking score value of the current node v at the current level l, π_l+1(u, t) is an individualized petit ranking score value of the neighbor node u at the next layer l +1, theta is an error parameter determined by the user according to the actual situation, alpha is the stopping probability of each step in the alpha-attenuation random walk, the specific value of the parameter alpha is determined by the user according to the actual situation, lambda (u) is a numerical value related to the node u, when lambda (u) is 1, for the node with the real score value of the individualized petit ranking larger than theta, the estimated score value and the real score value of the individualized petit ranking obtained finally do not exceed a constant relative error, when lambda (u) is 1, the estimated score value and the real score value of the individualized petit ranking are not more than a constant relative error, and when lambda

Then, the absolute error between the estimated score value and the real score value of the finally obtained personalized peclet ranking of each node is not more than theta, and a user selects the value of lambda (u) according to the actual situation;

if the neighbor node u does not meet the first preset condition but meets the second preset condition, independently and randomly generating a random number r epsilon [0,1 ] between 0 and 1, and utilizing a second updating formula to carry out personalized Petze ranking score value pi of the neighbor node u of the current node at the next layer_l+1(u, t) updating;

the second preset condition is as follows:

the second update formula is as follows:

and if the neighbor node u of the current node does not meet the first preset condition, and does not meet the second preset condition, ending the updating process of the node v.

5. The friend recommendation method based on personalized peclet ranking of claim 1, wherein L is the number of rounds that need to be repeated for the L-level personalized peclet ranking calculation, and L is log_1-αTheta and theta are error parameters determined by a user according to actual conditions, alpha is the stopping probability of each step in the alpha-attenuation random walk, and the specific value of the parameter alpha is determined by the user according to the actual conditions.

6. An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor when executing the program performs the steps of the method for friend recommendation based on personalized paged ranking according to any one of claims 1 to 5.

7. A non-transitory computer readable storage medium, having stored thereon a computer program, wherein the computer program, when being executed by a processor, performs the steps of the friend recommendation method based on personalized pagerank according to any one of claims 1 to 5.

Images