System and method for employing social networks for information discovery

• US 8,335,798 B2
• Filed: 10/24/2005
• Issued: 12/18/2012
• Est. Priority Date: 01/29/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Achlioptas, Dimitris
• Primary Examiner(s): BROWN, SHEREE N
• Application Number:
  US11/257,429
• Publication Number:
  US 20060041543A1
• Time in Patent Office: 2,612 Days
• Field of Search: 707/1, 707/3, 707/4, 707/10, 707/104.1, 707/784, 707/785
• US Class Current: 707/785
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

Systems and methods are provided that enable searches of social networks by acting as a “compass” that assists users in navigating the social network. Individual user participation is not required in response to queries from other users. The systems and methods offer navigational assistance or information as opposed to a traditional search which returns requested information, thus currently acceptable social mechanisms for arbitrating trust can be exploited. As a result, users do not make their personal information publicly searchable, while at the same time, they are protected from potential misrepresentations of facts.

Claims

1. A computer-implemented system for utilizing a social network comprising:

one or more processors;

one or more computer readable storage mediums maintaining computer-executable instructions that, when executed by the one or more processors, perform acts comprising;

receiving a plurality of buddy lists and personal information corresponding to a social network;

generating a plurality of directed subgraphs based on the buddy lists and the personal information, the directed subgraphs being subsets of a directed graph that functionally represents relationships between individuals and/or entities within the social network; and

encrypting the plurality of directed subgraphs to protect personal information returned as part of a search over the social network, wherein the encrypting encrypts a first portion of the directed graph and the encrypting further includes encrypting a second portion of the directed graph using a different encryption to provide layered encryption, the second portion comprising at least;

a part of the encrypted first portion of the graph; and

a part of the directed graph not included in the encrypted first portion.

2. The system of claim 1, the directed graph comprising a plurality of nodes, each node representing an individual or entity with the social network, the plurality of directed subgraphs having a sub graph limit wherein the subgraph limit is predefined number of nodes from a user of which the subgraph extends.

3. The system of claim 2, the subgraph limit being 3 degrees wherein a degree equals one path between two adjacent nodes.

4. The system of claim 2, the encrypted subgraphs respectively having a base user and being at least partially hidden from the base user.

5. The system of claim 4, the encrypted subgraphs being returnable to a number of users and being respectively searchable for a referral path by a base user.

6. A computer implemented method that utilizes a social network represented by a database storing a collection of information about individuals and/or entities and intra-relationships there between, the method comprising:

receiving information for users of the social network, the information comprising attribute and relationship information;

generating, by one or more processors, a directed graph of the social network by representing the individuals and/or entities as nodes and the relationship information as arcs interconnecting the nodes, the arcs having a directionality according to the relationship information received; and

encrypting a portion of the directed graph to protect a portion of the relationship information, the portion of the directed graph being encrypted being less than the complete directed graph, wherein the portion of the directed graph that is encrypted is a first portion of the directed graph and the encrypting further includes encrypting a second portion of the directed graph using a different encryption to provide layered encryption, the second portion comprising at least;

a part of the encrypted first portion of the graph; and

a part of the directed graph not included in the encrypted first portion.

7. The method of claim 6, the relationship information received including buddy lists.

8. The method of claim 6, further comprising entering the received information by the users employing predefined categories and default attributes.

9. The method of claim 6, further comprising assigning familiarities to the arcs, the familiarities being a portion of the relationship information.

10. The method of claim 6, the information received further comprising corroboration information, the corroboration information being assigned to the nodes.

11. The method of claim 6, further comprising:

generating a query for requested information;

searching the directed graph for the requested information; and

returning a referral path towards the requested information.

12. The method of claim 6 further comprising distributing the directed graph to a third party.

13. The method of claim 6, further comprising:

generating a subgraph that is a subset of the directed graph in response to a query for information, the subgraph being returned as at least a part of a response to the query for information; and

wherein the encrypting the portion of the directed graph includes an encrypting of the subgraph.

14. The method of claim 6, wherein the encrypting further includes encrypting the portion of the directed graph to protect at least a portion of personal information.

15. A computer implemented method that utilizes a social network represented by a database storing a collection of information about individuals and/or entities and intra-relationships there between, the method comprising:

receiving information for users of the social network, the information comprising attribute and relationship information;

generating, by one or more processors, a directed graph of the social network by representing the individuals and/or entities as nodes and the relationship information as arcs interconnecting the nodes, the arcs having a directionality according to the relationship information received; and

encrypting a portion of the directed graph to protect a portion of the relationship information, the portion of the directed graph being encrypted being less than the complete directed graph,

wherein the portion of the directed graph that is encrypted is a first portion of the directed graph and the encrypting further includes encrypting a second portion of the directed graph using a different encryption to provide layered encryption, the second portion comprising at least;

a part of the encrypted first portion of the graph, and

a part of the directed graph not included in the encrypted first portion.