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

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 viεV comprising a pair <Ov,av>, where Ov is a set of media objects including a main HTML file and av is a page author, and where each object oεOv has a known end-user preference upref(u) for an end-user u and a page author preference apref(av) for a page author av, an end-user u accessing at a seed Web page vc, 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 vi by applying preference rules defined by upref(u) and apref(av) to the contents of Ov
• calculating an object preference weight pref(u,o,v) for each object oεOv by applying the preference rules defined by upref(u) and apref(av) to the contents of Ov;
• generating a random walk graph Gw having a set of vertices Vw and a set of edges Ew;
• 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.

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 va and vb and other Web pages viεV, comprising:

• memory for storing a location of the seed Web pages va and vb and the other Web pages vi in V;
• and
• a processor programmed for modeling the computer network as an undirected neighborhood graph GN(VN,EN), and programmed for
• constructing a directed random walk graph by
• creating a new vi′ in V for each viεVN, and creating two directed edges e′2×k=<vi′,vj′> and e′2×k+1=<vj′,vi′> in E for each ek=<vi,vj>εEN wherein both vi and vj are in VN,
• computing a penalty value penalty(vi′) for all vertices vi′ε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 vi from vertex vj;
• 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 Vi.

On a computer network having a set of Web pages V and a set of links between those Web pages E, each Web page viεV comprising a pair <Ovav>, where Ov is a set of media objects including a main HTML file and av is a page author, a system for estimating an association between the media objects and a seed Web page vc corresponding to a current location of an end-user u, comprising:

• memory for storing, for each object oεOv, a known end-user preference upref(u) for the end-user u, a page author preference apref(av) for the page author av, and a location of the seed Web page vc;
• 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 vi by applying preference rules defined by upref(u) and apref(av) to the contents of Ov,
• calculating an object preference weight pref(u,o,v) for each object oεOv by applying the preference rules defined by upref(u) and apref(av) to the contents of Ov,
• generating a random walk graph Gw having a set of vertices Vw and a set of edges Ew,
• 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.