# A new class of minimal asymptotic bases

Melvyn B. Nathanson  Lehman College (CUNY), Bronx, NY 10468
<EMAIL_ADDRESS>
###### Abstract.

A set $A$ of nonnegative integers is an asymptotic basis of order $h$ if every
sufficiently large integer can be represented as the sum of $h$ not
necessarily distinct elements of $A$. An asymptotic basis $A$ is minimal if
removing any element of $A$ destroys every representation of infinitely many
integers. In this paper, a new class of minimal asymptotic bases is
constructed.

###### Key words and phrases:

Additive number theory, additive basis, asymptotic basis, minimal asymptotic
basis, Erdős-Turán conjecture.

###### 2010 Mathematics Subject Classification:

11B13, 11B05, 11B34, 11B75.

Supported in part by a grant from the PSC-CUNY Research Awards Program.

##  1\. $\mathcal{G}$-adic asymptotic bases

Let $\mathbf{N}_{0}=\\{0,1,2,3,\ldots\\}$ be the set of nonnegative integers
and let $h$ be a positive integer. Let $A,A_{1},\ldots,A_{h}$ be subsets of
$\mathbf{N}_{0}$. We define the _sumset_

$A_{1}+\cdots+A_{h}=\\{a_{1}+\cdots+a_{h}:a_{i}\in A_{i}\text{ for all
}i=1,2,\ldots,h\\}$

and the _$h$ -fold sumset_

$hA=\underbrace{A+\cdots+A}_{\text{$h$
summands}}=\\{a_{1}+\cdots+a_{h}:a_{i}\in A\text{ for all }i=1,2,\ldots,h\\}.$

The set $A$ is a _basis of order $h$_ if every nonnegative integer can be
represented as the sum of $h$ not necessarily distinct elements of $A$, that
is, if $hA=\mathbf{N}_{0}$. The set $A$ is an _asymptotic basis of order $h$_
if $hA$ contains all sufficiently large integers. An asymptotic basis of order
$h$ is _minimal_ if no proper subset of $A$ is an asymptotic basis of order
$h$. Thus, if $A$ is a minimal asymptotic basis of order $h$, then, for all
$a\in A$, there are infinitely many integers $n$ such that removing $a$ from
$A$ destroys every representation of $n$ as a sum of $h$ elements of $A$.

Minimal asymptotic bases are extremal objects in additive number theory, and
are related to the conjecture of Erdős and Turán [4] that the representation
function of an asymptotic basis of order $h$ must be unbounded.

At this time there are few explicit constructions of minimal asymptotic bases.
Nathanson [11, 12] used a 2-adic construction to produce the first examples of
minimal asymptotic bases. This method was extended to $g$-adically defined
sets by Chen [2], Chen and Chen [1], Chen and Tang [3], Jia [5], Jia and
Nathanson [6], Lee [7], Li and Li [8], Ling and Tang [9, 10], Sun [15, 16],
and Sun and Tao [17]. This paper constructs a new class of minimal asymptotic
bases.

An _interval of integers of length $t$_ is a set of $t$ consecutive integers.
For $u,v\in\mathbf{N}_{0}$ with $u\leq v$, the set

$[u,v]=\\{x\in\mathbf{N}_{0}:u\leq x\leq v\\}$

is an interval of integers of length $v-u+1$. Thus,
$[1,h]=\\{1,2,\ldots,h\\}$.

A _$\mathcal{G}$ -adic sequence_ is a strictly increasing sequence of positive
integers $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ such that $g_{0}=1$ and
$g_{i-1}$ divides $g_{i}$ for all $i\geq 1$. Let $(d_{i})_{i=1}^{\infty}$ be
the sequence of positive integers defined by

$d_{i}=\frac{g_{i}}{g_{i-1}}.$

For all $i\geq 1$, we have

(1) $d_{i}\geq 2$

and

(2) $g_{i}=d_{1}d_{2}\cdots d_{i}.$

For all $i$ and $j$ with $0\leq i<j$, we have

(3) $\frac{g_{i+j}}{g_{i}}=d_{i+1}d_{i+2}\cdots d_{i+j}.$

Every positive integer $n$ has a unique $\mathcal{G}$-adic representation

$n=\sum_{j=0}^{\infty}x_{j}g_{j}$

where

$x_{j}\in[0,d_{j+1}-1]$

for all $j\in\mathbf{N}_{0}$ and $x_{j}=0$ for all sufficiently large $j$
(Nathanson [13, 14]). Equivalently, for every positive integer $n$, there is a
unique nonempty finite set $F\subseteq\mathbf{N}_{0}$ and a unique set
$\\{x_{j}:j\in F\\}$ such that

(4) $n=\sum_{j\in F}x_{j}g_{j}$

where $x_{j}\in[1,d_{j+1}-1]$ for all $j\in F$.

For every integer $g\geq 2$, the usual $g$-adic representation uses the
$\mathcal{G}$-adic sequence $\mathcal{G}=\left(g^{i}\right)_{i=0}^{\infty}$
with quotients $d_{i}=g$ for all $i\geq 1$.

######  Lemma 1.

Let $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be a $\mathcal{G}$-adic system. If
$n=\sum_{j\in F}x_{j}g_{j}$ is a positive integer with $x_{j}\in[1,d_{j+1}-1]$
for all $j\in F$, then

$g_{M}\leq n<g_{M+1}$

if and only if

$\max(F)=M.$

###### Proof.

If $\max(F)=M$, then $F\subseteq[0,M]$ and

$\displaystyle g_{M}$ $\displaystyle\leq x_{M}g_{M}\leq n\leq\sum_{j\in
F}(d_{j+1}-1)g_{j}$
$\displaystyle\leq\sum_{j=0}^{M}(d_{j+1}-1)g_{j}=\sum_{j=0}^{M}(g_{j+1}-g_{j})$
$\displaystyle=g_{M+1}-1<g_{M+1}.$

Conversely, if $g_{M}\leq n<g_{M+1}$ and $\max(F)=M^{\prime}$, then the
inequality

$g_{M^{\prime}}\leq x_{M^{\prime}}g_{M^{\prime}}\leq n<g_{M+1}$

implies $M^{\prime}\leq M$. If $M^{\prime}\leq M-1$, then

$n\leq\sum_{j=0}^{M^{\prime}}(d_{j+1}-1)g_{j}<g_{M^{\prime}+1}\leq g_{M}$

which is absurd. Therefore, $g_{M}\leq n<g_{M+1}$ implies $\max(F)=M$. This
completes the proof. ∎

Let $W$ be a nonempty set of nonnegative integers, and let
$\mathcal{F}^{*}(W)$ be the set of all nonempty finite subsets of $W$. Let
$\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be a $\mathcal{G}$-adic sequence. We
define the set of positive integers

$A_{\mathcal{G}}(W)=\left\\{\sum_{j\in
F}x_{j}g_{j}:F\in\mathcal{F}^{*}(W)\text{ and
}x_{j}\in[1,d_{j+1}-1]\right\\}.$

Note that $0\notin A_{\mathcal{G}}(W)$ because
$\emptyset\notin\mathcal{F}^{*}(W)$.

Let $h\geq 2$. A _partition_ of $\mathbf{N}_{0}$ is a sequence
$\mathcal{W}=(W_{i})_{i=0}^{h-1}$ of nonempty pairwise disjoint sets such that

$\mathbf{N}_{0}=W_{0}\cup W_{1}\cup\cdots\cup W_{h-1}.$

######  Theorem 1.

Let $h\geq 2$ and let $\mathcal{W}=(W_{i})_{i=0}^{h-1}$ be a partition of
$\mathbf{N}_{0}$. Let $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be a
$\mathcal{G}$-adic sequence. The set

$A_{\mathcal{G}}(\mathcal{W})=\bigcup_{i=0}^{h-1}A_{\mathcal{G}}(W_{i})$

is an asymptotic basis of order $h$ with $h$-fold sumset

$hA_{\mathcal{G}}(\mathcal{W})=\\{n\in\mathbf{N}_{0}:n\geq h\\}.$

###### Proof.

The smallest integer in the set $A_{\mathcal{G}}(\mathcal{W})$ is $1=1\cdot
g_{0}$. It follows that $h\in hA_{\mathcal{G}}(\mathcal{W})$ but $[0,h-1]\cap
hA_{\mathcal{G}}(\mathcal{W})=\emptyset$.

Every positive integer $n$ has a unique $\mathcal{G}$-adic representation
$n=\sum_{j\in F}x_{j}g_{j}$, where $F$ is a nonempty finite set of nonnegative
integers and $x_{j}\in[0,d_{j+1}-1]$. For $i\in[0,h-1]$, let

$F_{i}=F\cap W_{i}$

and

$n_{i}=\sum_{j\in F_{i}}x_{j}g_{j}.$

If $F_{i}=\emptyset$, then $n_{i}=0\notin A_{\mathcal{G}}(\mathcal{W})$. If
$F_{i}\neq\emptyset$, then

$n_{i}=\sum_{j\in F_{i}}x_{j}g_{j}\in A_{\mathcal{G}}(W_{i})\subseteq
A_{\mathcal{G}}(\mathcal{W}).$

Let

$L=\left\\{i\in[0,h-1]:F_{i}\neq\emptyset\right\\}=\left\\{i\in[0,h-1]:n_{i}\geq
1\right\\}$

and

$|L|=\ell_{0}.$

We have $\ell_{0}\in[1,h]$ and

$n=\sum_{i\in L}n_{i}\in\ell_{0}A_{\mathcal{G}}(\mathcal{W}).$

Let $\ell$ be the largest integer such that $\ell\leq h$ and $n\in\ell
A_{\mathcal{G}}(\mathcal{W})$. We must prove that $\ell=h$.

If $n\in\ell A_{\mathcal{G}}(\mathcal{W})$, then there exist integers
$n_{1},\ldots,n_{\ell}\in A_{\mathcal{G}}(\mathcal{W})$ such that

$n=n_{1}+\cdots+n_{k-1}+n_{k}+n_{k+1}+\cdots+n_{\ell}.$

For each $i\in[1,\ell]$ there is an integer $s_{i}\in[0,h-1]$ and a set
$F_{s_{i}}\in\mathcal{F}^{*}(W_{s_{i}})$ such that $n_{i}$ has the
$\mathcal{G}$-adic representation

$n_{i}=\sum_{j\in F_{s_{i}}}x_{j}g_{j}\in A_{\mathcal{G}}(W_{s_{i}}).$

Suppose that $\ell<h$. If $|F_{s_{k}}|\geq 2$ for some $k\in[1,\ell]$, then
there are nonempty sets $F^{\prime}_{s_{i}}$ and $F^{\prime\prime}_{s_{i}}$
such that

$F_{s_{k}}=F^{\prime}_{s_{k}}\cup
F^{\prime\prime}_{s_{k}}\operatorname{\qquad\text{and}\qquad}F^{\prime}_{s_{k}}\cap
F^{\prime\prime}_{s_{k}}=\emptyset.$

The integers

$n^{\prime}_{k}=\sum_{j\in F^{\prime}_{s_{k}}}x_{j}g_{j}\in
A_{\mathcal{G}}(W_{s_{k}})\operatorname{\qquad\text{and}\qquad}n^{\prime\prime}_{k}=\sum_{j\in
F^{\prime\prime}_{s_{k}}}x_{j}g_{j}\in A_{\mathcal{G}}(W_{s_{k}})$

satisfy

$n_{k}=n^{\prime}_{k}+n^{\prime\prime}_{k}$

and so

$n=n_{1}+\cdots
n_{k-1}+n^{\prime}_{k}+n^{\prime\prime}_{k}+n_{k+1}+\cdots+n_{\ell}\in(\ell+1)A_{\mathcal{G}}(\mathcal{W}).$

