# Realization of zero-divisor graphs of finite commutative rings as threshold
graphs

Rameez Raja1 and Samir Ahmad Wagay2††,2Department of Mathematics, National
Institute of Technology Srinagar, Jammu and Kashmir, India. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author:1

###### Abstract

Let $R$ be a finite commutative ring with unity, and let $G=(V,E)$ be a simple
graph. The zero-divisor graph, denoted by $\Gamma(R)$ is a simple graph with
vertex set as $R$, and two vertices $x,y\in R$ are adjacent in $\Gamma(R)$ if
and only if $xy=0$. In [10], the authors have studied the Laplacian
eigenvalues of the graph $\Gamma(\mathbb{Z}_{n})$ and for distinct proper
divisors $d_{1},d_{2},\cdots,d_{k}$ of $n$, they defined the sets as,
$\mathcal{A}_{d_{i}}=\\{x\in\mathbb{Z}_{n}:(x,n)=d_{i}\\}$, where $(x,n)$
denotes the greatest common divisor of $x$ and $n$. In this paper, we show
that the sets $\mathcal{A}_{d_{i}}$, $1\leq i\leq k$ are actually orbits of
the group action: $Aut(\Gamma(R))\times R\longrightarrow R$, where
$Aut(\Gamma(R))$ denotes the automorphism group of $\Gamma(R)$. Our main
objective is to determine new classes of threshold graphs, since these graphs
play an important role in several applied areas. For a reduced ring $R$, we
prove that $\Gamma(R)$ is a connected threshold graph if and only if
$R\cong{F}_{q}$ or $R\cong{F}_{2}\times{F}_{q}$. We provide classes of
threshold graphs realized by some classes of local rings. Finally, we
characterize all finite commutative rings with unity of which zero-divisor
graphs are not threshold.

Keywords: Group action, orbits, zero-divisor, zero-divisor graph, threshold
graph.

2020 AMS Classification Code: 13A70, 05C25, 05C50.

##  1 Introduction

The zero-divisor graph of a commutative ring $R$ with unity was introduced by
Beck [3]. The graph $\Gamma(R)$ is defined to be the graph with vertex set as
$R$, and two distinct vertices $x,y\in R$ are adjacent in $\Gamma(R)$ if and
only if $xy=0$ in $R$. The notion of zero-divisor graphs was further studied
by Anderson and Livingston in [1], who restricted vertices of the graph
$\Gamma(R)$ to non-zero zero-divisors of the ring $R$. The main objective of
the investigation of associating a graph to $R$ is to study the interplay of
graph theoretic properties of $\Gamma(R)$ and ring theoretic properties of
$R$. This interplay between different properties of $R$ and $\Gamma(R)$ was
thoroughly investigated in [4, 11, 12, 13, 14]. For basic definitions from
graph theory, we refer to [10], and for ring theory we refer to [8].

A vertex in a graph $G$ is called dominating if it is adjacent to every other
vertex of $G$. A graph $\mathbf{G}$ is called a threshold graph if it is
obtained by the following procedure.

Start with $K_{1}$, a single vertex, and use any of the following steps, in
any order, an arbitrary number of times.
(i) Add an isolated vertex.
(ii) Add a dominating vertex, that is, add a new vertex and make it adjacent
to each existing vertex. The family of threshold graphs represent an important
class of simple graphs.

The concept of threshold graphs was first established by the authors Chvátal
and Hammer in [6] and Henderson and Zalcstein in [7]. There are many different
generalizations of threshold graphs. These graphs can be viewed as special
cases of some wider classes of graphs like cographs, split graphs and interval
graphs.

By the definition of Beck’s zero-divisor graph $\Gamma(R)$, it appears that
the vertex $0$ in $\Gamma(R)$ is adjacent to every other vertex of
$\Gamma(R)$. Therefore, $\Gamma(R)$ is a simple connected graph, that is,
$\Gamma(R)$ is without parallel edges and self loops. The distance between any
two vertices in $\Gamma(R)$ is at least $1$, which is the minimum eccentricity
of $\Gamma(R)$ and at most $2$, which is the maximum eccentricity of
$\Gamma(R)$.

A graph $G=(V,E)$ is said to be complete if every pair of distinct vertices of
$G$ are adjacent in $G$. Recall that a clique of $G$ is a complete subgraph of
$G$. A subset $S$ of a vertex set of $G$ is said to be an independent set if
no two members of $S$ are adjacent in $G$. A graph $G$ is said to be bipartite
if $V$ can be partitioned into non-empty subsets $V_{1}$ and $V_{2}$ such that
each edge of $G$ has one end in $V_{1}$ and other in $V_{2}$. A bipartite
graph is said to be complete if every element of $V_{1}$ is adjacent to every
element of $V_{2}$. A complete bipartite is called a star graph if either
$|V_{1}|=1$ or $|V_{2}|=1$. If $R\cong{F}_{q}$, where ${F}_{q}$ is a finite
field, then it is easy verify that $\Gamma(R)$ is a star graph

An element $r\in R$ is said to be nilpotent if $r^{n}=0$, for some
$n\in\mathbb{Z}_{>0}$. A ring $R$ is called reduced if it has no non-zero
nilpotent element and it is called local if $R$ has a unique maximal ideal.

This research article is organised as follows. In Section 2, we present some
preliminary information related to the zero-divisor graph
$\Gamma(\mathbb{Z}_{n})$. For $R\cong\mathbb{Z}_{p^{\alpha}}$, we show that
the sets $\mathcal{A}_{d_{i}}=\\{x\in\mathbb{Z}_{n}:(x,n)=d_{i}\\}$ defined in
[10] are actually orbits of the group action $Aut(\Gamma(R))\times
R\longrightarrow R$. In Section $3$, we show that for a reduced ring $R$,
$\Gamma(R)$ is a connected threshold graph if and only if $R\cong{F}_{q}$ or
$R\cong{F}_{2}\times{F}_{q}$. We discuss classes of threshold graphs realized
by some classes of local rings and finally we characterize all finite
commutative rings of which zero-divisor graphs are not threshold.

##  2 Preliminaries

It is always interesting to determine new classes of threshold graphs, since a
threshold graph $\mathbf{G}$ with $n$ vertices can be represented by a binary
code of the type $b=(b_{1}b_{2}\cdots
b_{n})=0^{s_{1}}1^{t_{1}}0^{s_{2}}1^{t_{2}}\cdots 0^{s_{k}}1^{t_{k}}$, where
$s_{i}~{}~{}and~{}~{}t_{i}$ are positive integers for all $1\leq i\leq k$. In
the binary code $b$, $b_{i}=0$ if a vertex $v_{i}$ is added as an isolated
vertex in $\mathbf{G}$ and $b_{i}=1$ if $v_{i}$ is added as a dominating
vertex in $\mathbf{G}$. These codes realized by some class of graphs
(threshold graphs) are known as the creation sequences of these graphs.

We partition the vertex set $V$ of $\mathbf{G}$ as $V_{1},V_{2},\cdots,V_{k}$.
The equivalent form of an equitable partition matrix $\mathcal{M}=(a_{ij})$ of
$\mathbf{G}$ is defined as,

$a_{ij}=\begin{cases}|V_{i}|-1&\text{ if }i=j\mbox{
and}~{}V_{i}~{}\mbox{induces a complete subgraph in}~{}\mathbf{G},\\\
|V_{j}|&\text{if }\mbox{there exists}~{}v_{i}\in V_{i}~{}\mbox{and}~{}v_{j}\in
V_{j}~{}\mbox{such that}~{}v_{i}~{}\mbox{is adjacent to}~{}v_{j},\\\
0&\text{otherwise.}\end{cases}$ (1)

The following example illustrates the equitable partition matrix of a
threshold graph.

Let $\mathbf{G}$ be a threshold graph of order $10$ represented by a binary
code $b=(0000111001)=0^{4}1^{3}0^{2}1$ as shown in the Figure 1. Then the
equitable partition matrix of $\mathbf{G}$ is,

$\mathcal{M}=\begin{pmatrix}0&3&0&1\\\ 4&2&0&1\\\ 0&0&0&1\\\
4&3&2&0\end{pmatrix}$

Figure 1: Threshold graph (0000111001)

The multiplicities of eigenvalues $0$ and $-1$ are $4$ and $2$, which can be
verified from [2]. The remaining eigenvalues of $\mathbf{G}$ can be computed
from the equitable partition matrix defined in (1). In fact, the remaining
eigenvalues of $\mathbf{G}$ are roots of the characteristic polynomial
$x^{4}-2x^{3}-21x^{2}-12x+24$.

Thus constructing some new classes of threshold graphs provides us a way of
developing some new binary codes from graphs and a theory which involves
spectral analysis related to graphs.

Recall that the graph obtained from the union of two graphs $G_{1}$ and
$G_{2}$ by adding new edges from each vertex of $G_{1}$ to every vertex of
$G_{2}$ is called join of $G_{1}$ and $G_{2}$, denoted by $G_{1}\vee G_{2}$.
The generalised join graph which is also called generalised composition graph
in [15] is defined as follows.

######  Definition 1.

Let $G$ be a graph with vertex set $V(G)=\\{v_{1},v_{2},\cdots,v_{k}\\}$, and
let $G_{1},G_{2},\cdots,G_{k}$ be $k$ pairwise disjoint graphs. The
$G-$generalized join graph $G_{\vee}=[G_{1},G_{2},\cdots,G_{k}]$ of
$G_{1},G_{2},\cdots,G_{k}$ is the graph obtained by replacing each vertex
$v_{i}$ of $G$ with the graph $G_{i}$ and two vertices $G_{i}$ and $G_{j}$ are
adjacent in $G_{\vee}$ if and only if every vertex $v_{i}$ of $G_{i}$ is
adjacent to every vertex $v_{j}$ of $G_{j}$ in $G$.

Let $Aut(G)$ denotes the automorphism group of a graph $G$, consider the group
action $Aut(G)\\\ ~{}acting~{}on~{}V(G)$ by some permutation of $Aut(G)$, that
is, $Aut(G)\times V(G)\rightarrow V(G)$ is given as, $\sigma(v)=u$, where
$\sigma\in Aut(G)$ and $v,u\in V(G)$ are any two vertices of $G$.

The graph $\Gamma(\mathbb{Z}_{n})$ is simple and its vertices are all elements
of the ring $\mathbb{Z}_{n}$ and two distinct vertices are adjacent in
$\Gamma(\mathbb{Z}_{n})$ if and only if there product is zero in
$\mathbb{Z}_{n}$. The canonical decomposition of $n$ is
$p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{r}^{n_{r}}$ and total number of divisors
of $n$ is $\prod\limits_{i=1}^{r}(n_{i}+1)$.

The authors in [10] defined $\Upsilon_{n}$ as a simple graph whose vertices
are the proper divisors of $n$, and two distinct vertices $d_{i}$ and $d_{j}$
are adjacent in $\Upsilon_{n}$ if and only if $d_{i}d_{j}$ is a multiple of
$n$. Thus, $V(\Upsilon_{n})=\\{d_{1},d_{2},\cdots,d_{r}\\}$ and
$E(\Upsilon_{n})=\\{(d_{i},d_{j}):d_{i}d_{j}\equiv 0(mod~{}n)\\}$.

