Generating an implied object graph based on user behavior
First Claim
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 based on the user behaviors, 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, wherein a link between two objects of the subset is generated based on the user interaction with each of the two objects;
storing the links between objects of the subset of objects associated with each local object graph in a corresponding adjacency matrix;
for each local object graph, identifying at least one object that is common with another local object graphs of the plurality of local object graphs based on the links in the corresponding adjacency matrices associated with the plurality of local object graphs;
merging the plurality of local object graphs to generate a global object graph based on the identified common objects, the global object graph comprising the plurality of objects and links between the plurality of objects in the plurality of local object graphs; and
generating an adjacency matrix for the global object graph based on the adjacency matrices associated with the plurality of local object graphs.
1 Assignment
0 Petitions
Accused Products
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.
101 Citations
20 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 based on the user behaviors, 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, wherein a link between two objects of the subset is generated based on the user interaction with each of the two objects; storing the links between objects of the subset of objects associated with each local object graph in a corresponding adjacency matrix; for each local object graph, identifying at least one object that is common with another local object graphs of the plurality of local object graphs based on the links in the corresponding adjacency matrices associated with the plurality of local object graphs; merging the plurality of local object graphs to generate a global object graph based on the identified common objects, the global object graph comprising the plurality of objects and links between the plurality of objects in the plurality of local object graphs; and generating an adjacency matrix for the global object graph based on the adjacency matrices associated with the plurality of local object graphs. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. 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 based on the user behaviors, 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, wherein a link between two objects of the subset is generated based on the user interaction with each of the two objects; storing the links between objects of the subset of objects associated with each local object graph in a corresponding adjacency matrix; for each local object graph, identifying at least one object that is common with another local object graphs of the plurality of local object graphs based on the links in the corresponding adjacency matrices associated with the plurality of local object graphs; merging the plurality of local object graphs to generate a global object graph based on the identified common objects, the global object graph comprising the plurality of objects and links between the plurality of objects in the plurality of local object graphs; and generating an adjacency matrix for the global object graph based on the adjacency matrices associated with the plurality of local object graphs. - View Dependent Claims (13, 14, 15, 16, 17, 18, 19, 20)
-
Specification