# US 2013/0159100 A1 · Selecting advertisements for users of a social networking system using collaborative filtering

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0159100 A1
- Document ID: US20130159100A1
- Status: Published application
- Kind: A1
- Application number: 13/330,502
- Filed: 2011-12-19
- Published: 2013-06-20
- Earliest claimed: 2011-12-19
- Inventors: Rajat Raina; Gokul Rajaram; Hong Ge; Junfeng Pan; John Hegeman
- Web page: https://patentgrep.com/patent/US20130159100A1

## CPC

- G06Q 30/0241: Advertisements
- G06Q 10/42: Determination of affinities or common interests between users
- G06Q 10/48: using social graphs
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A social networking system selects advertisements for its users using collaborative filtering based on the users' interactions with objects in the social networking system. The objects may be games, pages, groups, deals, messages, content items, advertisements, or any other object with which a user may interact in the system. The system may identify a viewing user's interaction with a first object, determine a second object that is similar to the first object based on interactions of users with both of the objects, and send an advertisement associated with the second object to the viewing user. The system determines a second object based a similarity score between the first object and the second object, which may be a measure of users who have interacted with both objects and may be normalized by a number of user interactions by the users with the objects.

## Claims

### Claim 1

A method comprising:
maintaining an interaction log by a social networking system, the interaction log including information about a plurality of user interactions with a plurality of objects in the social networking system;
computing a similarity score for each of a plurality of pairs of the plurality of objects, each similarity score based on a measure of users who have interacted with both of the pair of objects, normalized by a number of interactions by the users with one or both of the pair of objects;
identifying, from the interaction log, an interaction with a first object of the plurality of objects by a viewing user;
selecting a second object from the plurality of objects based on the similarity score between the first and the second object; and
sending an advertisement associated with the second object for display to the viewing user.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating a user-object interaction matrix data structure from the interaction log, the user-object interaction matrix data structure storing a user-object interaction matrix, the user-object matrix including values for a plurality of user-object pairs,
wherein computing the similarity score for a pair of objects comprises obtaining the measure of users who have interacted with both of the pair of objects from the values in the user-object interaction matrix.

### Claim 3 (depends on 2)

The method of claim 2, wherein the values for the plurality of user-object pairs comprise binary values, and wherein each binary value indicates whether an interaction exists between a user and an object.

### Claim 4 (depends on 2)

The method of claim 2, wherein the values for the plurality of user-object pairs comprise non-binary values computed based on a measure of the interactions between users and objects.

### Claim 5 (depends on 4)

The method of claim 4, wherein the values are decayed based on an age of the corresponding interactions.

### Claim 6 (depends on 2)

The method of claim 2, wherein the user-object interaction matrix data is a sparse matrix.

### Claim 7 (depends on 2)

The method of claim 2, wherein the similarity score is computed based on comparing rows of the user-object interaction matrix.

### Claim 8 (depends on 2)

The method of claim 2, wherein is the similarity score is computed using one or more map and reduce steps.

### Claim 9 (depends on 1)

The method of claim 1, wherein the similarity scores are computed based on interactions of only those users who are part of a segment of all users of the social networking system.

### Claim 10 (depends on 9)

The method of claim 9, wherein the segment of users is defined by at least one of gender, age, and geographic location.

### Claim 11 (depends on 1)

The method of claim 1, wherein the plurality of objects are selected from a group consisting of: games, pages, groups, deals, content items, messages, advertisements, and any combination thereof.

### Claim 12 (depends on 1)

The method of claim 1, wherein the advertisement includes a suggestion to interact with the second object.

### Claim 13 (depends on 1)

The method of claim 1, wherein the similarity score for a pair of objects is determined based on the formula:
Object


A
⋂
Object


B
(
Object


A
)

(
Object


B
)
,
where Object A ∩Object B comprises a measure of users who have interacted with both the first and second objects, Object A comprises a measure of users who have interacted with the first object, and Object B comprises a measure of users who have interacted with the second object.

### Claim 14

A non-transitory computer readable storage medium storing one or more programs configured to be executed by a server system, the one or more programs comprising instructions for:
maintaining an interaction log by a social networking system, the interaction log including information about a plurality of user interactions with a plurality of objects in the social networking system;
computing a similarity score for each of a plurality of pairs of the plurality of objects, each similarity score based on a measure of users who have interacted with both of the pair of objects, normalized by a number of interactions by the users with one or both of the pair of objects;
identifying, from the interaction log, an interaction with a first object of the plurality of objects by a viewing user;
selecting a second object from the plurality of objects based on the similarity score between the first and the second object; and
sending an advertisement associated with the second object for display to the viewing user.

### Claim 15

A method comprising:
maintaining an interaction log by a social networking system, the interaction log including information about a plurality of user interactions with a plurality of objects in the social networking system;
computing a similarity score between a first object and a second object, the similarity score based on a measure of users who have interacted with both the first object and the second object, normalized by a number of interactions by users with one or both of the first object and the second object.
identifying, from the interaction log, an interaction with a first object by a viewing user;
selecting the second object from the plurality of objects based on the similarity score between the first object and the second object; and
sending an advertisement associated with the second object for display to the viewing user.