公开(公告)号：US09064002B1

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

申请号：US14093984

申请日：2013-12-02

Applicant: Google Inc.

Inventor： Zoltan I. Gyongyi ,  Maureen Heymans ,  Mikhail Lopyrev ,  Hein Roehrig

IPC: G06F15/16 ,  G06F17/30

CPC classification number: G06F17/30598 ,  G06Q10/10 ,  G06Q50/01

Abstract: Methods, systems, and apparatus, including computer programs encoded on computer storage media, for social identity clustering. In one aspect, a method includes receiving a connection graph representing public social data, where the nodes represent social identities and each edge is either a “me” edge between identities claimed to belong to the same person or a “friend” edge between identities claimed to belong to different identities. The method further includes converting the graph to a cluster graph in which each node initially corresponds to a single node of the connection graph. The method further includes updating the cluster graph by iteratively merging cluster nodes based on an analysis of the weight of the “me” edges connecting them, and then replacing the merged cluster nodes within the graph with a new cluster node containing the merged cluster nodes, where the edges of the new cluster node are the aggregated edges of the merged cluster nodes.

Abstract translation: 方法，系统和装置，包括在计算机存储介质上编码的计算机程序，用于社会身份聚类。 一方面，一种方法包括接收表示公共社交数据的连接图，其中节点表示社会身份，并且每个边缘是要求属于同一个人的身份之间的“我”边缘或被要求的身份之间的“朋友”边缘 属于不同的身份。 该方法还包括将图转换成其中每个节点最初对应于连接图的单个节点的聚类图。 该方法还包括通过基于连接它们的“我”边的权重的分析迭代地合并集群节点来更新聚类图，然后用包含合并的集群节点的新集群节点替换图中的合并集群节点， 其中新集群节点的边缘是合并的集群节点的聚合边缘。