This contradicts the maximality of $\ell$, and so $|F_{s_{i}}|=1$ for all
$i\in[1,\ell]$ and

$n_{i}=x_{j_{i}}g_{j_{i}}$

for some $g_{j_{i}}\in W_{s_{i}}$ and $x_{j_{i}}\in[0,d_{j_{i}+1}-1]$.

If $x_{j_{k}}\geq 2$ for some $k\in[1,\ell]$, then

$g_{j_{k}}\in
A_{\mathcal{G}}(W_{s_{k}})\operatorname{\qquad\text{and}\qquad}(x_{j_{k}}-1)g_{j_{k}}\in
A_{\mathcal{G}}(W_{s_{k}})$

and

$n_{k}=g_{j_{k}}+(x_{j_{k}}-1)g_{j_{k}}.$

It follows that

$n=n_{1}+\cdots
n_{k-1}+g_{j_{k}}+(x_{j_{k}}-1)g_{j_{k}}+n_{k+1}+\cdots+n_{\ell}\in(\ell+1)A_{\mathcal{G}}(\mathcal{W}),$

which again contradicts the maximality of $\ell$. Therefore, $x_{j_{i}}=1$ for
all $i\in[1,\ell]$, and

$n=g_{j_{1}}+\cdots+g_{j_{k}}+\cdots+g_{j_{\ell}}.$

If $j_{k}\geq 1$ for some $k\in[1,\ell]$, then

$g_{j_{k}}=g_{j_{k}-1}+(d_{j_{k}}-1)g_{j_{k}-1}$

and

$n=g_{j_{1}}+\cdots+g_{j_{k}-1}+(d_{j_{k}}-1)g_{j_{k}-1}+\cdots+g_{j_{\ell}}\in(\ell+1)A_{\mathcal{G}}(\mathcal{W}),$

which also contradicts the maximality of $\ell$. Therefore, $j_{k}=0$ and
$g_{j_{k}}=g_{0}=1$ for all $k\in[1,\ell]$, and so

$n=\underbrace{g_{0}+\cdots+g_{0}}_{\text{$\ell$
summands}}=\underbrace{1+\cdots+1+\cdots+1}_{\text{$\ell$ summands}}=\ell\leq
h-1,$

which is absurd. This completes the proof. ∎

######  Theorem 2.

Let $h\geq 2$ and let $\mathcal{W}=(W_{i})_{i=0}^{h-1}$ be a partition of
$\mathbf{N}_{0}$. The set

$A=\\{0\\}\cup A_{\mathcal{G}}(\mathcal{W})$

is a basis of order $h$ but not a minimal asymptotic basis of order $h$.

###### Proof.

Because $0\in A$ and $1\in A_{\mathcal{G}}(\mathcal{W})\subseteq A$, we have

$\ell=(h-\ell)\cdot 0+\ell\cdot 1\in hA$

for all $\ell\in[0,h-1]$. By Theorem 1,

$\\{n\in\mathbf{N}_{0}:n\geq h\\}=hA_{\mathcal{G}}(\mathcal{W})\subseteq hA$

and so $A$ is a basis of order $h$.

The set $A$ is not a minimal asymptotic basis of order $h$ because $0\in A$
and the removal of 0 from $A$ gives the set
$A\setminus\\{0\\}=A_{\mathcal{G}}(\mathcal{W})$, which is still an asymptotic
basis of order $h$. This completes the proof. ∎

##  2\. Minimal asymptotic bases

The following lemma generalizes a result of Jia [5].

######  Lemma 2.

Let $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be a $\mathcal{G}$-adic sequence. Let
$(u_{i})_{i=1}^{p}$ be a strictly increasing finite sequence of nonnegative
integers, and let $(v_{j})_{j=1}^{q}$ be a finite sequence of not necessarily
distinct nonnegative integers. Let

$x_{i}\in[1,d_{u_{i}+1}-1]$

for all $i\in[1,p]$ and

$y_{j}\in[1,d_{v_{j}+1}-1]$

for all $j\in[1,q]$. If

(5) $n=\sum_{i=1}^{p}x_{i}g_{u_{i}}=\sum_{j=1}^{q}y_{j}g_{v_{j}}$

then

(6) $\sum_{u_{i}\leq u_{k}}x_{i}g_{u_{i}}\leq\sum_{v_{j}\leq
u_{k}}y_{j}g_{v_{j}}$

for all $k\in[1,p]$.

###### Proof.

Because the sequence $(u_{i})_{i=1}^{p}$is strictly increasing, Lemma 1
implies

$\displaystyle\sum_{u_{i}\leq
u_{k}}x_{i}g_{u_{i}}=\sum_{i=1}^{k}x_{i}g_{u_{i}}<g_{u_{k+1}}$

for all $k\in[1,p]$. Choosing $k=p$ gives

$n=\sum_{i=1}^{p}x_{i}g_{u_{i}}<g_{u_{p+1}}.$

Relation (5) implies

$g_{v_{j}}\leq n<g_{u_{p}+1}$

an so $v_{j}\leq u_{p}$ for all $j\in[1,q]$. This implies (6) for $k=p$.

In the sequence $\mathcal{G}=(g_{i})_{i=0}^{\infty}$, the integer $g_{i}$
divides $g_{j}$ for all $i\leq j$. Let $k\in[1,p-1]$. Because the sequence
$(u_{i})_{i=1}^{p}$ is strictly increasing, for all $i\in[k+1,p]$ we have

$u_{k}<u_{k}+1\leq u_{k+1}\leq u_{i}$

and $g_{u_{k}+1}$ divides $g_{u_{i}}$, that is,

$g_{u_{i}}\equiv 0\pmod{g_{u_{k}+1}}.$

If $v_{j}\geq u_{k}+1$, then

$g_{v_{j}}\equiv 0\pmod{g_{u_{k}+1}}.$

Rearranging (5), we obtain

(7) $\displaystyle\sum_{u_{i}\leq u_{k}}x_{i}g_{u_{i}}-\sum_{v_{j}\leq
u_{k}}y_{j}g_{v_{j}}$ $\displaystyle=\sum_{v_{j}\geq
u_{k}+1}y_{j}g_{v_{j}}-\sum_{u_{i}>u_{k}}x_{i}g_{u_{i}}$ $\displaystyle\equiv
0\pmod{g_{u_{k}+1}}.$

If

$\sum_{u_{i}\leq u_{k}}x_{i}g_{u_{i}}>\sum_{v_{j}\leq u_{k}}y_{j}g_{v_{j}}$

then Lemma 1 gives

$0<\sum_{i=1}^{k}x_{i}g_{u_{i}}-\sum_{v_{j}\leq
u_{k}}y_{j}g_{v_{j}}\leq\sum_{i=1}^{k}x_{i}g_{u_{i}}<g_{u_{k+1}}.$

This inequality contradicts congruence (7). This completes the proof. ∎

######  Theorem 3.

Let $h\geq 2$ and let $t$ be an integer such that

(8) $t\geq 1+\frac{\log h}{\log 2}.$

Let $\mathcal{W}=(W_{i})_{i=0}^{h-1}$ be a partition of $\mathbf{N}_{0}$ such
that, for all $i\in[0,h-1]$, there is an infinite set $\mathcal{M}_{i}$ of
positive integers such that

(9) $[M_{i}-t+1,M_{i}]\subseteq W_{i}$

for all $M_{i}\in\mathcal{M}_{i}$. Let $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be
a $\mathcal{G}$-adic sequence. The set

$A_{\mathcal{G}}(\mathcal{W})=\bigcup_{i=0}^{h-1}A_{\mathcal{G}}(W_{i})$

is a minimal asymptotic basis of order $h$.

###### Proof.

By Theorem 1, the set $A_{\mathcal{G}}(\mathcal{W})$ is an asymptotic basis of
order $h$.

Let $a\in A_{\mathcal{G}}(\mathcal{W})$. Without loss of generality, we can
assume that $a=a_{0}\in A_{\mathcal{G}}(W_{0})$ and

(10) $a_{0}=\sum_{j\in F_{0}}x_{0,j}g_{j}$

where $F_{0}\in\mathcal{F}^{*}(W_{0})$ and $x_{0,j}\in[1,d_{j+1}-1]$ for all
$j\in F_{0}$. Let $M_{0}=\max(F_{0})$. By Lemma 1,

$g_{M_{0}}\leq a_{0}<g_{M_{0}+1}.$

For all $i\in[1,h-1]$, choose an integer $M_{i}$ in the infinite set
$\mathcal{M}_{i}$ such that

(11) $M_{i}\geq M_{0}+t$

and let

(12) $a_{i}=\sum_{\begin{subarray}{c}j\in W_{i}\\\
j<M_{0}\end{subarray}}(d_{j+1}-1)g_{j}+g_{M_{i}}\in A_{\mathcal{G}}(W_{i}).$

This is the $\mathcal{G}$-adic representation of $a_{i}$. Let

(13)
$n=\sum_{i=0}^{h-1}a_{i}=a_{0}+\sum_{i=1}^{h-1}\sum_{\begin{subarray}{c}j\in
W_{i}\\\ j<M_{0}\end{subarray}}(d_{j+1}-1)g_{j}+\sum_{i=1}^{h-1}g_{M_{i}}.$

This is the $\mathcal{G}$-adic representation of $n$.

Let

$n=\sum_{i=0}^{h-1}b_{k_{i}}$

be any representation of $n$ as the sum of $h$ elements of
$A_{\mathcal{G}}(\mathcal{W})$, where $k_{i}\in[0,h-1]$ for all $i\in[0,h-1]$
and $b_{k_{i}}\in A_{\mathcal{G}}(W_{k_{i}})$. We must prove that
$b_{k_{i}}=a_{0}$ for some $i\in[0,h-1]$.

Each integer $b_{k_{i}}$ is of the form

$b_{k_{i}}=\sum_{j\in E_{k_{i}}}y_{i,j}g_{j}\in A_{\mathcal{G}}(W_{k_{i}})$

where $E_{k_{i}}\in\mathcal{F}^{*}(W_{k_{i}})$ and $y_{i,j}\in[1,g_{j+1}-1]$
for all $j\in E_{k_{i}}$. The uniqueness of the $\mathcal{G}$-adic
representation implies that if $\\{k_{0},k_{1},\ldots,k_{h-1}\\}=[0,h-1]$,
then, after rearrangement, $k_{i}=i$ and $a_{i}=b_{i}$ for all $i\in[0,h-1]$.

If $\\{k_{0},k_{1},\ldots,k_{h-1}\\}\neq[0,h-1]$, then there exists
$s\in[0,h-1]$ such that $s\notin\\{k_{0},k_{1},\ldots,k_{h-1}\\}$. Suppose
that $s\neq 0$. Recall that

$M_{s}\geq M_{0}+t$

and

$[M_{s}-t+1,M_{s}]\subseteq W_{s}.$

Because $k_{i}\neq s$ for all $i\in[0,h-1]$, we have

$[M_{s}-t+1,M_{s}]\cap E_{k_{i}}\subseteq W_{s}\cap W_{k_{i}}=\emptyset.$

We construct the partition

$E_{k_{i}}=E^{\prime}_{k_{i}}\cup E^{\prime\prime}_{k_{i}}$

with

$E_{k_{i}}^{\prime}=\\{j\in E_{k_{i}}:j\leq M_{s}-t\\}$

and

$E_{k_{i}}^{\prime\prime}=\\{j\in E_{k_{i}}:j\geq M_{s}+1\\}.$

The sets $E_{k_{i}}^{\prime}$ and $E_{k_{i}}^{\prime\prime}$ are not
necessarily nonempty. Let

