System and method employing random walks for mining web page associations and usage to optimize user-oriented web page refresh and pre-fetch scheduling

Claim 2

On a computer network having a set of Web pages V and a set of links E between those Web pages represented as an undirected neighborhood graph G N (V N ,E N ), the computer network further including seed Web pages v a and v b in V, a method executable on the computer network for estimating associations between v a and v b and other Web pages v i εV, the method comprising the steps of: constructing a directed random walk graph by creating a new v i ′ in V for each v i εV N , and creating two directed edges e′ 2×k =<v i ′,v j ′) and e′ 2×k−1 =<v j ′,v i ′> in E for each e k =<v i ,v j >εE N wherein both v i and V j are in V N , computing a penalty value penalty(v i ′) for all vertices v i ′εV, and constructing a |V|×|V| transition matrix T, where T[j,i] represents a transition value for each directed edge in E denoting a likelihood of moving to vertex v i from vertex v j ; and calculating a steady state distribution convergence vector t of T, wherein for each v i εV, t[i] represents the association between the seed Web pages and v i .

Claim 3

A method as recited in claim 1 , the step of computing a penalty value penalty(v i ′) for all vertices v i ′εV comprising the steps of: computing sdist(v i ′,v a ′) as a shortest distance in G N between v i ′ and the vertex v a ′ corresponding to v a ; computing sdist(v i ′,v b ′) as the shortest distance in G N between v i ′ and the vertex v b ′ corresponding to v b ; and computing the penalty value as penalty (υ i ′)=sdist(v i ′, v a ′)+sdist(υ i ′,υ b ′).

Claim 4

A method as recited in claim 2 , the step of constructing a |V|×|V| transition matrix T comprising the steps of: resetting T[j,i]=0.0 for all vertices υ i ′εV and for all (υ i ′,υ j ′)∉E; and solving the following set of linear equations for all vertices υ i ′εV, L  ( υ i ′ ) = { ∑ ( υ i ′ , υ j ′ ) ∈ ɛ   T  [ j , i ] = 1.0 } ⋃  { T  [ j , i ]  x   penalty  ( υ j ′ ) = T  [ k , i ]  x   penalty  ( υ k ′ )  ( υ i ′ , υ j ′  ) ∈ E   and   ( υ i ′ , υ k ′  ) ∈ E } .

Claim 5

A method as recited in claim 3 , the step of calculating a steady state distribution (convergence vector) t of T comprising solving a linear equation (I−T)t=0, where I is a unit matrix, and ∑ 1 ≤ i ≤  v w    t  [ i ] = 1.0 .

Claim 6

A method as recited in claim 2 , the computer network further including a set of seed Web pages |S|≧2 in V, the step of computing a penalty value penalty(v i ′) for all vertices v i ′εV comprising computing the penalty value as penalty  ( v i ′ ) = ∑ u j ∈ S   sdist   ( v i ′ , v j ′ ) .

Claim 7

A method as recited in claim 2 , the computer network further including a set of seed Web pages |S|≧2 in V, the step of computing a penalty value penalty(v i ′) for all vertices v i ′εV comprising computing the penalty value as penalty( v i ′)=length (minimum_steiner_tree( S∪{v i ′})).

Claim 8

A method as recited in claim 6 , further including the step of defining a relevant neighborhood of G N (V N ,E N ) for constructing the random walk graph as a set of vertices, V N =V G U (S,d), that are reachable either from the vertices in S in d edge traversals such that ∀ v 1 ∈ V G u  ( S , d )   v j ∈ S  reachable G u  ( v j , v i , d ) .

Claim 9

A method as recited in claim 1 , further including the step of defining a relevant neighborhood of G N (V N ,E N ) for constructing the random walk graph as a set of vertices, V N =V G u (v a ,v b ,d), that are reachable either from v a or v b in d edge traversals such that ∀v i εV G u (v a ,v b ,d) reachable G u (v a ,v i ,d) ν reachable G u (v b ,v i ,d).

Claim 10

A method as recited in claim 1 , each Web page v i εV having a known relevance value for a particular topic relevance(v,topic), the method further including the step of adjusting the penalty value penalty(v i ′) for all vertices v i ′εV by dividing penalty(v i ′) by relevance(v,topic).

Claim 11

A method as recited in claim 1 , further including the step of pre-fetching Web pages into a memory in decreasing order of t[i].

Claim 12

