Paths with Jumps Definition, Topology-preserving Dynamics, and Applications

Goggle and other list-based web services like Yahoo, Twitter and Facebook present their n-item results in m pages, where m 1. The list can be represented as a path Pn(V, E) of order n and size n – 1, where Pn is particularly a sequence of n distinct nodes v0, v1, …, vn–1  V and (n – 1) links (0, 1), (1, 2), …, (n– 2, n–1)  E. When users are not satisfied with the first few nodes, they will conduct a walk W, often with jumps, that goes back and forth along Pn until they find the kth node, 0 k < n, that satisfies their search. The simple walk can be modeled as a sequence of non-distinct nodes in Pn, but modeling it with jumps is difficult because there are no links in Pn to allow the jumps between two non-adjacent nodes. To model this user behavior, the path is alternatively modeled as a sequence of m (m/n–1)-power of Pm/n’s separated by P2’s, which is termed here as a path with jumps Jm,n. With this new representation for the list, W can be modeled as a simple walk over Jm,n. In reality, the final walk W is an evolution of the time-progressed s sub-walks W(0), W(1), …, W(s–1), where W(t) is a walk that was developed up to time t <s. This means that W(q)  W(r) or W(q) ⊏ W(r), q < r, where the symbols  and ⊏ represent the subset and prefix relations, respectively. These relations are true when Jm,n is static at best or under steady state at worst. However, Jm,n is likewise dynamic. In this paper, a path with jumps as a special graph is introduced, the analysis of its dynamics is presented, and its possible application to modeling user behavior in most popular web services is discussed.

Keywords – paths, walks, jumps, user-behavior modeling, web services