$b_{k_{i}}=b^{\prime}_{k_{i}}+b^{\prime\prime}_{k_{i}}$

where

$b^{\prime}_{k_{i}}=\sum_{j\in
E^{\prime}_{k_{i}}}y_{i,j}g_{j}\operatorname{\qquad\text{and}\qquad}b^{\prime\prime}_{k_{i}}=\sum_{j\in
E^{\prime\prime}_{k_{i}}}y_{i,j}g_{j}.$

Note that $b^{\prime}_{k_{i}}=0$ if $E^{\prime}_{k_{i}}=\emptyset$ and
$b^{\prime\prime}_{k_{i}}=0$ if $E^{\prime\prime}_{k_{i}}=\emptyset$.

By Lemma 1,

(14) $b^{\prime}_{k_{i}}<g_{M_{s}-t+1}$

and

$b^{\prime\prime}_{k_{i}}=0\qquad\text{or}\qquad b^{\prime\prime}_{k_{i}}\geq
g_{M_{s}+1}.$

Let

(15)
$n^{\prime}=\sum_{i=0}^{h-1}b^{\prime}_{k_{i}}\operatorname{\qquad\text{and}\qquad}n^{\prime\prime}=\sum_{i=0}^{h-1}b^{\prime\prime}_{k_{i}}.$

Recall inequalities (1) and (8):

$d_{i}\geq 2\operatorname{\qquad\text{and}\qquad}h\leq 2^{t-1}.$

From (15), (14), and (3), we obtain

$n^{\prime}<hg_{M_{s}-t+1}\leq 2^{t-1}g_{M_{s}-t+1}\leq
g_{M_{s}-t+1}\prod_{i=1}^{t-1}d_{M_{s}-t+i}=g_{M_{s}}.$

Therefore, the $\mathcal{G}$-adic representation of $n^{\prime}$ is of the
form

$n^{\prime}=\sum_{j=0}^{M_{s}-1}z_{j}g_{j}$

with $z_{j}\in[0,d_{j+1}-1]$. Because

$n^{\prime\prime}=0\qquad\text{or}\qquad n^{\prime\prime}\geq g_{M_{s}+1},$

the $\mathcal{G}$-adic representation of $n^{\prime\prime}$ is of the form

$n^{\prime\prime}=\sum_{j=M_{s}+1}^{\infty}z_{j}g_{j}$

with $z_{j}\in[0,d_{j+1}-1]$ and $z_{j}\geq 1$ for only finitely many $j$.
Therefore,

$n=n^{\prime}+n^{\prime\prime}=\sum_{i=0}^{M_{s}-1}z_{i}g_{i}+\sum_{i=M_{s}+1}^{\infty}z_{i}g_{i}$

is the $\mathcal{G}$-adic representation of $n$. In this representation, the
coefficient of $g_{M_{s}}$ is 0, which contradicts the construction of $n$. It
follows that

$[1,h-1]\subseteq\\{k_{0},k_{1},\ldots,k_{h-1}\\}.$

Renumbering the integers $b_{i}$, we can assume that $k_{i}=i$ and $b_{i}\in
A_{\mathcal{G}}(W_{i})$ for all $i\in[1,h-1]$.

We must prove that $k_{0}=0$, or, equivalently, that $b_{0}\in
A_{\mathcal{G}}(W_{0})$. If not, then $b_{0}\in A_{\mathcal{G}}(W_{r})$ for
some $r\in[1,h-1]$. Because

$M_{0}=\max(F_{0})\in F_{0}\subseteq W_{0}$

we have

$M_{0}\notin\bigcup_{i=0}^{h-1}E_{k_{i}}\subseteq\bigcup_{i=1}^{h-1}W_{i}.$

Identity (10) and Lemma 1 give

$g_{M_{0}}\leq a_{0}=\sum_{j\in F_{0}}x_{0,j}g_{j}<g_{M_{0}+1}.$

From (12) we have

$\displaystyle n$
$\displaystyle=a_{0}+\sum_{i=1}^{h-1}\sum_{\begin{subarray}{c}j\in W_{i}\\\
j<M_{0}\end{subarray}}(d_{j+1}-1)g_{j}+\sum_{i=1}^{h-1}g_{M_{i}}$
$\displaystyle=\sum_{i=0}^{h-1}\sum_{j\in E_{i}}y_{i,j}g_{j}.$

Summing only over terms $g_{j}$ with $j\leq M_{0}$ and applying Lemma 2, we
obtain

$\displaystyle a_{0}+\sum_{i=1}^{h-1}\sum_{\begin{subarray}{c}j\in W_{i}\\\
j<M_{0}\end{subarray}}(d_{j+1}-1)g_{j}$
$\displaystyle\leq\sum_{i=0}^{h-1}\sum_{\begin{subarray}{c}j\in E_{i}\\\ j\leq
M_{0}\end{subarray}}y_{i,j}g_{j}=\sum_{i=0}^{h-1}\sum_{\begin{subarray}{c}j\in
E_{i}\\\ j<M_{0}\end{subarray}}y_{i,j}g_{j}$
$\displaystyle=\sum_{\begin{subarray}{c}j\in E_{0}\\\
j<M_{0}\end{subarray}}y_{0,j}g_{j}+\sum_{i=1}^{h-1}\sum_{\begin{subarray}{c}j\in
E_{i}\\\ j<M_{0}\end{subarray}}y_{i,j}g_{j}$
$\displaystyle<g_{M_{0}}+\sum_{i=1}^{h-1}\sum_{\begin{subarray}{c}j\in
W_{i}\\\ j<M_{0}\end{subarray}}(d_{j+1}-1)g_{j}$ $\displaystyle\leq
a_{0}+\sum_{i=1}^{h-1}\sum_{\begin{subarray}{c}j\in W_{i}\\\
j<M_{0}\end{subarray}}(d_{j+1}-1)g_{j}.$

This is absurd, and so $b_{0}\in A_{\mathcal{G}}(W_{0})$. It follows that the
integer $n$ defined by (13) has a unique representation as the sum of $h$
elements of $A_{\mathcal{G}}(\mathcal{W})$. Therefore,

(16) $n\notin h\left(A_{\mathcal{G}}(\mathcal{W})\setminus\\{a\\}\right).$

For all $i\in[1,h-1]$, there are infinitely many integers
$M_{i}\in\mathcal{M}_{i}$ with $M_{i}\geq M_{0}+t$, and so infinitely many
positive integers $n$ satisfying (16). It follows that
$A_{\mathcal{G}}(\mathcal{W})\setminus\\{a\\}$ is not an asymptotic basis of
order $h$ for all $a\in A_{\mathcal{G}}(\mathcal{W})$. Equivalently,
$A_{\mathcal{G}}(\mathcal{W})$ is a minimal asymptotic basis of order $h$.
This completes the proof. ∎

######  Corollary 1.

Let $\mathcal{W}=W_{0}\cup W_{1}$ be a partition of $\mathbf{N}_{0}$ such that
both $W_{0}$ and $W_{1}$ contain infinitely many pairs of consecutive
integers. Let $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be a $\mathcal{G}$-adic
sequence. The set

$A_{\mathcal{G}}(\mathcal{W})=A_{\mathcal{G}}(W_{1})\cup
A_{\mathcal{G}}(W_{2})$

is a minimal asymptotic basis of order $2$.

###### Proof.

This is the case $h=2$ of Theorem 3. ∎

##  3\. Open problems

  1. (1)

Let $h\geq 2$. By Theorem 1, for every partition
$\mathcal{W}=(W_{i})_{i=0}^{h-1}$ of $\mathbf{N}_{0}$ and every
$\mathcal{G}$-adic sequence, the set

$A=\\{0\\}\cup A_{\mathcal{G}}(\mathcal{W})$

is a basis of order $h$ that is not a minimal asymptotic basis of order $h$.

    1. (a)

Determine the set of all integers $a\in A$ such that $A\setminus\\{a\\}$ is an
asymptotic basis of order $h$.

    2. (b)

Determine the set of all integers $a\in A$ such that $A\setminus\\{a\\}$ is a
minimal asymptotic basis.

  2. (2)

Let $\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be a $\mathcal{G}$-adic sequence. Let
$h\geq 2$.

    1. (a)

Construct partitions $\mathcal{W}=(W_{i})_{i=0}^{h-1}$ of $\mathbf{N}_{0}$
such that the set $A_{\mathcal{G}}(\mathcal{W})$ is a minimal asymptotic basis
of order $h$.

    2. (b)

Construct partitions $\mathcal{W}=(W_{i})_{i=0}^{h-1}$ of $\mathbf{N}_{0}$
such that the set $A_{\mathcal{G}}(\mathcal{W})$ is not a minimal asymptotic
basis of order $h$.

  3. (3)

Let $(d_{i})_{i=1}^{\infty}$ be a sequence of 2s and 3s. Let
$\mathcal{G}=(g_{i})_{i=0}^{\infty}$ be the $\mathcal{G}$-adic sequence
defined by $g_{0}=1$ and $g_{i}=\prod_{j=1}^{i}d_{i}$ for $i\geq 1$. Consider
problem (2) with respect to this $\mathcal{G}$-adic sequence. Of particular
interest are the infinitely many $\mathcal{G}$-adic sequences
$\mathcal{G}=(g_{i})_{i=0}^{\infty}$ with quotients
$\\{d_{2i-1},d_{2i}\\}=\\{2,3\\}$ for all $i=1,2,3,\ldots$. In this case,
$g_{2i}=6^{i}$ for all $i$.

## References

  * [1] F.-J. Chen and Y.-G. Chen, _On minimal asymptotic bases_ , European J. Combin. 32 (2011), no. 8, 1329–1335.
  * [2] Y.-G. Chen, _On the Erdős-Turán conjecture_ , C. R. Math. Acad. Sci. Paris 350 (2012), no. 21-22, 933–935.
  * [3] Y.-G. Chen and M. Tang, _On a problem of Nathanson_ , Acta Arith. 185 (2018), no. 3, 275–280.
  * [4] P. Erdős and P. Turán, _On a problem of Sidon in additive number theory, and on some related problems_ , J. London Math. Soc. 16 (1941), 212–215.
  * [5] X.-D. Jia, _Minimal bases and $g$-adic representations of integers_, Number Theory: New York Seminar 1991-1995 (New York), Springer-Verlag, 1996, pp. 201–209.
  * [6] X.-D. Jia and M. B. Nathanson, _A simple construction of minimal asymptotic bases_ , Acta Arith. 52 (1989), no. 2, 95–101.
  * [7] J. B. Lee, _A construction of minimal asymptotic bases_ , Periodica Math. Hungar. 26 (1993), 211–218.
  * [8] J. Li and J. Li, _On minimal asymptotic basis of order 4_ , J. Math. Res. Appl. 36 (2016), no. 6,16, 651–658.
  * [9] D. Ling and M. Tang, _On minimal asymptotic $g$-adic bases_, Bull. Aust. Math. Soc. 92 (2015), no. 3, 374–379.
  * [10] by same author, _On minimal asymptotic bases of order three_ , Colloq. Math. 151 (2018), no. 1, 9–18.
  * [11] M. B. Nathanson, _Minimal bases and maximal nonbases in additive number theory_ , J. Number Theory 6 (1974), 324–333.
  * [12] by same author, _Minimal bases and powers of $2$_, Acta Arith. 49 (1988), no. 5, 525–532.
  * [13] by same author, _Additive systems and a theorem of de Bruijn_ , Amer. Math. Monthly 121 (2014), no. 1, 5–17.
  * [14] by same author, _Limits and decomposition of de Bruijn’s additive systems_ , Combinatorial and additive number theory. II, Springer Proc. Math. Stat., vol. 220, Springer, Cham, 2017, pp. 255–267.
  * [15] C.-F. Sun, _On minimal asymptotic basis of order $g-1$_, Indag. Math. (N.S.) 30 (2019), no. 1, 128–135.
  * [16] by same author, _On a problem of Nathanson on minimal asymptotic bases_ , Journal of Number Theory 218 (2021), 152–160.
  * [17] C.-F. Sun and T.-T. Tao, _On $g$-adic minimal asymptotic bases of order $h$_, Int. J. Number Theory 15 (2019), no. 2, 389–406.