Let $n=p^{\alpha}$, where $p$ is a prime number and $\alpha\geq 1$. If
$R\cong\mathbb{Z}_{p^{\alpha}}$, then orbits of the group action
$Aut(\Gamma(R))\times R\longrightarrow R$ are given as,
$\mathcal{O}_{\alpha,p^{i}}=\\{p^{i}b(\bmod~{}p^{\alpha})\mid
b\in\mathbb{Z},(b,p)=1\\}$, $\mathcal{O}_{\alpha,p^{i}}$ is the $p^{i}$-th
orbit of $R$, where $i\in[0,\alpha-1]$.

For $0\leq i<j\leq\alpha-1$, $p^{i}b\equiv
p^{j}b^{\prime}(\bmod~{}p^{\alpha}),\text{ where }(b,p)=1\text{ and
}(b^{\prime},p)=1$. Therefore, $p^{(j-i)}b^{\prime}\equiv
b(\bmod~{}p^{(\alpha-i)}),$ which is a contradiction. Thus, for $i\neq j$,
$\mathcal{O}_{\alpha,p^{i}}\cap\mathcal{O}_{\alpha,p^{j}}=\emptyset$.

Any element $a\in\mathbb{Z}_{p^{\alpha}}$ can be expressed as,

$a\equiv
p^{\alpha-1}b_{1}+p^{\alpha-2}b_{2}+\cdots+pb_{\alpha-1}+b_{\alpha}(\bmod~{}p^{\alpha}),$

where $b_{i}\in[0,p-1].$ If $a\in\mathcal{O}_{\alpha,1}$, then $b_{\alpha}\neq
0.$ So, $|\mathcal{O}_{\alpha,1}|=p^{\alpha-1}(p-1)=\phi(p^{\alpha})$. If
$a^{\prime}\in\mathcal{O}_{\alpha,p}$, then for some
$a\in\mathcal{O}_{\alpha,1}$, $a^{\prime}=pa$, that is, $b_{\alpha}\neq 0$, so
$|\mathcal{O}_{\alpha,p}|=\phi(\frac{p^{\alpha}}{p})$. Similarly, for
$i\in[0,\alpha-1]$, we have
$|\mathcal{O}_{\alpha,p^{i}}|=\phi(\frac{p^{\alpha}}{p^{i}})$ and
$\mathcal{O}_{\alpha,p^{\alpha}}=\\{0\\}$. It follows that the size of the
sets $\mathcal{O}_{\alpha,p^{i}}=\phi(\frac{p^{\alpha}}{p^{i}})$ for
$i\in[0,\alpha]$. Therefore, total number of elements in all the sets
$\mathcal{O}_{\alpha,p^{i}}=\sum\limits_{i=0}^{\alpha}\phi(\frac{p^{\alpha}}{p^{i}})=|\mathbb{Z}_{p^{\alpha}}|={p^{\alpha}}$

Note that $1,p,\cdots,p^{\alpha}$ are the representatives of orbits
$\mathcal{O}_{\alpha,1},\mathcal{O}_{\alpha,p},\cdots,\mathcal{O}_{\alpha,p^{\alpha}}$
and divisors of the order of $R$. It follows that the vertices of the graph
$\Upsilon_{n}$ are elements of sets
$\mathcal{O}_{\alpha,p},\cdots,\mathcal{O}_{\alpha,p^{\alpha-1}}$. Moreover,
by definition of the graph $\Gamma(R)$, an element $0$ of $R$ is adjacent to
all vertices in $\Gamma(R)$, elements of the orbit $\mathcal{O}_{\alpha,1}$
are adjacent to $0$ only in $\Gamma(R)$. Also, elements of the orbit
$\mathcal{O}_{\alpha,p}$ are adjacent to $0$ and elements of the orbit
$\mathcal{O}_{\alpha,p^{\alpha-1}}$. The elements of the orbit
$\mathcal{O}_{\alpha,p^{2}}$ are adjacent to $0$ and elements of orbits
$\mathcal{O}_{\alpha,p^{\alpha-1}}$, $\mathcal{O}_{\alpha,p^{\alpha-2}}$.
This, for $k\geq 1$, elements of the orbit $\mathcal{O}_{\alpha,p^{k}}$ are
adjacent to $0$ and elements of orbits $\mathcal{O}_{\alpha,p^{\alpha-k}}$,
$\mathcal{O}_{\alpha,p^{\alpha-k+1}},\cdots,\mathcal{O}_{\alpha,p^{\alpha-1}}$.

Thus, the graph $\Upsilon_{n}$ can be obtained as a subgraph of $\Gamma(R)$
with vertices as elements of orbits
$\mathcal{O}_{\alpha,p},\cdots,\mathcal{O}_{\alpha,p^{\alpha-1}}$, and two
vertices $x$ and $y$ are adjacent in $\Upsilon_{n}$ if and only $xy=0$.

There is an advantage for knowing the orbits of this group action
$Aut(\Gamma(R))\times R\rightarrow R$, since we get some structural
information about some elements of $R$ from $\Gamma(R)$. As a consequence, we
do not consider all elements of $R$ to decode the symmetry of $\Gamma(R)$. We
explore this information to reveal some interesting spectral properties of
$\Gamma(R)$.

From the structure of $\Gamma(R)$, the subgraphs induced by elements of orbits
$\bigcup\limits_{i=0}^{k-1}\mathcal{O}_{\alpha,p^{i}}$, are independent parts
in $\Gamma(R)$, whereas the subgraphs induced by elements of orbits
$\bigcup\limits_{j=0}^{k-1}\mathcal{O}_{\alpha,p^{k+j}}$ are cliques in
$\Gamma(R)$. Also the orbit $\mathcal{O}_{\alpha,p^{\alpha}}=\\{0\\}$ is
connected to every element of $\Gamma(R)$. The following Lemma shows adjacency
of vertices in $\Gamma(\mathbb{Z}_{p^{\alpha}})$.

######  Lemma 2.

For $i,j\in\\{0,1,\cdots,\alpha-1\\}$, two vertices
$x\in\mathcal{O}_{\alpha,p^{i}}$, $y\in\mathcal{O}_{\alpha,p^{j}}$ of
$\Gamma(R)$ are adjacent in $\Gamma(R)$ if and only if $i+j\geq\alpha$.

######  Proof 1.

Since $x\in\mathcal{O}_{\alpha,p^{i}}$ and $y\in\mathcal{O}_{\alpha,p^{j}}$,
therefore, $x=p^{i}b$ and $y=p^{j}b^{\prime}$ for some integers $b$ and
$b^{\prime}$ with $(p,b)=(p,b^{\prime})=1$. The vertices $x$ and $y$ are
adjacent in $\Gamma(R)$ if and only if $p^{\alpha}$ divides $xy$. This implies
$x$ and $y$ are adjacent in $\Gamma(R)$ if and only if $i+j\geq\alpha$.

######  Lemma 3.

Let $\Gamma(R)$ be the graph realized by $R\cong\mathbb{Z}_{p^{\alpha}}$. Then
the induced subgraph $\Gamma(\mathcal{O}_{\alpha,p^{i}})$ of $\Gamma(R)$ on
the vertex set $\mathcal{O}_{\alpha,p^{i}}$ for
$i\in\\{0,1,2,\cdots,\alpha-1\\}$ is either the complete graph
$K_{\phi(\frac{p^{\alpha}}{p^{i}})}$ or its complement graph
$\overline{K}_{\phi(\frac{p^{\alpha}}{p^{i}})}$. Furthermore, for $\alpha=2k$
or $2k-1$,
$\Gamma(\mathcal{O}_{\alpha,p^{i}})=K_{\phi(\frac{p^{\alpha}}{p^{i}})}$ if and
only if $i\geq k$ and $\Gamma(\mathcal{O}_{\alpha,p^{\alpha}})=K_{1}$.

######  Proof 2.

The subgraph $\Gamma(\mathcal{O}_{\alpha,p^{i}})$ has
$\phi(\frac{p^{\alpha}}{p^{i}})$ vertices for $i\in[0,\alpha]$. By taking
$i=j$ in Lemma (1), we get the result.

######  Observation 2.1.

If $\Gamma(\mathcal{O}_{\alpha,p^{i}})$ is the induced subgraph of $\Gamma(R)$
on vertices $\mathcal{O}_{\alpha,p^{i}}$ for $i\in\\{0,1,2,\cdots,\alpha\\}$,
then
$\Gamma(R)_{\vee}=[\Gamma(\mathcal{O}_{\alpha,1}),\Gamma(\mathcal{O}_{\alpha,p}),\cdots,\Gamma(\mathcal{O}_{\alpha,p^{\alpha}})]$.

######  Proof 3.

Proof follows from the adjacency relations in $\Gamma(R)$, since orbits are
adjacent in $\Gamma(R)_{\vee}$ if and only if their representatives are
adjacent in $\Gamma(R)$.

We conclude this section with the following example which illustrates the
zero-divisor graph realized by $\mathbb{Z}_{3^{3}}$ with its orbits.

######  Example 4.

Let $R=\mathbb{Z}_{3^{3}}$. Consider the group action
$Aut(\Gamma(\mathbb{Z}_{3^{3}}))\times\mathbb{Z}_{3^{3}}\rightarrow\mathbb{Z}_{3^{3}}$.
The orbits of this action are: $\mathcal{O}_{3,1}=\\{1,2,4,\cdots,25,26\\}$,
$\mathcal{O}_{3,3}=\\{3,6,12,15,21,24\\}$, $\mathcal{O}_{3,3^{2}}=\\{9,18\\}$
and $\mathcal{O}_{3,3^{3}}=\\{0\\}$. Therefore, by observation (2.1),

$\Gamma(\mathbb{Z}_{3^{3}})_{\vee}=[\Gamma(\mathcal{O}_{3,1}),\Gamma(\mathcal{O}_{3,3}),\Gamma(\mathcal{O}_{3,3^{2}}),\Gamma(\mathcal{O}_{3,3^{3}})],$

where $\Gamma(\mathcal{O}_{3,1})=\overline{K}_{18}$,
$\Gamma(\mathcal{O}_{3,3})=\overline{K}_{6}$,
$\Gamma(\mathcal{O}_{3,3^{2}})={K}_{2}$, and
$\Gamma(\mathcal{O}_{3,3^{3}})={K}_{1}$ as shown in the Figure 2.

Figure 2: Generalised join graph $\Gamma(\mathbb{Z}_{3^{3}})_{\vee}$

##  3 Threshold graphs realized by reduced, local and mixed rings

The Artinian decomposition of $R=R_{1}\times\cdots\times
R_{r}\times{F}_{1}\times\cdots\times{F}_{s}$, where each $R_{i}$ is a finite
commutative local ring with unity and ${F}_{j}$ is a field, $1\leq i\leq r$
and $1\leq j\leq s$. A ring $R$ is said to be product of local rings if $s=0$
and $r\geq 2$. A ring $R$ is said to be a mixed ring if $r\geq 1$ and $s\geq
1$. A ring $R$ is said to be a reduced ring if $r=0$ and $s\geq 1$.

This section is dedicated to study the realization of zero-divisor graphs as
threshold graphs for reduced rings, product of local rings and mixed rings.

