61-69
Paths with Jumps: Definition, Topology-preserving Dynamics, and Applications
Authors: Jaderick P. Pabico
Number of views: 489
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.