Patent ID: 11868916
Assignee: SNAP INC.
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A method comprising:
accessing a baseline social graph modeling relationships and attributes of multiple users of a social network application, the baseline social graph comprising:
nodes representing respective users of the social network application;
links representing established relationships between the users of the social network application, each link extending between a corresponding pair of nodes; and
labels associated with the nodes, each label being associated with one or more of the nodes to indicate a corresponding attribute of the one or more associated nodes;

in an automated refinement operation performed using a graph refinement engine comprising one or more computer processors configured to perform the refinement operation, dynamically refining the baseline social graph by augmenting the baseline social graph with predicted links and with inferred labels, thereby constructing a refined social graph, the refinement operation comprising:
defining a graph smoothness objective expression having cumulative terms comprising:
a label propagation objective function indicative of label similarity, the label propagation objective function being a function, at least in part, of link closeness; and
a graph construction objective function indicative of link closeness between respective nodes, wherein link closeness is indicative of path-wise proximity of respective nodes, the graph construction objective function being a function, at least in part, of label similarity; and

based at least in part on the objective expression, optimizing the graph smoothness objective expression by performing iterative operations of alternately:
in a label inference iteration, inferring labels using the graph construction objective function and based at least in part on predicted links generated in a previous link prediction iteration; and
in a link prediction iteration, predicting links using the graph construction objective function and based at least in part on inferred labels generated in a previous label inference iteration; and

in an automated recommendation operation performed using a recommendation engine comprising one or more computing devices configured to perform the recommendation operation:
generating a recommendation for a particular one of the users based at least in part on automated analysis of the refined social graph; and
causing display of the recommendation on a user device associated with the particular user.