Network-aware product rollout in online social networks

• US 9,292,884 B2
• Filed: 07/10/2013
• Issued: 03/22/2016
• Est. Priority Date: 07/10/2013
• Status: Expired due to Fees

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Marlow, Cameron Alexander, Eckles, Dean, Karrer, Brian, Ugander, Johan, Backstrom, Lars Seren, Kleinberg, Jon
• Primary Examiner(s): Lazaro, David
• Assistant Examiner(s): ABU ROUMI, MAHRAN Y
• Application Number:
  US13/939,093
• Publication Number:
  US 20150019639A1
• Time in Patent Office: 986 Days
• Field of Search: 345/440, 709/204
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/0244 Optimization
• CPC Class Codes: G06Q 50/01 Social networking
• 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
• CPC Class Codes: H04L 67/535 Tracking the activity of the user network monitoring arrangements H04L43/00; recording of computer activity G06F11/34
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

In one embodiment, a method includes accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each node corresponding to a user of an online social network, identifying a plurality of clusters in the social graph using graph clustering, providing a treatment to a first set of users based on the clusters, and determining a treatment effect treatment for the users in the first set based on a network exposure to the treatment for each user.

Claims

1. A method comprising, by one or more processors associated with one or more computing devices:

accessing a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the plurality of nodes corresponding to a plurality of users associated with an online social network, respectively;

identifying a plurality of non-overlapping clusters in the social graph using graph clustering, each cluster comprising a discrete set of nodes from the plurality of nodes;

providing a treatment to at least a first set of users and a second set of users, the first and second sets of users corresponding to a first set of clusters and a second set of clusters of the plurality of clusters, respectively, the first set of clusters being discrete from the second set of clusters; and

determining, for each of at least the first and second sets of users, a treatment effect of the treatment on the users of the set of users based on a network exposure to the treatment for each user, wherein, for each respective cluster, the network exposure of the nodes in the cluster is absolute k-neighborhood exposure, absolute k-core exposure, fractional q-neighborhood exposure, or fractional q-core exposure.

2. The method of claim 1, wherein the treatment effect is a function of a network effect of the treatment for the users and an individual effect of the treatment for the users.

3. The method of claim 1, further comprising modifying the treatment based on the determined treatment effect of the treatment.

4. The method of claim 1, wherein, for each cluster, the network exposure of the nodes in the cluster has a specified distribution ranging from a threshold level of network exposure to a maximum level of network exposure.

5. The method of claim 4, wherein determining the treatment effect of the treatment comprises determining the treatment effect of the treatment for different levels of network exposure of the specified distribution range.

6. The method of claim 1, wherein, for each cluster, the network exposure of the nodes in the cluster is full neighborhood exposure or component exposure.

7. The method of claim 1, wherein, for each cluster, the social-graph affinity of the nodes in the cluster with respect to the other nodes in the cluster is greater than a threshold social-graph affinity.

8. The method of claim 1, wherein a node in a particular cluster is network exposed if a threshold fractions of nodes within one degree of separation of the node are in the same treatment condition.

9. The method of claim 1, wherein a threshold number of nodes is all nodes.

10. The method of claim 1, wherein providing the treatment comprises randomizing between treatment and control to the clusters of the plurality of clusters.

11. The method of claim 1, wherein the treatment is a particular advertisement.

12. The method of claim 1, wherein the treatment is a particular product or feature of a third-party system.

13. The method of claim 1, wherein the treatment is a particular product or feature of the online social network.

14. The method of claim 1, wherein identifying the plurality of clusters comprises identifying clusters such that a threshold number of nodes in each cluster is network exposed with respect to the other nodes in the cluster.

15. The method of claim 1, wherein the determined treatment effect of the treatment on the users in a particular cluster is an average treatment effect, τ

, wherein

16. The method of claim 1, further comprising:

determining an estimated average treatment effect between two randomized clusters, {circumflex over (τ

)}, wherein

17. The method of claim 1, wherein for each identified cluster, a threshold number of nodes in each cluster is network exposed with respect to the other nodes in the cluster.

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

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the plurality of nodes corresponding to a plurality of users associated with an online social network, respectively;

identify a plurality of non-overlapping clusters in the social graph using graph clustering, each cluster comprising a discrete set of nodes from the plurality of nodes;

provide a treatment to at least a first set of users and a second set of users, the first and second sets of users corresponding to a first set of clusters and a second set of clusters of the plurality of clusters, respectively, the first set of clusters being discrete from the second set of clusters; and

determine, for each of at least the first and second sets of users, a treatment effect of the treatment on the users of the set of users based on a network exposure to the treatment for each user, wherein, for each respective cluster, the network exposure of the nodes in the cluster is absolute k-neighborhood exposure, absolute k-core exposure, fractional q-neighborhood exposure, or fractional q-core exposure.

19. A system comprising:

one or more processors; and

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

access a social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, each of the edges between two of the nodes representing a single degree of separation between them, the plurality of nodes corresponding to a plurality of users associated with an online social network, respectively;

identify a plurality of non-overlapping clusters in the social graph using graph clustering, each cluster comprising a discrete set of nodes from the plurality of nodes;

provide a treatment to at least a first set of users and a second set of users, the first and second sets of users corresponding to a first set of clusters and a second set of clusters of the plurality of clusters, respectively, the first set of clusters being discrete from the second set of clusters; and

determine, for each of at least the first and second sets of users, a treatment effect of the treatment on the users of the set of users based on a network exposure to the treatment for each user, wherein, for each respective cluster, the network exposure of the nodes in the cluster is absolute k-neighborhood exposure, absolute k-core exposure, fractional q-neighborhood exposure, or fractional q-core exposure.