Discovery of friends using social network graph properties

• US 8,744,976 B2
• Filed: 04/28/2008
• Issued: 06/03/2014
• Est. Priority Date: 04/28/2008
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Jagadish, Sunil, Parikh, Jignashu
• Primary Examiner(s): Kirlin, Amanda
• Application Number:
  US12/111,050
• Publication Number:
  US 20090271370A1
• Time in Patent Office: 2,227 Days
• Field of Search: 705/319
• US Class Current: 705/319
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: H04L 51/02 using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
• CPC Class Codes: H04L 51/216 Handling conversation history, e.g. grouping of messages in sessions or threads
• CPC Class Codes: H04L 51/48 Message addressing, e.g. address format or anonymous messages, aliases
• CPC Class Codes: H04L 51/52 for supporting social networking services

Abstract

Embodiments are directed towards providing a list of potential friends to a user based on an analysis of friends'"'"' contact lists. The user may provide a subset of friends within a contact list for analysis, along with a degree of separation over which to perform the analysis, and/or a minimum threshold number of occurrences for identifying a candidate friend. The subset of friends'"'"' contact lists may then be recursively traversed and merged, where common friends may be identified as members of a candidate set for suggesting friends to the user. In one embodiment, the candidate members may be retained within the candidate set if there is a commonality between the friends and the candidate that exceeds the minimum threshold. The candidate list may also be rank order using various approaches, including a weighted energy diffusion model based in part on a number of communications between the candidates.

Claims

1. A non-transitory processor readable storage medium that includes data and instructions, wherein the execution of the instructions on a computing device provides for managing social networking relationships over a network by enabling actions, comprising:

receiving a list of contacts within at least one contact list associated with a requesting user;

receiving access to a plurality of contact lists, each contact list within the plurality of contact lists being associated with a different contact within the received list of contacts;

determining a degree of separation over which to perform a search for a list of candidate friends;

searching within the plurality of contact lists to identify a list of candidate friends wherein each candidate friend is identified as a contact within at least two contact lists within the plurality of contact lists, independent of use of profile information;

recursively performing the searching of contact lists by replacing contact lists within the plurality of contact lists with contact lists associated with friends within the list of candidate friends and performing the recursive search until the determined degree of separation is exceeded;

generating a graph from at least a portion of the list of candidate friends which includes each degree of separation for the at least portion of the list of candidate friends and an initial amount of energy that is propagated from the requesting user to each candidate friend at each degree of separation within the graph, wherein each candidate friend at each edge of the graph corresponds to at least a defined threshold of energy;

ordering the at least portion of the list of candidate friends based on an input energy of each of the candidate friends after the initial amount of energy is propagated through the graph by distributing the initial amount of energy among each downstream relationship of the requesting user; and

providing, for display, the ordered list of candidate friends to the requesting user.

2. The non-transitory processor readable storage medium of claim 1, wherein propagating the initial amount of energy through the graph results in an equal distribution of friends of a friend within the graph.

3. The non-transitory processor readable medium of claim 1, wherein the execution of the instructions enable actions, further comprising:

receiving a request from the requesting user to communicate with at least one contact within the ordered list of friends;

sending an invite to the at least one contact indicating that the requesting user would like to initiate a communication; and

if the at least on contact indicates a consent, enabling a communication between the requesting user and the at least one contact to proceed.

4. The non-transitory processor readable storage medium of claim 1, wherein the execution of the instructions enable actions, further comprising:

employing the list of candidate friends to identify another plurality of contact lists, wherein each contact list in the other plurality of contact lists is associated with different friends within the list of candidate friends; and

searching within the other plurality of contact lists to identify additions to the list of candidate friends wherein each additional candidate friend is identified as a contact in at least two contact lists within the other plurality of contact lists.

5. A method for managing social networking relationships over a network with a network device that performs actions, comprising:

receiving a list of contacts from within an initial contact list;

determining a degree of separation over which to perform a search for a list of candidate friends;

recursively employing the network device for performing the following actions until he determined degree of separation is exceeded;

searching contact lists, where each contact list is associated with one of the contacts within the list of contacts, to identify the list of candidate friends by adding to the list of candidate friends any contact that is in at least two contact lists, wherein the two contact lists are associated with different contacts within the list of contacts, wherein the searching is performed by the network device;

accessing contact lists associated with each added contact within the list of candidate friends; and

updating the list of contacts based on the added contacts to the list of candidate friends; and