On a computer network having a set of Web pages V and a set of links between those Web pages E modeled as a directed graph G(V,E), each Web page v i εV comprising a pair <O v ,a v >, where O v is a set of media objects including a main HTML file and a v is a page author, and where each object oεO v has a known end-user preference upref(u) for an end-user u and a page author preference apref(a v ) for a page author a v , an end-user u accessing at a seed Web page v c , a method executable on the computer network for estimating an association between the media objects and the seed Web page, the method comprising the steps of: calculating a page preference weight pref(u,v) for each Web page v i by applying preference rules defined by upref(u) and apref(a v ) to the contents of O v calculating an object preference weight pref(u,o,v) for each object oεO v by applying the preference rules defined by upref(u) and apref(a v ) to the contents of O v ; generating a random walk graph G w having a set of vertices V w and a set of edges E w ; calculating a page gain gain(u,v) by finding a steady state distribution convergence vector of the random walk graph; and calculating an object gain gain(u,o) for each object as gain  ( u , o ) = ∑ o ∈ O v   gain  ( u , v ) × pref  ( u , o , v ) , wherein the object gain represents an association between the object and the seed Web page.

Claim 13

On a computer network having a set of Web pages V and a set of links between those Web pages E modeled as a directed graph G(V,E), each Web page v i εV comprising a pair <O v ,a v >, where O v is a set of media objects including a main HTML file and a v is a page author, and where each object oεO v has a known end-user preference upref(u) for an end-user u and a page author preference apref(a v ) for a page author a v , an end-user u accessing at a seed Web page v c , a method executable on the computer network for estimating an association between the media objects and the seed Web page, the method comprising the steps of: calculating a page preference weight pref(u,v) for each Web page v i by applying preference rules defined by upref(u) and apref(a v ) to the contents of O v calculating an object preference weight pref(u,o,v) for each object oεO v by applying the preference rules defined by upref(u) and apref(a v ) to the contents of O v ; generating a random walk graph G w having a set of vertices V w and a set of edges E w ; calculating a page gain gain(u,v) by finding a steady state distribution convergence vector of the random walk graph; and calculating an object gain gain(u,o) for each object as gain  ( u , o ) = ∑ o ∈ O v   gain  ( u , v ) × pref  ( u , o , v ) , wherein the object gain represents an association between the object and the seed Web page.

Claim 14

A method as recited in claim 11 , the step of generating a random walk graph G w having a set of vertices V w and a set of edges E w comprising the steps of: creating a vertex v i in V w for each Web page in V; creating two edges e′ j =<v′ a ,v′ b > and e″ j =<v′ b ,v′ a > in E w for each edge e j =<v a , v b > in E; and assigning an edge weight w(e)=s(u, v j ) to each edge e j =<v a , v b > in E.

Claim 15

A method as recited in claim 12 , wherein s(u,v j ) is a known stickiness value for each Web page v j εV.

Claim 16

A method as recited in claim 12 , wherein s(u,v j ) is assigned a unit value for each edge e j =<v a ,v b > in E.

Claim 17

A method as recited in claim 12 , wherein s(u,v j ) is assigned a larger value than the unit value for each edge e j =<v a ,v b > in E that crosses a domain boundary.

Claim 18

A method as recited in claim 12 , the step of calculating a page gain gain(u,v) by finding a steady state distribution (convergence vector) of the random walk graph comprising the steps of: finding a shortest distance shortest (v c , v i ) from vertex v c to all vertices v i εV while taking into account the edge weight using a shortest path algorithm; for each vertex vεV w , calculating a penalty penalty(u,v)=shortest(v c ,v i )/(pref(u,v)+1), and calculating a unit probability unit(u,v) by solving ∑ 〈 v , v i 〉 ∈ E w   unit  ( u , v ) penalty  ( u , v i ) = 1 ; calculating prob  ( u )  ( v j | v i ) = unit  ( u , v j ) penalty  ( u , v i ) for each edge e=ε<v i ,v j >εV w ; and calculating gain(u,v) by finding a steady state distribution (convergence vector) t of T, wherein for each v i εV, t[i] represents the association between the seed Web pages and v i , where T is a matrix of transition values prob(u)(v j |v i ).

Claim 19

A method as recited in claim 16 , the step of calculating gain(u,v) by finding a steady state distribution (convergence vector) t of T comprising solving a linear equation (I−T)t=0, where I is a unit matrix, and Σ 1≦i≦|v w | gain(u,v)=1.0.

Claim 20

A method as recited in claim 17 , wherein each object oεO v has a known size size(o) and, having an available pre-fetch bandwidth P u and a pre-fetch duration δt in which a server may pre-fetch objects into a memory, the method further includes the step of identifying a set of objects O s highly associated with the end-user or seed Web page, the step comprising: defining a cost of each object as cost(o)=size(o); and identifying a subset O s of O v such that Σ oεO s cost(o)≦P u ×δt and Σ oεO s gain(u,o) is maximized.

