Recommendation ranking system with distrust

• US 9,152,969 B2
• Filed: 04/07/2010
• Issued: 10/06/2015
• Est. Priority Date: 04/07/2010
• Status: Active Grant

• Current Assignee: ROVI Product Corporation (Xperi Inc.)
• Original Assignee: Rovi Technologies Corporation (Adeia Inc.)
• Inventors: Borgs, Christian H., Chayes, Jennifer T., Kalai, Adam T., Malekian, Azarakhsh, Tennenholtz, Moshe
• Primary Examiner(s): Eskandarnia, Arvin
• Assistant Examiner(s): DESAI, MARGISHI V
• Application Number:
  US12/755,791
• Publication Number:
  US 20110252121A1
• Time in Patent Office: 2,008 Days
• Field of Search: 707/3, 709/223
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A recommendation ranking system that computes trust for entities based on negative expressions of trust. Negative expressions of trust are used to reduce the trust of entities. However, the system may discount entities that in the aggregate are distrusted. The system may be used with a social network to provide accurate, personalized recommendations for members of the social network. The network may be modeled as a voting network, with each member of the social network represented as a node and expressions of trust between members represented as weights on edges between nodes. Values of trust may be computed for nodes in the network and used to generate a recommendation. Opinions expressed on a topic may be weighted by trust in the node expressing the opinion. The system may be applied in other settings that can be modeled as a voting network, including ranking of Internet search results.

Claims

1. A method comprising:

with at least one processor;

adding a first friend to a user'"'"'s network of friends in a social network;

receiving a first rating from the first friend regarding a first product or service;

receiving a first indication from the user that the user agrees with the first friend'"'"'s rating of the first product or service;

adding a second friend to the user'"'"'s network of friends;

receiving a second rating from the second friend regarding a second product or service;

receiving a second indication from the user that the user disagrees with the second friend'"'"'s rating of the product or service;

computing a trust value for each of the first friend and the second friend based on trust values associated with each of the first friend and the second friend in the social network;

creating a data set representing the first friend as a first node and the second friend as a second node and connections between the first node, the second node, and the user as a plurality of directional edges, each having an associated value for an expression of trust, wherein;

a first directional edge of the plurality of directional edges represents the connection between the first node and the user and has a positive expression of trust based on the first indication from the user that the user agrees with the first friend'"'"'s rating of the first product or service,

a second directional edge of the plurality of directional edges represents the connection between the second node and the user and has a negative expression of trust based on the second indication from the user that the user disagrees with the second friend'"'"'s rating of the second product or service, and,

the computed trust value for each of the first friend and the second friend being greater than a threshold associated with a minimum level of trust in the social network;

transmitting, to the user, a recommendation for a third product or service based on the positive expression of trust associated with the first friend and information that the first friend rated the third product or service positively.

2. The method of claim 1, wherein the computing comprises minimizing an equation subject to constraints.

3. The method of claim 2, wherein the equation comprises

4. The method of claim 3, wherein the constraints comprise:

5. The method of claim 1, wherein the minimum level of trust in the social network correlates with no trust, whereby friends that are distrusted do not impact computation of trust of other friends.

6. The method of claim 1, wherein the data set comprises information defining a plurality of friends in the social network in which at least a first portion of the plurality of friends have expressed trust in at least a second portion of the plurality of friends, each friend of the plurality of friends being represented as a node of the plurality of nodes and each expression of trust being an associated trust for a directional edge of the plurality of directional edges.

7. The method of claim 6, further comprising producing a recommendation based on ratings expressed by a third portion of the plurality of friends, the producing comprising forming a weighted combination of values representing the ratings, the weighted combination comprising a combination of each of the values representing a rating weighted by the value of trust computed for a node of the plurality of nodes representing the friend that expressed the ratings.

8. The method of claim 1, wherein the data set comprises information defining a plurality of web pages accessible over a network in which at least a first portion of the plurality of web pages have links to at least a second portion of the plurality of web pages, each web page of the plurality of web pages being represented as a node of the plurality of nodes and each link defining an associated trust value for an edge.

9. A non-transitory computer-readable medium having instructions recorded thereon for transmitting a recommendation, the instructions comprising:

instructions for adding a first friend to a user'"'"'s network of friends in a social network;

instructions for receiving a first rating from the first friend regarding a first product or service;

instructions for receiving a first indication from the user that the user agrees with the first friend'"'"'s rating of the first product or service;

instructions for adding a second friend to the user'"'"'s network of friends;

instructions for receiving a second rating from the second friend regarding a second product or service;

instructions for receiving a second indication from the user that the user disagrees with the second friend'"'"'s rating of the product or service;

instructions for computing a trust values for each of the first friend and the second friend based on trust values associated with each of the first friend and the second friend in the social network;

