Estimating influence of subjects based on a subject graph

• US 8,244,664 B2
• Filed: 12/01/2009
• Issued: 08/14/2012
• Est. Priority Date: 12/01/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Topsy Labs, Inc (Apple Inc.)
• Inventors: Ghosh, Rishab Aiyer, Prakash, Vipul Ved
• Primary Examiner(s): Rivas, Omar Fernandez
• Assistant Examiner(s): Coughlan, Peter
• Application Number:
  US12/628,801
• Publication Number:
  US 20100153329A1
• Time in Patent Office: 987 Days
• Field of Search: None
• US Class Current: 706/54
• CPC Class Codes: G06Q 10/10 Office automation; Time management
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0204 Market segmentation

Abstract

Estimating influence includes receiving a subject graph, in which the subject graph includes two or more subject nodes, in which each subject node corresponds to a subject; and determining an objective influence measure for each first subject node of the subject graph, in which the determination is based at least on part on a function of inward scores and outward scores, in which inward scores are computed from one or more paths leading to the first subject of a length of at least one, and outward scores are computed from one or more paths leading from the first subject of a length of at least one.

Claims

1. A computer-implemented method, comprising:

receiving a subject graph, wherein the subject graph includes two or more subject nodes, and wherein each subject node corresponds to a subject; and

determining an objective influence measure based on the subject graph for each first subject node of the subject graph, wherein the determination is based at least on part on a function of inward scores and outward scores, wherein inward scores are computed from one or more paths leading to the first subject of a length of at least one, and wherein outward scores are computed from one or more paths leading from the first subject of a length of at least one, wherein the computation of objective influence measure for the first subject node performed using the inward scores and the outward scores is a minimum-spend eigenvector centrality of the first subject node, wherein the minimum-spend eigenvector centrality is determined by an iterative computation of eigenvector centrality.

2. The method recited in claim 1, wherein the subject graph is a directed graph, or if the subject graph is an undirected graph, then each undirected edge is interpreted as two directed edges in opposite directions.

3. The method recited in claim 1, wherein the subject graph is a weighted graph, or if the subject graph is an unweighted graph, then each unweighted edge is interpreted as a weighted edge of a constant weight, and wherein the said constant weight can be any value including zero.

4. The method recited in claim 1, wherein a path is a sequence of contiguous edges with a length equal to its number of edges, wherein at least one of the inward paths or outward paths is of length greater than one.

5. The method recited in claim 1, wherein the inward scores are based on the count and weights of one or more paths leading to the first subject of a length of at least one.

6. The method recited in claim 1, wherein the outward scores are based on the count and weights of one or more paths leading from the first subject of a length of at least one.

7. The method recited in claim 1, wherein the inward scores are based on a count of one or more paths leading to the first subject of a length of at least one.

8. The method recited in claim 1, wherein the outward scores are based on a count of one or more paths leading from the first subject of a length of at least one.

9. The method recited in claim 1, wherein the objective influence measure is determined for all paths of the subject graph.

10. The method recited in claim 1, wherein the objective influence measure is determined as a function of a count of actual requests for data, opinion, or searches relating to or originating from other entities.

11. The method recited in claim 1, wherein the determining the objective influence measure is performed using one or more of the following functions:

any form of graph centrality, including betweenness centrality, degree centrality, closeness centrality, eigenvector centrality, flow centrality;

including wherein such functions are applied using additional weightings on each edge of the graph additional to any existing edge weights, such additional weightings being functions of a the use of each edge in order to serve actual requests for data, opinion, or searches relating to or originating from other entities.

12. The method recited in claim 1, further comprising:

determining whether a first entity is a subject or an object;

determining whether a second entity is a subject or an object; and

generating a graph, wherein a subset of the graph is the subject graph of subject nodes that includes at least one or more subject entities linked to one or more other subject entities, and wherein the graph includes one or more object entities each linked to one or more subject entities in the subject graph.

13. The method recited in claim 1, further comprising:

generating a graph, wherein a subset of the graph is the subject graph of subject nodes that includes at least one or more subject entities linked to one or more other subject entities, and wherein the graph includes one or more object entities each linked to one or more subject entities in the subject graph.

14. The method recited in claim 1,

generating the subject graph of subject nodes that includes at least one or more subject entities linked to one or more other subject entities.

15. The method recited in claim 1, wherein the first subject corresponds to one or more of the following:

representations of a person, web log, and entities representing Internet authors or users of social media services including is one or more of the following;

blogs, Twitter, or reviews on Internet web sites.

16. The method recited in claim 1, wherein the computation of the objective influence measure for the first subject node performed using the inward scores and the outward scores is a measure of eigenvector centrality of the first subject node.

17. The method recited in claim 1, wherein object nodes correspond to one or more of the following:

books, films, music, documents, websites, objects for sale, objects that are reviewed or recommended or cited, or any entities that are or can be associated with a Uniform Resource Identifier (URI).

18. The method recited in claim 1, wherein the objective influence measure of each first subject node is transformed into a rank or percentile relative to the objective influence measure of a plurality of other entities represented in the subject graph.

19. A computer-implemented method, comprising:

receiving a subject graph, wherein the subject graph includes two or more subject nodes, and wherein each subject node corresponds to a subject; and

determining an objective influence measure based on the subject graph for each first subject node of the subject graph, wherein the determination is based at least on part on a function of inward scores and outward scores, wherein inward scores are computed from one or more paths leading to the first subject of a length of at least one, and wherein outward scores are computed from one or more paths leading from the first subject of a length of at least one,

wherein the computation of objective influence measure for the first subject node performed using the inward scores and the outward scores is a minimum-spend eigenvector centrality of the first subject node, wherein the minimum-spend eigenvector centrality is determined by an iterative computation of eigenvector centrality, wherein at each iteration for each node a minimum outdegree is assumed if the actual outdegree falls below the minimum outdegree, such minimum outdegree being computed as a non-linear function of the minimum spend eigenvector centrality of the first subject node from the previous iteration.

20. A computer-implemented method, comprising:

receiving a subject graph, wherein the subject graph includes two or more subject nodes, and wherein each subject node corresponds to a subject; and

determining an objective influence measure based on the subject graph for each first subject node of the subject graph, wherein the determination is based at least on part on a function of inward scores and outward scores, wherein inward scores are computed from one or more paths leading to the first subject of a length of at least one, and wherein outward scores are computed from one or more paths leading from the first subject of a length of at least one,

wherein the computation of the objective influence measure for the first subject node performed using the inward scores and the outward scores is a minimum-spend eigenvector centrality of the first subject node, wherein the minimum-spend eigenvector centrality is determined by an iterative computation of eigenvector centrality, and wherein at each iteration for each node a minimum outdegree is assumed if the actual outdegree falls below the minimum outdegree, such minimum outdegree being computed as a generated non-linear function of the minimum spend eigenvector centrality of the first subject node from the previous iteration and the generated non-linear function is generated from the distribution of the actual indegrees and outdegrees of a plurality of nodes.

21. A computer-implemented method, comprising:

receiving a subject graph, wherein the subject graph includes two or more subject nodes, and wherein each subject node corresponds to a subject; and

determining an objective influence measure based on the subject graph for each first subject node of the subject graph, wherein the determination is based at least on part on a function of inward scores and outward scores, wherein inward scores are computed from one or more paths leading to the first subject of a length of at least one, and wherein outward scores are computed from one or more paths leading from the first subject of a length of at least one, and

computing a citation-weighted minimum spend eigenvector centrality or a citation-weighted ordinary eigenvector centrality as a function of the minimum-spend eigenvector centrality or ordinary eigenvector centrality, respectively, and the number of citations made by the first subject node, wherein the number of citations made by the first subject node is determined based on a number of outgoing links from the first subject node to each of the object nodes.

22. A computer-implemented system comprising:

a processor configured to;

receive a subject graph, wherein the subject graph includes two or more subject nodes, wherein each subject node corresponds to a subject, and wherein the subject graph is a directed graph, or if the subject graph is an undirected graph, then each undirected edge is interpreted as two directed edges in opposite directions; and

determine an objective influence measure based on the subject graph for each first subject node of the subject graph, wherein the determination is based at least on part on a function of inward scores and outward scores, wherein inward scores are based on a count of one or more paths leading to the first subject of a length of at least one, and wherein outward scores are based on a count of one or more paths leading from the first subject of a length of at least one, wherein the computation of objective influence measure for the first subject node performed using the inward scores and the outward scores is a minimum-spend eigenvector centrality of the first subject node, wherein the minimum-spend eigenvector centrality is determined by an iterative computation of eigenvector centrality; and

a memory coupled to the processor and configured to provide the processor with instructions.

23. The system recited in claim 22, wherein a path is a sequence of contiguous edges with a length equal to its number of edges, wherein at least one of the inward paths or outward paths is of length greater than one, wherein the inward scores are based on the count and weights of one or more paths leading to the first subject of a length of at least one, and wherein the outward scores are based on the count and weights of one or more paths leading from the first subject of a length of at least one.

24. A computer program product, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

receiving a subject graph, wherein the subject graph includes two or more subject nodes, wherein each subject node corresponds to a subject, and wherein the subject graph is a directed graph, or if the subject graph is an undirected graph, then each undirected edge is interpreted as two directed edges in opposite directions; and

determining an objective influence measure based on the subject graph for each first subject node of the subject graph, wherein the determination is based at least on part on a function of inward scores and outward scores, wherein inward scores are based on a count of one or more paths leading to the first subject of a length of at least one, wherein outward scores are based on a count of one or more paths leading from the first subject of a length of at least one, wherein a path is a sequence of contiguous edges with a length equal to its number of edges, wherein at least one of the inward paths or outward paths is of length greater than one, wherein the inward scores are based on the count and weights of one or more paths leading to the first subject of a length of at least one, and wherein the outward scores are based on the count and weights of one or more paths leading from the first subject of a length of at least one, wherein the computation of objective influence measure for the first subject node performed using the inward scores and the outward scores is a minimum-spend eigenvector centrality of the first subject node, wherein the minimum-spend eigenvector centrality is determined by an iterative computation of eigenvector centrality.