©2017 International World Wide Web Conference Committee
(IW3C2), published under Creative Commons CC BY 4.0 License.

# What Makes a Link Successful on Wikipedia?

Dimitar Dimitrov

Both authors contributed equally to this work. GESIS – Leibniz Institute for
the Social Sciences<EMAIL_ADDRESS>Philipp Singer11footnotemark:
1

GESIS – Leibniz Institute for the Social Sciences  & University of Koblenz-
Landau<EMAIL_ADDRESS>Florian Lemmerich

GESIS – Leibniz Institute for the Social Sciences  & University of Koblenz-
Landau<EMAIL_ADDRESS>Markus Strohmaier

GESIS – Leibniz Institute for the Social Sciences  & University of Koblenz-
Landau<EMAIL_ADDRESS>
###### Abstract

While a plethora of hypertext links exist on the Web, only a small amount of
them are regularly clicked. Starting from this observation, we set out to
study large-scale click data from Wikipedia in order to understand _what makes
a link successful_. We systematically analyze effects of link properties on
the popularity of links. By utilizing mixed-effects hurdle models supplemented
with descriptive insights, we find evidence of user preference towards links
leading to the periphery of the network, towards links leading to semantically
similar articles, and towards links in the top and left-side of the screen. We
integrate these findings as Bayesian priors into a navigational Markov chain
model and by doing so successfully improve the model fits. We further adapt
and improve the well-known classic PageRank algorithm that assumes random
navigation by accounting for observed navigational preferences of users in a
weighted variation. This work facilitates understanding navigational click
behavior and thus can contribute to improving link structures and algorithms
utilizing these structures.

††conference: WWW 2017, April 3–7, 2017, Perth, Australia.

Keywords: Human Click Behavior; Navigation; Wikipedia

##  1 Introduction

Even though links are omnipresent on the Web, only a minority of them get
regularly clicked by humans. For example, on Wikipedia only around $4\%$ of
all existing links are clicked by visitors more frequently than 10 times
within a month (cf. Section 3). This phenomenon demonstrates the importance of
a deeper understanding of human navigation behavior in order to provide
efficient and effective navigational support for users. While a variety of
navigational regularities, patterns and strategies have been identified in
previous work [43, 37, 32, 27], our research community still lacks a
systematic understanding of _factors that make a link successful in
information networks_. Towards that end, we turn our attention to Wikipedia,
one of the most popular information sources on today’s Web.

Problem and objectives. In particular, we are interested in understanding _the
relationship between link properties and link popularity_ as measured by
_large-scale transitional click data_. Understanding what link features affect
user click behavior can have implications for how we place links on Wikipedia,
but can also have consequences for fundamental Web algorithms such as Google’s
PageRank that assume random navigation casting all links as equal and do not
account for potential preferences towards specific links.

Materials, approach and methods. We utilize openly available large-scale
datasets about the English Wikipedia: the network of internal links within
Wikipedia articles and navigational data capturing user transitions between
articles (cf. Section 2). Motivated by previous work, we study three types of
features that we compute from the link network and full texts of the articles:
(i) _structural features_ (e.g., humans might prefer to navigate to central
nodes in the information network) [43], (ii) _semantic features_ (e.g., humans
might prefer to navigate between semantically similar articles) [39], and
(iii) _visual features_ (e.g., humans might prefer links on the top of the
screen) [14]. For example, in Figure 1, given the Wikipedia article
“Manchester” and the out-going links to the articles “England” and
“Association Football”, we are interested in understanding which link features
(e.g., the visual position of the link) can better predict the actual
transitions (popularity) of a link.

Methodologically, we start by gaining descriptive insights into the success of
links before we statistically model corresponding effects using mixed-effects
hurdle models [33, 19] allowing us to account for the heterogeneity in the
data (e.g., links in the article “USA” might in general be more frequently
used compared to links in the article “Manchester”). Subsequently, we
integrate obtained insights into existing stochastic models of human
navigation. To that end, we utilize the first-order Markov chain
model—probably the most popular model for this task—in two separate analyses.
First, we craft hypotheses about human navigation based on our insights and
integrate these into a Bayesian inference process as priors; cf. [37]. Based
on Bayesian model selection, this allows us to identify whether given
hypotheses can improve the Markov chain model fit compared to an uninformed
model; additionally, we can obtain a ranking of hypotheses allowing us to
confirm our statistical results within a coherent research approach. Second,
we aim at further utilizing these hypotheses to advance the classic well-known
PageRank algorithm in a weighted variation relaxing the basic assumption of an
uninformed random surfer; we evaluate the ranking of articles against actual
page views.

Figure 1: Example. Wikipedia pages are connected by links for which we can
compute a variety of features that are categorized in _network features_
(e.g., target article’s out-degree), _semantic features_ (e.g., text
similarity between source and target articles), and _visual features_ (e.g.,
position of the link on the screen). This work aims at understanding what
makes a link successful—i.e., which link properties best explain observed
numbers of user transitions (shown on edges).

Contributions and findings. The main contributions of this paper are three-
fold: (i) We provide empirical evidence that Wikipedia users have a preference
of choosing links leading to the periphery of underlying topological link
network, that they prefer links leading to semantically similar articles, and
that links positioned at the top and left-side of an article have a higher
likelihood of being used. (ii) We integrate this evidence with first-order
Markov chain models demonstrating an improvement of respective model fits by
incorporating the assumed behavior of human navigation into the inference
process (Section 5.1). (iii) Finally, we demonstrate the utility of these
findings by adapting the well-known PageRank algorithm to better reflect human
navigation behavior. Our enhancements lead to a significant improvement over
the uninformed baseline algorithm that assumes random navigation by evaluating
obtained ranking against actual article page views on Wikipedia (Section 5.2).
The methodological framework provided in this work can also easily be applied
to other transitional click data apart from Wikipedia.

##  2 Description of Data

This section describes the utilized datasets and extracted features. We make
an implementation of the data extraction process as well as a sample of the
data publicly available online111https://github.com/trovdimi/wikilinks.

###  2.1 Wikipedia link and transition data

Wikipedia data. In this work, we focus on all articles contained in the main
namespace of the English Wikipedia as extracted from the public XML dump from
March, 2015222https://archive.org/details/enwiki-20150304. To obtain
authentically rendered pages, we retrieved the corresponding static HTML pages
by using Wikimedia’s public API
333https://www.mediawiki.org/wiki/API:Main_page. In contrast to using readily
available link dumps, this allowed also for considering links that are
indirectly included in a page, e.g., by templates. A tiny part ($<0.01\%$) of
articles could not be retrieved and had to be excluded from the analysis. With
this data, we created the Wikipedia link network $D_{wiki}$ using articles as
nodes and unique links as directed edges; $D_{wiki}$ contains
$\scriptstyle\mathtt{\sim}$$4.8$ million articles connected by
$\scriptstyle\mathtt{\sim}$$340$ million distinct links.

Transition data. For measuring actual usage of links, we utilize openly
available transition data from Wikipedia from February 2015 [46]. It contains
aggregated page requests extracted from the server log for the English desktop
version of Wikipedia in the form of (referrer, resource) pairs, i.e.,
transitions, and their respective transition counts. The data has already been
pre-processed to filter bots and web crawlers and transitions occurring less
than 10 times, see [46] for details. Since in this paper we are only
interested in studying _internal_ navigation on Wikipedia, we excluded article
requests from outside of Wikipedia (e.g., users arriving directly from search
engines) and focus only on transitions corresponding to an internal link in
our network $D_{wiki}$. These amount for about $1$ billion or $31\%$ of all
page requests and cover $\scriptstyle\mathtt{\sim}$$13.6$ million distinct
links between $\scriptstyle\mathtt{\sim}$$1.4$ million source and
$\scriptstyle\mathtt{\sim}$$2.1$ million target articles. With this
information we can weight edges in $D_{wiki}$ by their transition counts to
obtain an edge-weighted network $D_{trans_{w}}$. Additionally, we denote the
sub-network of $D_{wiki}$ that contains only edges (links) that we observe in
the transition data—i.e., those links having a weight larger than 0 in
$D_{trans_{w}}$—as $D_{trans}$.

###  2.2 Link features

For studying link success, we focus on three types of link features: network
features, semantic similarity features, and visual features.

Network features. Here, we capture the centrality of the source (_src_) and
target articles (_trg_) of a specific link in the Wikipedia link network
$D_{wiki}$ considering the _in-degree_ , the _out-degree_ , the overall
_degree_ , the _pagerank_ [31] and the _k-core_ [2] measure.

Semantic similarity features. Here, we detect the semantic similarity between
the source and target article of a specific link. First, we computed a _text
similarity_ score by utilizing a sub-linear scaled tf-idf weighted vector
space model capturing word tokens of Wikipedia articles [37]. For
dimensionality reduction, we used sparse random projection retaining the
pairwise distance between concepts with some small error. The text similarity
between two pages was then determined by the cosine similarity of
corresponding vectors. We also computed a _topic similarity_ score with the
cosine similarity between Wikipedia categories assigned to source and target.

Visual features. The third group of features is based on the placement of
links within the source article, cf. also [14]. For that purpose, we rendered
the HTML of each articles on a screen for a resolution of 1920 $\times$ 1080,
a common resolution for desktop users. This enables deriving the exact screen
position of links in terms of their x/y-coordinates. Based on visual position,
CSS classes, and HTML tags, we additionally assigned each link to one of the
following visual regions:(1) lead: all links in the first section of the
article excluding infobox, (2) body: all other links in the main text, (3)
left-body: links in the body that are displayed in the 10% most left part of
the screen, (4) right-body: links in the remaining right part of the body, (5)
infobox: all links in the infobox, (6) navbox: all links in a table in the
last section of the article placed by editors for facilitating navigation. As
links can occur multiple times on an article, we derived the visual position
of a link based on its first occurrence on the screen. This goes hand-in-hand
with our empirical results elaborated in Section 4.2. A more detailed
discussion about this facet of our data is provided in Section 7.

##  3 Focus of Attention

We start our analysis by investigating the focus of attention with respect to
link usage in Wikipedia, i.e., we study how strongly user transitions are
concentrated on the few most visited links.

(a) Transitions counts

(b) Out-degrees

(c) Gini coefficients

Figure 2: Focus of attention. This figure illustrates the focus of users’
attention towards specific links. In
LABEL:sub@fig:distributionOfTransitionCounts, we see the frequency
distribution of link transition counts. The long tail distribution shows that
majority of links have low popularity. Figure
LABEL:sub@fig:distributions_wiki_transitions_filtered compares the out-degree
distributions of the Wikipedia link network $D_{wiki}$ (blue) and the
transition network $D_{trans}$ (red) for nodes contained in both networks. We
can observe that only a few links are visited regularly on articles (peak at
out-degree of one in $D_{trans}$) while more links are available (peak at out-
degree of eleven in $D_{wiki}$); Figure LABEL:sub@fig:gini shows the histogram
of Gini coefficients calculated on article vectors of link transition counts
revealing clear inequality of link popularity within articles.