An alternating $4-cycle$ of a graph ${G}=(V,E)$ is a configuration consisting
of four distinct vertices $a,b,c,d$ such that $(a,b),(c,d)\in E$ and
$(a,c),(b,d)\notin E$. By considering the presence or absence of edges $(a,d)$
and $(b,c)$, we see that the vertices of an alternating $4$-cycle induce a
path $P_{4}$, a cycle $C_{4}$, or a matching $2K_{2}$.

Since threshold graphs has been characterised by many ways. One of the
characterizations of a threshold graph [[9], Theorem 1.2.4] is presented in
the following result.

######  Theorem 5.

For a graph ${G}=(V,E),$ the following are equivalent,
1\. ${G}$ is a threshold graph,
2\. ${G}$ does not have an alternating $4-cycle$.

Let $R\cong{F}_{q_{1}}\times{F}_{q_{2}}\times\cdots\times{F}_{q_{n}}$ be a
reduced ring. In the following characterization, we discuss the realization of
$\Gamma(R)$ as a threshold graph.

######  Theorem 6.

Let $R\cong\mathbb{F}_{q_{1}}\times{F}_{q_{2}}\times\cdots\times{F}_{q_{n}}$.
Then $\Gamma(R)$ is a connected threshold graph if and only if
$R\cong{F}_{q_{i}}$, or $R\cong{F}_{q_{i}}\times{F}_{q_{j}}$, where
${F}_{q_{i}}\cong\mathbb{Z}_{2}$ for any $i,j\in\\{1,2,\cdots,n\\}$.

######  Proof 4.

Let $R$ be a ring such that $R\cong{F}_{q_{i}}$ for some
$i\in\\{1,2,\cdots,n\\}$. Then $\Gamma(R)$ is a complete bipartite graph
isomorphic to $K_{1,q_{i}-1}$. This implies, $\Gamma(R)$ is a star graph. So,
$\Gamma(R)$ is a connected threshold graph.

Let $R$ be a ring such that $R\cong{F}_{q_{i}}\times{F}_{q_{j}}$ for some
$i,j\in\\{1,2,\cdots,n\\}$ with ${F}_{q_{i}}\cong\mathbb{Z}_{2}$. Then
$|V(\Gamma(R))|=2{q_{i}}$. Let $V(\Gamma(R))=X\bigcup Y$, where $X$ represents
the independent part of the graph whose vertices are of the form $(0,a_{k})$
and $(1,a_{k})$, $k\in\\{1,2,\cdots,{q_{j}-1}\\}$. The set $Y$ represents
complete part of the graph which consists of only two vertices $(1,0)$ and
$(0,0)$.

To prove $\Gamma(R)$ is threshold, it is suffices to show that $\Gamma(R)$
does not contain an alternating $4$-cycle, that is, the graph $\Gamma(R)$ has
no induced subgraph of four vertices isomorphic to $P_{4}$, $C_{4}$ or
$2K_{2}$.

Let $a,b,c,d$ be any four distinct vertices of $\Gamma(R)$. We consider the
following cases.
Case - 1. If $a,b,c,d\in X$, then they are all isolated vertices. This
implies, $\Gamma(R)$ has no alternating $4$-cycle. Therefore, the result
follows.
Case - 2. If $a,b,c\in X$ and $d\in Y$, then the only possibilities are as
follows,

cdabcdabcdabcdab

but none of them is isomorphic to $P_{4}$, $C_{4}$ or $2K_{2}$. Therefore,
$\Gamma(R)$ is a connected threshold graph.

Case - 3. If $a,b\in X$ and $c,d\in Y$, where $c=(1,0)$ and $d=(0,0)$. By
definition, the vertex $(0,0)$ is adjacent to three other vertices.
Consequently, no two disjoint edges exists and therefore no alternating
$4-cycle$ is possible. Thus, $\Gamma(R)$ is threshold.

Conversely, suppose that $\Gamma(R)$ is a connected threshold graph, we show
that $R\cong{F}_{q_{i}}$, or $R\cong{F}_{q_{i}}\times{F}_{q_{j}}$, where
${F}_{q_{i}}\cong\mathbb{Z}_{2}$ for any $i,j\in\\{1,2,\cdots,n\\}$. We
consider the following cases.

Case - 1. Suppose $R\cong{F}_{q_{1}}\times{F}_{q_{2}}$, $2<q_{1}\leq q_{2}$.
Then, $|V(\Gamma(R))|=q_{1}q_{2}$. Since $(a,b),(a,c),(c,d),\\\ (b,d)\in
E(\Gamma(R))$, where $a=(1,0),b=(0,y),c=(0,1)$ and $d=(x,0)$,
$x\in{F}_{q_{1}}\setminus\\{0,1\\}$, $y\in{F}_{q_{2}}\setminus\\{0,1\\}$. This
implies, $\Gamma(R)$ has an induced subgraph of order $4$ isomorphic to
$C_{4}$, a contradiction. Thus, $R\ncong{F}_{q_{1}}\times{F}_{q_{2}}$,
$2<q_{1}\leq q_{2}$.

Case - 2. Suppose
$R\cong{F}_{q_{1}}\times{F}_{q_{2}}\times\cdots\times{F}_{q_{n}}$ with
$q_{1}\leq q_{2}\leq\cdots\leq q_{n}$ and $n\geq 3$. Then, $\Gamma(R)$ always
contains an induced subgraph of the form
$P_{4}=(1,0,1,0,\cdots,0)\sim(0,1,0,0,\cdots,0)\sim(1,0,0,0,\cdots,0)\sim(0,1,1,0,\cdots,0)$,
or $2K_{2}=\\{(1,0,1,0,\cdots,0)\sim(0,1,0,1,\cdots,0)$,
$(0,1,1,0,\cdots,0)\\\ \sim(1,0,0,1,\cdots,0)\\}$ or
$C_{4}=(a,b),(a,c),(c,d),(b,d)$, where
$a=(1,0,0,\cdots,0),b=(0,y,0,\cdots,0),c=(0,1,0,\cdots,0)$ and
$d=(x,0,0,\cdots,0)$, $x\in{F}_{q_{1}}\setminus\\{0,1\\}$,
$y\in{F}_{q_{2}}\setminus\\{0,1\\}$, a contradiction. This implies,
$R\neq{F}_{q_{1}}\times{F}_{q_{2}}\times\cdots\times{F}_{q_{n}}$, for
$q_{1}\leq q_{2}\leq\cdots\leq q_{n}$.

Therefore, $\Gamma(R)$ fails to be threshold for cases $1$ and $2$. We
conclude that either $R\cong{F}_{q_{i}}$ or
$R\cong{F}_{q_{i}}\times{F}_{q_{j}}$.

Now, we consider the case of local rings. We show that if $R$ is a local ring,
then $\Gamma(R)$ is not always a threshold graph. Let
$R\cong\mathbb{Z}_{8}[x]/(x^{2},2x),\mathbb{Z}_{2}[x]/(x^{3},2x^{2},2x)$ or
$\mathbb{Z}_{2}[x,y]/(x^{3},xy,y^{2})$. Then the zero-divisor graph realized
by $\mathbb{Z}_{8}[x]/(x^{2},2x)$ is shown in the Figure 3. If we relabel the
vertices of $\Gamma(\mathbb{Z}_{8}[x]/(x^{2},2x))$ by elements of rings
$\mathbb{Z}_{2}[x]/(x^{3},2x^{2},2x)$ and
$\mathbb{Z}_{2}[x,y]/(x^{3},xy,y^{2})$, then we obtain isomorphic copies of
$\Gamma(\mathbb{Z}_{8}[x]/(x^{2},2x))$ as zero-divisor graphs of
$\mathbb{Z}_{2}[x]/(x^{3},2x^{2},2x)$ and
$\mathbb{Z}_{2}[x,y]/(x^{3},xy,y^{2})$. It can be easily verified from the
Figure 3, that $\Gamma\big{(}\mathbb{Z}_{8}[x]/(x^{2},2x)\big{)}$ is a
threshold graph.

Figure 3: $\Gamma\big{(}\mathbb{Z}_{8}[x]/(x^{2},2x)\big{)}$

.

On the other hand, if
$R\cong\mathbb{Z}_{4}[x]/(x^{2}),\mathbb{Z}_{2}[x,y]/(x^{2},y^{2})$ or
$\mathbb{Z}_{4}[x,y]/(x^{2},y^{2},xy-2,2x,2y)$, then the graph realized by
these rings are isomorphic to each other. The graph realized by the ring
$\mathbb{Z}_{4}[x]/(x^{2})\big{)}$ is shown in the Figure 4. The graph
$\Gamma\big{(}\mathbb{Z}_{4}[x]/(x^{2})\big{)}$ fails to be threshold, since
it contains an induced subgraph isomorphic to $2K_{2}$, that is the edges
$(x,3x)$ and $(2,2+2x)$ are disjoint in
$\Gamma\big{(}\mathbb{Z}_{4}[x]/(x^{2})\big{)}$.

01+3x1+2x1+x12+x2+3x2xx3x2+2x233+x3+2x3+3x Figure 4:
$\Gamma\big{(}\mathbb{Z}_{4}[x]/(x^{2})\big{)}$

Thus from preceding examples it is hard to characterize local rings such that
their zero-divisor graphs are threshold. Below, we present some classes of
local rings of which associated zero-divisor graphs are threshold.

######  Theorem 7.

For each prime $p$ and positive integer $\alpha$, the zero-divisor graph
realized by the ring $\mathbb{Z}_{p^{\alpha}}[x]/(x^{2},px)$ is a connected
threshold graph.

######  Proof 5.

Let $R\cong\mathbb{Z}_{p^{\alpha}}[x]/(x^{2},px)$. Then orbits of the group
action $Aut(\Gamma(R))\times R\longrightarrow R$ are as follows,

$\mathcal{O}_{\alpha,p^{i}}=\\{p^{i}a+bx:0\neq
a\in\mathbb{Z}_{p^{\alpha}},~{}b\in\mathbb{Z}_{p}~{}\mbox{and}~{}(a,p)=1\\}$,
where $0\leq i\leq\alpha-2$, and

$\mathcal{O}_{\alpha,p^{\alpha-1}}=\\{p^{\alpha-1}a+bx\neq
0:~{}a\in\mathbb{Z}_{p^{\alpha}},~{}b\in\mathbb{Z}_{p}~{}\mbox{and}~{}(a,p)=1\\}.$