Claim 21

A method as recited in claim 18 , further including the step of pre-fetching or refreshing objects from O s into the memory.

Claim 22

A method as recited in claim 18 , where each object oεO v has a known expiration time expire(o), the method further including the step of refining the set of objects O s by removing those objects that will expire before their earliest time to view, the step comprising: finding a shortest path shortest_path(v c ,v i ) from vertex v c to all vertices v i εV while taking into account the edge weight using a shortest path algorithm; calculating a measure of an earliest time that a page p may be accessed as earliest(u,p)=shortest_path(v c , v p ); calculating a measure of an earliest time that an object o may be needed as earliest(u,o)=min{earliest(u,p)|pεpages(o)}; and eliminating those objects from O v in which expire(o)<earliest(u,o) before identifying the set of objects O s .

Claim 23

A method as recited in claim 17 , wherein each object oεO v has a known size size(o) and, having an available pre-fetch bandwidth P u and a pre-fetch duration δt in which a server may pre-fetch objects into a memory, and given a set of users U or seed Web pages, the method further includes the step of identifying a set of objects O s highly associated with the set of users or seed Web pages, the step comprising: calculating an object gain gain(o) for each object as gain  ( o ) = ∑ u ∈ U   ∑ o ∈ O v   gain  ( u , v ) × pref  ( u , o , v ) , wherein the object gain represents an association between the object and the set of end-users or seed Web pages; defining a cost of each object as cost(o)=size(o); and identifying a subset O s of O v such that ∑ o ∈ O s   cost  ( o ) ≤ P U × δ   t   and   ∑ o ∈ O s   gain  ( o ) is maximized.

Claim 24

On a computer network having a set of Web pages V and a set of links E between those Web pages, a system for estimating associations between seed Web pages v a and v b and other Web pages v i εV, comprising: memory for storing a location of the seed Web pages v a and v b and the other Web pages v i in V; and a processor programmed for modeling the computer network as an undirected neighborhood graph G N (V N ,E N ), and programmed for constructing a directed random walk graph by creating a new v i ′ in V for each v i εV N , and creating two directed edges e′ 2×k =<v i ′,v j ′> and e′ 2×k+1 =<v j ′,v i ′> in E for each e k =<v i ,v j >εE N wherein both v i and v j are in V N , computing a penalty value penalty(v i ′) for all vertices v i ′εV, and constructing a |V|×|V| transition matrix T, where T[j,i] represents a transition value for each directed edge in E denoting a likelihood of moving to vertex v i from vertex v j ; and calculating a steady state distribution convergence vector t of T, wherein for each vεV, t[i] represents the association between the seed Web pages and V i .

Claim 25

On a computer network having a set of Web pages V and a set of links E between those Web pages, a system for estimating associations between seed Web pages v a and v b and other Web pages v i εV, comprising: memory for storing a location of the seed Web pages v a and v b and the other Web pages v i in V; and a processor programmed for modeling the computer network as an undirected neighborhood graph G N (V N ,E N ), and programmed for constructing a directed random walk graph by creating a new v i ′ in V for each v i εV N , and creating two directed edges e′ 2×k =<v i ′,v j ′> and e′ 2×k+1 =<v j ′,v i ′> in E for each e k =<v i ,v j >εE N wherein both v i and v j are in V N , computing a penalty value penalty(v i ′) for all vertices v i ′εV, and constructing a |V|×|V| transition matrix T, where T[j,i] represents a transition value for each directed edge in E denoting a likelihood of moving to vertex v i from vertex v j ; and calculating a steady state distribution convergence vector t of T, wherein for each vεV, t[i] represents the association between the seed Web pages and V i .

Claim 26

A system as recited in claim 22 , the processor further programmed for computing a penalty value penalty(v i ′) for all vertices v i ′εV by: computing sdist(v i ′,v a ′) as a shortest distance in G N between v i ′ and the vertex v a ′ corresponding to v a ; computing sdist(v i ′,v b ′) as the shortest distance in G N between v i ′ and the vertex v b ′ corresponding to v b ; and computing the penalty value as penalty(υ i ′)=sdist(v i ′,v a ′)+sdist(υ i ′,υ b ′).

Claim 27