Distribution of transition counts. As a first key statistic, we observe that
of $\scriptstyle\mathtt{\sim}$$340$ million links in $D_{wiki}$ only about
$13.6$ million links (or about 4% of all links) are regularly used, i.e., are
visited at least 10 times within a month. However, even when considering only
these 4% regularly used links, we can observe that users focus heavily on a
comparatively small set of links: about 50% of all transitions stem from only
about $600,000$ links. A frequency plot of the distribution, see Figure
2LABEL:sub@fig:distributionOfTransitionCounts, reveals a long-tailed
distribution, where most of the links receive very low amounts of transitions.

Out-degree distribution.  A similar effect can be observed at the level of
individual articles. We compare the out-degree distributions of nodes in
$D_{wiki}$ and $D_{trans}$, i.e., we compare the number of available links on
articles in $D_{wiki}$ with the number of regularly used links in $D_{trans}$.
For a fair comparison, we consider only the out-degrees of nodes that occur in
both networks. The results in Figure
2LABEL:sub@fig:distributions_wiki_transitions_filtered reveal clear
differences. The out-degree distribution of $D_{wiki}$ reaches a maximum
frequency for articles having eleven out-links indicating a decent amount of
links to choose from. However, the out-degree distribution of $D_{trans}$
clearly reveals that for most articles, users only visit a few articles
regularly with the maximum frequency of only a single link. Formal comparison
of both distributions with respect to (truncated) power-law, exponential, and
log-normal distributions by their goodness of fit reveals that for $D_{trans}$
the out-degree distribution resembles a truncated power-law most closely,
while for $D_{wiki}$ a log-normal distribution is preferred.

Gini coefficient of transition counts.  The previous analyses have suggested a
discrepancy between the link network $D_{wiki}$ and actually transitioned
links in $D_{trans}$ and $D_{trans_{w}}$. The _Gini coefficient_ is a measure
of statistical dispersion allowing us to quantify the inequality of link
popularity within articles. We calculate the Gini coefficient for each article
based on a vector containing the transition counts for all links (including
zeros) in this article from $D_{trans_{w}}$. A Gini coefficient of 0 indicates
complete equality, while a result of 1 would mean that only a single link gets
the whole attention. We visualize the histogram of all coefficients for each
article in Figure 2LABEL:sub@fig:gini; results indicate that there is a clear
inequality of link popularity within articles, i.e., attention focuses on just
a few links.

Summary. In this section, we have presented empirical evidence that on
Wikipedia user attention focuses on a small set of links while navigating.
This hints towards a clear _preference towards a few links_ and demonstrates
the importance of finding indicators of link success, on which we focus in the
remainder of this paper.

##  4 What makes a link successful?

Motivated by the discrepancy between link presence and link usage, we now
study link success. That is, as illustrated in Figure 1, given a Wikipedia
article, we aim at identifying effects of link features (network features,
semantic features, or visual features) on counts of transitions to the
respective target article. This allows us to answer questions such as: “Are
links leading to peripheral articles more popular and thus, more successful?”
We propose a methodology in Section 4.1 and discuss results in Section 4.2.

###  4.1 Methodology

For studying effects of link features on the success of links, we employ
descriptive statistics and _hurdle mixed-effects regression models_ ; we
outline both approaches next.

Descriptive analysis. We start our analysis with a descriptive overview on the
effects of our features on transition counts. For an intuitive picture, we
investigate boolean expressions on our features and determine for each feature
the number of links, the number of transitions, and the average number of
transitions per link. We focus on easy-to-interpret expressions: for network
features, we compare the centrality of the target node with the centrality of
the source node. For semantic similarity features, we compare the similarity
between source and target article of the link with the median of the
respective values for all links within the same source article. Finally, for
the visual features, we divide the screen position in three areas for each
dimension, that is the left, the middle, and the right third of the screen,
and links in the top-half, the bottom-half and links that are only visible
after vertical scrolling (assuming a resolution of 1920 $\times$ 1080)
respectively. Furthermore, we use the position of the link in a specific part
of the article such as the lead or the infobox.

Mixed-effects hurdle model. Additionally, we aim at statistically modeling the
effects of all link features on link success given a certain start node. Our
setting (cf. Figure 1) implies that individual links represent data points
with the transition counts being the outcome to predict, and the respective
link features the effects at interest. Yet, links in the dataset are not
independent of each other, but rather nested within Wikipedia articles.
Heterogeneous effects might be present as e.g., apart from generally different
amounts of total transitions, the article of “Manchester” might pose different
navigational behavior than the article of “USA”. Pooling all links into a
single dataset for ordinary regression can lead to biased results;
consequently we resort to _mixed-effects models_ (also known as multilevel
models or hierarchical models), allowing us to account for the nested
structure—specifically the resulting random variations—between links (level 1)
and Wikipedia pages (level 2). We define our mixed-effects model following
[18]; for a broader introduction we point to [33]:

$Y_{i,j}=\gamma_{0,0}+\gamma_{1,0}X_{1,i,j}+u_{0,j}+u_{1,j}X_{1,i,j}+e_{i,j}$
(1)

Here, $Y_{i,j}$ refers to the transition count of a link $i$ (level 1) on a
Wikipedia page $j$ (level 2); $\gamma_{0,0}$ refers to the overall intercept
and $\gamma_{1,0}$ to the overall regression coefficient for the level 1
predictor $X_{1,i,j}$, e.g., the degree of the target node. These are the
fixed effects. The remainder refers to the random effects: $u_{0,j}$ is the
error component of the intercept allowing the group intercepts to differ,
$u_{1,j}$ refers to the error component of the slope allowing the group slopes
to differ, and $e_{i,j}$ is the classic random error of predictions.

To study the effects of network, semantic similarity and visual features, we
model each feature separately. As shown in Section 3, only 4% of all links
have been used at least 10 times, resulting in a large amount of zeros in the
data outcomes. To account for that, we employ hurdle models [19] in a two-step
approach. (i) First, we model the binary data in $D_{trans}$; i.e., the link
values are set to $1$ iff at least $10$ transitions for these links have been
observed, and to $0$ otherwise. We then model this data with a mixed effect
binomial logistic regression and make inference on the fit. (ii) In a second
step, we only take the data from $D_{trans_{w}}$ capturing those links that
have been clicked and their respective transition counts. As our outcome
variable is generated by count data, basic assumptions for _linear_ mixed-
effects models are violated. Consequently, we resort to zero-truncated
negative binomial mixed-effect models that do not allow the outcome to be zero
(as all outcome counts are at least $10$). The choice of model also enables
modeling the presence of overdispersion in the data. For comparison, we also
fitted Poisson mixed-effects models with an observation-level random effect
that allows for overdispersion [15] but could not find core differences in
inference. Thus, we overall build two models for each feature: one to model
_if_ a link has been used at least 10 times in a month, and a second to model
the transition _counts_ for these regularly used links.

We fit our models using the “Template Model Builder” framework [26] that
evaluates and maximizes the Laplace approximation of the marginal likelihood
utilizing automatic differentiation of the joint likelihood; we use the R
package “glmmTMB”444https://github.com/glmmTMB/glmmTMB. For improving
convergence, we scale non-binary features by subtracting the mean and dividing
by their standard deviation. For judging significance of individual effects,
we follow an incremental model comparison approach [3]. That is, we compare
the model including the effect of interest with a restricted model that
neglects the effect using a _likelihood ratio chi-square test_. Results could
be confirmed by model comparison via AIC and BIC.

Table 1: Descriptive results. This table provides a descriptive overview on link success; it shows for each boolean feature the number of links, the overall number of transitions these links accumulated, and the average transition count per link. Results show that links leading to the periphery of the network, to semantically similar articles, and links positioned in the lead and left area of an article accumulate relatively more transitions than opposite links. Feature | # Links | # Transitions |  | Mean Trans.
---
per Link
trg_degree $<$ src_degree | 462,147 | 3,944,747 | 8.54
trg_degree $\geq$ src_degree | 566,557 | 2,741,834 | 4.84
trg_in_degree $<$ src_in_degree | 412,653 | 3,831,100 | 9.28
trg_in_degree $\geq$ src_in_degree | 616,051 | 2,855,481 | 4.64
trg_out_degree $<$ src_out_degree | 545,980 | 3,912,604 | 7.17
trg_out_degree $\geq$ src_out_degree | 482,724 | 2,773,977 | 5.75
trg_kcore $<$ src_kcore | 283,668 | 3,477,828 | 12.26
trg_kcore $\geq$ src_kcore | 745,036 | 3,208,753 | 4.31
trg_page_rank $<$ src_page_rank | 414,124 | 3,833,596 | 9.26
trg_page_rank $\geq$ src_page_rank | 614,580 | 2,852,985 | 4.64
text_sim $>$ median of article | 511,871 | 4,335,445 | 8.47
text_sim $\leq$ median of article | 516,833 | 2,351,136 | 4.55
topic_sim $>$ median of article | 392,955 | 3,246,766 | 8.26
topic_sim $\leq$ median of article | 635,749 | 3,439,815 | 5.41
position = lead | 93,546 | 2,489,342 | 26.61
position = body | 373,407 | 3,442,017 | 9.22
position = left-body | 64,320 | 934,766 | 14.53
position = right-body | 309,087 | 2,507,251 | 8.11
position = navbox | 502,079 | 99,498 | 0.2
position = infobox | 59,672 | 655,724 | 10.99
screen_x_coord: left third | 211,549 | 2,358,899 | 11.15
screen_x_coord: middle third | 291,260 | 1,422,183 | 4.88
screen_x_coord: right third | 525,847 | 2,905,499 | 5.53
screen_y_coord: top half | 221,980 | 3,991,912 | 17.98
screen_y_coord: bottom half | 174,500 | 998,287 | 5.72
screen_y_coord: scroll needed | 632,176 | 1,696,382 | 2.68
Overall | 1,028,704 | 6,686,581 | 6.5
Table 2: Mixed-effects hurdle modeling results. This table presents the results for the mixed-effects hurdle models based on a basic model specification of: $\text{transition}_{i,j}=\gamma_{0,0}+\gamma_{1,0}\text{feature}_{1,i,j}+u_{0,j}+u_{1,j}\text{ feature}_{1,i,j}+e_{i,j}$. For each feature (first column) and a given transformation (second column), results for both parts of the hurdle model are reported. The binomial models the binary outcome whether a link has been used at all, and the zero-truncated negative-binomial models the transition counts of regularly used links. For each model, we report the fixed effect coefficient of the fitted model, the likelihood ratio test statistic compared to a reduced nested model without the fixed effect, and the significance according to $\chi^{2}$-test. Overall, the results confirm the descriptive results of Table 1 suggesting a preference of links leading to the periphery of the network, links targeting semantically similar articles, and links being positioned at the beginning and left-side of articles.  |  | Binomial Model | Zero-truncated NB Model
---|---|---|---
Feature | Transformation | Fixed effect | LRT | Pr($>$Chi) | Fixed effect | LRT | Pr($>$Chi)
trg_degree | scale | -9.0704 | 9441 |  $<$ 1.0 e-300 *** | -0.1353 | 174 | 7.98 e-40 ***
trg_in_degree | scale | -9.2925 | 9456 |  $<$ 1.0 e-300 *** | -0.1341 | 185 | 4.2 e-42 ***
trg_out_degree | scale | -0.6425 | 4052 |  $<$ 1.0 e-300 *** | -0.0375 | 32 | 1.6 e-08 ***
trg_kcore | scale | -9.4873 | 9470 |  $<$ 1.0 e-300 *** | -0.1296 | 180 | 4.5 e-41 ***
trg_pagerank | scale | -8.8103 | 9384 |  $<$ 1.0 e-300 *** | -0.1457 | 196 | 1.7 e-44 ***
text_sim | scale | 0.2944 | 617 | 3.4 e-136 *** | 0.238 | 1179 | 1.9 e-258 ***
topic_sim | scale | 0.2052 | 482 | 8.6 e-107 *** | 0.1212 | 401 | 3.7 e-89 ***
position = lead | none | 1.9682 | 6146 |  $<$ 1.0 e-300 *** | 0.2858 | 498 | 2.7 e-110 ***
position = body | none | 0.2351 | 93 | 5.9 e-22 *** | -0.4581 | 1478 |  $<$ 1.0 e-300 ***
position = left-body | none | 1.106 | 739 | 9.4 e-163 *** | -0.1671 | 123 | 1.7 e-28 ***
position = right-body | none | -0.3631 | 231 | 4.4 e-52 *** | -0.4389 | 1236 | 1.0 e-270 ***
position = infobox | none | -0.1955 | 25 | 7.2 e-07 *** | 0.1365 | 37 | 1.4 e-09 ***
position = navbox | none | -6.3237 | 9226 |  $<$ 1.0 e-300 *** | -0.9963 | 688 | 1.5 e-151 ***
screen_x_coord | scale | -0.2974 | 1081 | 4.4 e-237 *** | 0.0225 | 16 | 6.0 e-05 ***
screen_y_coord | scale | -4.258 | 10588 |  $<$ 1.0 e-300 *** | -0.4004 | 419 | 3.987 e-93 ***

