Eigenvalue ranking of social offerings using social network information

• US 8,799,296 B2
• Filed: 05/21/2012
• Issued: 08/05/2014
• Est. Priority Date: 02/23/2012
• Status: Active Grant

• Current Assignee: Borislav Agapiev
• Original Assignee: Borislav Agapiev
• Inventors: Agapiev, Borislav
• Primary Examiner(s): CHANNAVAJJALA, SRIRAMA T
• Application Number:
  US13/476,195
• Publication Number:
  US 20130226912A1
• Time in Patent Office: 806 Days
• Field of Search: 709/203, 709215-220, 707705-711, 707723-724, 707730-732, 707737-741, 707776-785, 707805-806, 707748-751, 707/767
• US Class Current: 707/748
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Systems and methods in which a ranking engine, for example such an engine as is communicatively coupled to a search engine or social networking system, or is part of such a system, ranks social offerings for eventual display to a user, said social offerings being ranked according to eigenvalues of matrices associated with a social graph G of the user and the user'"'"'s friends and other connections. In some instances, the social offerings may be divided into categories and ranks for the social offerings computed for each of the categories based on activities and communications of the user with friends and other connections for each category. The eigenvalues are used for ranking the social offerings based on actions of the user'"'"'s friends and other connections with respect to the social offerings.

Claims

1. A computer-based system comprising a processor and a memory, said memory storing computer readable instructions which, when executed by said processor cause said processor to rank social offerings for eventual display to a user, said social offerings ranked according to eigenvalues of matrices associated with a social graph G describing connections between the user, the user'"'"'s friends and other individuals within a social network of the user.

2. The computer-based system of claim 1, wherein the social offerings are divided into categories and ranks for the social offerings are computed, for each of the categories, based on activities and communications of the user with the user'"'"'s friends and other individuals within the social network of the user for each category.

3. The computer-based system of claim 1, wherein the eigenvalues are used for ranking the social offerings based on actions of the user'"'"'s friends and other individuals within the social network of the user with respect to the social offerings.

4. The computer-based system of claim 1, wherein for the social graph G describing connections between the user and the user'"'"'s friends and other individuals within the social network of the user, a connectivity matrix C(G) having N rows and columns and being defined as

5. The computer-based system of claim 4, wherein values in a principal eigenvector associated with the principal eigenvalue of the connectivity matrix C(G) are used as ranks of nodes (users) in the social graph G and ranks of the social offerings are then computed as sums of ranks of nodes (users) in the social graph.

6. The computer-based system of claim 5, wherein computation of the principal eigenvalue of the connectivity matrix is carried out as an iterative process where a rank vector R of length N, where N is the number of nodes in the social graph G, associated with ranks of nodes in the social graph G, is initialized to a vector of non-zero values and then successively iterated according to:

7. The computer-based system of claim 1, wherein for each user a social graph with weights corresponding to levels of activity (affinity) between users is created.

8. The computer-based system of claim 7, wherein users who are more active in interacting with each other are assigned higher weights.

9. The computer-based system of claim 8, wherein for the social graph G describing connections between the user and the user'"'"'s friends and other individuals within the social network of the user, a connectivity matrix C(G) is computed and the eigenvalues comprise a principal eigenvalue of the connectivity matrix C(G), said principal eigenvalue of the connectivity matrix being computed through an iterative process where a rank vector R of length N, where N is the number of nodes in the social graph G, associated with ranks of nodes in the social graph G, is initialized to a vector of non-zero values and then successively iterated according to

10. The computer-based system of claim 9, wherein the probabilities are derived from activities of users in interacting with each other.

11. The computer-based system of claim 1, wherein a subject ad determined as being relevant for display, and so displayed to the user, is accompanied by information indicating that a known friend of the user or another individual within the social network of the user has clicked on the subject ad.

12. The computer-based system of claim 11, wherein an order in which friends or connections of the user are displayed along with the subject ad is determined by computed ranks.

13. The computer-based system of claim 1, wherein the social offerings comprise one or more of:

search engine search results, advertisements, commercial product or service offerings, social game offerings, movie offerings, music offerings, travel offerings, vehicle offerings, and jobs offerings.

14. A method, comprising ranking, by a ranking engine of a computer system and communicatively coupled to a search engine or social networking system, social offerings for eventual display to a user, said social offerings being ranked according to eigenvalues of matrices associated with a social graph G describing connections between the user, the user'"'"'s friends and other individuals within a social network of the user.

15. The method of claim 14, wherein the social offerings are divided into categories and ranks for the social offerings are computed, for each of the categories, based on activities and communications of the user with the user'"'"'s friends and other individuals within the social network of the user for each category.

16. The method of claim 14, wherein the eigenvalues are used for ranking the social offerings based on actions of the user'"'"'s friends and other individuals within the social network of the user with respect to the social offerings.

17. The method of claim 14, wherein for the social graph G describing connections between the user and the user'"'"'s friends and other individuals within the social network of the user, a connectivity matrix C(G) having N rows and columns and being defined as

18. The method of claim 17, wherein values in a principal eigenvector associated with the principal eigenvalue of the connectivity matrix C(G) are used as ranks of nodes (users) in the social graph G and ranks of the social offerings are then computed as sums of ranks of nodes (users) in the social graph.

19. The method of claim 17, wherein computation of the principal eigenvalue of the connectivity matrix is carried out as an iterative process where a rank vector R of length N, where N is the number of nodes in the social graph G, associated with ranks of nodes in the social graph G, is initialized to a vector of non-zero values and then successively iterated according to:

20. The method of claim 14, wherein for each user a social graph with weights corresponding to levels of activity (affinity) between users is created.

21. The method of claim 20, wherein users who are more active in interacting with each other are assigned higher weights.

22. The method of claim 21, wherein for the social graph G describing connections between the user and the user'"'"'s friends and other individuals within the social network of the user, a connectivity matrix C(G) is computed and the eigenvalues comprise a principal eigenvalue of the connectivity matrix C(G), said principal eigenvalue of the connectivity matrix being computed through an iterative process where a rank vector or R of length N, where N is the number of nodes in the social graph G, associated with ranks of nodes in the social graph G, is initialized to a vector of non-zero values and then successively iterated according to

23. The method of claim 22, wherein the probabilities are derived from activities of users in interacting with each other.

24. The method of claim 14, wherein a subject ad determined as being relevant for display, and so displayed to the user, is accompanied by information indicating that a known friend of the user or another individual within the social network of the user has clicked on the subject ad.

25. The method of claim 24, wherein an order in which friends or connections of the user are displayed along with the subject ad is determined by computed ranks.

26. The method of claim 14, wherein the social offerings comprise one or more of:

search engine search results, advertisements, commercial product or service offerings, social game offerings, movie offerings, music offerings, travel offerings, vehicle offerings, and jobs offerings.