Systems and methods for clustering items associated with interactions

• US 10,255,358 B2
• Filed: 12/30/2014
• Issued: 04/09/2019
• Est. Priority Date: 12/30/2014
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Green, Bradley Ray
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US14/585,590
• Publication Number:
  US 20160188713A1
• Time in Patent Office: 1,561 Days
• Field of Search: 707738
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06Q 50/01 Social networking
• CPC Class Codes: H04L 51/52 for supporting social networking services

Abstract

Systems, methods, and non-transitory computer readable media configured to generate session information based on information regarding items of a plurality of item types associated with interactions performed by active users of a social networking system. A graph is generated based on the session information. At least a first item of the items is assigned to a cluster based on similarity between the item and the cluster. The cluster is provided to a recommender system to facilitate selection of relevant information for potential presentation to a user.

Claims

1. A computer-implemented method comprising:

generating, by a computing system, session information based on information regarding items of a plurality of item types associated with interactions performed by active users of a social networking system;

removing, by the computing system, noise in the session information based on a determination that one or more interactions may be a result of automated behavior;

generating, by the computing system, a graph based on the session information, the graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, each node of the plurality of nodes being associated with at least one item, and each edge of the plurality of edges being associated with at least one transition probability;

removing, by the computing system, one or more edges connected to a first node of the plurality of nodes based on a determination that the first node exceeds a threshold number of edges and further based on transition probabilities associated with the one or more edges wherein the removing one or more edges connected to the first node comprises;

for each node connected to the first node, multiplying a transition count associated with each edge by a constant value between zero and one to determine a weight for each edge,

rounding each weight for each edge to a nearest integer to determine a rounded weight for each edge, and

removing any edges with a rounded weight equal to zero;

assigning, by the computing system, at least a first item of the items to a cluster based on similarity between the first item and the cluster, wherein the similarity is determined based on transition probability information stored in the graph; and

providing, by the computing system, the cluster to a recommender system to facilitate selection of relevant information for potential presentation to a user.

2. The computer-implemented method of claim 1, wherein the plurality of item types include at least one of other users, profiles, groups, pages, hashtags, topics, links, photos, and search terms.

3. The computer-implemented method of claim 1, wherein the session information is based on a user or a post.

4. The computer-implemented method of claim 1, further comprising:

limiting the information regarding items of a plurality of item types by at least one of a threshold number of the active users and a threshold number of interactions associated with the active users.

5. The computer-implemented method of claim 1, wherein the removing noise in the session information comprises removing noise in the session information based on at least one of activity for more than a threshold amount of time for a session and engagement in a cycle of interaction.

6. The computer-implemented method of claim 1, further comprising:

determining a similarity score between the first item and a representative item of the cluster; and

determining whether the similarity score satisfies a threshold value.

7. The computer-implemented method of claim 1, wherein the assigning at least the first item to the cluster comprises:

determining bi-directional agreement between the first item and a representative item of the cluster based on interactions between the first item and the representative item of the cluster.

8. A system comprising:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the system to perform;

generating session information based on information regarding items of a plurality of item types associated with interactions performed by active users of a social networking system;

removing noise in the session information based on a determination that one or more interactions may be a result of automated behavior;

generating a graph based on the session information, the graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, each node of the plurality of nodes being associated with at least one item, and each edge of the plurality of edges being associated with at least one transition probability;

removing one or more edges connected to a first node of the plurality of nodes based on a determination that the first node exceeds a threshold number of edges and further based on transition probabilities associated with the one or more edges, wherein the removing one or more edges connected to the first node comprises;

for each node connected to the first node, multiplying a transition count associated with each edge by a constant value between zero and one to determine a weight for each edge,

rounding each weight for each edge to a nearest integer to determine a rounded weight for each edge, and

removing any edges with a rounded weight equal to zero;

assigning at least a first item of the items to a cluster based on similarity between the first item and the cluster, wherein the similarity is determined based on transition probability information stored in the graph; and

providing the cluster to a recommender system to facilitate selection of relevant information for potential presentation to a user.

9. The system of claim 8, wherein the plurality of item types include at least one of other users, profiles, groups, pages, hashtags, topics, links, photos, and search terms.

10. The system of claim 8, wherein the session information is based on a user or a post.

11. The system of claim 8, wherein the removing noise in the session information comprises removing noise in the session information based on at least one of activity for more than a threshold amount of time for a session and engagement in a cycle of interaction.

12. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of a computing system, cause the computing system to perform a method comprising:

generating session information based on information regarding items of a plurality of item types associated with interactions performed by active users of a social networking system;

removing noise in the session information based on a determination that one or more interactions may be a result of automated behavior;

generating a graph based on the session information, the graph comprising a plurality of nodes and a plurality of edges connecting the plurality of nodes, each node of the plurality of nodes being associated with at least one item, and each edge of the plurality of edges being associated with at least one transition probability;

removing one or more edges connected to a first node of the plurality of nodes based on a determination that the first node exceeds a threshold number of edges and further based on transition probabilities associated with the one or more edges, wherein the removing one or more edges connected to the first node comprises;

for each node connected to the first node, multiplying a transition count associated with each edge by a constant value between zero and one to determine a weight for each edge,

rounding each weight for each edge to a nearest integer to determine a rounded weight for each edge, and

removing any edges with a rounded weight equal to zero;

assigning at least a first item of the items to a cluster based on similarity between the first item and the cluster, wherein the similarity is determined based on transition probability information stored in the graph; and

providing the cluster to a recommender system to facilitate selection of relevant information for potential presentation to a user.

13. The non-transitory computer-readable storage medium of claim 12, wherein the plurality of item types include at least one of other users, profiles, groups, pages, hashtags, topics, links, photos, and search terms.

14. The non-transitory computer-readable storage medium of claim 12, wherein the session information is based on a user or a post.

15. The non-transitory computer-readable storage medium of claim 12, wherein the removing noise in the session information comprises removing noise in the session information based on at least one of activity for more than a threshold amount of time for a session and engagement in a cycle of interaction.