###  4.2 Results

For computational reasons, we applied the methodology to a random sample of
$10,000$ articles containing at least one out-going link in the transition
data $D_{trans}$ considering all links and their features. The sample contains
$1,028,704$ links with $6,686,581$ transitions. We made sure that the sample
captures similar power-law degree distributions as the overall dataset (cf.
Section 3); multiple sampling iterations did not change the results. For
reproducibility reasons, we make the full sample
available555https://github.com/trovdimi/wikilinks/raw/master/sample.csv.gz. We
present the descriptive results in Table 1 and the mixed-effects model results
in Table 2. For the statistical models, we only report fixed effects at
interest but make the full results available in additional
material666https://github.com/trovdimi/wikilinks/tree/master/notebooks. We
discuss results for our three major feature groups next.

Network features. The results in Table 1 highlight that there appears to be a
preference of users to choose links leading to target Wikipedia articles that
have a smaller in-degree, out-degree and degree compared to the source
article. This is specifically imminent when controlling for the presence of
links as the last column indicates. Similar behavior can be seen for the
k-core and pagerank of nodes. Our mixed-effects model results shown in Table 2
statistically confirm this observation. The coefficients for both parts of the
hurdle model (binomial and zero-truncated negative binomial models) show
negative signs for all network features at hand meaning that the higher those
features are (i.e., the more central the target nodes are) the less likely it
is that those links are clicked. Interestingly, the effect sizes and model
fits (LRT) are quite similar for all features except the out-degree which can
be explained by the fact that in general the out-degree is not a good
indicator regarding the centrality of a node in the network as it just depends
on the number of links present on a given page. Overall, the results suggest a
preference for users to navigate to peripheral nodes in the network in
contrast to navigating towards the core of the network. A potential
explanation of this behavior could be that pages located in the core of the
network are more general, whereas pages located in the periphery of the
network are more specific and thus possibly more interesting to the user on
average. Moreover, more general Wikipedia pages are likely more often returned
as results to search engine queries, making them the entry point to Wikipedia.
Then, with the next click within Wikipedia, the user narrows down her
information need. Such a behavior—looking up specific facts or
information—would be in-line with a common use of encyclopedias in general.

Semantic similarity features. The results in Table 1 and Table 2 indicate that
links connecting two semantically related Wikipedia articles—both for text and
topic similarity—are more likely to be transitioned compared to those links
that indicate less semantic similarity. This is imminent from the higher ratio
of transitions to high similarity target articles, and specifically, by the
positive mixed-effects model coefficients for the hurdle models at hand.
Overall, the results suggest a preference towards navigating semantically
similar articles supporting previous research [43, 39, 37].

Visual features. The descriptive results in Table 1 indicate user preference
towards choosing links on the left side of the screen and specifically links
that are at the beginning of a Wikipedia article. The model results in Table 2
confirm these observations. The positional lead feature has strongly positive
coefficients in both the binomial and zero-truncated negative binomial model
indicating that links in the lead are more frequently used. Additionally, we
can see that the right-body feature (links in the right 90% body region)
indicates negative coefficients while the left-body feature (links in the left
10% body region) has a positive coefficient for the binomial model. The models
for the infobox are contradicting each other, but overall show much less model
improvements over the baseline model compared to our other visual feature
models (lower LRT). Furthermore, we can clearly see that the navbox feature
has a strong negative coefficient suggesting that links positioned at the
bottom of the page in the navigation boxes are only seldomly visited. The
coordinate features summarize the more fine-grained results in a broader level
indicating that there is a preference towards choosing links that are at the
beginning and also on the left side of the screen. The results presented are
by and large confirming previous findings on the F-shaped way of information
consumption [14, 30, 10].

Summary. Our results suggest three indicators having an effect on the success
of links on Wikipedia. First, humans appear to have a preference towards
choosing links leading to the periphery of the underlying topological link
network. Second, links connecting semantically related articles tend to be
clicked more frequently than those connecting semantically unrelated articles.
Third, the visual position of a link appears to have an impact of the link’s
success. Links that are located on the top of the screen (i.e., lead of an
article) and on the left of the screen are preferred by humans navigating
Wikipedia suggesting a visual top-left preference.

##  5 Integration in Markov Models

While the results presented in Section 4 provide evidence of factors effecting
the success of links on Wikipedia, it is an open question how we can integrate
these findings into existing models of human navigation. To that end, we
investigate the influence of link features on models of human navigation in
this section. We focus on first-order Markov chains as the most wide-spread
models for this task [6, 7, 38]. First-order Markov chains are stochastic
systems that assume a memoryless generative process, i.e., the probability of
the next state (Wikipedia article) depends only on the current state. We
utilize these models in two separate analyses. First, in Section 5.1, we craft
hypotheses about human navigation based on our insights of Section 4.2 and
incorporate these into a Bayesian inference process. This allows us to (a)
identify whether given hypotheses can better explain observed transition
behavior compared to a uniform structural baseline hypothesis and thus,
potentially improve the Markov chain model fit, and (b) the model comparison
provides an additional ranking of given hypotheses helping in confirming our
previous results within a coherent research approach. Second, in Section 5.2,
we aim at utilizing these insights to improve the classic PageRank algorithm
in a weighted variation and validate its precision against the observed visit
counts of Wikipedia articles.

###  5.1 Bayesian integration

Next, we explore the impact of integrating our findings in Markov chain
navigation models; for that task we resort to a recently proposed Bayesian
approach called HypTrails [37].

Methodology. We aim to integrate hypotheses about navigational behavior, which
we form based on our results obtained in Section 4.2, as prior knowledge into
the inference process for Markov chains. HypTrails [37] provides a coherent
framework for this task. First, one can express a hypothesis, i.e., beliefs in
transition probabilities of a Markov chain, as a matrix $M=(m_{ij})$, where a
higher value expresses higher belief in a transition between articles $i$ and
$j$. Then, these hypotheses matrices are incorporated as Dirichlet priors into
the Bayesian model inference procedure. Due to the sensitivity of a Bayesian
model to the priors on its parameters, more plausible hypotheses—i.e.,
hypotheses that are in line with the observed data—induce higher marginal
likelihood (evidence) values used for model comparison. Marginal likelihoods
can be compared along different values of a parameter $\kappa$ expressing the
strength of belief in a hypothesis. Higher values reflect a higher belief in
given hypothesis; i.e., a stronger probability mass concentration of the
Dirichlet prior. Formally, model comparison is done by calculating a _Bayes
factor_ [24], which is the ratio of the marginal likelihoods for two
hypotheses $H_{1}$ and $H_{2}$; if positive, the first hypothesis is judged as
more plausible—strength of Bayes factors can be checked in an interpretation
table of Kass and Raftery [24].

Comparing the marginal likelihood of a specific hypothesis (e.g., that humans
prefer to navigate to the periphery of the network) with a structural baseline
hypothesis (i.e., random preference of out-links) allows us to detect whether
integrating given hypothesis into the inference process enhances the general
model fit. Additionally, we can compare hypotheses with each other to obtain a
ranking of hypotheses. For more methodological details, we point the reader to
[37]. We describe how we construct hypotheses for our data next.

Hypotheses. We formalize and compare several hypotheses based on our main
findings of Section 4 providing evidence of feature effects on link success.
As mentioned, hypotheses are expressed as matrices $M=(m_{ij})$ indicating
belief in transition probabilities. For finding good formalizations of these
hypotheses, we experimented with different scaling variations such as
logarithmic, square-root, and exponential feature scaling, but only report on
the best formalization for each of the three feature groups due to limited
space.

As a baseline, we use the _structural hypothesis_ expressing the belief that
someone navigating in the Wikipedia network chooses any out-link of an article
randomly. Here, we set $m^{structure}_{ij}=1$ if there is a link from article
$i$ to article $j$ and $m^{structure}_{ij}=0$ otherwise. If other hypotheses
do not reveal higher marginal likelihoods than this baseline hypothesis (i.e.,
positive Bayes factors), they indicate no improvements to the model fit—i.e.,
they do not capture the actual human navigation behavior well.

For the network features, we focus on the _k-core_ having shown promising
results in Section 4. Since we want to formulate a hypothesis that expresses
higher beliefs in transitions to articles with lower k-cores (i.e., the
periphery of the network), we set the entries of the hypothesis matrix to
$m^{kcore}_{ij}=\frac{1}{\sqrt{trg\\_kcore}}$. Regarding semantic similarity,
we use the _text_sim_ feature as it is, i.e.,
$m^{text\\_sim}_{ij}=text\\_sim$. This reflects a belief that transitions to
similar articles (w.r.t. to the text similarity) are more likely. For visual
features, we concentrate on the _position_ feature. Our visual hypothesis
states that links that are in the lead, in the most left part of the body, or
in the infobox are more likely to be visited than the others (as the results
of Section 4 suggest). Thus, we express this hypothesis as $m^{visual}_{ij}=1$
in these cases, and $m^{visual}_{ij}=0$ otherwise. For these hypotheses, we
add the structural baseline hypothesis for smoothing in order to guarantee a
minimum belief in all transitions to linked articles.

In addition to these individual hypotheses, we also include combinations of
them in our comparison. In this direction, we form the hypotheses
_kcore+text_sim_ , _kcore+visual_ , _text_sim+visual_ , and
_kcore+text_sim+visual_ by adding the respective matrices element-wise to each
other—here, no smoothing is necessary.

Figure 3: Bayesian integration results. This figure reports the results for
our experiments on integrating navigational hypotheses as Bayesian priors in
Markov chain models. The x-axis depicts different hypothesis weighting factors
$\kappa$—higher values reflect stronger belief in a given hypothesis. The
y-axis denotes the Bayes factor for a given hypothesis (different lines); the
Bayes factor compares the fit of the respective hypothesis model to the fit of
the baseline, i.e., the structural hypothesis. Higher Bayes factors reflect
higher plausibility of given hypothesis; all Bayes factors in this plot are
strongly decisive. All hypotheses improve the fit of the Markov chain model
when integrated as prior assumptions. Hypotheses labels are in order of their
ranking. A combination of visual and network features leads to the strongest
improvement.