Moreover, for $0\leq i\leq\alpha-2$,
$|\mathcal{O}_{\alpha,p^{i}}|=\phi\big{(}\frac{p^{\alpha+1}}{p^{i}}\big{)}$
and
$|\mathcal{O}_{\alpha,p^{\alpha-1}}|=\phi\big{(}\frac{p^{\alpha+1}}{p^{\alpha-1}}\big{)}+p-1=p^{2}-1$.
Note that $\mathcal{O}_{\alpha,p^{\alpha}}=\\{0\\}$. The vertex set
$V\big{(}\Gamma(R)\big{)}=\big{(}\bigcup\limits_{i=0}^{\alpha}\mathcal{O}_{\alpha,p^{i}}\big{)}$.
To prove the desired result, we consider the following cases.
Case - 1. $\alpha=2k$ for some $k\geq 1$. Then the subgraphs associated with
orbits
$X=\big{(}\bigcup\limits_{i=0}^{k-1}\mathcal{O}_{\alpha,p^{k+i}}\big{)}$
represents complete part of the graph $\Gamma\big{(}R\big{)}$ and the
subgraphs associated with orbits
$Y=\big{(}\bigcup\limits_{i=0}^{k-1}\mathcal{O}_{\alpha,p^{i}}\big{)}$
represents the independent part of $\Gamma(R)$ and each element of $X$ and $Y$
are connected to $\mathcal{O}_{\alpha,p^{\alpha}}=\\{0\\}$. Furthermore, if
$r\in\mathcal{O}_{\alpha,p^{k+i}}$ and $s\in\mathcal{O}_{\alpha,p^{i}}$ for
some $i$, then $r$ and $s$ are adjacent in the graph if and only if
$p^{\alpha}$ divides $p^{2i+k}$. This implies,

$|V\big{(}\Gamma(R)\big{)}|=\sum\limits_{i=0}^{k-1}|\mathcal{O}_{\alpha,p^{i}}|+\sum\limits_{i=0}^{k-2}|\mathcal{O}_{\alpha,p^{k+i}}|+\big{(}|\mathcal{O}_{\alpha,p^{2k-1}}|+(p-1)\big{)}+1=p^{\alpha+1}.$
To prove that $\Gamma(R)$ is a threshold graph it suffices to show that
$\Gamma(R)$ has no induced subgraph of the form $C_{4}$, $P_{4}$ or $2K_{2}$,
that is, it has no alternating $4$-$cycle$.

Let $a,b,c,d$ be four distinct vertices of $\Gamma(R)$.
Subcase - 1. If $a=0$ and $b,c,d\in X\cup Y$, then $(b,0),(c,0),(d,0)\in
E\big{(}\Gamma(R)\big{)}$. Thus no two disjoint edges are present and
therefore no alternating $4-cycle$ is possible.
Subcase - 2. If all $a,b,c,d\in X\cup Y$, that is, no one among $a,b,c,d$
represents the vertex $0$, then we have the following cases .
Subcase - 2.1. Suppose that all four vertices $a,b,c,d\in X$. Then they are
all adjacent to each other and hence no alternating $4-cycle$ is possible.
Subcase - 2.2. Suppose that all four vertices $a,b,c,d\in Y$. Then these
vertices are all isolated and therefore no alternating $4-cycle$ is possible.
Subcase - 2.3. Suppose $a\in X$ and $b,c,d\in Y$. Then in $\Gamma(R)$, there
may not be any edge from $a$ to $b,c,d$. Without of loss of generality, the
other possibilities are either $(a,d)\in E(\Gamma(R))$ or $(a,b),(a,d)\in
E(\Gamma(R))$ or $(a,b),(a,c),(a,d)\in E(\Gamma(R))$ as follows.

cdabcdabcdabcdab

Thus no one among the above graphs is isomorphic to $C_{4}$, $P_{4}$ or
$2K_{2}$. Therefore the result follows.
Subcase - 2.4. Suppose $a,b\in X$ and $c,d\in Y$, then the only possibilities
are as follows.

cdabcdabcdabcdabcdabcdab

Subcase - 2.5. Suppose $a,b,c\in X$ and $d\in Y$, then the only possibilities
are as follows.

cdabcdabcdabcdab

Thus it follows that the graph $\Gamma(R)$ has no alternating $4-cycle$.
Therefore, $\Gamma(R)$ is a connected threshold graph.
Case - 2. $\alpha=2k-1$ for some $k\geq 1$. Then the subgraphs associated with
orbits
$X=\big{(}\bigcup\limits_{i=0}^{k-2}\mathcal{O}_{\alpha,p^{k+i}}\big{)}$
represents complete part of the graph $\Gamma\big{(}R\big{)}$ and the
subgraphs associated with orbits
$Y=\big{(}\bigcup\limits_{i=0}^{k-1}\mathcal{O}_{\alpha,p^{i}}\big{)}$
represents the independent part of $\Gamma(R)$ and each element of $X$ and $Y$
are connected to $\mathcal{O}_{\alpha,p^{\alpha}}=\\{0\\}$. This implies,

$|V\big{(}\Gamma(R)\big{)}|=\sum\limits_{i=0}^{k-1}|\mathcal{O}_{\alpha,p^{i}}|+\sum\limits_{i=0}^{k-3}|\mathcal{O}_{\alpha,p^{k+i}}|+\big{(}|\mathcal{O}_{\alpha,p^{2k-2}}|+(p-1)\big{)}+1=p^{\alpha+1}.$

We can prove that $\Gamma\big{(}R\big{)}$ does not have an alternating
$4$-cycle by considering four distinct vertices $a,b,c,d$ and using the same
argument as above for the case $\alpha=2k$.

######  Theorem 8.

For each prime $p$, zero-divisor graphs realized by rings
$\mathbb{Z}_{p}[x]/(x^{p})$, $\mathbb{Z}_{p}[x,y]/(x^{3},xy,y^{2})$, and
$\mathbb{Z}_{p^{2}}[x]/(px,x^{2}-p)$ are connected threshold graphs.

######  Proof 6.

Let $R\cong\mathbb{Z}_{p}[x]/(x^{p})$. Then orbits of the group action
$Aut(\Gamma(R))\times R\longrightarrow R$ are as follows,

$\mathcal{O}_{p,x^{i}}=\\{x^{i}(a_{0}+a_{1}x+\cdots+a_{p-(1+i)}x^{p-(1+i)}):a_{i}\in\mathbb{Z}_{p},~{}\mbox{and}~{}a_{0}\neq
0\\},$

where $0\leq i\leq p-1$. For $0\leq i\leq p-1$,
$|\mathcal{O}_{p,x^{i}}|=\phi\big{(}\frac{p^{p}}{p^{i}}\big{)}$ and
$|\mathcal{O}_{p,x^{i}}|=\\{0\\}$. The vertex set
$V\big{(}\Gamma(R)\big{)}=X\bigcup Y$, where
$X=\big{(}\bigcup\limits_{i=0}^{\frac{p-1}{2}}\mathcal{O}_{p,x^{i+\frac{p+1}{2}}}\big{)}$
and
$Y=\big{(}\bigcup\limits_{i=0}^{\frac{p-1}{2}}\mathcal{O}_{p,x^{i}}\big{)}$,
represents complete and independent parts of the graph $\Gamma(R)$, and
$\mathcal{O}_{p,x^{p}}=\\{0\\}$. Also, two distinct vertices
$r\in\mathcal{O}_{p,x^{i}}$ and $s\in\mathcal{O}_{p,x^{j}}$ for
$i,~{}j\in\\{0,1,\cdots,\frac{p-1}{2}\\}$ are adjacent in $\Gamma(R)$ if and
only if $i+j\geq p$. Therefore,

$|V\big{(}\Gamma(R)\big{)}|=\sum\limits_{i=0}^{\frac{p-1}{2}}|\mathcal{O}_{p,x^{i+\frac{p+1}{2}}}|+\sum\limits_{i=0}^{\frac{p-1}{2}}|\mathcal{O}_{p,x^{i}}|=p^{p}.$

Moreover, for $R\cong\mathbb{Z}_{p}[x,y]/(x^{3},xy,y^{2})$ and for each
$a_{0},~{}a_{1},~{}a_{2},~{}b_{1}\in\mathbb{Z}_{p}$, the orbits of the group
action $Aut(\Gamma(R))\times R\longrightarrow R$ are as follows,

$\displaystyle\mathcal{O}_{p,x}$ $\displaystyle=$
$\displaystyle\\{a_{1}x+a_{2}x^{2}+b_{1}y:~{}~{}a_{1}\neq 0\\},$
$\displaystyle\mathcal{O}_{p,y}$ $\displaystyle=$
$\displaystyle\\{a_{2}x^{2}+b_{1}y\neq 0\\},$ $\displaystyle\mathcal{O}_{p,1}$
$\displaystyle=$
$\displaystyle\\{a_{0}+a_{1}x+a_{2}x^{2}+b_{1}y:~{}~{}a_{0}\neq 0\\},$
$\displaystyle\mathcal{O}_{p,p}$ $\displaystyle=$ $\displaystyle\\{0\\},$

where $x,y,p$ and $1$ are representatives of orbits $\mathcal{O}_{p,x}$,
$\mathcal{O}_{p,y}$, $\mathcal{O}_{p,1}$ and $\mathcal{O}_{p,p}$ with
$|\mathcal{O}_{p,x}|=p^{3}-p^{2}$, $|\mathcal{O}_{p,y}|=p^{2}-1$,
$|\mathcal{O}_{p,1}|=p^{4}-p^{3}$ and $|\mathcal{O}_{p,p}|=1$. The vertex set
$V\big{(}\Gamma(R)\big{)}=X\bigcup Y$, where
$X=\big{(}\mathcal{O}_{p,y}\big{)}$ and
$Y=\big{(}\mathcal{O}_{p,x}\cup\mathcal{O}_{p,1}\big{)}$ represents complete
and independent parts of the graph $\Gamma(R)$, and
$\mathcal{O}_{p,p}=\\{0\\}$. Furthermore, every vertex in $\mathcal{O}_{p,y}$
is adjacent to each vertex in $\mathcal{O}_{p,x}$ and the vertex $0$ is
adjacent to each vertex of $\Gamma(R)$. Therefore,
$|V\big{(}\Gamma(R)\big{)}|=p^{4}$.

Finally, for $R\cong\mathbb{Z}_{p^{2}}[x]/(px,x^{2}-p)$, the orbits of the
group action $Aut(\Gamma(R))\times R\longrightarrow R$ are as follows,

$\displaystyle\mathcal{O}_{p,x}$ $\displaystyle=$
$\displaystyle\\{pa+bx:~{}0\neq b\in\mathbb{Z}_{p},~{}a\in\mathbb{Z}_{p}\\},$
$\displaystyle\mathcal{O}_{p,p}$ $\displaystyle=$ $\displaystyle\\{pa:~{}0\neq
a\in\mathbb{Z}_{p}\\},$ $\displaystyle\mathcal{O}_{p,1}$ $\displaystyle=$
$\displaystyle\\{a+bx:~{}0\neq
a\in\mathbb{Z}_{p^{2}},~{}b\in\mathbb{Z}_{p}~{}and~{}(a,p)=1\\}$
$\displaystyle\mathcal{O}_{p,p^{2}}$ $\displaystyle=$ $\displaystyle\\{0\\},$

where $|\mathcal{O}_{p,x}|=p^{2}-p$, $|\mathcal{O}_{p,p}|=p-1$,
$|\mathcal{O}_{p,1}|=p^{3}-p^{2}$ and $|\mathcal{O}_{p,p^{2}}|=1$. The vertex
set $V\big{(}\Gamma(R)\big{)}=X\bigcup Y$, where
$X=\big{(}\mathcal{O}_{p,p}\big{)}$ and
$Y=\big{(}\mathcal{O}_{p,x}\cup\mathcal{O}_{p,1}\big{)}$ represents complete
and independent parts of the graph $\Gamma(R)$ and
$\mathcal{O}_{p,p^{2}}=\\{0\\}$. From the structure of the graph, every vertex
in $\mathcal{O}_{p,1}$ is adjacent to the vertex $0$ only, whereas every
vertex in $\mathcal{O}_{p,p}$ is adjacent to each vertex of
$\mathcal{O}_{p,x}$ and to the vertex $0$. Thus,
$|V\big{(}\Gamma(R)\big{)}|=p^{3}$.

