Learning and reasoning from web projections

• US 7,970,721 B2
• Filed: 06/15/2007
• Issued: 06/28/2011
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Leskovec, Jurij, Dumais, Susan T., Horvitz, Eric J.
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): GONZALES, VINCENT
• Application Number:
  US11/763,719
• Publication Number:
  US 20080313119A1
• Time in Patent Office: 1,474 Days
• Field of Search: 706/46
• US Class Current: 706/46
• CPC Class Codes: G06F 16/38 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A system and method that facilitates and effectuates making an inference related to objects of interest within a context. A web projection component can generate sub graphs by projecting objects of interest onto a web graph representing a superset or partially overlapping set of objects to the objects of interest. An inference component can provide inferences relating to the quality of the objects of interest, adjustments to the context, and patterns recognized from graphical properties of the sub graphs.

Claims

1. A system for analyzing one or more objects of interest within a context comprising:

one or more processors configured with executable instructions to instantiate a web projection component and an inference component;

the web projection component configured to project the one or more objects of interest onto a web graph to produce one or more sub graphs, the web projection component producing the one or more sub graphs by adding connection nodes and edges between a largest set of connected nodes and a second largest set of connected nodes; and

the inference component configured to make an inference related to at least one of the context or the one or more objects of interest, the inference based upon graphical properties of the one or more sub graphs.

2. The system of claim 1, wherein the context delineates the one or more objects of interest from a larger set of objects in a data store.

3. The system of claim 2, wherein the context is one of defined by one or more users, defined by one or more systems, or inferred by the system.

4. The system of claim 2, wherein the context is at least one of results from a user or system query, objects a user has previously viewed, pages on a website, newly added objects, objects above or below an occurrence threshold, objects that have recently changed, objects linked to a particular object, or objects downloaded within a period of time.

5. The system of claim 2, wherein the web graph comprises nodes representing objects from the data store and edges between nodes representing associations between objects.

6. The system of claim 1, wherein the one or more sub graphs are at least one of a context sensitive projection sub graph or a context sensitive connection sub graph.

7. The system of claim 6, wherein the context sensitive projection sub graph comprises nodes representing nodes from the web graph, wherein each node contains at least one object from the one or more objects of interest, the context sensitive projection sub graph further comprises edges representing edges between nodes from the web graph that contain at least one object from the one or more objects of interest.

8. The system of claim 7, wherein the context sensitive connection sub graph comprises all nodes and edges from the context sensitive projection graph, along with a minimal set of edges and connection nodes to connect all nodes.

9. The system of claim 8, wherein the graphical properties are based upon at least one of an individual sub graph, or a plurality of sub graphs, wherein the graphical properties are further based at least on one of nodes, edges, paths, connected components, connector nodes, path shape, path length, node ratio, edge ratio, path ratio, clustering coefficient, node degree, node density, edge density, or node size.

10. The system of claim 1, wherein the inference at least one of predicts quality of the one or more objects of interest, predicts an adjustment of the context, or identifies one or more patterns based upon graphical properties of the one or more sub graphs.

11. The system of claim 10, wherein the quality of the one or more objects of interest is associated with individual objects from the one or more objects of interest, a sub set of the one or more objects of interest, or the entire set of one or more objects of interest.

12. The system of claim 10, wherein the quality can be indicated by a numerical ranking, alpha ranking, alpha-numeric ranking, ordered ranking, range, or class.

13. The system of claim 10, wherein predicting an adjustment of the context comprises at least one of predicting whether a context will be narrowed or broadened, whether a related or completely different context is needed, if a context adjustment is needed, or predicting one or more delineation criteria for objects of interest.

14. The system of claim 10, wherein identifying a pattern comprises at least one of identifying clusters, loops, anomalies, linkage patterns, edge density, path length between nodes, and patterns matching or approximating stored reference patterns.

15. A method for analyzing objects of interest within a context comprising:

controlling one or more processors configured with executable instructions for;

projecting objects of interest onto a web graph to produce one or more sub graphs, wherein producing the sub graphs comprises;

ordering sets of connected nodes by size;

identifying a shortest path between a largest set of connected nodes, from among the ordered sets, to a second largest set of connected nodes, from among the ordered sets;

adding, according to the shortest path, connection nodes and edges between the largest set of connected nodes and the second largest set of connected nodes; and

repeating the step of identifying the shortest path and the step of adding connection nodes while more sets of nodes are available in the sets of connected nodes ordered by size; and

making an inference related to at least one of the context or objects of interest based upon graphical properties of the one or more sub graphs.

16. The method of claim 15, wherein the web graph comprises nodes representing objects from a data store and edges between nodes representing associations between objects.

17. The method of claim 15, wherein projecting objects of interest onto the web graph comprises:

identifying each node on the web graph that contains an object of interest;

identifying each edge on the web graph between identified nodes; and

copying each identified node and each identified edge onto a sub graph.

18. The method of claim 15, wherein making the inference comprises at least one of predicting the quality of the objects of interest, predicting one or more changes to the context, or identifying one or more patterns based upon graphical properties of the one or more sub graphs.

19. A method for analyzing objects of interest within a context comprising:

controlling one or more processors configured with executable instructions for;

projecting objects of interest onto a web graph to produce one or more sub graphs, the projecting of the objects of interest comprising;

identifying each node on the web graph that contains an object of interest;

identifying each edge on the web graph between identified nodes; and

copying each identified node and each identified edge onto a sub graph;

making an inference related to at least one of the context or objects of interest based upon graphical properties of the one or more sub graphs;

identifying a shortest path from web graph between the largest set of connected nodes in the sub graph to the second largest set of connected nodes in the sub graph;

adding nodes and edges along the identified shortest path to the sub graph to form a new largest set of connected nodes;

identifying a shortest path from web graph between the new largest set of connected nodes in the sub graph to the second largest set of connected nodes in the sub graph; and

adding nodes and edges along the identified shortest path to the sub graph to form a new largest set of connected nodes until all nodes of the sub graph are connected.