Patent Document ID: 8793283
Application ID: 13452275
Patent Status: 1

Claim One:
1. A computer-implemented method comprising: maintaining data in a distributed computing system, the data describing a graph representing relationships among items, having a plurality of vertices representing the items, and having a plurality of edges connecting the plurality of vertices representing the relationships among the items, at least one vertex of the plurality of vertices having a set of label values indicating the at least one vertex's strength of association with a set of labels, the set of labels describing possible characteristics of an item represented by the at least one vertex, at least one edge of the plurality of edges having a set of label weights for influencing label values traversing the at least one edge; and executing a label propagation algorithm for the plurality of vertices in the graph in parallel for a series of synchronized iterations to propagate labels through the graph, wherein operations of the label propagation algorithm for a respective vertex of the plurality of vertices include: receiving an incoming message including a weighted label value; updating a label value for a first label in the set of labels of the respective vertex based on the weighted label value included in the received message to produce an updated label value for the first label; determining a new weighted label value by weighting the updated label value by a respective label weight for an edge of the plurality of edges that connects the respective vertex and a target vertex of the plurality of vertices; and sending an outgoing message to the target vertex, the outgoing message including the new weighted label value; assigning labels from the set of labels to the plurality of vertices based on label values associated with the plurality of vertices; and outputting the assigned labels of the plurality of vertices.