Network-aware Product Rollout in Online Social Networks

Patent metadata

Field	Value
Publication number	US-2015019639-A1
Application number	US-201313939093-A
Country	US
Kind code	A1
Filing date	Jul 10, 2013
Priority date	Jul 10, 2013
Publication date	Jan 15, 2015
Grant date	—

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.

First claim

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 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 a first set of users corresponding to a first set of clusters of the plurality of clusters; and determining a treatment effect of the treatment on the users of the first set of users based on a network exposure to the treatment for each user, wherein, for each 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 , further comprising applying the treatment to a second set of users corresponding to a second set of clusters of the plurality of clusters, the second set of clusters being discrete from the first set of clusters.

5 . 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.

6 . The method of claim 5 , 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.

7 . 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.

8 . (canceled)

9 . (canceled)

10 . 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.

11 . 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.

12 . The method of claim 1 , wherein the threshold number of nodes is all nodes.

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

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

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

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

17 . 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.

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 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 a first set of users corresponding to a first set of clusters of the plurality of clusters; and determine a treatment effect of the treatment on the users of the first set of users based on a network exposure to the treatment for each user, wherein, for each 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 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 a first set of users corresponding to a first set of clusters of the plurality of clusters; and determine a treatment effect of the treatment on the users of the first set of users based on a network exposure to the treatment for each user, wherein, for each 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.

Assignees

• Facebook Inc

Inventors

• Marlow Cameron Alexander
• Eckles Dean
• Karrer Brian
• Ugander Johan
• Backstrom Lars Seren
• Kleinberg Jon

Classifications

• G06Q10/40 Primary

  Business processes related to social networking or social networking services · CPC title

• H04W4/21

  for social networking applications · CPC title

• G06Q30/0244 Primary

  Optimization · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L67/306

  User profiles · CPC title