By taking any four distinct vertices a, b, c and d from vertex set of each of
the graphs realized by rings $(\mathbb{Z}_{p}[x]/(x^{p}))$,
$\mathbb{Z}_{p}[x,y]/(x^{3},xy,y^{2})$, $\mathbb{Z}_{p^{2}}[x]/(px,x^{2}-p)$
and use the similar approach as in Theorem (7), it can be shown that zero
divisor graphs realized by above mentioned rings does not contain an
alternating $4-cycle$ and therefore the result follows.

######  Corollary 9.

For each prime $p$ and positive integer $\alpha$, the zero-divisor graph
realized by a local ring $\mathbb{Z}_{p^{\alpha}}$ is a connected threshold
graph.

Problem. Characterise all finite local rings such that $\Gamma(R)$ is a
threshold graph.

In the following result, we consider the Artinian decomposition of $R$ for
$r\geq 2$ and $s=0$, that is, we investigate the structure of $\Gamma(R)$ when
$R$ is a product of local rings only.

######  Lemma 10.

If $R\cong{R}_{1}\times{R}_{2}\times\cdots\times{R}_{r}$, where $r\geq 2$ and
each ${R}_{i},1\leq i\leq r$ is a finite local ring (not a field), then
$\Gamma(R)$ is not a threshold graph.

######  Proof 7.

Since $R$ is a product of at least two finite local rings, therefore
$\Gamma(R)$ always has an induced subgraph either of the form $P_{4}$ or
$C_{4}$ or $2K_{2}$ described as follows.

(1, ${b}_{1}$, 0, $\cdots$ ,0)(0, ${b}_{2}$, 0, $\cdots$ ,0)(${a}_{1}$, 0, 0,
$\cdots$ ,0)(${a}_{2}$, 1, 0, $\cdots$ ,0)(1, 0, 0, $\cdots$ ,0)(0, 1, 0,
$\cdots$ ,0)(0, ${b}_{1}$, 0, $\cdots$ ,0)(${a}_{1}$, 0, 0, $\cdots$ ,0)(1, 0,
0, $\cdots$ ,0)(0, 1, 0, $\cdots$ ,0)(${a}_{1}$, ${b}_{1}$, 0, $\cdots$
,0)(${a}_{2}$, ${b}_{2}$, 0, $\cdots$ ,0)

Note that $a_{i}\in Z^{*}(R_{1})$ and $b_{i}\in Z^{*}(R_{2})$. where
$Z^{*}(R_{1})$ and $Z^{*}(R_{2})$ denotes the set of non-zero zero-divisors of
rings $R_{1}$ and $R_{2}$.

In the following result, we classify all finite commutative rings $R$ such
that $\Gamma(R)$ is not a threshold graph.

######  Theorem 11.

If
$R\cong{R}_{1}\times{R}_{2}\times\cdots\times{R}_{r}\times{{F}_{1}}\times{{F}_{2}}\times\cdots\times{{F}_{s}}$,
where $r$ and $s$ are positive integers, each $R_{i}$ is a finite commutative
local ring (not a field), and each ${F}_{i}$ is a finite field, then
$\Gamma(R)$ is not threshold.

######  Proof 8.

The proof follows from Theorem (6) and Lemma (10).

Conclusion: In this research article, we presented some new classes of
threshold graphs. As discussed above, the construction of new classes of
threshold graphs are effective in a sense that it assists to advance in coding
theory and spectral analysis. We obtained the results related to reduced and
local rings. In fact, we characterized all reduced rings of which zero-divisor
graphs are realized as threshold graphs. Furthermore, we obtained classes of
threshold graphs realized by some classes of local rings and provided an
example which illustrates that a zero-divisor graph associated with some local
ring is not always a threshold graph. So, it is interesting to determine all
classes of local rings of which zero-divisor graphs are always threshold. This
investigation has been included in the paper as a problem for future research
work.

Acknowledgement
We thank the anonymous reviewers for their careful reading of the manuscript
and their many insightful comments and suggestions. The second author’s
research is supported by the University Grants Commission, Govt. of India
under UGC-Ref. No. 1337/(CSIR-UGC NET JUNE 2019).

Declaration of competing interest
There is no conflict of interest to declare.

Data Availability.
Data sharing not applicable to this article as no datasets were generated or
analysed during the current study.

## References

  * [1] D. F. Anderson and P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra 217 (1999) 434 - 447.
  * [2] R. B. Bapat, Graphs and Matrices, Springer/Hindustan Book Agency, London/New Delhi 2010.
  * [3] I. Beck, Coloring of commutative rings, J. Algebra 116 (1988) 208 - 226.
  * [4] Bilal A. Rather, S. Pirzada, T. A. Naikoo, Y. Shang, On Laplacian eigenvalues of the zero-divisor graph associated to the ring of integers modulo n, Math. 9 (5) (2021) 482.
  * [5] S. Chattopadhyay, K. L. Patra and B. K. Sahoo, Laplacian eigenvalues of the zero divisor graph of the ring $\mathbb{Z}_{n}$, L. Algeb. Appl. 584 (2020) 267 - 286.
  * [6] V. Chvátal, P. L. Hammer, Aggregation of Inequalities in Integer Programming, Ann. Disc. Math. 1 (1977) 145 - 162.
  * [7] P. B. Henderson and Y. Zalcstein, Synchronization problems solvable by generalized pv systems, J. ACM. 27 (1) (1980) 60 - 71.
  * [8] I. Kaplansky, Commutative Rings, rev. edn. University of Chicago Press, Chicago, 1974.
  * [9] N. V. R. Mahadev, U.N. Peled, Threshold Graphs and Related Topics, Ann. Disc. Math. 56, (1995).
  * [10] S. Pirzada, An Introduction to Graph Theory, Universities Press, OrientBlackSwan, Hyderabad, 2012.
  * [11] S. Pirzada, Bilal A. Rather and T. A. Chishti, On distance Laplacian spectrum of zero divisor graphs of $\mathbb{Z}_{n}$, Carpathian Mathematical Publications, 13 (1) (2021) 48 - 57.
  * [12] S. Pirzada, Bilal A. Wani, A. Somasundaram, On the eigenvalues of zero divisor graph associated to finite commutative ring $\mathbb{Z}_{p^{M}q^{N}}$. AKCE International J. Graphs Combinatorics, 18 (1) (2021) 1 - 16.
  * [13] R. Raja, Total perfect codes in graphs realized by commutative rings, Transactions of Comb. 11 (4) (2022) 295 - 307.
  * [14] S. P. Redmond, On zero-divisor graphs of small finite commutative rings, Disc. Math. 307 (9-10) (2007) 1155 - 1166.
  * [15] A.J. Schwenk, Computing the characteristic polynomial of a graph, Graphs and Comb. Springer, Berlin, Heidelberg (1974) 153 - 172.


# HopRank: How Semantic Structure Influences Teleportation in PageRank (A Case
Study on BioPortal)

Lisette Espín-Noboa  GESIS & Uni. Koblenz-Landau<EMAIL_ADDRESS>,
Florian Lemmerich  RWTH Aachen University<EMAIL_ADDRESS>aachen.de ,  Simon Walk  Detego GmbH<EMAIL_ADDRESS>,  Markus Strohmaier
RWTH Aachen University & GESIS<EMAIL_ADDRESS>and  Mark
Musen  BMIR-Stanford<EMAIL_ADDRESS>
(2019)

###### Abstract.

This paper introduces HopRank, an algorithm for modeling human navigation on
semantic networks. HopRank leverages the assumption that users know or can see
the whole structure of the network. Therefore, besides following links, they
also follow nodes at _certain distances_ (i.e., k-hop neighborhoods), and not
at random as suggested by PageRank, which assumes only links are known or
visible. We observe such preference towards k-hop neighborhoods on BioPortal,
one of the leading repositories of biomedical ontologies on the Web. In
general, users navigate within the vicinity of a concept. But they also “jump”
to distant concepts less frequently. We fit our model on 11 ontologies using
the transition matrix of clickstreams, and show that semantic structure can
influence teleportation in PageRank. This suggests that users—to some
extent—utilize knowledge about the underlying structure of ontologies, and
leverage it to reach certain pieces of information. Our results help the
development and improvement of user interfaces for ontology exploration.

Biased random walker; PageRank; k-hop neighborhood; BioPortal

††journalyear: 2019††copyright: iw3c2w3††conference: Proceedings of the 2019
World Wide Web Conference; May 13–17, 2019; San Francisco, CA, USA††booktitle:
Proceedings of the 2019 World Wide Web Conference (WWW ’19), May 13–17, 2019,
San Francisco, CA, USA††doi: 10.1145/3308558.3313487††isbn:
978-1-4503-6674-8/19/05††ccs: Information systems Content ranking††ccs:
Mathematics of computing Exploratory data analysis††ccs: Information systems
Browsers

(a) Transitions

(b) HopPortation Vector

(c) Transition Probabilities

Figure 1. HopRank on semantic networks. This example illustrates an instance
of navigation on an ontology. (a) Shows the underlying network composed by
seven concepts (a-g) and six _isASubClassOf_ relationships (straight-thin grey
arrows). Transitions (curved-thick black arrows) are labeled by the actual
number of transitions between concepts, as well as the [k-hop] distance (i.e.,
shortest path) between them. (b) Illustrates how the HopPortation vector
$\vec{\beta}$ is built using transition counts per k-hop. (c) Shows the
transition probabilities inferred by HopRank, see Equation 1.

##  1\. Introduction

Ontology Engineering and Ontology Learning are two branches of the Semantic
Web whose aim is to accurately build and curate ontologies. The former studies
new techniques to improve collaboration among humans while editing ontologies
(Tudorache et al., 2008; Walk et al., 2015), and the latter introduces new
methodologies and algorithms to automatically create ontologies by crawling
the Web (Auer et al., 2007; Suchanek et al., 2007). These efforts represent
significant advances in the development of knowledge bases, which represent
facts about the real world (e.g., people, diseases). However, there is little
knowledge about how users consume such ontologies on the Web. To this end,
Walk et al. studied how users browse BioPortal (Walk et al., 2017). Their
findings suggest that some ontologies influence the way users interact with
the website. However, how users navigate through the ontology structure (i.e.,
from one concept to another) remains unclear.

Problem Statement: In this paper, we study the influence of semantic structure
on _teleportation_ (i.e., jumping to any node chosen at random) in PageRank.
For example, consider the ontology shown in Figure 1(a), where nodes represent
_classes_ (a.k.a. concepts) and edges _isASubClassOf_ relationships. On
BioPortal, ontologies are shown vertically as hierarchical trees, and concepts
can be explored using the _expand-on-demand_ principle. This means that only
top level concepts are shown first, and then users are able to expand and
collapse as many concepts as they need at any level of the ontology. In other
words, users can use and therefore are potentially aware of a _virtually fully
connected network_ in all stages of navigation. Previous studies (Page et al.,
1999; Xing and Ghorbani, 2004) have modeled user navigation using PageRank.
However, these assume that navigation paths are constrained by links and
random teleportation. In our scenario, where the whole structure of an
ontology can be visualized at any time, we believe that teleportation is not
fully random, but rather biased towards k-hop neighborhoods.