instructions for creating a data set representing the first friend as a first node and the second friend as a second node and connections between the first node, the second node, and the user as a plurality of directional edges, each having an associated expression of trust value, wherein;

a first directional edge of the plurality of directional edges represents the connection between the first node and the user and has a positive expression of trust value based on the first indication from the user that the user agrees with the first friend'"'"'s rating of the first product or service,

a second directional edge of the plurality of directional edges;

represents the connection between the second node and the user and has a negative expression of trust value based on the second indication from the user that the user disagrees with the second friend'"'"'s rating of the second product or service, and,

the computed trust values for each of the first friend and the second friend being greater than or equal to a threshold associated with a minimum level of trust in the social network; and

instructions for transmitting, to the user, a recommendation for a third product or service based on the positive expression of trust associated with the friend and information that the first friend rated the third product or service positively.

10. The non-transitory computer-readable medium of claim 9, wherein the non-transitory computer-readable medium further comprises instructions for computing associated expression of trust values for directional edges of the plurality of directional edges, the computing comprising, for nodes having a plurality of leaving edges leaving the node, scaling initial expression of trust values for each leaving directional edge based on a combined value of the initial expression of trust values for leaving directional edges for the node.

11. The non-transitory computer-readable medium of claim 9, wherein the non-transitory computer-readable medium further comprises instructions for receiving input from the user'"'"'s friends in the social network, the input representing ratings of a plurality of products and services and expressing trust in friends of the social network to provide a rating.

12. The non-transitory computer-readable medium of claim 11, wherein the non-transitory computer-readable medium further comprises:

instructions for receiving user input representing a request for a recommendation for a product or service;

instructions for forming the data set based on information stored for selected friends of the social network, the selected friends comprising friends that expressed a rating of a product or service and friends that expressed a level of trust in the friends that expressed a rating of a product or service.

13. The non-transitory computer-readable medium of claim 9, wherein the minimum level of trust is a value indicating zero trust.

14. The non-transitory computer-readable medium of claim 9, wherein:

the data set comprises information defining a plurality of web pages accessible over a network in which at least a first portion of the plurality of web pages have links to at least a second portion of the plurality of web pages, each web page of the plurality of web pages being represented as a node of the plurality of nodes and each link defining an associated expression of trust value for an edge; and

the instructions further comprise;

instructions for collecting associated expression of trust values for the data set, each trust value having a value based on a nature of a link between two web pages.

15. The non-transitory computer-readable medium of claim 14, wherein instructions for collecting associated trust values comprise assigning a negative trust value for a link classified in the web page containing the link as a negative link.

16. A computerized system implementing a social network, the computerized system comprising:

at least one processor configured to;

add a first friend to a user'"'"'s network of friends in a social network;

receive a first rating from the first friend regarding a first product or service;

receive a first indication from the user that the user agrees with a first friend'"'"'s rating of the product or service;

add a second friend to the user'"'"'s network of friends;

receive a second rating from the second friend regarding a second product or service;

receive a second indication from the user that the user disagrees with the second friend'"'"'s rating of the product or service;

compute a value of trust for each of the first friend and the second friend based on trust values associated with each of the first friend and the second friend in the social network;

create a data set representing the first friend as a first node and the second friend as a second node and connections between the first node, the second node, and the user as a plurality of directional edges, each having an associated value for an expression of trust, wherein;

a first directional edge of the plurality of directional edges represents the connection between the first node and the user and has a positive expression of trust based on the first indication from the user that the user agrees with the first friend'"'"'s rating of the first product or service,

a second directional of the plurality of directional edges represents the connection between the second node and the user and has a negative expression of trust based on the second indication from the user that the user disagrees with the second friend'"'"'s rating of the second product or service, and,

the computed trust value for each of the first friend and the second friend being above a threshold associated with a minimum level of trust in the social network;

transmit, to the user, a recommendation for a third product or service based on the positive expressions of trust associated with the first friend and information that the first friend rated the third product or service positively.

17. The computerized system of claim 16, further configured to receive and store a plurality of ratings from friends of a plurality of friends relating to a plurality of products and services.

18. The computerized system of claim 17, further configured to:

present a rating of the plurality of ratings to the user, the rating having been made by a friend;

receive input from the user indicating a level of agreement with the presented rating; and

store a value indicating an expression of trust between the user and the friend based on the input indicating the level of agreement.

19. The computerized system of claim 16, wherein the threshold corresponds to zero trust.

20. The computerized system of claim 16, further configured to compute a value for an expression of trust of a first friend in a second friend based on scaling an expression of trust value assigned by the first friend to the second friend, the trust value being scaled in proportion to the total amount of trust values assigned by the first friend to friends of the plurality of friends.