System and method for managing an online social network

• US 9,241,027 B2
• Filed: 10/08/2013
• Issued: 01/19/2016
• Est. Priority Date: 05/26/2004
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Galbreath, Nicholas, Predosin, Mirko
• Primary Examiner(s): SMARTH, GERALD A
• Application Number:
  US14/048,925
• Publication Number:
  US 20140040378A1
• Time in Patent Office: 833 Days
• Field of Search: 709/204
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 21/629 to features or functions of an application
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 65/403 Arrangements for multi-party communication, e.g. for conferences data switching systems for conference H04L12/18; arrangements for connecting several subscribers to a common circuit, i.e. affording conference facilities H04M3/56; television conferencing systems H04N7/15
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/306 User profiles

Abstract

An online social network is managed using one server for database management tasks and another server, preferably in a distributed configuration, for CPU-intensive computational tasks, such as finding a shortest path between two members or a degree of separation between two members. The additional server has a memory device containing relationship information between members of the online social network and carries out the CPU-intensive computational tasks using this memory device. With this configuration, the number of database lookups is decreased and processing speed is thereby increased.

Claims

1. A method comprising:

responsive to a processing request from an application server to handle a task to determine all registered users of the online social network who are within N degrees of separation from a registered user M, executing, by one or more computing devices, the task by using a graph data structure representing a social network map, the social network map being based on relationship information stored in a database indicating which of the registered users are friends in the online social network;

for each registered user R of the online network that is connected to the registered user M;

determining, by the one or more computing devices, a degree of separation from the registered user M, the degree of separation corresponding to the shortest path between the registered user R and the registered user M; and

when the registered user R is within N degrees of separation from the registered user M, providing, by the one or more computing devices, to the application server, a user ID for the registered user R; and

for each registered user R of the online network that is not connected to the registered user M, providing, by the one or more computing devices, to the application server, an indication that the registered user R is not connected to the registered user M.

2. The method of claim 1, wherein the relationship information comprises a plurality of entries, the entries including user IDs of the registered users.

3. The method of claim 1, wherein the graph data structure representing the social network map is stored in a dedicated memory device communicably coupled to the one or more computing devices.

4. The method of claim 3, wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM.

5. The method of claim 3, further comprising:

regenerating, at periodic intervals, the graph data structure based on changes in the relationship information stored in the database.

6. The method of claim 1, wherein the shortest path between the registered user R and the registered user M is calculated using a shortest path algorithm for a node network defined by an adjacency list.

7. The method of claim 1, wherein two registered users are friends in the online social network if they are each represented by nodes within the social network map and if the two nodes are connected within one degree of separation.

8. A graph server comprising:

one or more processors; and

a memory coupled to the processors and comprising instructions executable by the processors, the processors being operable when executing the instructions to;

responsive to a processing request from an application server to handle a task to determine all registered users of the online social network who are within N degrees of separation from a registered user M, execute the task by using a graph data structure representing a social network map, the social network map being based on relationship information stored in a database indicating which of the registered users are friends in the online social network;

for each registered user R of the online network that is connected to the registered user M;

determine a degree of separation from the registered user M, the degree of separation corresponding to the shortest path between the registered user R and the registered user M; and

when the registered user R is within N degrees of separation from the registered user M, provide to the application server, a user ID for the registered user R; and

for each registered user R of the online network that is not connected to the registered user M, provide, to the application server, an indication that the registered user R is not connected to the registered user M.

9. The graph server of claim 8, wherein the relationship information comprises a plurality of entries, the entries including user IDs of the registered users.

10. The graph server of claim 8, wherein the graph data structure representing the social network map is stored in a dedicated memory device communicably coupled to the one or more computing devices.

11. The graph server of claim 10, wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM.

12. The graph server of claim 10, wherein the processors are further operable when executing the instructions to:

regenerate, at periodic intervals, the graph data structure based on changes in the relationship information stored in the database.

13. The graph server of claim 8, wherein the shortest path between the registered user R and the registered user M is calculated using a shortest path algorithm for a node network defined by an adjacency list.

14. The graph server of claim 8, wherein two registered users are friends in the online social network if they are each represented by nodes within the social network map and if the two nodes are connected within one degree of separation.

15. One or more computer-readable non-transitory storage media embodying software that is operable when executed to:

responsive to a processing request from an application server to handle a task to determine all registered users of the online social network who are within N degrees of separation from a registered user M, execute the task by using a graph data structure representing a social network map, the social network map being based on relationship information stored in a database indicating which of the registered users are friends in the online social network;

for each registered user R of the online network that is connected to the registered user M;

determine a degree of separation from the registered user M, the degree of separation corresponding to the shortest path between the registered user R and the registered user M; and

when the registered user R is within N degrees of separation from the registered user M, provide to the application server, a user ID for the registered user R; and

for each registered user R of the online network that is not connected to the registered user M, provide to the application server, an indication that the registered user R is not connected to the registered user M.

16. The media of claim 15, wherein the relationship information comprises a plurality of entries, the entries including user IDs of the registered users.

17. The media of claim 15, wherein the graph data structure representing the social network map is stored in a dedicated memory device communicably coupled to the one or more computing devices.

18. The media of claim 17, wherein the dedicated memory device is random access memory (RAM) and the graph data structure is stored in the RAM.

19. The media of claim 17, wherein the software is further operable when executed to:

regenerate, at periodic intervals, the graph data structure based on changes in the relationship information stored in the database.

20. The media of claim 15, wherein the shortest path between the registered user R and the registered user M is calculated using a shortest path algorithm for a node network defined by an adjacency list.