A system as recited in claim 23 , the processor further programmed for constructing a |V|×|V| transition matrix T by: resetting T[j,i]=0.0 for all vertices υ i ′εV and for all (υ i ′,υ j ′)∉E; and solving the following set of linear equations for all vertices v i ′εV, L  ( υ i ′ ) = { ∑ ( υ i ′ , υ j ′ ) ∈ ɛ   T  [ j , i ] = 1.0 } ⋃  { T  [ j , i ]  x   penalty  ( υ j ′ ) = T  [ k , i ]  x   penalty  ( υ k ′ )  ( υ i ′ , υ j ′  ) ∈ E   and   ( υ i ′ , υ k ′  ) ∈ E } .

Claim 28

A system as recited in claim 24 , the processor further programmed for calculating a steady state distribution (convergence vector) t of T by solving a linear equation (I−T)t=0, where I is a unit matrix, and ∑ 1 ≤ i ≤ v w    t  [ i ] = 1.0 .

Claim 29

A system as recited in claim 23 , the computer network further including a set of seed Web pages |S|≧2 in V, the processor further programmed for computing a penalty value penalty(v i ′) for all vertices v i ′ ∈ V   as   penalty  ( v i ′ ) = ∑ u j ∈ S   sdist   ( v i ′ , v j ′ ) .

Claim 30

A system as recited in claim 23 , the computer network further including a set of seed Web pages |S|≧2 in V, the processor further programmed for computing a penalty value penalty(v i ′) for all vertices v i εV as penalty(v i ′)=length(minimum_steiner_tree (S∪{v i ′})).

Claim 31

A system as recited in claim 27 , the processor further programmed for defining a relevant neighborhood of G N (V N , E N ) for constructing the random walk graph as a set of vertices, V N =V G U (S,d), that are reachable either from the vertices in S in d edge traversals such that ∀ v 1 ∈ V G u  ( S , d )   v j ∈ S  reachable G u  ( v j , v i , d ) .

Claim 32

A system as recited in claim 22 , the processor further programmed for defining a relevant neighborhood of G N (V N ,E N ) for constructing the random walk graph as a set of vertices, V N =V G u (v a ,v b ,d), that are reachable either from v a or v b in d edge traversals such that ∀v i εV G u (v a ,v b ,d)reachable G u (v a ,v i ,d)v reachable G u (v b ,v i ,d).

Claim 33

A system as recited in claim 22 , each Web page v i εV having a known relevance value for a particular topic relevance(v,topic), the processor further programmed for adjusting the penalty value penalty(v i ′) for all vertices v i ′εV by dividing penalty(v i ′) by relevance(v,topic).

Claim 34

A system as recited in claim 22 , the processor further programmed for pre-fetching Web pages into the memory in decreasing order of t[i].

Claim 35

On a computer network having a set of Web pages V and a set of links between those Web pages E, each Web page v i εV comprising a pair <O v a v >, where O v is a set of media objects including a main HTML file and a v is a page author, a system for estimating an association between the media objects and a seed Web page v c corresponding to a current location of an end-user u, comprising: memory for storing, for each object oεO v , a known end-user preference upref(u) for the end-user u, a page author preference apref(a v ) for the page author a v , and a location of the seed Web page v c ; and a processor programmed for modeling the computer network as a directed graph G(V,E), and programmed for calculating a page preference weight pref(u,v) for an end user u for each Web page v i by applying preference rules defined by upref(u) and apref(a v ) to the contents of O v , calculating an object preference weight pref(u,o,v) for each object oεO v by applying the preference rules defined by upref(u) and apref(a v ) to the contents of O v , generating a random walk graph G w having a set of vertices V w and a set of edges E w , calculating a page gain gain(u,v) by finding a steady state distribution convergence vector of the random walk graph, and calculating an object gain gain(u,o) for each object as gain   ( u , o ) = ∑ o ∈ O v   gain   ( u , v ) × pref  ( u , o , v ) , wherein the object gain represents an association between the object and the end-user or seed Web page.

Claim 36

On a computer network having a set of Web pages V and a set of links between those Web pages E, each Web page v i εV comprising a pair <O v a v >, where O v is a set of media objects including a main HTML file and a v is a page author, a system for estimating an association between the media objects and a seed Web page v c corresponding to a current location of an end-user u, comprising: memory for storing, for each object oεO v , a known end-user preference upref(u) for the end-user u, a page author preference apref(a v ) for the page author a v , and a location of the seed Web page v c ; and a processor programmed for modeling the computer network as a directed graph G(V,E), and programmed for calculating a page preference weight pref(u,v) for an end user u for each Web page v i by applying preference rules defined by upref(u) and apref(a v ) to the contents of O v , calculating an object preference weight pref(u,o,v) for each object oεO v by applying the preference rules defined by upref(u) and apref(a v ) to the contents of O v , generating a random walk graph G w having a set of vertices V w and a set of edges E w , calculating a page gain gain(u,v) by finding a steady state distribution convergence vector of the random walk graph, and calculating an object gain gain(u,o) for each object as gain   ( u , o ) = ∑ o ∈ O v   gain   ( u , v ) × pref  ( u , o , v ) , wherein the object gain represents an association between the object and the end-user or seed Web page.