Approach: Motivated by previous studies on information foraging (Pirolli and
Card, 1999; Chi et al., 2000; Card et al., 2001; Chi et al., 2001),
decentralized search (Kleinberg, 2002; Helic et al., 2013), and PageRank (Page
et al., 1999; Haveliwala, 2003; Xing and Ghorbani, 2004; Gorman, 2004; Abbott
et al., 2015), we propose HopRank, a method for modeling transitions across
k-hop neighborhoods on semantic networks. The key idea of this work relies on
the HopPortation vector $\vec{\beta}$, which defines the probabilities of
transitioning to each k-hop neighborhood. From the PageRank point of view, we
can say that teleportation is not fully random, and the probability of
following the structure of a page is not based only on one parameter (i.e.,
probability of following links), but on $k$ parameters, representing all k-hop
neighborhoods _reached from the current page_. Technically, we pass the
HopPortation vector to a random walker to make biased decisions on which
neighborhood to go next. Once this decision is made, the random walker
uniformly chooses a concept within that neighborhood.

Contributions: The contributions of this paper are:

  1. (1)

We empirically show how users leverage the structure of the ontologies on
BioPortal by quantifying the proportion of transitions per k-hop neighborhood.

  2. (2)

We propose HopRank, an algorithm for modeling human navigation on semantic
networks.

  3. (3)

We demonstrate that HopRank outperforms traditional navigation and popularity-
based models on BioPortal, especially when users browse ontologies directly
without search.

  4. (4)

We make an implementation of this approach openly available on the Web (Espín-
Noboa, 2018).

##  2\. Related Work

BioPortal provides users with a _tree-like explorer_ and a _local search_
engine to navigate ontologies. In addition, concepts can be _expanded on
demand_ to see their children nodes. Although these functionalities are
exploited differently across ontologies (Walk et al., 2017), it is unclear how
users navigate through the ontology structure. Thus, this section covers
previous work on search and navigation on networks.

Search. _Information Foraging_ (Pirolli and Card, 1999) assumes that people,
when possible, modify their strategies or the structure of the environment to
maximize their gain of valuable information. These patterns are also found in
the way humans recall information from memory (Hills et al., 2012). Similarly,
_berrypicking_ (Bates, 1989), a model of online searching, states that queries
are not static, but rather evolve, and users commonly gather information in
pieces instead of in one large set.

Navigation. _PageRank_ (Page et al., 1999) is the most popular method to
measure the importance of web pages based on their incoming and outgoing
links. It relies on an imaginary surfer who is randomly _clicking on links_ ,
and eventually _jumps_ to any node in the network. The probability of
following links is given by a _damping factor_. Multiple variations have been
proposed for improving information retrieval systems, e.g., a biased PageRank
(Haveliwala, 2003) to capture the importance of a page more accurately by
taken topics into account or a weighted PageRank (Xing and Ghorbani, 2004) to
assign larger rank values to more popular pages (i.e., preferential
attachment) instead of distributing the rank value of a page uniformly to all
outgoing pages. Geigl et al. suggest that the behavior of a _random surfer_ is
almost similar to real users, as long as they do not use search engines (Geigl
et al., 2015). They also find that classical navigation structures, such as
navigation hierarchies or breadcrumbs, only exercise limited influence on
navigation. Experiments in (Singer et al., 2014) reveal that memory-less
_Markov chains_ represent a quite practical model for human navigation on a
page level. However, this assumption is violated when the analysis is expanded
to a topical level. Helic et al. identify certain configurations of
_decentralized search_ that are capable of modeling human navigation in
information networks (Helic et al., 2013). Their findings suggest that
navigation on such networks is a two phase process combined with the
_exploitation of the known_ (i.e., goal-seeking) and the _exploration of the
unknown_ (i.e., orientation).

User Interfaces. Human navigation has also been studied for enhancing
interfaces. For instance, (Furnas, 1986) explores _fisheye_ views to display
large information structures such as programs and databases. The intuition
behind this paradigm is that users often explore their neighborhood, and
distant major landmarks in more detail. Similarly, Van Ham and Perer studied
the _search, show context, expand on demand_ browsing model in (Van Ham and
Perer, 2009), and proposed techniques to design better graph visualization
tools.

We propose HopRank—a biased random walker—to model navigation on semantic
networks. HopRank builds upon insights from information foraging (Pirolli and
Card, 1999; Hills et al., 2012), decentralized search (Helic et al., 2013;
Kleinberg, 2002) and PageRank (Page et al., 1999). More precisely, we replace
the _damping factor_ by a HopPortation vector to encode the probabilities of
visiting each k-hop neighborhood. The intuition here is that users browse
semantically close terms more often than semantically distant ones.

##  3\. BioPortal

There exist a large number of ontologies in the biomedical domain. They are
highly specialized and therefore expensive to develop. To enable ontology
adoption and reuse, effective support for browsing and exploring existing
ontologies is required. Towards that goal, the National Center for Biomedical
Ontology (NCBO) (NCB, 2011; Musen et al., 2011) features BioPortal (Bio, 2011;
Noy et al., 2009; Whetzel et al., 2011)—one of the leading repositories of
biomedical ontologies on the Web— containing currently more than $700$
ontologies with more than $9$ million ontology classes. On BioPortal,
practitioners and experts can access ontologies via Web services and Web
browsers. The latter allows users to navigate ontologies by searching specific
classes, or by directly browsing their concept hierarchies within a tree-like
explorer (Walk et al., 2017).

Ontologies.  We propose to model human navigation on semantic networks using
the structure of the underlying ontology. On BioPortal, ontologies are defined
as directed networks, where nodes represent _concepts_ and edges
_isASubClassOf_ relationships. Since such edges are usually non-cyclic and
have a common root, these ontologies often form trees. Table 1 shows 11 of the
most visited ontologies in 2015111As ontologies can be edited over time, we
work with their latest snapshots from 2015.. For instance, LOINC the largest
ontology with $175K$ nodes, $153K$ edges, and $74K$ connected components.

Table 1. Datasets. This table illustrates network properties of 11 of the most
popular ontologies on BioPortal in 2015. Ontologies represent networks whose
nodes refer to _concepts_ and edges _isASubClassOf_ relationships. Original
number of nodes, edges, and connected components of ontologies are shown under
N, E and cc, respectively. Properties of the largest connected component (LCC)
of each ontology are shown under N’, E’, d’ and T’, where d’ refers to the
diameter and T’ to the number of transitions.

# | Ontology | N | E | cc | N’ | E’ | d’ | T’
---|---|---|---|---|---|---|---|---
1 | CPT | 13219 | 13235 | 3 | 13092 | 13110 | 15 | 44651
2 | MEDDRA | 66506 | 31863 | 43493 | 22889 | 31738 | 8 | 42746
3 | NDFRT | 35019 | 34504 | 522 | 32074 | 32080 | 24 | 22452
4 | LOINC | 174513 | 152683 | 73518 | 100871 | 152558 | 13 | 6349
5 | ICD9CM | 22534 | 22531 | 3 | 22407 | 22406 | 12 | 4434
6 | WHO-ART | 1852 | 2997 | 3 | 1725 | 2872 | 4 | 2811
7 | MESH | 165166 | 24182 | 145652 | 16947 | 21596 | 31 | 2623
8 | ICD10 | 12446 | 11256 | 1190 | 11132 | 11131 | 10 | 2288
9 | CHMO | 2966 | 3071 | 3 | 2964 | 3071 | 22 | 1423
10 | HL7 | 10319 | 10600 | 1049 | 9146 | 10475 | 19 | 1374
11 | OMIM | 81821 | 39359 | 44110 | 37587 | 39234 | 6 | 1291

Transitions. We analyzed all HTTP requests made in 2015 and extracted $336K$
valid sessions (i.e., after filtering out sessions with less than $2$
requests, and requests to ontologies or concepts which do not exist). Each
session contains transitions (i.e., a sequence of visited concept pages)
triggered by a single user (i.e., IP address) without breaks (i.e., pauses of
at least $60$ minutes). For simplicity, we only consider transitions within
the largest connected component (LCC) of each ontology, and discard ontologies
with less than $1000$ transitions222Transitions within the LCCs of these
ontologies represent $80\%$ of all transitions.. Overall, we found 11
ontologies and $133K$ transitions between their concepts333We left out the
popular SNOMEDCT ontology due to computational limitations., see Table 1 for
some key properties.

Figure 2. Navigation Types. Each bar shows the fraction of transitions within
the LCC of each ontology. Stacked bars differentiate types of navigation:
details (DE, blue), direct click (DC, orange), direct URL (DU, green), expand
(EX, red), external link (EL, purple), external search (ES, brown) and local
search (LS, pink). Most ontologies are mainly navigated by _expanding_ nodes
within the tree-like explorer.

Navigation Types. Based on the HTTP request headers, we inferred $7$
navigation types: Details (DE), Direct Click (DC), Direct URL (DU), Expand
(EX), External Link (EL), External Search (ES), and Local Search (LS). DE: are
all clicks made within the _Details_ tab of a selected concept. DC: are all
clicks made on concepts within the tree-like explorer. DU: refers to all
concept requests without HTTP referrer (e.g., direct URL in the browser). EX:
considers all clicks on the (+) symbol of a concept, which triggers the
expansion of the concept to show all its children nodes. Notice that this
request is called only once, even if the symbol is clicked multiple times. The
opposite behavior (collapse) is not considered444Collapse is a client-side
functionality, and thus, it is not recorded in the log files.. EL: captures
all requests coming from external websites that are not search engines. ES:
are all requests coming from the top $10$ most popular external search engines
such as Google and Yahoo. LS: are all requests made via the local search
functionality of each ontology. Notice that this search is a 3-step process.
First users type a keyword, then the system shows auto-suggestions and finally
users click on one of the concepts shown in the auto-suggestion list. We only
consider the final step a local search transition. ALL: includes all the
above-mentioned types. Figure 2 shows the distribution of transitions across
navigation types for each ontology. In general, most traffic comes from
expanding a concept (EX, $44\%$), followed by local search (LS, $17\%$),
direct URL (DU, $16\%$) and details (DE, $14\%$). Surprisingly, direct clicks
on concepts (DC) only represent $7\%$ of all transitions. This suggests that
users spend substantial time expanding concepts before they find a concept of
interest.

##  4\. HopRank: A biased random walker

HopRank models human navigation on semantic networks. Imagine a random walker
whose decisions on where to go next are biased towards specific k-hop
neighborhoods. This bias is what we call _HopPortation_ , which encodes the
probabilities of transitioning to each k-hop neighborhood. In our model,
navigation on networks can be explained as a 2-step process. First, a $k$-hop
neighborhood of the current node $i$ is drawn from a categorical distribution.
Second, a node $j$ is randomly chosen within that $k$-hop neighborhood. Note
that this process holds only if the walker is fully or partially aware of the
structure of the network (i.e., knows or can see it). Without this
prerequisite, and if links are not preferred, then random jumps to random
pages will be more plausible. In comparison to the classic random walker with
teleportation (e.g., PageRank (Page et al., 1999)), where its movements are
constrained by the damping factor $\alpha$ (i.e., probability of following
links), HopRank is constrained by a vector $\vec{\beta}$ containing $k$
different factors, which define the probabilities of going to each k-hop
neighborhood from the current location.