generating a graph from at least a portion of the list of candidate friends which includes each degree of separation for the at least portion of the list of candidate friends and an initial amount of energy that is propagated from a user to each candidate friend at each degree of separation within the graph, wherein each candidate friend at each edge of the graph corresponds to at least a defined threshold of energy, wherein the generating is performed by the network device;

ordering the at least portion of the list of candidate friends based on an input energy of each of the candidate friends after the initial amount of energy is propagated through the graph by distributing the initial amount of energy among each downstream relationship of the requesting user, wherein the ordering is performed by the network device; and

displaying the list of candidate friends to the user, such that the user is enabled to seek communications with at least one candidate friend within the list of candidate friends.

6. The method of claim 5, wherein the recursive search is independent of profile information associated with a contact within a contact list.

7. The method of claim 5, further comprising:

truncating display of the list of candidate friends by inhibiting display of candidate friends having a value less than the threshold value, wherein the value represents at least a number of friends having the candidate friend in their respective contact lists.

8. A network device to manage a social networking interaction over a network, comprising:

a transceiver to send and receive data over a network; and

a processor that is operative to perform actions, comprising;

receiving a list of contacts from within an initial contact list from a requesting user;

determining a degree of separation over which to perform a search for a list of candidate friends;

recursively performing the following until the determined degree of separation is exceeded;

searching contact lists, where each contact list is associated with one of the contacts within the list of contacts, to identify the list of candidate friends by adding to the list of candidate friends any contact that is in at least two contact lists, wherein the two contact lists are associated with different contacts within the list of contacts;

accessing contact lists associated with each added contact within the list of candidate friends; and

updating the list of contacts based on the added contacts to the list of candidate friends; and

generating a graph from at least a portion of the list of candidate friends which includes each degree of separation for the at least portion of the list of candidate friends and an initial amount of energy that is propagated from the requesting user to each candidate friend at each degree of separation within the graph, wherein each candidate friend at each edge of the graph corresponds to at least a defined threshold of energy;

ordering the at least portion of the list of candidate friends based on an input energy of each of the candidate friends after the initial amount of energy propagated through the graph by distributing the initial amount of energy among each downstream relationship of the requesting user; and

displaying the list of candidate friends to the requesting user, such that the requesting user is enabled to seek communications with at least one candidate friend within the list of candidate friends.

9. The network device of claim 8, wherein displaying the list of candidate friends further comprises inhibiting display of candidate friends within the list having an associated value less than a threshold.

10. The network device of claim 8, wherein at least one contact list includes at least one contact that is identified as being excluded from the searching.

11. The network device of claim 8, wherein the requesting user is enabled to seek communications further comprises proxying a communication to the at least one candidate friend from the requesting user, such that the requesting user is unable to communicate with the at least one candidate friend directly, until the at least one candidate friend provides authorization.

12. A mobile device for enabling a communications within a social network over a network, comprising:

a memory arranged to store data and instructions;

an input interface for receiving requests and sending responses; and

a processor arranged to execute the stored instructions to enable actions embodied by at least a portion of the stored instructions, the actions comprising;

receiving a list of contacts from within an initial contact list;

determining a degree of separation over which to perform a search for a list of candidate friends;

recursively employing the mobile device for performing the following actions until the determined degree of separation is exceeded;

searching contact lists, where each contact list is associated with one of the contacts within the list of contacts, to identify the list of candidate friends by adding to the list of candidate fiends any contact that is in at least two contact lists, wherein the two contact lists are associated with different contacts within the list of contacts;

accessing contact lists associated with each added contact within the list of candidate friends; and

updating the list of contacts based on the added contacts to the list of candidate friends; and

generating a graph from at least a portion of the list of candidate friends which includes each degree of separation for the at least portion of the list of candidate friends and an initial amount of energy that is propagated from a user to each candidate friend at each degree of separation within the graph, wherein each candidate friend at each edge of the graph corresponds to at least a defined threshold of energy;

ordering the at least portion of the list of candidate friends based on an input energy of each of the candidate friends after the initial amount of energy is propagated through the graph by distributing the initial amount of energy among each downstream relationship of the requesting user; and

displaying the list of candidate friends to the user, such that the user is enabled to seek communications with at least one candidate friend within the list of candidate friends.

13. The mobile device of claim 12, wherein the searching of contact lists further comprises performing the searching of at least one contact list residing on another mobile device.

14. The mobile device of claim 12, wherein ordering the list of candidate friends further comprises employing at least one of a most common friend of friends ordering, a diffusion based ordering, a weighted energy propagation ordering, or an ordering based on available profile information.

15. The mobile device of claim 12, wherein at least two contact lists are associated with a same contact, and wherein the two contact lists is associate with different communication mechanisms.