公开(公告)号：US20150220530A1

公开(公告)日：2015-08-06

申请号：US14278811

申请日：2014-05-15

Applicant: GOOGLE INC.

Inventor： Seyed Vahab Mirrokni Banadaki ,  Silvio Lattanzi ,  Jonathan Ezra Feldman ,  Alessandro Epasto ,  Stefano Leonardi ,  Hugh Lynch ,  Varun Sharma

IPC: G06F17/30

CPC classification number: G06F17/30943 ,  G06F2216/03 ,  G06Q30/0241

Abstract: Systems and methods offer an efficient approach to computing similarity rankings in bipartite graphs. An example system includes at least one processor and memory storing a bipartite graph having a first set and a second set of nodes, with nodes in the first set being connected to nodes in the second set by edges. The memory also stores instructions that, when executed by the at least one processor, cause the system to assign each node in the second set to one of a plurality of categories and, for each of the plurality of categories, generate a subgraph. The subgraph comprises of a subset of nodes in the first set and edges linking the nodes in the subset, where the nodes in the subset are selected based on connection to a node in the second set that is assigned to the category. The system uses the subgraph to respond to queries.

Abstract translation: 系统和方法提供了一种有效的方法来计算二分图中的相似性排名。 示例系统包括至少一个处理器和存储具有第一组和第二组节点的二分图的存储器，其中第一组中的节点通过边缘连接到第二组中的节点。 存储器还存储指令，当由至少一个处理器执行时，使得系统将第二组中的每个节点分配给多个类别中的一个，并且对于多个类别中的每一个分类，生成子图。 子图包括第一组中的节点的子集和链接子集中的节点的边缘，其中基于与分配给该类别的第二集合中的节点的连接来选择子集中的节点。 系统使用子图来回应查询。

公开(公告)号：US10152557B2

公开(公告)日：2018-12-11

申请号：US14278811

申请日：2014-05-15

Applicant: GOOGLE INC.

Inventor： Seyed Vahab Mirrokni Banadaki ,  Silvio Lattanzi ,  Jonathan Ezra Feldman ,  Alessandro Epasto ,  Stefano Leonardi ,  Hugh Lynch ,  Varun Sharma

IPC: G06F17/30 ,  G06F17/00 ,  G06Q30/02

Abstract: Systems and methods offer an efficient approach to computing similarity rankings in bipartite graphs. An example system includes at least one processor and memory storing a bipartite graph having a first set and a second set of nodes, with nodes in the first set being connected to nodes in the second set by edges. The memory also stores instructions that, when executed by the at least one processor, cause the system to assign each node in the second set to one of a plurality of categories and, for each of the plurality of categories, generate a subgraph. The subgraph comprises of a subset of nodes in the first set and edges linking the nodes in the subset, where the nodes in the subset are selected based on connection to a node in the second set that is assigned to the category. The system uses the subgraph to respond to queries.

公开(公告)号：US09760619B1

公开(公告)日：2017-09-12

申请号：US14279200

申请日：2014-05-15

Applicant: Google Inc.

Inventor： Silvio Lattanzi ,  Stefano Leonardi

IPC: G06F17/30 ,  G06F17/00

CPC classification number: G06F17/30598 ,  G06F17/30958 ,  G06Q50/01

Abstract: The disclosure includes a system and method for generating weighted clustering coefficients for a social network graph. The system includes a processor and a memory storing instructions that when executed cause the system to: receive social graph data associated with a social network, the social graph data including nodes, edges that connect the nodes and weights associated with the edges in a social graph, determine a first probability of existence of an edge in the social graph based on the weights, determine a second probability that a first node forms a triangle with two neighbor nodes, and compute a weighted clustering coefficient for the first node based on the first and second probabilities.