| 摘要 |
Methods, systems, and apparatus include computer programs encoded on a computer-readable storage medium, including a method for updating graphs. Labels associated with nodes of a graph are identified, including designators describing an attribute associated with a given node. The graph is provided, wherein labels have been assigned to each node in the graph. An initial set of weights for the labels are assigned reflecting a magnitude of a contribution of an associated label to a characterization of a respective node. A portion of the labels are assigned based on a propagation from other nodes. A change is identified in the graph that, when propagated, will affect other nodes. Sparse matrices, generated to describe the change, contain nonzero entries only in rows wherein connection weights and/or labels have changed. A new graph is generated using the sparse matrices without having to recalculate weights for other nodes not affected by the change. |
| 主权项 |
1. A method implemented by a computer system, the method comprising:
identifying, by the computer system, a set of labels to be associated with nodes of a graph, the labels including one or more designators for describing an attribute that is associated with a given node; providing the graph, wherein one or more labels of the identified set of labels have been assigned to each node and wherein an initial set of weights for the labels have been assigned reflecting a magnitude of a contribution of an associated label to a characterization of a respective node and wherein at least a portion of the labels are assigned based on a propagation from other nodes that are connected to a given node in the graph,
wherein the graph is represented by a matrix of weights that includes rows and columns, wherein a row corresponds to a node, a column corresponds to a label, wherein an entry in a row at a column indicates a weight that reflects a magnitude of contribution of the label associated with the given column to the node,wherein the matrix of weights is constructed from an un-propagated matrix of weights and a matrix of connections,wherein the un-propagated matrix of weights is a matrix that includes rows and columns, wherein a row corresponds to a node, and a column corresponds to a label,wherein an entry in a row at a column indicates a weight that reflects a magnitude of contribution of the label associated with the given column to the node before taking into consideration effects from labels propagated from connections to a given node, andwherein the matrix of connections includes rows and columns that represent nodes and wherein an entry in the matrix of connections represents a degree of connection between a given pair of nodes in the graph; identifying a change in the graph that when propagated will affect fewer than all nodes in the graph; generating a sparse matrix representing the change, the sparse matrix containing nonzero entries only in those rows of the sparse matrix corresponding to nodes having connection weights that have changed or labels that have changed or both; and generating, by one or more processors, a new graph that incorporates the change using the sparse matrix, including changing weights for one or more nodes affected by the change by combining the sparse matrix with the graph without recalculating weights for other nodes in the graph not affected by the change. |