Results. We report the resulting Bayes factors for the comparison between
expressed hypotheses and the structural baseline hypothesis (for varying
hypotheses weighting factors) in Figure 3; for a detailed description of this
figure, please resort to the figure caption. The primary observation is that
all investigated hypotheses improve the fit of the Markov chain model in
comparison to the structural baseline hypothesis as imminent from the Bayes
factors for all values of $\kappa$. Complementary hypotheses (e.g.,
navigational preference towards the core of the network) result in negative
Bayes factors falling below the baseline (not shown here). The relative
ranking of hypotheses also provides interesting insights. Comparing the single
hypotheses (text_sim, kcore and visual) reveals that the visual hypothesis
appears to be the most relevant, followed by the kcore and then the text_sim
hypothesis. Additionally, by combining these hypotheses, we can further
improve the model. Overall, a combination of all three hypotheses has the
highest evidence for higher values of $\kappa$. Yet, the combination of belief
of peripheral navigation and preference towards choosing links in the visual
top and left position already provides a similarly large improvement.

Summary. By and large, the results of this section have successfully
demonstrated that we can improve models of human navigation on Wikipedia—i.e.,
the Markov chain model—by integrating hypotheses (beliefs) about human
navigational behavior into the inference process of the models. In this case,
we have utilized Bayesian inference to incorporate expressed hypotheses based
on our insights of Section 4 as priors. All hypotheses improve the model fit.
Additionally, a ranking of hypotheses reveals the relative plausibility and
combinations show further improvements. Next, we want to further make use of
these insights to improve the well-known PageRank algorithm utilizing the
Markovian framework.

###  5.2 PageRank integration

In this section, we investigate if our insights can be used for improving the
well-known PageRank algorithm for Wikipedia.

Weighted PageRank. The PageRank algorithm [31] is one of the most popular Web
algorithms. It computes a centrality measure—pagerank—for each node in the
network, such that a node receives a high value if it has many in-coming links
from other important nodes. This can be interpreted as the probability of a
random surfer in the network to land on respective page—i.e., the stationary
distribution of a Markov chain model. While for the classic PageRank
algorithm, weights in the network are propagated equally through all links, we
propagate weights according to the eight hypotheses that we formalized in
Section 5.1 based on our main findings. That is, we model the landing
probabilities of a random surfer that chooses the next node in the network
proportional to the entries in the respective hypothesis matrix $M=(m_{ij})$.
This weighted version of PageRank implements a _reasonable surfer model_ [12],
i.e., a model where a random surfer does not choose links uniformly, but is
influenced by link features such as the link position. Formally, we compute
the weighted pagerank of a node as:

$PR(j)=\frac{1-\alpha}{N}+\alpha\sum_{i\in\Gamma^{-}(j)}\frac{PR(i)\cdot
m_{ij}}{Z_{i}}$

where $N$ is the number of nodes in the network, $\Gamma^{-}(j)$ is the set of
nodes linking to the node with index $j$, $\alpha$ is the damping factor and
$Z_{i}=\sum_{j\,^{\prime}\in\Gamma^{+}(i)}m_{ij^{\prime}}$ is a normalization
factor for each matrix row $i$.

For evaluation, we determine the Spearman rank correlation of respective
weighted PageRank with the sum of incoming transitions for a page from
$D_{trans_{w}}$, i.e., the number of views of an article stemming from
internal navigation. As a baseline, we use the classic unweighted PageRank
algorithm assuming random navigation.

Results. Table 3 shows the resulting Spearman correlation coefficient for the
different evaluated hypotheses and the unweighted PageRank as a baseline for
different damping factors $\alpha$. We observe that most, but not all
hypotheses achieve an improvement of the correlation between the aggregated
transitions per target article and the pagerank values. In particular, the
_kcore_ and _visual_ hypotheses lead to improvements. The best result can be
obtained by combining these two hypotheses: the _kcore_visual_ hypothesis
achieves the best correlation score, which is about $0.1$ better than the
baseline. In contrast, and unexpected considering the previous results, the
_text_sim_ hypothesis is not able to increase the correlation, and also does
not lead to improvements when combined with other hypotheses. This might be
caused by the fact that PageRank assumes an infinite random walk while people
navigate in line with this hypothesis maybe only in certain phases of their
Wikipedia visit, e.g., at the end of their visit, cf. [43] and Section 7.
Please note that the correlation increases with the increase of the damping
factor. This is a natural behavior, since we base our analysis on Wikipedia
internal transitions and higher damping factors reduce the chances of
teleportation.

Apart from that, results are mostly in line with the ranking that we obtained
from the Bayesian integration of the hypothesis, cf. Section 5.1. All
correlation coefficients reported in this paper are strongly significant
according a t-test with a null hypothesis that two datasets are uncorrelated.
Additionally, we formally test whether the improvements of the weighted
PageRank algorithms in terms of their correlation coefficients with view
statistics are significant compared to the unweighted algorithm. To that end,
we employ Steiger’s one-tailed hypothesis test for assessing the difference
between two paired correlations [40]; the results reveal clear significance
for all correlations when compared to the baseline.

Summary. The results presented in this section suggest that a PageRank model
with an intelligent edge weighting reflecting the users’ transition behavior
explains the page views stemming from internal navigation better than the
standard random surfer model. The reasonable surfer implemented through the
edge weighting that performs best tend to select links that are leading _out
of the network core to articles in the periphery and located in the top of the
screen, on the left side of the screen and in the infoboxes_.

Table 3: Weighted PageRank results. Comparison of the hypotheses specified in Section 5.1 with respect to the Spearman correlation between the transitions (aggregated per target article) and the pagerank values of the corresponding articles in $D_{wiki}$ for different damping factors. The correlation coefficient for the unweighted PageRank (marked italic) is used as a baseline. We see that most, but not all hypotheses achieve an improvement (marked bold); the best correlation with an improvement of $\scriptstyle\mathtt{\sim}$ $0.1$ across the three dumping factors is achieved by the hypothesis kcore_visual. Damping factor $\alpha$/Hypothesis $M$ | 0.80 | 0.85 |  0.90
---|---|---|---
_baseline_ | 0.421 | 0.428 | 0.436
kcore | 0.434 | 0.440 | 0.447
visual | 0.507 | 0.516 | 0.526
text_sim | 0.400 | 0.407 | 0.415
text_sim+kcore | 0.407 | 0.412 | 0.417
text_sim+visual | 0.489 | 0.500 | 0.513
kcore+visual | 0.530 | 0.538 | 0.545
kcore+visual+text_sim | 0.494 | 0.505 | 0.517

##  6 Related Work

Since the inception of the Web, our research community has been interested in
studying human navigational click data on the Web—e.g., see [20]. In this line
of research, a variety of models has been proposed including the well-known
Markov chain model utilized in this work [38, 31, 35, 37], or models such as
decentralized search [17, 13] motivated by small-world navigation [25].

Insights have been utilized to infer missing links [44], to predict break-ups
of the navigation process [36], for recommendations [42], or to improve the
link structure of a website [32]. For the latter, Paranjape et al. [32]
highlighted the importance of improving hyperlink structures based on their
usage due to the large amount of unused links. Consequently, they proposed an
algorithm for suggesting useful links and estimate their success based on
clickthrough rates.

Based on this wide range of studies aiming at understanding human Web
navigation, a series of navigational regularities, patterns and strategies
have been suggested. For example, West and Leskovec [45] found trade-offs
between similarity and degree in navigational behavior suggesting different
phases in user sessions, namely an exploration (orientation) and an
exploitation (goal-seeking) phase [17]. Subsequent research has suggested that
humans prefer to navigate between semantically similar websites [43, 39, 37],
have preferences for choosing links at the beginning of pages [27, 32, 14],
and that navigational patterns exhibit regularities with respect to underlying
network characteristics [43, 32, 37, 27].

While, as elaborated, a large amount of studies on human navigational behavior
exist and a variety of navigational hypotheses have been proposed, there still
has been a lack of a systematic understanding of what makes a link successful
in information networks. To that end, we have extended previous work covered
in this section by providing a study on effects of link properties on actual
user transition behavior on the complete English Wikipedia utilizing large-
scale data. Instead of providing a global view on clickthrough rates, we have
also focused our attention on the clear setting of given a current Wikipedia
article, which features best predict the popularity of links on that article.
The features of interest have been motivated by previous work and our results
broadly confirm previous hypotheses. Also, our analyses allow for more fine-
grained insights such as navigational preference towards peripheral nodes or
visual preferences on detailed screen coordinates. We have also demonstrated
the importance of better understanding human navigational behavior and link
popularity by successfully enriching existing Markov chain models and the
PageRank algorithm with supplementary behavioral hypotheses.

Our work is also broadly connected to research studying click data in other
contexts, e.g., characterizing user behavior and sybil detection in online
social networks [5, 41], improving search engine ranking functions [21, 47,
22, 1, 23], and marketing and next purchase prediction [11, 9, 8, 29].
However, these do not cover the specifics of large-scale information networks
such as Wikipedia.

##  7 Discussion

In this section, we discuss limitations and future work.

No session information. In this paper, we have focused on aggregated click
counts for link transitions. While this was perfectly suited for our task at
hand, we cannot differentiate between potentially varying phases within
navigation sessions as e.g., zoom-in and zoom-out phases postulated in [43].
Also, we have only looked at _internal navigation_ while observed behavior
might differ when people navigate between different platforms (e.g., Google to
Wikipedia).

Multiple link occurrence. Although the Wikipedia editor guidelines discourage
placing multiple occurrences of links to the same target article within one
source article, this is sometimes ignored by editors. Additionally, links can
be repeated in the infoboxes or overview tables for improved usability.
Unfortunately, the data at hand does not disambiguate which link instance has
been clicked if a link occurs multiple times. While this has no implications
for the network and semantic features as they are independent of the link
position, it influences the analysis of the visual features. In this paper, we
have decided to use the visual feature of the first occurrence of a link on
the screen based on its x- and y-coordinates. This choice is justified by
additional experiments on a restricted dataset filtering out links with
multiple occurrences. As for the main data, a strong preference for links in
the top and the left hand side of the page can be found, cf. also Section 4.2.
The results for the restricted dataset confirm our main findings, but also
reveal a bias: the popularity of links at the top of the page is less
pronounced (but still substantial) in this variation. For further analysis, we
included the number of times a link occurs on an article as a nuisance
parameter to our regression model, but this did not change the main inference.
Thus, we are confident that our main findings are robust with respect to that
issue. However, in future—preferably supplemented with more fine-grained click
data—further studies on the impact of multiple link occurrences should be
conducted.

Different screen resolutions. In our analysis, we chose the specific screen
resolution of 1920 $\times$ 1080 for deriving visual features. While this
adheres to our data only containing click information from desktop users only,
different users may have different visual perception of the same article.
Since this may affect presented results, future work could set out to tackle
this limitation by, e.g., repeating the visual analysis for different screen
resolutions. Another issue of special interest would be to complement the
analysis using transitions data capturing the mobile user behavior on
Wikipedia.

Definition of success. We defined success of a link as the click popularity
derived from user transitions. However, other forms of link success can be
studied. For example, instead of explaining transition preference of out-going
links, one could modify the research question of this study and look at in-
going links. Then, the question of interest would be: Given a set of in-going
links to a given article, which ones are more popular than others and how can
we explain them? Also, in this work, we have not considered the narrow textual
context of a link which is tightly related to the concept of information scent
[34]. Further research can concentrate on this aspect and study the
relationship between diminishing information scent [16] caused, i.e., by
editors and the success of a link. Apart from that, the success of a link
could also be defined in light of how much a link contributes to the different
types of navigation. One could analyze navigability of the networks
$D_{trans}$ and $D_{trans_{w}}$ on the edge and node level, i.e., by studying
the flow in and out of a node or by removing nodes and edges. Link success
could be also examined in terms of its ability to enable and encourage further
navigation and exposing the user to a more richer content or to the strongly
connected component of the network.

