Using social networks while respecting access control lists

• US 8,214,883 B2
• Filed: 10/22/2007
• Issued: 07/03/2012
• Est. Priority Date: 10/22/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Obasanjo, Oludare, Nichols, David, Sethi, Bhupinder, Ming, Paul
• Primary Examiner(s): ZECHER, CORDELIA P K
• Application Number:
  US11/975,771
• Publication Number:
  US 20090106822A1
• Time in Patent Office: 1,716 Days
• Field of Search: 726/4
• US Class Current: 726/4
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 63/102 Entity profiles
• CPC Class Codes: H04L 67/306 User profiles

Abstract

Techniques are described for use with social networks and associated access information, such as access control lists, indicating which users are allowed to access the social networks. The social networks represent relationships between users. The social networks and access control lists may be represented in a graph which is traversed in connection with performing different operations using the social networks.

Claims

1. A computer-implemented method for determining whether a first user and a second user of a social networking website are connected comprising:

allowing, by a server of the social networking website, each user to define a social network list, the social network list defined by a user indicating other users having a direct relationship with the user;

allowing, by the server, each user to define an access control list, the access control list defined by a user indicating other users granted access to view direct relationships indicated by the social network list defined by the user;

receiving, by the server, an inquiry from the first user to discover whether the first user is indirectly related to a second user through one or more other users;

determining, by the server, that a distance represented by a number of hops between the first user and the second user is within a maximum distance;

receiving, by the server, a graph representing the social network lists and the access control lists defined by each of the first user and the one or more other users between the first user and the second user, wherein;

the graph includes all paths connecting a starting node representing the first user and a target node representing the second user which are within the maximum distance,

each path of the graph includes links connecting the starting node and the target node through one or more intervening nodes representing each of the one or more other users between the first user and the second user, and

if a user represented by an intervening node in one more paths of the graph has defined an access control list which includes the first user, an edge connecting the intervening node and the starting node is included in the one or more paths of the graph to indicate that the first user has been granted access to view direct relationships indicated by a social network list defined by the user represented by the intervening node;

traversing, by the server, the graph to determine a viewable path from the starting node to the target node, wherein each intervening node in the viewable path is connected to the starting node by an edge indicating that the first user has been granted access to view the direct relationships indicated by each social network list defined by each user represented by each intervening node; and

outputting, by the server, the viewable path in response to the inquiry from the first user.

2. The method of claim 1, wherein a breadth-first technique is performed to determine the paths connecting the starting node and the target node.

3. The method of claim 1, wherein at least one path in the graph includes an intervening node at a current level of traversal that represents a user who is included in the social network list defined by the first user.

4. The method of claim 3, wherein the at least one path in the graph includes a descendant node at a next level of traversal that represents a user who is included in the social network list defined by the user represented by the intervening node at the current level of traversal.

5. The method of claim 4, wherein a determination is made as to whether the first user is included in the access control list defined by the user represented by the intervening node at the current level of traversal before proceeding to the descendant node at the next level of traversal.

6. The method of claim 5, wherein the descendant node is traversed if there is an edge connecting the intervening node at the current level of traversal and the starting node.

7. The method of claim 1, further comprising:

determining, by the server, all paths originating from the starting node which are within the maximum distance.

8. The method of claim 7, further comprising:

determining, by the server, whether the target node is included in one of the paths originating from the starting node.

9. The method of claim 1, further comprising:

determining, by the server, a plurality of viewable paths from the starting node to the target node; and

outputting, by the server, a response to the inquiry from the first user that indicates the plurality of viewable paths.

10. The method of claim 1, wherein a user defines an access control list by explicitly listing each other user included in the access control list.

11. The method of claim 1, wherein a user defines an access control list implicitly by defining a particular distance.

12. The method of claim 1, wherein the access control list defined by the first user includes all users included in the social network list defined by the first user.

