PROPAGATING INFORMATION THROUGH NETWORKS
First Claim
1. A computer implemented method comprising:
- providing data representing a data structure that includes a plurality of nodes, a portion of the nodes being entity nodes and a portion of the nodes being label nodes, wherein at least some entity nodes are connected to other entity nodes by one or more incoming or outgoing weighted edges, and wherein at least some label nodes are connected to entity nodes by one or more outgoing weighted edges;
for each entity node;
computing an aggregated incoming between-entity edge weight for the entity node including adding the weights of the edges that are incoming to the entity node from other entity nodes;
when there are one or more positively-weighted incoming between-entity edges into the entity node, replacing each of the between-entity edge weights by a respective initial edge weight of the between-entity edge divided by the aggregated incoming between-entity edge weight to generate pre-normalized between-entity edge weights;
computing an aggregated from-label weight by adding the label weights from label nodes with edges that are incoming to the entity node;
when there are one or more positively-weighted from-label node edges into the entity node, replacing each of the corresponding label weights from the label nodes by a respective initial label weight from the label node divided by the aggregated from-label weight to generate pre-normalized from-label weights;
determining influence values for each of a plurality of influence factors, where each influence factor is associated with a degree of propagation through the data structure of label weights to the entity nodes, and where the influence values are all non-negative and sum to one; and
using the pre-normalized from-label weights, the pre-normalized between-entity edge weights and the influence values as a set of linear constraints to determine final label weightings for the entity nodes.
1 Assignment
0 Petitions
Accused Products
Abstract
Methods, and systems, including computer programs encoded on computer-readable storage mediums, including a method for providing a graph that includes entity nodes, label nodes and weighted connecting edges. The method comprises computing an aggregated incoming between-entity edge weight for the entity nodes. When there are positively-weighted incoming between-entity edges into the entity node, the method comprises replacing each of the between-entity edge weights by a pre-normalized between-entity edge weights. The method comprises computing an aggregated from-label weight for the entity node. When there are positively-weighted from-label node edges, the method comprises replacing the corresponding label weights by pre-normalized from-label weights. The method comprises determining influence values for a first, second and third influence factors, where the influence factors have values that sum to one. The method further comprises using the pre-normalized weights and influence factors as a set of linear constraints to determine final label weightings for the entity nodes.
-
Citations
60 Claims
-
1. A computer implemented method comprising:
-
providing data representing a data structure that includes a plurality of nodes, a portion of the nodes being entity nodes and a portion of the nodes being label nodes, wherein at least some entity nodes are connected to other entity nodes by one or more incoming or outgoing weighted edges, and wherein at least some label nodes are connected to entity nodes by one or more outgoing weighted edges; for each entity node; computing an aggregated incoming between-entity edge weight for the entity node including adding the weights of the edges that are incoming to the entity node from other entity nodes; when there are one or more positively-weighted incoming between-entity edges into the entity node, replacing each of the between-entity edge weights by a respective initial edge weight of the between-entity edge divided by the aggregated incoming between-entity edge weight to generate pre-normalized between-entity edge weights; computing an aggregated from-label weight by adding the label weights from label nodes with edges that are incoming to the entity node; when there are one or more positively-weighted from-label node edges into the entity node, replacing each of the corresponding label weights from the label nodes by a respective initial label weight from the label node divided by the aggregated from-label weight to generate pre-normalized from-label weights; determining influence values for each of a plurality of influence factors, where each influence factor is associated with a degree of propagation through the data structure of label weights to the entity nodes, and where the influence values are all non-negative and sum to one; and using the pre-normalized from-label weights, the pre-normalized between-entity edge weights and the influence values as a set of linear constraints to determine final label weightings for the entity nodes. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A method for propagating labels in a social graph comprising:
-
providing a social graph that includes a plurality of nodes and includes edges connecting the nodes, a portion of the nodes being user nodes, a portion of the nodes being injection nodes that inject a label into a respective user node and a portion of the nodes being uncertainty nodes that inject a measure of attenuation to be applied when propagating labels between user nodes; determining for a given node an influence value for label weights for each of three factors;
influence for injections, influence for neighbors and influence for uncertainty;determining weights for labels at each node including normalizing at receipt weights for labels that are propagated or injected into a user node including; normalizing the weights for labels injected into a node, and adjusting the normalized weights by the influence factor for injections to produce an injected label weight contribution for the label for the node; adjusting the weights for labels received from a neighbor by the influence factor for neighbors to produce a neighbor label weight contribution for the label for the node; and using the weights and influence values as a set of linear constraints to determine final label weightings for the nodes. - View Dependent Claims (18, 19, 20, 21, 22)
-
-
23. A method for propagating labels in a social graph comprising:
-
identifying a first user node in a social graph; identifying one or more labels that are injected into the first user node, thereby associating respective labels with the first user node; normalizing weights of the labels that are injected into the first user node to be equal to one; determining an influence factor for injected labels for the first user node; adjusting the normalized weights for the labels using the influence factor for injected labels to produce a injected label weight contribution for each label associated with the first user node; determining if there are other neighbor nodes that contribute labels to the first user node; determining an influence factor for the neighbor nodes; when there are neighbor nodes, determining a neighbor node contribution for each label propagated from a respective neighbor node including identifying a label weight for a label from the neighbor node, adjusting the label weight based on an effective influence of the neighbor node on the first user node, and further adjusting the adjusted label weight based on the determined influence factor for the neighbor node; and summing the neighbor node contribution with the injected weight contribution for each label for the first user node; storing the sum for each label, producing a label weight for label for the first user node; and propagating the label weight for each label to one or more neighbor nodes to the first user node. - View Dependent Claims (24, 25, 26)
-
-
27. A method for propagating labels in a social graph comprising:
-
identifying one or more labels associated with a user in a social graph, where the user is connected to one or more other users in the social graph; identifying an influence value for label weights for each of at least two factors for the user;
influence for injections and influence for neighbors;determining weights for labels for the user including normalizing at receipt weights for labels that are propagated or associated with a user including; normalizing the weights for labels associated with the user and adjusting the normalized weights by the influence value for injections to produce an injected label weight contribution for the user; adjusting the weights for labels received from a neighbor by the influence value for neighbors to produce a neighbor label weight contribution for the user; and using the weights and influence values as a set of linear constraints to determine final label weightings for the user. - View Dependent Claims (28, 29, 30)
-
-
31. A method implemented by a computer system, the method comprising:
-
identifying, by the computer system, a set of labels to be associated with users of a social network, the labels including one or more designators for specifying areas of interest for a respective user; labeling, using the identified labels, nodes in a graph that represents the social network, wherein the users are represented by user nodes in the graph; assigning, by the computer system and for each respective node, weights for the labels, each weight reflecting a magnitude of a contribution of an associated label to a characterization of the respective node, wherein assigning weights includes; determining initial weights for each label that is either injected into a node or propagated from a neighbor node; determining an influence factor for labels that are injected to a node and labels that are propagated from other neighbor nodes; adjusting the initial weights based on the influence factors; and using the adjusted weights and influence factors as a set of linear constraints to determine final label weightings for the nodes. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59)
-
-
60. A computer implemented method comprising:
-
identifying one or more labels of interest to be associated with users of a user group; classifying each user including determining an association between the one or more labels and each respective user where the labels include areas of interest as either explicitly or implicitly determined for a given user; providing a first graph of the user group that includes a plurality of nodes, one node for each user and one or more label nodes that inject weights for the labels into each respective user node, including providing edges between user nodes that represent relationships between the users and assigning labels to each user based on the classifying; determining weights for each label for each user node in the first graph including; normalizing the weights for labels injected into a node, and adjusting the normalized weights by an influence factor for injections to produce an injected label weight contribution for the label for the node; adjusting the weights for labels received from a neighboring node by an influence factor for neighbor nodes to produce a neighbor label weight contribution for the label for the node; and using the weights and influence factors as a set of linear constraints to determine final label weightings for the user nodes.
-
Specification