Markov chain hypotheses formulation. The results of Section 5 depend on how we
code the hypotheses as priors. In this paper, we hand-crafted hypotheses that
are in line by our data-driven insights of Section 4. We acknowledge that more
fine-grained engineering and learning of good priors and weightings might
further improve results. Additionally, even though in different context and
with different methodology, one might argue that some results of Section 5
could have been expected given our earlier findings. Yet, the main goal here
was to demonstrate the utility of incorporating assumptions about transition
behavior into existing navigational models (i.e., Markov chain and PageRank)
that predominantly, often have assumed uniform behavior. Additionally,
obtained results helped us to further confirm our empirical insights of this
paper. Nonetheless, we hope that in the future more studies on additional
datasets, e.g., on other language editions of Wikipedia, are conducted in
order to enrich our understanding of human navigation and link success.

Explaining and modeling heterogeneity. While we have accounted for basic
heterogeneity by utilizing mixed-effects models and Markov chain models that
both model transitions given a current start article, more fine-grained
analyses in that direction are warranted in future. For example, there might
be specific user groups, positions within sessions, or specific times that
exhibit deviating navigation behavior. In this direction, a detailed analysis
of the random effects in the mixed-effects models might lead to better
understanding of heterogeneous effects. Additionally, pattern mining
approaches could be employed to detect interpretable subgroups of Markovian
transition behavior [28]. Obtained insights could then eventually be used to
further advance existing models by integrating mixtures of navigational
hypotheses into the modeling process [4].

##  8 Conclusions

In this paper, we studied what makes a link successful on Wikipedia. To that
end, (i) we investigated link features and their effects on link popularity
utilizing descriptive analyses supplemented by mixed-effects hurdle models.
Results suggest that Wikipedia users prefer to navigate to articles that are
in the periphery of the Wikipedia link network, to articles that are
semantically similar, and to articles that are linked at the top or at the
most left-hand side of the source article. (ii) Based on these findings, we
integrated hypotheses about human navigational behavior into the well-known
Markov chain model utilizing Bayesian inference. By doing so, we could improve
respective model fits compared to a uniform baseline model. (iii) For further
demonstrating the utility of our findings, we adapted the well-known PageRank
algorithm that assumes random navigation by accounting for observed
navigational preferences in a weighted variation. An evaluation of resulting
pagerank values obtained by link weighting against actual view statistics
revealed significant improvements over the unweighted baseline algorithm.

Our work is relevant for researchers interested in studying human navigational
behavior and link structures on the Web. Obtained insights can be utilized for
providing qualitative link structures and for supplementing existing
algorithms utilizing these structures to better adhere to observed transition
behavior. In addition to future work directions discussed in Section 7, we
also aim at extending our studies to different language versions of Wikipedia
and newer time frames for identifying similarities and differences. Also,
apart from Wikipedia, the provided methodological framework can be applied to
other platform data in a straight-forward manner.

Acknowledgments. We would like to thank Denis Helic for the inspiring
discussions on the PageRank section. This work was partially funded by the
Austrian Science Fund project "Navigability of Decentralized Information
Networks".

## References

  * [1] E. Agichtein, E. Brill, and S. Dumais.  Improving web search ranking by incorporating user behavior information.  In Int. Conference on Research and Development in Information Retrieval, 2006.
  * [2] G. D. Bader and C. W. Hogue.  An automated method for finding molecular complexes in large protein interaction networks.  BMC Bioinformatics, 4(1):1, 2003.
  * [3] D. Bates, M. Maechler, B. Bolker, S. Walker, et al.  lme4: Linear mixed-effects models using eigen and s4.  R Package Version, 1(7), 2014.
  * [4] M. Becker, F. Lemmerich, P. Singer, M. Strohmaier, and A. Hotho.  Mixedtrails: Bayesian hypotheses comparison on heterogeneous sequential data.  arXiv:1612.07612, 2016.
  * [5] F. Benevenuto, T. Rodrigues, M. Cha, and V. Almeida.  Characterizing user behavior in online social networks.  In Internet Measurement Conference, 2009.
  * [6] J. Borges and M. Levene.  Data mining of user navigation patterns.  In Web usage analysis and user profiling, pages 92–112. Springer, 2000.
  * [7] S. Brin and L. Page.  The anatomy of a large-scale hypertextual web search engine.[en línea].  Disponible en Web, 1998.
  * [8] R. E. Bucklin and C. Sismeiro.  A model of web site browsing behavior estimated on clickstream data.  Journal of Marketing Research, 40(3):249–267, 2003.
  * [9] R. E. Bucklin and C. Sismeiro.  Click here for internet insight: Advances in clickstream data analysis in marketing.  Journal of Interactive Marketing, 23(1):35–48, 2009.
  * [10] G. Buscher, E. Cutrell, and M. R. Morris.  What do you see when you’re surfing?: using eye tracking to predict salient regions of web pages.  In Conference on Human Factors in Computing Systems, 2009.
  * [11] P. Chatterjee, D. L. Hoffman, and T. P. Novak.  Modeling the clickstream: Implications for web-based advertising efforts.  Marketing Science, 22(4):520–541, 2003.
  * [12] J. A. Dean, C. Anderson, and A. Battle.  Ranking documents based on user behavior and/or feature data, 2010.  US Patent 7,716,225.
  * [13] D. Dimitrov, P. Singer, D. Helic, and M. Strohmaier.  The role of structural information for designing navigational user interfaces.  In Conference on Hypertext and Social Media, 2015.
  * [14] D. Dimitrov, P. Singer, F. Lemmerich, and M. Strohmaier.  Visual positions of links and clicks on wikipedia.  In Int. Conference Companion on World Wide Web, 2016.
  * [15] X. A. Harrison.  Using observation-level random effects to model overdispersion in count data in ecology and evolution.  PeerJ, 2:e616, 2014.
  * [16] M. Hearst.  Search user interfaces.  Cambridge University Press, 2009.
  * [17] D. Helic, M. Strohmaier, M. Granitzer, and R. Scherer.  Models of human navigation in information networks based on decentralized search.  In Conference on Hypertext and Social Media, 2013.
  * [18] J. J. Hox, M. Moerbeek, and R. van de Schoot.  Multilevel analysis: Techniques and applications.  Routledge, 2010.
  * [19] M.-C. Hu, M. Pavlicova, and E. V. Nunes.  Zero-inflated and hurdle models of count data with extra zeros: examples from an hiv-risk reduction intervention trial.  The American Journal of Drug and Alcohol Abuse, 37(5):367–375, 2011\.
  * [20] B. A. Huberman, P. L. Pirolli, J. E. Pitkow, and R. M. Lukose.  Strong regularities in world wide web surfing.  Science, 280(5360):95–97, 1998.
  * [21] T. Joachims.  Optimizing search engines using clickthrough data.  In Int. Conference on Knowledge Discovery and Data Mining, 2002\.
  * [22] T. Joachims.  Evaluating retrieval performance using clickthrough data.  Technical report, Cornell University, 2003.
  * [23] S. Jung, J. L. Herlocker, and J. Webster.  Click data as implicit relevance feedback in web search.  Information Processing & Management, 43(3):791–807, 2007.
  * [24] R. E. Kass and A. E. Raftery.  Bayes factors.  Journal of the American Statistical Association, 90(430):773–795, 1995.
  * [25] J. M. Kleinberg.  Navigation in a small world.  Nature, 406(6798):845–845, 2000.
  * [26] K. Kristensen, A. Nielsen, C. W. Berg, H. Skaug, and B. Bell.  Tmb: automatic differentiation and laplace approximation.  arXiv:1509.00660, 2015.
  * [27] D. Lamprecht, K. Lerman, D. Helic, and M. Strohmaier.  How the structure of wikipedia articles influences user navigation.  New Review of Hypermedia and Multimedia, pages 1–22, 2016.
  * [28] F. Lemmerich, M. Becker, P. Singer, D. Helic, A. Hotho, and M. Strohmaier.  Mining subgroups with exceptional transition behavior.  In Int. Conference on Knowledge Discovery and Data Mining, 2016\.
  * [29] A. L. Montgomery, S. Li, K. Srinivasan, and J. C. Liechty.  Modeling online browsing and path analysis using clickstream data.  Marketing Science, 23(4):579–595, 2004.
  * [30] J. Nielsen.  F-shaped pattern for reading web content.  https://www.nngroup.com/articles/f-shaped-pattern-reading-web-content.  Accessed: 2016-07-12.
  * [31] L. Page, S. Brin, R. Motwani, and T. Winograd.  The pagerank citation ranking: bringing order to the web.  Stanford InfoLab, 1999.
  * [32] A. Paranjape, R. West, L. Zia, and J. Leskovec.  Improving website hyperlink structure using server logs.  In Int. Conference on Web Search and Data Mining, 2016.
  * [33] J. Pinheiro and D. Bates.  Mixed-effects models in S and S-PLUS.  Springer Science & Business Media, 2006.
  * [34] P. Pirolli.  Information foraging theory: Adaptive interaction with information.  Oxford University Press, 2007.
  * [35] P. L. Pirolli and J. E. Pitkow.  Distributions of Surfers’ Paths through the World Wide Web: Empirical Characterizations.  World Wide Web, 2(1-2):29–45, 1999.
  * [36] A. T. Scaria, R. M. Philip, R. West, and J. Leskovec.  The last click: Why users give up information network navigation.  In Int. Conference on Web Search and Data Mining, 2014.
  * [37] P. Singer, D. Helic, A. Hotho, and M. Strohmaier.  Hyptrails: A bayesian approach for comparing hypotheses about human trails on the web.  In Int. Conference on World Wide Web, 2015.
  * [38] P. Singer, D. Helic, B. Taraghi, and M. Strohmaier.  Detecting memory and structure in human navigation patterns using markov chain models of varying order.  PloS One, 9(7):e102070, 2014.
  * [39] P. Singer, T. Niebler, M. Strohmaier, and A. Hotho.  Computing semantic relatedness from human navigational paths on wikipedia.  In Int. Conference on World Wide Web, 2013.
  * [40] J. H. Steiger.  Tests for comparing elements of a correlation matrix.  Psychological Bulletin, 87(2):245, 1980.
  * [41] G. Wang, T. Konolige, C. Wilson, X. Wang, H. Zheng, and B. Y. Zhao.  You are how you click: Clickstream analysis for sybil detection.  In USENIX Security Symposium, volume 9, pages 1–008, 2013.
  * [42] Y. Wang, W. Dai, and Y. Yuan.  Website browsing aid: A navigation graph-based recommendation system.  Decision Support Systems, 45(3):387–400, 2008.
  * [43] R. West and J. Leskovec.  Human wayfinding in information networks.  In Int. Conference on World Wide Web, 2012.
  * [44] R. West, A. Paranjape, and J. Leskovec.  Mining missing hyperlinks from human navigation traces: A case study of wikipedia.  In Int. Conference on World Wide Web, 2015.
  * [45] R. West, J. Pineau, and D. Precup.  Wikispeedia: An online game for inferring semantic distances between concepts.  In Int. Joint Conference on Artificial Intelligence, 2009.
  * [46] E. Wulczyn and D. Taraborelli.  Wikipedia clickstream. figshare.  doi:10.6084/m9.figshare.1305770.  Accessed: 2015-12-13.
  * [47] G.-R. Xue, H.-J. Zeng, Z. Chen, Y. Yu, W.-Y. Ma, W. Xi, and W. Fan.  Optimizing web search using web click-through data.  In Int. Conference on Information and Knowledge Management, 2004\.