13. The method of claim 1, wherein the access control list defined by the first user does not include all users included in the social network list defined by the first user.

14. A computer readable storage medium that does not consist of a signal, the computer readable storage medium storing computer-executable instructions that, when executed, cause a computing device to perform a computer-implemented method for determining whether a first user and a second user of a social networking website are connected, the method comprising:

allowing each user to define a social network list, the social network list defined by a user indicating other users having a direct relationship with the user;

allowing each user to define an access control list, the access control list defined by a user indicating other users granted access to view direct relationships indicated by the social network list defined by the user;

receiving, from the first user, an inquiry to discover whether the first user is indirectly related to a second user through one or more other users;

determining that a distance represented by a number of hops between the first user and the second user is within a maximum distance;

receiving a graph representing the social network lists and the access control lists defined by each of the first user and the one or more other users between the first user and the second user, wherein;

the graph includes all paths connecting a starting node representing the first user and a target node representing the second user which are within the maximum distance,

each path of the graph includes links connecting the starting node and the target node through one or more intervening nodes representing each of the one or more other users between the first user and the second user, and

if a user represented by an intervening node in one more paths of the graph has defined an access control list which includes the first user, an edge connecting the intervening node and the starting node is included in the one or more paths of the graph to indicate that the first user has been granted access to view direct relationships indicated by a social network list defined by the user represented by the intervening node;

traversing the graph to determine a viewable path from the starting node to the target node, wherein each intervening node in the viewable path is connected to the starting node by an edge indicating that the first user has been granted access to view the direct relationships indicated by each social network list defined by each user represented by each intervening node; and

outputting the viewable path in response to the inquiry from the first user.

15. The computer readable storage medium of claim 14, wherein the access control list defined by the first user includes all users included in the social network list defined by the first user.

16. The computer readable storage medium of claim 14, wherein the access control list defined by the first user does not include all users included in the social network listed defined by the first user.

17. The computer readable storage medium of claim 14, wherein method further comprises:

determining a plurality of viewable paths from the starting node to the target node; and

outputting a response to the inquiry from the first user that indicates the plurality of viewable paths.

18. A computing device comprising:

a processor for executing computer-executable instructions; and

memory storing computer-executable instructions for performing a method to determine whether a first user and a second user of a social networking website are connected, the method comprising;

allowing each user to define a social network list, the social network list defined by a user indicating other users having a direct relationship with the user;

allowing each user to define an access control list, the access control list defined by a user indicating other users granted access to view direct relationships indicated by the social network list defined by the user;

receiving, from the first user, an inquiry to discover whether the first user is indirectly related to a second user through one or more other users;

determining that a distance represented by a number of hops between the first user and the second user is within a maximum distance;

receiving a graph representing the social network lists and the access control lists defined by each of the first user and the one or more other users between the first user and the second user, wherein;

the graph includes all paths connecting a starting node representing the first user and a target node representing the second user which are within the maximum distance,

each path of the graph includes links connecting the starting node and the target node through one or more intervening nodes representing each of the one or more other users between the first user and the second user, and

if a user represented by an intervening node in one more paths of the graph has defined an access control list which includes the first user, an edge connecting the intervening node and the starting node is included in the one or more paths of the graph to indicate that the first user has been granted access to view direct relationships indicated by a social network list defined by the user represented by the intervening node;

traversing the graph to determine a viewable path from the starting node to the target node, wherein each intervening node in the viewable path is connected to the starting node by an edge indicating that the first user has been granted access to view the direct relationships indicated by each social network list defined by each user represented by each intervening node; and

outputting the viewable path in response to the inquiry from the first user.

19. The computing device of claim 18, wherein the access control list defined by the first user does not include all users included in the social network list defined by the first user.

20. The computing device of claim 18, wherein the method further comprises:

determining a plurality of viewable paths from the starting node to the target node; and

outputting a response to the inquiry from the first user that indicates the plurality of viewable paths.