GENERATING AN IMPLIED OBJECT GRAPH BASED ON USER BEHAVIOR

• US 20140074863A1
• Filed: 05/29/2013
• Published: 03/13/2014
• Est. Priority Date: 09/12/2012
• Status: Active Grant

• Current Assignee: Flipboard Incorporated
• Original Assignee: Flipboard Incorporated
• Inventors: van Hoff, Arthur Anthonie, Walkingshaw, Andrew David, Aleksandrovsky, Boris Lev, Breunig, Markus
• Granted Patent: US 9,037,592 B2
• Time in Patent Office: Days
• US Class Current: 707/748
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 65/40 Support for services or applications

Abstract

An online system generates implied links between objects distributed by the online system based on a plurality of users'"'"' behaviors with respect to the objects. For a behavior of a user with respect to an object that satisfies a link criterion, the online system identifies a connection between the user and the object. Local object graphs are generated to represent the relationships between the objects connected to each user, and the local object graphs are merged into a global object graph. An adjacency matrix is extracted from the global object graph as a representation of the strength of relationships between the objects distributed by the online system. The online system may then apply graph analysis techniques to the adjacency matrix, thereby analyzing the relationships between the objects without relying upon explicit links between the objects.

Claims

1. A method for generating an implied object graph, the method comprising:

identifying a plurality of user behaviors by an online system, each user behavior comprising an interaction with an object of a plurality of objects and performed by a user of a plurality of users of the online system;

generating a plurality of local object graphs, each local object graph associated with a user of the plurality of users and comprising a subset of the objects with which the user interacted and links between objects of the subset;

determining a weight for each of the links in the local object graphs, the weight determined based on the corresponding user behavior;

merging the plurality of local object graphs to generate a global object graph, the global object graph comprising the plurality of objects and links between the plurality of objects;

determining a weight for each of the links in the global object graph based on the weights of the merged local object graphs; and

storing the links and the corresponding weights from the global object graph in an adjacency matrix.

2. The method of claim 1, further comprising:

ranking the objects in the online system based on the adjacency matrix and the weights.

3. The method of claim 1, wherein identifying the plurality of user behaviors comprises:

monitoring the user behaviors over a sliding time window.

4. The method of claim 1, wherein a user behavior of the plurality of user behaviors is a user viewing the object, and wherein generating a plurality of local object graphs comprises:

responsive to the user viewing the object, identifying a connection between the user and the object.

5. The method of claim 1, wherein generating the plurality of local objects graphs comprises:

responsive to a user of the plurality of users interacting with an object for longer than a threshold dwell time, identifying a connection between the object and the user.

6. The method of claim 1, wherein generating the plurality of local object graphs comprises:

responsive to a user of the plurality of users sharing an object on a social networking system, identifying a connection between the object and the user.

7. The method of claim 1, wherein generating the plurality of local object graphs comprises:

identifying connections between respective objects and users responsive to the corresponding user behavior having occurred within a recent time period.

8. The method of claim 1, wherein a user behavior of the plurality of user behaviors is an explicit feedback signal supplied by a user and corresponding to an object of the plurality of objects, and wherein generating the plurality of local object graphs comprises:

responsive to receiving the explicit feedback signal, identifying a connection between the user and the corresponding object.

9. The method of claim 1, wherein determining the weight for each of the links in the local object graphs comprises:

determining the weight based on a type of the corresponding user behavior.

10. The method of claim 1, wherein determining the weight for each of the links in the local object graphs comprises:

decaying the weight based on a time since the corresponding user behavior was identified.

11. A non-transitory computer-readable medium storing computer program instructions for generating an implied object graph, the computer program instructions comprising instructions for:

identifying a plurality of user behaviors by an online system, each user behavior comprising an interaction with an object of a plurality of objects and performed by a user of a plurality of users of the online system;

generating a plurality of local object graphs, each local object graph associated with a user of the plurality of users and comprising a subset of the objects with which the user interacted and links between objects of the subset;

determining a weight for each of the links in the local object graphs, the weight determined based on the corresponding user behavior;

merging the plurality of local object graphs to generate a global object graph, the global object graph comprising the plurality of objects and links between the plurality of objects;

determining a weight for each of the links in the global object graph based on the weights of the merged local object graphs; and

storing the links and the corresponding weights from the global object graph in an adjacency matrix.

12. The non-transitory computer-readable storage medium of claim 11, the instructions further comprising instructions for:

ranking the objects in the online system based on the adjacency matrix and the weights.

13. The non-transitory computer-readable storage medium of claim 11, wherein identifying the plurality of user behaviors comprises:

monitoring the user behaviors over a sliding time window.

14. The non-transitory computer-readable storage medium of claim 11, wherein a user behavior of the plurality of user behaviors is a user viewing the object, and wherein generating a plurality of local object graphs comprises:

responsive to the user viewing the object, identifying a connection between the user and the object.

15. The non-transitory computer-readable storage medium of claim 11, wherein generating the plurality of local objects graphs comprises:

responsive to a user of the plurality of users interacting with an object for longer than a threshold dwell time, identifying a connection between the object and the user.

16. The non-transitory computer-readable storage medium of claim 11, wherein generating the plurality of local object graphs comprises:

responsive to a user of the plurality of users sharing an object on a social networking system, identifying a connection between the object and the user.

17. The non-transitory computer-readable storage medium of claim 11, wherein generating the plurality of local object graphs comprises:

identifying connections between respective objects and users responsive to the corresponding user behavior having occurred within a recent time period.

18. The non-transitory computer-readable storage medium of claim 11, wherein a user behavior of the plurality of user behaviors is an explicit feedback signal supplied by a user and corresponding to an object of the plurality of objects, and wherein generating the plurality of local object graphs comprises:

responsive to receiving the explicit feedback signal, identifying a connection between the user and the corresponding object.

19. The non-transitory computer-readable storage medium of claim 11, wherein determining the weight for each of the links in the local object graphs comprises:

determining the weight based on a type of the corresponding user behavior.

20. The non-transitory computer-readable storage medium of claim 11, wherein determining the weight for each of the links in the local object graphs comprises:

decaying the weight based on a time since the corresponding user behavior was identified.