Visited k-hop Neighborhoods on BioPortal. We aggregate ALL transitions by the
shortest distance between two sequentially visited nodes. This distance is
referred to as k-hop neighborhood. In Figure 3(a) we see that target nodes at
large distances are less likely to be visited next. This is expected, since—to
some extent—larger distances enclose more branches, therefore more target
candidates. Note that ontologies are sorted by diameter in descendant order
from MESH to WHO-ART. Interestingly, users tend to hop as far as the
ontology’s diameter, for $d^{\prime}\leq 12$. For instance, OMIM’s diameter is
$6$ (see Table 1), and $6$ is the maximum hop done by users. Otherwise, users
(roughly) hop up to two-thirds of the ontology’s diameter, for
$d^{\prime}>12$. For example, MESH’s diameter is $31$, and the largest hop
reached is $19$.

Transitions per k-hop Neighborhood on BioPortal. Figure 3(b) shows the average
percentage of transitions across k-hop neighborhoods per navigation type. We
see that users on average (ALL, grey) prefer to navigate through $2$-hop (41%)
and $1$-hop (23%) neighbors. In particular, when navigation is triggered by
direct clicks (DC, orange) and expand (EX, red). Notice their fast decay when
$khop>8$. Other types of navigation such as external link (EL, purple), and
direct URL (DU, green)—which do not leverage the tree-like explorer—tend to
reach concepts at larger distances more frequently. Notice their peaks at
$khop=\\{5,11\\}$, respectively. Interestingly, when users opt for external
search (ES, brown), they often click on 2-hop concepts, but also on 12-hop and
15-hop neighbors. Intuitively, the details tab (DE, blue) helps users to click
on nearby concepts at $khop\leq 2$, more often than local search (LS, pink),
which is more likely to reach concepts at $khop\geq 2$.

##  5\. Models of Human Transitions

In this section, we formally introduce our HopRank model, and recap popular
navigation models for comparison. We denote the transition probabilities, and
# of parameters according to HopRank and $7$ other models that we will use
later on for model selection.

(a) % of dyads traversed per ontology

(b) Mean % of transitions per navigation type

Figure 3. Popularity of k-hops. (a) Shows the percentage of dyads that are
traversed per k-hop neighborhood. Lines represent ontologies and are sorted by
their LCC diameter: In descendent order from MESH (dark blue) to WHO-ART (dark
red). (b) Shows the distribution of transitions across k-hop neighborhoods per
navigation type. Percentages are averages across ontologies, and error bars
the respective standard deviation. While several k-hop distances are being
traversed non-uniformly, most transitions happen across nearby nodes,
especially when browsing (DE, DC, EX, ES) 2-hop neighbors. In contrast, non-
browsing types (EL, LS, DU) tend to reach more distant nodes more frequently.

We formally represent an ontology555We focus on its largest connected
component (LCC) as a graph $G=(V,E)$, with $V=(v_{1},\dots v_{n})$ being a set
of $N$ nodes, and $E=\\{(v_{i},v_{j})\\}\in{V\times V}$ a set of undirected
edges666Directionality of edges is omitted to calculate shortest paths between
all pair of nodes.. The ontology structure is captured by the adjacency matrix
$A_{N\times N}={a_{ij}}$, where $a_{ij}$ is $1$ if the link exists, $0$
otherwise. Transitions are represented by the transition matrix $T_{N\times
N}={t_{ij}}$, where $t_{ij}$ represents the number of transitions between
source node $i$ and target node $j$.

HopRank. Given the HopPortation vector $\vec{\beta}$, the probability of
reaching a k-hop neighborhood is denoted by factor $\beta_{k}\in\vec{\beta}$.
$M_{k}$, the stochastic $k$-hop matrix, describes all nodes $j$ with a
shortest distance $k$ from $i$. HopRank uniformly distributes $\beta_{k}$
across all nodes $j$ at distance $k$. The limits of k-hop neighborhoods go
from $1$ (direct edges), to $d^{\prime}$, the diameter of the ontology $G$.
Noise $\beta_{0}=1-\sum_{k=1}^{d^{\prime}}\beta_{k}$ is added to allow for
random jumps and self-loops. Figure 1(b) illustrates how the HopPortation
vector is computed from the transition counts. _Number of model parameters:
$d^{\prime}+1$_.

(1)
$P_{HR}=\beta_{1}\boldsymbol{M}_{1}+\beta_{2}\boldsymbol{M}_{2}+\dots+\beta_{k}\boldsymbol{M}_{k}+\frac{\beta_{0}}{N}$

Preferential Attachment (PA). Given the degree matrix $D_{N\times
N}={d_{ij}}={d_{j}}$, where ${d_{j}}$ represents the degree of the target node
$j$. The probability of moving from $i$ to $j$ is proportional to the degree
of $j$. _Number of model parameters: $0$_.

(2) $P_{PA}=\boldsymbol{D}$

Gravitational (Gr). Given the matrix $S_{N\times N}={(sp(i,j)+\epsilon)^{2}}$,
where $sp(i,j)$ denotes the shortest path between nodes $i$ and $j$. The
probability of navigating from $i$ to $j$ is proportional to the degree of
node $j$ and inversely proportional to the square distance between $i$ and
$j$. We add a smoothing factor $\epsilon$ to avoid overflows when dyads are
disconnected. In such cases, we set $\epsilon$ to the diameter $d^{\prime}$ of
$G$ plus $1$, to consider these jumps with a very low probability. Similarly,
we set the diagonal (i.e., self-loops) to $\epsilon=d^{\prime}+2$. _Number of
model parameters: $0$_.

(3) $P_{Gr}=\frac{\boldsymbol{D}}{S}$

Random Walker (RW). Given the damping factor $\alpha$ (i.e., probability of
following links), the probability of visiting a node $j$ is proportional to
$\alpha$ divided by the degree of the source node $i$, plus a random choice
equally distributed among all nodes. Depending on the $\alpha$ value, a random
walker can model four different behaviors: (i) $\alpha=0.0$: random jumps
only, (ii) $\alpha\approx 1.0$: navigation over links only, (iii)
$\alpha=0.85$: PageRank using the commonly used damping factor for navigating
the Web (Brin and Page, 1998), and (iv) the empirical PageRank which learns
the parameter $\alpha$ from the transitions data. _Number of model parameters:
$1$ if empirical, $0$ otherwise._

(4) $P_{PR}=\alpha\boldsymbol{A}+\frac{(1-\alpha)}{N}$

Markov Chain (MC). We assume that moving to the next node follows a Markov
process. Therefore, the probability of moving to a node $j$ only depends on
the current node $i$. These probabilities represent the maximum likelihood,
learned from the transition matrix $T$. Thus, the probability of visiting node
$j$ from node $i$ is proportional to the number of transitions $t_{ij}$.
_Number of model parameters: $N\times(N-2)$_.

(5) $P_{MC}=\boldsymbol{T}$

Note that $\boldsymbol{M}$, $\boldsymbol{A}$, and all $P_{*}$ from Equations
1, 2, 3, 4 and 5 are right stochastic matrices (i.e., each row must sum to
$1$).

##  6\. Experiments

In this section, we compare the performance of HopRank to the baselines on
synthetic and real-world networks.

###  6.1. Model Selection

