a fundamental for click stream analysis

Ist die innere Struktur des Web-Angebots dem Besucher nicht vollständig bekannt, so existieren häufiger gegangene Wege

Sei Ui eine URL des Web-Angebots und P(Ui) die Wahrscheinlichkeit für das direkte Aufsuchen dieser
URL. Seien doch alle gleichlangen Wege W=(Ui,Ui+1,...,Ui+k) auch gleichwahrscheinlich, d.h. es gäbe keine häufiger gegangenen Wege, so gilt
mit P(Wik)=P(Ui)*P(Ui+1|Ui)*...*P(Ui+k|Ui+k-1)), dass P(Wik)=P(Wlm) für alle i,k,l,m aus N mit k=m (für alle gleichlangen Wege, die a priori nicht der inneren,
vorgegebenen Route folgen). Wegen der nicht vollständigen Bekanntheit der inneren Struktur des Web-Angebots gilt aber, dass mindestens ein Un existiert mit P(Un)=0.
Damit gilt aber P(Ui) > P(Un), mithin auch P(Wi0) > P(Wn0) für alle i ungleich n, im Widerspruch zur Gleichwahrscheinlichkeit aller gleichlangen Wege.

Innerhalb eines Web-Angebots gibt es, folgt ein Besucher den vorgegebenen Wegen (inneren links), bereits dann häufiger gegangene Wege, wenn mindestens
zwei URLs so existieren, dass von jeder dieser URLs wenigstens ein Weg (n-ter link) zu genau einer URL existiert, die wenigstens einen weiteren (n+1-ter) link
zu einer nächsten URL des Web-Angebots besitzt.

#1 Die Voraussetzung ist bspw. schon dann erfüllt, wenn nur zwei URLs auf die Start-URL zurück verweisen (return button).

#2 Durch die Addition der bedingten Wahrscheinlichkeiten für den n+1-ten link lässt sich die Annahme einer Gleichwahrscheinlichkeit für gleichlange Wege widerlegen.

Wird ein Web-Angebot direkt addressiert (1) und nach einer direkten Adressierung einer URL den vorgegebenen links gefolgt (2) so gilt mit der Vereinbarung,
dass der Besuch nur genau einer URL ein Weg ist (Weg der Länge 0), dass es häufiger gegangene Wege gibt.

#2 Die Voraussetzung einer nicht vollständigen Bekanntheit der URL-Struktur aus (1) kann vernachlässigt werden, wenn die Voraussetzung aus (2) erfüllt ist.

created by Frank Johannsen, 1999
f.johannsen@clickedways.de

On the Existence of More Frequently Traversed Paths in Web Navigation Models

On the Existence of More Frequently Traversed Paths in Web Navigation Models

Abstract. User navigation in web environments can be considered as a Markov process on a directed graph. This paper shows that, under mild and realistic assumptions on either the initial distribution or the transition structure, paths of equal length cannot all have equal probability. Consequently, more frequently traversed paths necessarily exist. The result formalizes the emergence of preferred navigation patterns in web systems. Author: Frank Johannsen, 27 years later :)

1. Introduction

Empirical studies of web navigation (or of my own in a mall) reveal strong concentration effects: a small number of paths accounts for a large fraction of user traffic. This paper shows that such concentration is not accidental but follows necessarily from basic structural asymmetries.

The users navigation within a website can be considered as a Markov chain and be proved that uniform probabilities over all paths of equal length occur only in highly symmetric and therefore degenerate cases.

2. Model

Let $G = (U, E)$ be a finite directed graph, where $U$ is the set of nodes (URLs) and $E \subseteq U \times U$ is the set of directed edges (hyperlinks).

User navigation is modeled as a time-homogeneous Markov chain $(U_t)_{t \ge 0}$ with:

initial distribution $\pi$ on $U$,
transition matrix $P = (p_{ij})$, where

$$ p_{ij} = \mathbb{P}(U_{t+1} = j \mid U_t = i), \quad \sum_j p_{ij} = 1. $$

A path of length $k$ is a sequence

$$ W = (u_0, u_1, \dots, u_k), $$

with probability

$$ \mathbb{P}(W) = \pi(u_0)\prod_{t=0}^{k-1} p_{u_t u_{t+1}}. $$

3. Main Result

Theorem. If either

the initial distribution $\pi$ is not uniform, or
the transition matrix $P$ is not fully symmetric (i.e., transition probabilities differ across edges),

then there exist two paths of equal length with different probabilities.

4. Proof

Assume, for contradiction, that for some fixed $k \ge 1$, all paths of length $k$ have equal probability:

$$ \mathbb{P}(W) = c_k \quad \text{for all paths } W \text{ of length } k. $$

In particular, for all admissible pairs $(i,j)$ and $(l,m)$,

$$ \pi(u_i)\, p_{ij} = \pi(u_l)\, p_{lm}. $$

Hence there exists a constant $C$ such that

$$ \pi(u_i)\, p_{ij} = C $$

for all $(i,j) \in E$.

Summing over all $j$ yields

$$ \sum_j \pi(u_i)\, p_{ij} = \pi(u_i) = \sum_j C. $$

Thus $\pi(u_i)$ is constant over all $i$, and therefore $\pi$ is uniform.

Substituting back, it follows that all nonzero transition probabilities $p_{ij}$ are equal. Hence every node has identical outgoing structure and all transitions are uniformly distributed.

This implies a fully symmetric graph. Any deviation from this symmetry contradicts the assumption of equal path probabilities.

□

5. Discussion

The theorem shows that equal likelihood of all paths is an extremely restrictive condition. In realistic web systems, at least one of the following holds:

non-uniform entry distribution,
heterogeneous link structure,
presence of return links or cycles.

Each introduces asymmetry, which induces non-uniform path probabilities and leads to concentration effects.

6. Conclusion

We have shown that more frequently traversed paths arise inevitably in Markovian models of web navigation. Uniform path probabilities occur only in degenerate symmetric cases. Thus, preferential navigation behavior is an inherent structural property of realistic web graphs.