Claim 37

A system as recited in claim 32 , the processor further programmed for generating a random walk graph G w having a set of vertices V w and a set of edges E w by: creating a vertex v i in V w for each Web page in V; creating two edges e′ j =<v′ a ,v′ b > and e″ j =<v′ b ,v′ a > in E w for each edge e j =(v a , v b ) in E; and assigning an edge weight w(e)=s(u,v j ) to each edge e j =<v a ,v b > in E.

Claim 38

A system as recited in claim 33 , wherein s(u,v j ) is a known stickiness value for each Web page v j εV.

Claim 39

A system as recited in claim 33 , wherein s(u,v j ) is assigned a unit value for each edge e j =<v a ,v b > in E.

Claim 40

A system as recited in claim 33 , wherein s(u,v j ) is assigned a larger value than the unit value for each edge e j =<v a , v b > in E that crosses a domain boundary.

Claim 41

A system as recited in claim 33 , the processor further programmed for calculating a page gain gain(u,v) by finding a steady state distribution (convergence vector) of the random walk graph by: finding a shortest distance shortest (v c , v i ) from vertex v c to all vertices v i εV while taking into account the edge weight using a shortest path algorithm; for each vertex vεV w , calculating a penalty penalty(u,v)=shortest(v c ,v i )/(pref(u,v)+1), and calculating a unit probability unit(u,v) by solving ∑ 〈 v , v i 〉 ∈ E w   unit  ( u , v ) penalty  ( u , v i ) = 1 ; calculating prob  ( u )  ( v j | v i ) = unit  ( u , v j ) penalty  ( u , v i ) for each edge e=ε<v i ,v j >εV w ; and calculating gain(u,v) by finding a steady state distribution (convergence vector) of T, where T is a matrix of transition values prob(u)(v j |v i ), and ∑ 1 ≤ i ≤ v u i ′ |   gain  ( u , v ) = 1.0 .

Claim 42

A system as recited in claim 37 , the processor further programmed for calculating gain(u,v) by finding a steady state distribution (convergence vector) t of T by solving a linear equation (I−T)t=0, where I is a unit matrix, and ∑ 1 ≤ i ≤  v u    gain  ( u , v ) = 1.0 .

Claim 43

A system as recited in claim 38 : the memory for storing a known size size(o) for each object oεO v ; and the processor having an available pre-fetch bandwidth P u and a pre-fetch duration δt for pre-fetching objects into a memory, and further programmed for identifying a set of objects O s highly associated with the end-user or seed Web page by defining a cost of each object as cost(o)=size(o), and identifying a subset O s of O v such that Σ oεO s cost(o)≦P u ×δt and Σ oεO s gain(u,o) is maximized.

Claim 44

A system as recited in claim 39 , the processor further programmed for pre-fetching or refreshing objects from O s into the memory.

Claim 45

A system as recited in claim 39 : the memory for storing a known expiration time expire(o) for each object oεO v ; and the processor further programmed for refining the set of objects O s by removing those objects that will expire before their earliest time to view by finding a shortest path shortest_path(v c ,v i ) from vertex v c to all vertices v i εV while taking into account the edge weight using a shortest path algorithm, calculating a measure of an earliest time that a page p may be accessed as earliest(u,p)=shortest_path(v c ,v p ), calculating a measure of an earliest time that an object o may be needed as earliest(u,o)=min{earliest(u,p)|pεpages(o)}, and eliminating those objects from O v in which expire(o)<earliest(u,o) before identifying the set of objects O s .

Claim 46

A system as recited in claim 38 : the memory for storing a known size size(o) for each object oεO v ; and the processor having an available pre-fetch bandwidth P U and a pre-fetch duration δt in which a server may pre-fetch objects into a memory, and further programmed for identifying a set of objects O s highly associated with a set of users U or seed Web pages by calculating an object gain gain(o) for each object as gain   ( o ) = ∑ u ∈ U   ∑ o ∈ O v   gain   ( u , v ) × pref  ( u , o , v ) , wherein the object gain represents an association between the object and the set of end-users or seed Web pages, defining a cost of each object as cost(o)=size(o), and identifying a subset O s of O v such that ∑ o ∈ O s   cost  ( o ) ≤ P U × δ   t   and   ∑ o ∈ O s   gain  ( o )   is   maximized .