For comparing the models, we employ the Bayesian Information Criterion (BIC)
(Schwarz et al., 1978) to select the best, i.e., lowest BIC score. BIC
evaluates _log-likelihoods_ $LL$ (i.e., how likely our transitions are for a
given model) and takes into account the _number of model parameters_ and
_observations_ (i.e., # of transitions) to avoid over-fitting.

(6) $\displaystyle BIC$ $\displaystyle=-2\cdot LL+nparams\cdot
log(nobservations),$ (7) $\displaystyle LL$
$\displaystyle=\sum_{i=1}^{N}\sum_{j=1}^{N}t_{ij}\cdot log(p_{ij}),$

where $t_{ij}$ represents the actual number of transitions from node $i$ to
node $j$, and $p_{ij}$ the probability of transitioning from node $i$ to node
$j$ for a given model.

###  6.2. Synthetic Network

Setup. The underlying network (structure) is a binary tree composed by $N=7$
nodes and $|E|=6$ edges as shown in Figure 1(a). Transitions (curved-thick
edges) are biased towards 2-hop and 4-hop neighborhoods. These biases are
reflected in the HopPortation vector shown in Figure 1(b).

Results. Probabilities inferred using Equation 1 are depicted in Figure 1(c).
Figure 4 (left) shows the number of parameters inferred by each model. While
the Markov chain model (MC) requires 35 parameters, HopRank only needs $5$.
The empirical PageRank (RW E.) learned a damping factor of ${\alpha=0.01}$.
This means that users are $1\%$ likely to follow links. In Figure 4 (right) we
see the comparison of models using BIC scores. In this synthetic network,
transitions are best described by the Markov chain model because model
parameters (i.e., maximum likelihood) are proportional to the actual
transition counts per dyad, and the data structure is very small777Therefore,
number of parameters does not play a very important role in BIC.. In spite of
that, HopRank is the second best model and describes navigation better than
random (RW 0.0).

Figure 4. Results on Synthetic Network from Figure 1. X-axis maps the models
at interest. (a) Number of parameters inferred by each model. (b) BIC: The
lower the score, the better the model explaining the data. In this example,
navigation is best described by Markov chain followed by HopRank.

###  6.3. Medical Dictionary for Regulatory Activities Terminology (MEDDRA)

Setup. MEDDRA(MED, 2011) is one of the the largest ontologies in our dataset
(see Table 1). After pre-processing, its largest connected component (LCC)
consists of $23K$ nodes and $43K$ transitions.

Results. Figure 5(a) shows the HopPortation vectors learned for each type of
navigation in MEDDRA. We see that users mainly navigate through 1, 2, 6, and
8-hop neighbors. For instance, transitions through direct clicks—on a concept
(DC), its details (DE) or expand (EX)—mainly follow 1-hop and 2-hop neighbors.
However, when transitions are triggered by direct URLs (DU), local search (LS)
or external links (EL), users tend to reach distant target nodes (i.e., 6-hop
and 8-hop neighbors). Figure 5(b) shows the ranking of models according to BIC
scores (lower is better). We see that in MEDDRA all types of navigation are
best explained by HopRank.

(a) HopPortation vectors

(b) Model selection

Figure 5. Results on MEDDRA. (a) This heatmap shows the HopPortation vectors
learned from the transitions in MEDDRA. Cells represent the probabilities of
visiting a certain k-hop neighborhood (column) by a given navigation type
(row). In general, 2-hop and 1-hop neighborhoods are more likely to be visited
next, regardless of navigation type (ALL). However, distant hops are preferred
through _direct URLs_ (DU), _external links_ (EL), and _local search_ (LS).
(b) This figure shows the comparison of models across navigation types using
BIC scores. We see that HopRank outperforms all baseline models.

###  6.4. Top11 Ontologies in BioPortal

Setup. We fit HopRank and the baseline models to all transitions by ontology
and navigation type. These represent $133K$ transitions coming from the 11
ontologies described in Table 1.

Results. In Figure 6 we highlight the model that explains the number of
transitions per ontology and navigation type best (i.e., the model with lowest
BIC score). Ontologies are sorted by their number of transitions from CPT
(largest) to OMIM (smallest). HopRank outperforms the other models 89% of the
time, especially when users browse directly—regardless of the ontology—the
tree-like explorer via clicks (DC), details (DE) and expand (EX). When there
are not enough observations (i.e., the number of transitions is small), the
other models tend to outperform HopRank due to the fact that the other models
require fewer parameters and/or it is less likely to find transitions across
different k-hop neighborhoods. This is the case for $6$ ontologies in certain
navigation types. For instance, we found $5$ external search (ES) transitions
in MESH which are best described by the Gravitational model (Gr). Even though
HopRank was a better candidate (i.e., higher log-likelihood), BIC penalized it
for having more parameters ($nparams_{{Hop\\-Rank}}=32>nparams_{Gr}=0$).
Notice that we model navigation in ontologies with at least $2$ transitions.
Ontologies that do not fulfil this condition per navigation type are marked as
green cells “-”.

Figure 6. Model Selection on BioPortal. This heatmap highlights the model—with
lowest BIC score—that best describes the # of transitions per ontology and
navigation type. HopRank outperforms the other models 89% of the time,
especially when browsing concepts via details (DE), direct click (DC) and
expand (EX). When transitions are scarce (i.e., the other 11%), BIC penalizes
HopRank since it has more parameters than the other models (except Markov
chain).

##  7\. Discussion and Future Work

In this section, we discuss decisions made for data processing, and future
directions that can be pursued to improve our results.

Largest Connected Component (LCC). Surprisingly, ontologies on BioPortal may
have multiple connected components. In those cases, only the branch connected
to the root _owl:Thing_ is shown at first in the tree-like explorer.
Disconnected (and hidden) nodes or branches need to be accessed from external
pages or local search. For simplicity, we opted to work with the LCC of each
ontology with the cost of removing $20\%$ of all transitions. Future work
should consider the whole network to study the tradeoffs between number of
transitions and random teleportation.

HopRank Extensions. More extensions based on network properties or similarity
measures between nodes could improve our results. For instance, considering
ontologies as directed graphs, and assuming that navigation is not only
constrained by distance but also directionality: top-down or bottom-up.

Other Types of Networks. Even though this paper targets semantic networks, we
believe that HopRank can be utilized to model human navigation in other
networks, such as the Web or cities. The only assumption required is that
users must have background knowledge of the underlying network they are
surfing/traveling in.

##  8\. Conclusions

In this paper, we introduced the concept of _HopPortation_ which states that
users—navigating a known or visible network—are biased towards certain k-hop
neighborhoods. This is a variation of PageRank, where we assume that
teleportation is not fully random but rather distributed non-uniformly across
different neighborhoods. We proposed _HopRank_ —a biased random walker—to
model navigation on semantic networks. Our findings on BioPortal suggest that
semantic structure (i.e., shortest path) influences navigation on networks. In
particular, users tend to be biased towards certain k-hop neighborhoods
depending on the type of navigation. For instance, when manually browsing the
tree-like explorer, users tend to hop to nearby concepts, whereas far-away
concepts are more likely to be reached by non-browsing types such as external
links. These results advance our understanding of how ontologies are actually
navigated and consumed, and help to develop and improve user interfaces for
ontology exploration.

Acknowledgements. We would like to thank Tania Tudorache, John Graybeal,
Matthew Horridge, Clement Jonquet, Maulik Kamdar, Alex Skrenchuk, Marcos
Oliveira, Fabian Flöck, Reinhard Munz, Dimitar Dimitrov, Indira Sen, Mattia
Samory and the three anonymous reviewers for their time and suggestions to
improve the quality of the paper. This work was funded by DFG German Science
Fund research projects “KonSKOE” and “PoSTs II”.

## References

  * (1)
  * Bio (2011) 2011\.  BioPortal.  https://bioportal.bioontology.org/ Accessed: 2019-02-21.
  * MED (2011) 2011\.  MEDDRA.  https://bioportal.bioontology.org/ontologies/MEDDRA Accessed: 2019-02-21.
  * NCB (2011) 2011\.  National Center for Biomedical Ontology (NCBO).  https://www.bioontology.org/ Accessed: 2019-02-21.
  * Abbott et al. (2015) Joshua T Abbott, Joseph L Austerweil, and Thomas L Griffiths. 2015\.  Random walks on semantic networks can resemble optimal foraging.  (2015).
  * Auer et al. (2007) Sören Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak, and Zachary Ives. 2007\.  Dbpedia: A nucleus for a web of open data.  _The semantic web_ (2007), 722–735.
  * Bates (1989) Marcia J Bates. 1989\.  The design of browsing and berrypicking techniques for the online search interface.  _Online review_ 13, 5 (1989), 407–424.
  * Brin and Page (1998) Sergey Brin and Lawrence Page. 1998.  The anatomy of a large-scale hypertextual web search engine.  _Computer networks and ISDN systems_ 30, 1-7 (1998), 107–117.
  * Card et al. (2001) Stuart K Card, Peter Pirolli, Mija Van Der Wege, Julie B Morrison, Robert W Reeder, Pamela K Schraedley, and Jenea Boshart. 2001\.  Information scent as a driver of Web behavior graphs: results of a protocol analysis method for Web usability. In _Proceedings of the SIGCHI conference on Human factors in computing systems_. ACM, 498–505.
  * Chi et al. (2001) Ed H Chi, Peter Pirolli, Kim Chen, and James Pitkow. 2001\.  Using information scent to model user information needs and actions and the Web. In _Proceedings of the SIGCHI conference on Human factors in computing systems_. ACM, 490–497.
  * Chi et al. (2000) Ed H Chi, Peter Pirolli, and James Pitkow. 2000.  The scent of a site: A system for analyzing and predicting information scent, usage, and usability of a web site. In _Proceedings of the SIGCHI conference on Human Factors in Computing Systems_. ACM, 161–168.
  * Espín-Noboa (2018) Lisette Espín-Noboa. 2018\.  HopRank.  https://github.com/lisette-espin/HopRank Accessed: 2019-01-23.
  * Furnas (1986) George W Furnas. 1986\.  _Generalized fisheye views_. Vol. 17.  ACM.
  * Geigl et al. (2015) Florian Geigl, Daniel Lamprecht, Rainer Hofmann-Wellenhof, Simon Walk, Markus Strohmaier, and Denis Helic. 2015.  Random surfers on a web encyclopedia. In _Proceedings of the 15th International Conference on Knowledge Technologies and Data-driven Business_. ACM, 5.
  * Gorman (2004) Michael Gorman. 2004\.  Google and God’s mind.  _Los Angeles Times_ 17 (2004).
  * Haveliwala (2003) Taher H Haveliwala. 2003\.  Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search.  _IEEE transactions on knowledge and data engineering_ 15, 4 (2003), 784–796.
  * Helic et al. (2013) Denis Helic, Markus Strohmaier, Michael Granitzer, and Reinhold Scherer. 2013.  Models of human navigation in information networks based on decentralized search. In _Proceedings of the 24th ACM Conference on Hypertext and Social Media_. ACM, 89–98.
  * Hills et al. (2012) Thomas T Hills, Michael N Jones, and Peter M Todd. 2012\.  Optimal foraging in semantic memory.  _Psychological review_ 119, 2 (2012), 431.
  * Kleinberg (2002) Jon M Kleinberg. 2002\.  Small-world phenomena and the dynamics of information. In _Advances in neural information processing systems_. 431–438.
  * Musen et al. (2011) Mark A Musen, Natalya F Noy, Nigam H Shah, Patricia L Whetzel, Christopher G Chute, Margaret-Anne Story, Barry Smith, and NCBO team. 2011\.  The national center for biomedical ontology.  _Journal of the American Medical Informatics Association_ 19, 2 (2011), 190–195.
  * Noy et al. (2009) Natalya F Noy, Nigam H Shah, Patricia L Whetzel, Benjamin Dai, Michael Dorf, Nicholas Griffith, Clement Jonquet, Daniel L Rubin, Margaret-Anne Storey, Christopher G Chute, et al. 2009\.  BioPortal: ontologies and integrated data resources at the click of a mouse.  _Nucleic acids research_ (2009), gkp440.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank citation ranking: Bringing order to the web._ Technical Report. Stanford InfoLab.
  * Pirolli and Card (1999) Peter Pirolli and Stuart Card. 1999.  Information foraging.  _Psychological review_ 106, 4 (1999), 643.
  * Schwarz et al. (1978) Gideon Schwarz et al. 1978\.  Estimating the dimension of a model.  _The annals of statistics_ 6, 2 (1978), 461–464.
  * Singer et al. (2014) Philipp Singer, Denis Helic, Behnam Taraghi, and Markus Strohmaier. 2014.  Detecting memory and structure in human navigation patterns using markov chain models of varying order.  _PloS one_ 9, 7 (2014), e102070.
  * Suchanek et al. (2007) Fabian M Suchanek, Gjergji Kasneci, and Gerhard Weikum. 2007\.  Yago: a core of semantic knowledge. In _Proceedings of the 16th international conference on World Wide Web_. ACM, 697–706.
  * Tudorache et al. (2008) Tania Tudorache, Jennifer Vendetti, and Natalya Fridman Noy. 2008\.  Web-Protege: A Lightweight OWL Ontology Editor for the Web.. In _OWLED_ , Vol. 432.
  * Van Ham and Perer (2009) Frank Van Ham and Adam Perer. 2009.  “Search, show context, expand on demand”: supporting large graph exploration with degree-of-interest.  _IEEE Transactions on Visualization and Computer Graphics_ 15, 6 (2009).
  * Walk et al. (2017) Simon Walk, Lisette Espín-Noboa, Denis Helic, Markus Strohmaier, and Mark A Musen. 2017\.  How Users Explore Ontologies on the Web: A Study of NCBO’s BioPortal Usage Logs. In _Proceedings of the 26th International Conference on World Wide Web_. International World Wide Web Conferences Steering Committee, 775–784.
  * Walk et al. (2015) Simon Walk, Philipp Singer, Lisette Espín-Noboa, Tania Tudorache, Mark A Musen, and Markus Strohmaier. 2015.  Understanding how users edit ontologies: Comparing hypotheses about four real-world projects. In _International Semantic Web Conference_. Springer, 551–568.
  * Whetzel et al. (2011) Patricia L Whetzel, Natalya F Noy, Nigam H Shah, Paul R Alexander, Csongor Nyulas, Tania Tudorache, and Mark A Musen. 2011\.  BioPortal: enhanced functionality via new Web services from the National Center for Biomedical Ontology to access and use ontologies in software applications.  _Nucleic acids research_ 39, suppl_2 (2011), W541–W545.
  * Xing and Ghorbani (2004) Wenpu Xing and Ali Ghorbani. 2004.  Weighted pagerank algorithm. In _Proceedings of the Second Annual Conference on Communication Networks and Services Research, 2004._ IEEE, 305–314.