System and method for predicting web user flow by determining association strength of hypermedia links

• US 6,671,711 B1
• Filed: 03/31/2000
• Issued: 12/30/2003
• Est. Priority Date: 03/31/2000
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chi, Ed H., Pirolli, Peter L., Pitkow, James E.
• Primary Examiner(s): Sheikh, Ayaz
• Assistant Examiner(s): ZIA, SYED
• Application Number:
  US09/540,976
• Time in Patent Office: 1,369 Days
• Field of Search: 715/513, 707/501, 707/501.1, 707/513, 709/200
• US Class Current: 709/200
• CPC Class Codes: G06F 16/94 Hypermedia Hyperlinking G06F40/134
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

The present invention also provides a system and method for predicting user traffic flow in a collection of hypermedia documents by determining the association strength of the hypermedia links. Hypermedia links are identified among a plurality of documents, where the documents include content items such as keywords that may or may not be relevant to a user information need. The distribution of the content items in the document collection is then determined. An information item is received as input, and is compared to the content items. In response to the comparison, association strengths are assigned to the hypermedia links. A network flow model uses the association strengths of the hypermedia links to predict user traffic flow in response to an initial condition.

Claims

1. A method for determining the association strength of hypermedia links, comprising:

identifying the hypermedia links of a plurality of documents, wherein the documents include a plurality of content items;

determining the distribution of the content items in the documents;

comparing an information need item to the content items to determine a relevance value for each document; and

assigning an association strength to the hypermedia links using the relevance value for each document.

2. A method for determining an association strength of hypermedia links, comprising:

identifying the hypermedia links of a plurality of documents, wherein the documents include a plurality of content items;

determining the frequency of occurrence of the content items in the documents;

generating a query representing an information need item in terms of the content items;

determining a relevance value for each document based on the frequency of the content items in the documents and the query; and

determining an association strength for the hypermedia links associated with the documents in accordance with the relevance value.

3. A method for predicting user traffic flow, comprising the steps of:

identifying the hypermedia links of a plurality of documents, wherein the documents include a plurality of content items;

determining the distribution of the content items in the documents;

comparing an information need item to the distribution of the content items to generate a relevance value for each document;

assigning an association strength to the hypermedia links in accordance with the relevance value for each document;

selecting an initial condition, wherein the initial condition includes at least one document;

applying the association strength to the initial condition to predict user traffic flow.

4. A method for simulating user traffic flow in a plurality of hypermedia linked documents, comprising the steps of:

receiving a plurality of association strengths for the links between documents, the association strengths representing an information need and content of the plurality of documents;

selecting an initial condition, wherein the initial condition represents a starting state in the plurality of documents;

applying a network flow model to the initial condition, wherein the network flow model uses the association strengths to simulate traffic flow.

5. The method of claim 4, wherein the network flow model is a spreading activation algorithm.

6. The method of claim 4, wherein the association strengths are determined using a TF.IDF weighting scheme.

7. The method of claim 4, wherein the simulation continues for a predetermined number of steps.

8. The method of claim 4, wherein the proportion of users who continue is determined by the function α

(L).

9. The method of claim 4, wherein the total number of users who continue drops below a predetermined threshold ε

.

10. The method of claim 4, wherein the initial condition is an entry web page.

11. A system for determining the association strength of hypermedia links, comprising:

an identification component for identifying the hypermedia links of a plurality of documents, wherein the documents include a plurality of content items;

a distribution component for determining the distribution of the content items in the documents;

a comparison component for comparing an information need item to the content items to determine a relevance value of each document; and

an association strength component for assigning an association strength to hypermedia links in response to relevance values from the comparison component.

12. A system for determining an association strength of hypermedia links, comprising:

an identification component for identifying the hypermedia links of a plurality of documents, wherein the documents include a plurality of content items;

a frequency component for determining the frequency of occurrence of the content items in the documents;

a comparison component for comparing an information need item to the content items to generate a query;

a relevance component for determining a relevance value for each document based on the frequency of the content item in the documents and the query; and

an association strength component for determining an association strength for the hypermedia links associated with the documents in accordance with a relevance value.

13. A system for simulating user traffic flow in a plurality of hypermedia linked documents, comprising:

a selection component for selecting an initial condition, wherein the initial condition represents a starting state in the plurality of documents;

an identification component for identifying the hypermedia links of the documents, wherein the documents include a plurality of content items;

a frequency component for determining the frequency of occurrence of the content items in the documents;

a comparison component for comparing an information need item to the content items to generate a query;

a relevance component for determining a relevance value for each document based on the frequency of the content item in the documents and the query;

an association strength component for determining an association strength for the hypermedia links associated with the documents in accordance with a relevance value; and

a simulation component for applying a network flow model to the initial condition, wherein the network flow model simulates traffic flow in response to the association strengths representative of an information need and the content items of the documents.

14. The system of claim 13, wherein the network flow model is a spreading activation algorithm.

15. The system of claim 13, wherein the association strengths are determined using a TF.IDF weighting scheme.

16. The system of claim 13, wherein the simulation component operates for a predetermined number of steps.

17. The system of claim 13, wherein the proportion of users who continue is determined by the function α

(L).

18. The system of claim 13, wherein the total number of users who continue drops below a predetermined threshold ε

.

19. The system of claim 13, wherein the initial condition is an entry web page.