$\displaystyle=\frac{1}{|\mathcal{C}_{k}|}\mathbf{1}_{\mathcal{C}_{k}}-\frac{1}{|\mathcal{C}_{k^{\prime}}|}\mathbf{1}_{\mathcal{C}_{k^{\prime}}}$
$\displaystyle=\frac{1}{|\mathcal{C}_{k}|}\mathbf{1}_{\mathcal{C}_{k}}-\frac{1}{|\mathcal{C}_{k+1}|}\mathbf{1}_{\mathcal{C}_{k+1}}+\cdots+\frac{1}{|\mathcal{C}_{k^{\prime}-1}|}\mathbf{1}_{\mathcal{C}_{k^{\prime}-1}}-\frac{1}{|\mathcal{C}_{k^{\prime}}|}\mathbf{1}_{\mathcal{C}_{k^{\prime}}}$
$\displaystyle=\mathbf{v}_{k,k+1}+\dots+\mathbf{v}_{k^{\prime}-1,k^{\prime}}.$

Thus, we have
$\mathcal{E}\subset\mathrm{span}\left\\{\mathbf{v}_{k,k+1}:k\in[K-1]\right\\}.$
The other direction trivially holds.

We next show that $\mathbf{v}_{k,k+1}$ for $k\in[K-1]$ are linearly
independent. Suppose
$\overset{K-1}{\underset{k=1}{\sum}}\lambda_{k}\mathbf{v}_{k,k+1}=0.$ Note

$\displaystyle\overset{K-1}{\sum_{k=1}}\lambda_{k}\mathbf{v}_{k,k+1}$
$\displaystyle=\overset{K-1}{\sum_{k=1}}\lambda_{k}\left(\frac{1}{|\mathcal{C}_{k}|}\mathbf{1}_{\mathcal{C}_{k}}-\frac{1}{|\mathcal{C}_{k+1}|}\mathbf{1}_{\mathcal{C}_{k+1}}\right)$
$\displaystyle=\lambda_{1}\frac{1}{|\mathcal{C}_{1}|}\mathbf{1}_{\mathcal{C}_{1}}+\sum_{k=1}^{K-2}(\lambda_{k+1}-\lambda_{k})\frac{1}{|\mathcal{C}_{k+1}|}\mathbf{1}_{\mathcal{C}_{k+1}}-\lambda_{K-1}\frac{1}{|\mathcal{C}_{K}|}\mathbf{1}_{\mathcal{C}_{K}}.$

Define
$u\coloneqq\lambda_{1}\frac{1}{|\mathcal{C}_{1}|}\mathbf{1}_{\mathcal{C}_{1}}+\sum_{k=1}^{K-2}(\lambda_{k+1}-\lambda_{k})\frac{1}{|\mathcal{C}_{k+1}|}\mathbf{1}_{\mathcal{C}_{k+1}}-\lambda_{K-1}\frac{1}{|\mathcal{C}_{K}|}\mathbf{1}_{\mathcal{C}_{K}},$
and let $u_{j}$ denote $j$th entry of $u.$ Since
$u_{j}=\lambda_{1}\frac{1}{|\mathcal{C}_{1}|}=0$ for $j\in C_{1},$ we have
$\lambda_{1}=0.$ Then, since
${u_{j}=(\lambda_{2}-\lambda_{1})\frac{1}{|\mathcal{C}_{2}|}=\lambda_{2}\frac{1}{|\mathcal{C}_{2}|}=0}$
for $j\in\mathcal{C}_{2},$ we have $\lambda_{2}=0.$ The same argument holds
for $\lambda_{3},...,\lambda_{K-2}.$ Finally, since
$u_{j}=\lambda_{K-1}\frac{1}{|\mathcal{C}_{K}|}=0$ for $j\in\mathcal{C}_{K},$
we have $\lambda_{K-1}=0.$ Thus, $\lambda_{k}=0$ for all $k\in[K-1],$ and it
follows that $\mathbf{v}_{k,k+1}$ for $k\in[K-1]$ are linearly independent. ∎

####  A.2.2 The proposed test of Section 5.2

By Proposition 6, $S^{*}$ is a set of solutions to a system of inequalities,
where each inequality takes the form

$\displaystyle\lambda_{1}\psi+\lambda_{2}\sqrt{\psi}+\lambda_{3}\sqrt{\psi}\sqrt{\psi+r^{*}}+\lambda_{4}\sqrt{\psi+r^{*}}+\lambda_{5}\leq
0.$ (50)

In this section, we elaborate on the implementation for finding the set of
solutions to (50). Since $u\mapsto u^{2}$ on $[0,\infty)$ is a bijective map,
the set of values of $\sqrt{\psi}$ satisfying the inequality is bijective with
the set of values of $\psi$ satisfying the same inequality. Thus, we aim to
find the sub-level set of $f$ at 0, where $f:[0,\infty)\rightarrow\mathbb{R},$

$\displaystyle
f(y)=\lambda_{1}y^{2}+\lambda_{2}y+\lambda_{3}y\sqrt{y^{2}+r^{*}}+\lambda_{4}\sqrt{y^{2}+r^{*}}+\lambda_{5}.$
(51)

Define $\mathcal{A}_{f}=\\{y\in[0,\infty):f(y)=0\\}$ to be the set of non-
negative real roots of $f.$ Since $f$ is continuous, intermediate value
theorem implies that for any $y_{1}<y_{2}\in[0,\infty),$
$\mathrm{sign}(f(y_{1}))=-\mathrm{sign}(f(y_{2}))$ only if there exists
$y\in[y_{1},y_{2}]$ such that $y\in\mathcal{A}_{f},$ where $\mathrm{sign}(a)$
for $a\in\mathbb{R}$ is equal to 1 if $a>0,$ -1 if $a<0,$ and 0 if $a=0.$ Once
we compute $\mathcal{A}_{f},$ we find the set of solutions to the inequality
$f(y)\leq 0$ by checking the sign of $f$ on each interval partitioned by its
roots, i.e., the elements of $\mathcal{A}_{f}.$ To compute $\mathcal{A}_{f},$
write

$\displaystyle
f(y)=0\iff(\lambda_{3}y+\lambda_{4})\sqrt{y^{2}+r^{*}}=-\lambda_{1}y^{2}-\lambda_{2}y-\lambda_{5}$

and define $f_{1}:[0,\infty)\rightarrow\mathbb{R},$

$f_{1}(y)=(\lambda_{3}y+\lambda_{4})\sqrt{y^{2}+r^{*}}$

and $f_{2}:[0,\infty)\rightarrow\mathbb{R},$

$f_{2}(y)=-\lambda_{1}y^{2}-\lambda_{2}y-\lambda_{5}.$

Note

$\displaystyle f_{1}^{2}(y)=f_{2}^{2}(y)$
$\displaystyle\iff(\lambda_{3}y+\lambda_{4})^{2}(y^{2}+r^{*})=(\lambda_{1}y^{2}+\lambda_{2}y+\lambda_{5})^{2}$
$\displaystyle\iff(\lambda_{3}^{2}y^{2}+2\lambda_{3}\lambda_{4}y+\lambda_{4}^{2})(y^{2}+r^{*})=\lambda_{1}^{2}y^{4}+\lambda_{2}^{2}y^{2}+\lambda_{5}^{2}+2\lambda_{1}\lambda_{2}y^{3}+2\lambda_{2}\lambda_{5}y+2\lambda_{1}\lambda_{5}y^{2}$
$\displaystyle\iff\lambda_{3}^{2}y^{4}+2\lambda_{3}\lambda_{4}y^{3}+\lambda_{4}^{2}y^{2}+\lambda_{3}^{2}r^{*}y^{2}+2\lambda_{3}\lambda_{4}r^{*}y+\lambda_{4}^{2}r^{*}=\lambda_{1}^{2}y^{4}+\lambda_{2}^{2}y^{2}+\lambda_{5}^{2}+2\lambda_{1}\lambda_{2}y^{3}$
$\displaystyle\hskip
270.00041pt+2\lambda_{2}\lambda_{5}y+2\lambda_{1}\lambda_{5}y^{2}$
$\displaystyle\iff
0=(\lambda_{3}^{2}-\lambda_{1}^{2})y^{4}+2(\lambda_{3}\lambda_{4}-\lambda_{1}\lambda_{2})y^{3}+(\lambda_{4}^{2}+\lambda_{3}^{2}r^{*}-\lambda_{2}^{2}-2\lambda_{1}\lambda_{5})y^{2}$
(52)
$\displaystyle\qquad\qquad\qquad+2(\lambda_{3}\lambda_{4}r^{*}-\lambda_{2}\lambda_{5})y+\lambda_{4}^{2}r^{*}-\lambda_{5}^{2},$

which is a quartic equation in $y.$ We then solve for $\mathcal{A}_{f}$ by
checking the condition $f_{1}(y)=f_{2}(y)$ for each
$y\in\\{y\in[0,\infty):f_{1}^{2}(y)=f_{2}^{2}(y)\\}.$

We use the `R` base function `polyroot` to solve for the roots of the quartic
equality in (52). We now briefly discuss how we address finite precision in
our implementation in the rest of the procedure. For determining whether a
root is real, i.e., if its imaginary part is 0, and for checking if the
condition $f_{1}(y)=f_{2}(y)$ is satisfied, we use a relatively large
tolerance level of 1—note that having additional values in $\mathcal{A}_{f}$
leads to a finer partition of the interval, which does not alter the output of
the procedure for computing the set of solutions to (51). To determine if
there is multiplicity for a root, we use the function `almost.unique` from the
package `bazar` with a stringent threshold of $10^{-30}$ to avoid losing any
root of $f.$

####  A.2.3 Simulations of Section 6

Note that the tests proposed throughout this paper, as well as those of Chen
and Witten [2023], assume that the $K$-means algorithm outputs $K$ clusters at
each iteration of the algorithm, an assumption implicitly made in the
characterization of the truncation sets $\mathcal{S}_{\sigma,k,k^{\prime}}$ in
(6), $\mathcal{S}_{\sigma}$ in (9), and $\mathcal{S}^{*}$ in (19). Thus, the
tests cannot be applied with theoretical guarantees if $K$-means clustering
outputs a different number of clusters at any iteration of the algorithm.

However, there are instances in practice where the algorithm produces a
different number of clusters at the final step than that at the initial step.
We omit such cases in our simulations, having the corresponding functions
return `NA` for the p-value, and only the outputs that are not `NA` are
reflected in the QQ plots and the computation of the empirical powers. We have
observed that the number of instances of this phenomenon is small compared to
the number of p-values generated.


# Modal Semantics for Reasoning with Probability and Uncertainty

Nino Guallart

###### Abstract

This paper belongs to the field of probabilistic modal logic, focusing on a
comparative analysis of two distinct semantics: one rooted in Kripke semantics
and the other in neighbourhood semantics. The primary distinction lies in the
following: The latter allows us to adequately express belief functions (lower
probabilities) over propositions, whereas the former does not. Thus,
neighbourhood semantics is more expressive. The main part of the work is a
section in which we study the modal equivalence between probabilistic Kripke
models and a subclass of belief neighbourhood models, namely additive ones. We
study how to obtain modally equivalent structures.

Keywords: Neighbourhood semantics, Kripke semantics, Dempster-Shafer belief
function, probability, modal logic.

##  1 Introduction

The convergence of probability theory and modal logic has garnered significant
attention across multiple disciplines. Probabilistic modal logic has been the
object of intense research in these fields over the last few decades. Authors
such as Nilsson nilsson1986probabilistic (28), Bacchus bacchus1991representing
(4), Fagin and Halpern halpern1992two (18, 17, 10, 13, 11), Aumann
aumann1995backward (2, 3), Samet, Heifetz and Mongin heifetz1998modal (20, 19,
21) have applied modal logic for the formalisation of subjective probability
in different fields: economics, artificial intelligence or philosophy of
science. The basic idea is to develop a probability space within some kind of
structure, with Kripke models being the most obvious choice. Modal semantics
allows the combination of probability with other modal operators, and hence
its applicability to different kinds of modal logics such as epistemic logic
or dynamic epistemic logic kooi2003probabilistic (24).

The idea of generalising probability is not new and early works on lower
probabilities can be dated to Keynes keynes1921treatise (23) and Koopman
koopman1940bases (25). In this work, however, we will focus on belief
functions, probably the most known generalisation of probability, developed
from the works of Dempster dempster1967upper (8) and Shafer
shafer1976mathematical (31). There is also an extensive work on logic for
belief functions: Sossai sossai1999belief (35, 36) Ruspini (ruspini1986logical
(30) and Smets smets1988belief (33, 34) have developed works in the field. A
remarkable point is the similarity between modal epistemic logics and
Dempster-Shafer’s belief functions, which has been studied since the late 80’s
fine1988lower (14) boeva1998modelling (5)111See fine1988lower (14) for a
comprehensive description of different works in the area.. We are mainly
interested in the interpretation of belief functions as generalisation of
probability, leaving aside the interpretation of Dempster-Shafer theory as a
theory of evidence. Some approaches to the topic, such as
flaminio2011reasoning (15, 9, 16), esteva2000reasoning (9) focus on the
uncertainty of fuzzy events.

Goals and structure of this work. The purpose of this work is to develop a
neighborhood semantics for belief functions that is modally equivalent to
Kripke structures with probability, making the latter a subclass of
neighbourhood structures. The structure of the paper is as follows: Section 2
offers a summary of the main theoretical concepts in probability that will be
used. This work develops a modal logic for probability and belief functions
and two semantics for it: in section 3 we introduce the syntax of the
language, and then we focus on two possible semantics for it: We first develop
a standard Kripke semantics 4.1, and then a semantics based in neighbourhood
semantics 4.2. We make a study of several issues related to the structure of
the system of neighbourhoods in section 5, which will be used in section 6,
where it is studied the correspondence between probabilistic Kripke models and
a subclass of belief neighbourhood models, additive ones. It is based on the
proofs of the relationship between augmented neighbourhood models and Kripke
models. Thus we will compare them, observing their differences in
expressiveness. Section 7 concludes the paper.

##  2 Basic concepts

Subjective probability is an agent’s estimate or belief about the likelihood
of an event. In this work, we will use propositional formulas to represent
events using atomic and compound propositions, while modal operators ranging
over propositions will serve to represent the agent’s degrees of belief.
Probability is defined over $\sigma$-algebras, but here we will work over
Boolean algebras.

###### Definition 1

(Probability measure on a Boolean algebra.) Given a Boolean algebra
$\mathcal{A}$, the probability measure $pr\colon\mathcal{A}\to[0,1]$ is a
function that satisfies the following axioms:

  1. 1.

$pr(A)\geqslant 0$ for any $A\in\mathcal{A}$.

  2. 2.

$pr(\top)=1$.

  3. 3.

Finite additivity: $pr(\bigcup_{i=1}^{n}A_{i})=\sum_{A_{i}=1}^{n}pr(A_{i})$,
for a family of pairwise disjoint events $\\{A_{i}\\}_{i=1}^{n}$,
$n\in\mathbb{N}$.

For $\sigma$-algebras in general, the third axiom is stated for countable
sets: $pr(\bigcup_{i=1}^{\infty}A_{i})=\sum_{A_{i}=1}^{\infty}pr(A_{i})$.

Belief functions are a generalisation of subjective probabilities
halpern1992two (18). The following definition is taken from corsi2023logico
(7), which is an adaptation to Boolean algebras of the definition in
shafer1976mathematical (31):

###### Definition 2

(Belief function on a Boolean algebra.) A belief function on a Boolean algebra
$A$ is a function $bel\colon A\to[0,1]$ satisfying:

  1. 1.

$bel(\top)=1$ and $bel(\bot)=0$.

  2. 2.

$bel(A)\geqslant 0$ for any $A\in\mathcal{A}$.

  3. 3.

Superadditivity:
$bel(\bigcup_{i=1}^{n}A_{n})=\sum_{i=1}^{n}\sum_{J\subseteq\\{1,\ldots,n\\}:|J|=i}(-1)^{i+1}bel(\bigcap_{j\in
J}A_{j})$

The last condition is also called monotonicity. It can be seen as a weakened
form of additivity. Belief functions are a subset of a broader family, lower
probabilities. For the purposes of this work, it is sufficient to know that
lower probabilities encompass belief functions, that the lower probability of
$\top$ is 1, and the lower probability of $\bot$ is 0, whereas monotonicity is
not met, but a more general condition instead halpern1992two (18). Lower
probabilities and belief functions can be seen as the lower bound of a set of
probabilities, that is, stating $bel(A)=\alpha$ entails that all probabilities
for $A$ greater than or equal to $\alpha$ are compatible with that belief
function. From now on, when the term “lower probabilities” in mentioned in
this work, it actually refers to belief functions as described above.

The following remark, that is a consequence of the previous definitions. will
be one of the central ideas of this paper.

###### Remark 1

(Probability functions and belief functions.) A probability function is an
additive belief function (an additive lower probability). corsi2023logico (7)

As we will see, whereas Kripke semantics is able to interpret probabilities
directly, in neighbourhood semantics they are a special case of belief
functions. Neighbourhood semantics thus offers a broader expressiveness than
Kripke semantics.

##  3 Syntax of $\mathcal{L}_{PR}$

We now develop a modal propositional language to express probabilistic
beliefs. It is a variation of works such as fagin1988reasoning (13),
heifetz2001probability (19), aumann1999interactive (3), and other similar
works, although with a different notation. At will denote a non-empty finite
set of atomic propositions.

###### Definition 3

(Syntax.) We define recursively the formulas of the language
$\mathcal{L}_{PR}$ as follows, where $p\in\texttt{At}$:

$\phi::=p\ |\ \neg\phi\ |\ (\phi\lor\phi)\ |\ B_{\geqslant\alpha}\phi\ |\
\underline{B}_{\geqslant\alpha}\phi$

The usual equivalences hold: $\phi\land\psi$ stands for
$\neg(\neg\phi\lor\neg\psi)$, and $\top$ and $\bot$ are for $\phi\lor\neg\phi$
and $\phi\land\neg\phi$. $\alpha\in[0,1]$ is a rational value.
$B_{\geqslant\alpha}\phi$ is read in the same way that $L_{\alpha}$ in
heifetz2001probability (19): “ _the agent assigns to $\phi$ a probability
equal to or greater than $\alpha$ (at least $\alpha$)”_. Similarly
$B_{\leqslant\alpha}\phi$ is shorthand for $B_{\geqslant 1-\alpha}\neg\phi$,
which is read as “ _the agent assigns to $\phi$ a probability at most
$\alpha$_”. $B_{=\alpha}\phi$, “ _the agent assigns to $\phi$ a probability of
(exactly) $\alpha$_”, is just $B_{\geqslant\alpha}\phi\land
B_{\leqslant\alpha}\phi$. $B_{<\alpha}\phi$ is $\neg B_{\geqslant\alpha}\phi$
and $B_{>\alpha}\phi$ is $\neg B_{\geqslant 1-\alpha}\neg\phi$.

Analogously, $\underline{B}_{=\alpha}\phi$ refers to a belief function, which
can be understood as a lower probability, and could be read as “ _the agent
assigns a lower probability of $\alpha$ to $\phi$_”, or more informally as “
_the agent considers that the probability of $\phi$ is at least $\alpha$_”
(that is, $\alpha$ is the lower probability of $\phi$).
$\underline{B}_{\geqslant\alpha}\phi$ has a rather complicated translation, as
“ _the agent assigns a lower probability to $\phi$, which is at least
$\alpha$_”. $\underline{B}_{\leqslant\alpha}\phi$,
$\underline{B}_{>\alpha}\phi$ and $\underline{B}_{<\alpha}\phi$ are defined as
their probability counterparts.

##  4 Semantics of $\mathcal{L}_{PR}$

###  4.1 Kripke semantics

Works on Kripkean semantics for probabilistic modal logic such as
shirazi2007probabilistic (32) define a probability distribution over the
worlds that are accessible from a certain world $w$, and it is the type of
semantics that we will develop here. Fagin and Halpern fagin1990logic (12)
provide another approach, a probability distribution defined for measurable
_sets_ of accessible worlds in a Kripke model.

###### Definition 4

(Probabilistic Kripke model.) A probabilistic Kripke model
$\mathcal{M}^{P}_{K}$ is a tuple $\langle W,\mu,R,v\rangle$, where $W$ is a
non-empty and finite set of worlds or states, $v\colon\texttt{At}\to\wp(W)$ a
valuation function that assigns to each letter the set of worlds in $W$ that
satisfy it, $\mu:W\times W\to[0,1]$ a probability function following these
rules for a given $w$:

  1. 1.

$\mu(w,w^{\prime})\geqslant 0$

  2. 2.

$\sum_{w_{i}\in W}\mu(w,w_{i})=1$

$R\colon W\times W$ is defined in this way: $(w,w^{\prime})\in R$ (usually
stated as $wRw^{\prime}$) iff $\mu(w,w^{\prime})>0$, and $(w,w^{\prime})\notin
R$ iff $\mu(w,w^{\prime})=0$.

The definition of $R$ and the requirement that $\sum_{w_{i}\in
W}\mu(w,w^{\prime})=1$ entail that for every $w$ there is at least one
$w^{\prime}$ such that $wRw^{\prime}$. Neither $R$ nor $\mu$ are symmetric: In
general, $\mu(w,w^{\prime})\neq\mu(w^{\prime},w)$ and $wRw^{\prime}$ does not
equate to $w^{\prime}Rw$.

###### Remark 2

($R$ and $\mu$:) The accessibility relationship $R$ is not strictly necessary,
since it is implicit in the probability measure $\mu$. We have included it for
simplifying some explanations.

###### Definition 5

(Probability and belief measures in Kripke frames.) Given a $X\subseteq W$, we
define its probability and belief measures from world $w\in W$ as follows:

$pr(w,X)=bel(w,X)=\sum_{w_{i}\in X}\mu(w,w_{i})$

A pointed model is a pair $\langle M,w\rangle$ with $M$ a model and $w$ an
world of its domain $W$. We will write $M,w\models_{K}\phi$ if the formula
$\phi$ is true at the world $w\in W$ in Kripke model $M$. We assign truth
values to formulas at a certain world as follows:

###### Definition 6

(Interpretation of $\mathcal{L}_{PR}$ in probabilistic Kripke models.) Given a
probability Kripke model $\mathcal{M}^{P}_{K}$, the satisfaction relation
$\models_{K}$ between pointed models and formulas is defined as follows:

  1. 1.

$\mathcal{M}^{P}_{K},w\models_{K}p$ iff $w\in v(p)$.

  2. 2.

$\mathcal{M}^{P}_{K},w\models_{K}\neg\phi$ iff
$\mathcal{M}^{P}_{K},w\not\models\phi$.

  3. 3.

$\mathcal{M}^{P}_{K},w\models_{K}(\phi\lor\psi)$ iff
$\mathcal{M}^{P}_{K},w\models\phi$ or $\mathcal{M}^{P}_{K},w\models\psi$.

  4. 4.

$\mathcal{M}^{P}_{K},w\models_{K}B_{\geqslant\alpha}\phi$ iff
$pr(w,\llbracket\phi\rrbracket_{M})\geqslant\alpha$

  5. 5.

$\mathcal{M}^{P}_{K},w\models_{K}\underline{B}_{\geqslant\alpha}\phi$ iff
$bel(w,\llbracket\phi\rrbracket_{M})\geqslant\alpha$

$\llbracket\phi\rrbracket_{\mathcal{M}^{P}_{K}}$ denotes the set $\\{w\in W\
|\ M,w\models_{K}\phi\\}$. We simply use $\llbracket\phi\rrbracket_{M}$ or
$\llbracket\phi\rrbracket$ if there is there no possibility of confusion. The
interpretation of the probabilistic modal operator we have just defined is
close to previous works in subjective probabilities (shirazi2007probabilistic
(32) for example), and formally it is close to probabilistic labelled
transition systems LARSEN19911 (26).

###### Definition 7

(Logical consequence and logical equivalence in probabilistic Kripke models.)
A formula $\psi$ is a logical consequence of $\phi$ in probabilistic Kripke
models if for all pointed models such that $\mathcal{M}^{P}_{K},w\models\phi$,
it is also that $\mathcal{M}^{P}_{K},w\models\psi$. $\phi$ and $\psi$ are
logically equivalent in probabilistic Kripke models provided that, for all
pointed models, $\mathcal{M}^{P}_{K},w\models\phi$ if and only if
$\mathcal{M}^{P}_{K},w\models\psi$.

###### Remark 3

(Events and propositions.)  We can identify each event with the set of all
logically equivalent propositions, instead of with propositions. Thus, if
$\phi$ and $\psi$ are logically equivalent, for any Kripke model and any world
in it, $\mathcal{M}^{P}_{K},w\models B_{\geqslant\alpha}\phi$ if and only if
$\mathcal{M}^{P}_{K},w\models B_{\geqslant\alpha}\psi$.

###### Remark 4

(Equivalence between probabilities and belief functions in
$\mathcal{L}_{PR}$.)  Given that the conditions for the satisfaction of
$B_{\geqslant\alpha}\phi$ and $\underline{B}_{\geqslant\alpha}\phi$ are the
same, they are logically equivalent. This is not surprising, since
probabilities are a kind of belief functions 1. However, we cannot adequately
interpret a formula whose interpretation is a belief function which is not a
probability. Since we are going to study the relationship between Kripke and
neighbourhood semantics for $\mathcal{L}_{PR}$, we have included the operator
$\underline{B}_{\geqslant\alpha}$ in order to ensure that both semantics
interpret all the formulas of the same language.

###### Example 1

(Example 1: A simple probabilistic Kripke model.)

Let us define $W=\\{w_{1},w_{2},w_{3},w_{4}\\}$. $\mu\colon W\times W$ is
defined in the following matrix, where $M(\mu)_{i,j}=\mu(w_{i},w_{j})$ (for
example, $\mu(w_{1},w_{2})=M(\mu)_{1,2}=0.4$):

$M(\mu)_{ij}=\footnotesize{\begin{pmatrix}0&0.4&0.6&0\\\ 0.4&0&0.6&0\\\
0&0&0.1&0.9\\\ 0&0&0&1\\\ \end{pmatrix}}$

It can be verified that the sum of each row is 1. We add a valuation function
such that $v(p)=\\{w_{1},w_{3}\\}$ and $v(q)=\\{w_{1},w_{2}\\}$. In the
picture belowe, we have omitted the relationships when $\mu$ is 0.

$w_{1}$$w_{2}$$w_{3}$$w_{4}$$p,q$$p$$q$$0.4$$0.6$$0.4$$0.6$$0.9$$0.1$$1$

Picture 1. Example of probabilistic Kripke model.

We have that $R(w_{1})=\\{w_{2},w_{3}\\}$. In this model,
$M,w_{1}\models_{K}B_{\geqslant 0.6}p$ and
$M,w_{1}\models_{K}B_{1}B_{\geqslant 0.1}p$.

###  4.2 Neighbourhood semantics

###### Example 2

(Example 2: Expressing bounded probabilistic beliefs.)

Probability modal logic is commonly used for expressing beliefs with a certain
degree, but its formulation in natural language may be misleading. For
example, if $r$ means that it will rain tomorrow, $B_{\geqslant 0.5}r$ is
understood as “Ann believes that the probability of raining tomorrow is at
least 50% (i.e. 0.5)”, where the modal operator is used to express the graded
beliefs of the agent we are considering, namely Ann. However, the
interpretation of the modal formula according to the previous definition is
not exactly what has been expressed in natural language. $B_{\geqslant 0.5}r$
actually means that Ann believes with a certain degree of confidence that it
will rain tomorrow, and that degree is at least 0.6: There is a definite
probability value, which is at least 0.5.

“Ann believes that the probability of raining tomorrow is at least 50%” is
usually interpreted in natural language as a lower probability: Ann is
considering that the probability of raining cannot be lower than 50%, but she
does not have a definite value, and therefore all values above 50% are
compatible with her belief. If we see the model in Example 1, $w_{1}$
satisfies $B_{\geqslant 0.5}r$. If we try to express a lower probability by
stating $B_{\geqslant 0.5}r\land\neg B_{>0.5}r$, $w_{1}$ does not satisfy that
formula, which actually expresses that the agent believes that the probability
of raining is exactly 50%. Thus, we need another semantics for interpreting
lower probabilities.

A possible alternative to Kripke semantics is neighbourhood semantics. It is
better suited for non-normal logic, and probabilistic modal logic is a
monotonic, non-normal modal logic. Neighbourhood semantics for probability
modal logic are much rarer than Kripke semantics: Arló-Costa arlo2005non (1)
proposed a model for a non-normal high probability operator, and Herzig
herzig2003modal (22) offered a qualitative interpretation of the modal
operator.

We briefly recall a few preliminary definitions of neighbourhood semantics:

###### Definition 8

(Neighbourhood frame and neighbourhood model.)  A _neighbourhood frame_ is the
ordered pair $\langle W,N\rangle$ formed by a non-empty and finite set $W$ and
a neighbourhood function over it $N:\ W\to\wp(\wp(W))$ that assigns a set of
subsets of $W$ to each $w\in W$. Given a neighbourhood frame $\langle
W,N\rangle$ and a set of atomic propositional formulas At with a valuation
function $v:\ \texttt{At}\to\wp(W)$, a _neighbourhood model_ is a triple
$M=\langle W,N,v\rangle$.

In neighbourhood semantics, $M,w$ satisfies $\square\phi$ if
$\llbracket\phi\rrbracket_{M}\in N(w)$, that is, if the set formed by all
worlds that satisfy $\phi$ is one of the sets in the neighbourhood of $w$.

###### Definition 9

(Some properties of neighbourhoods.) These are some properties that
neighbourhoods may have:

  1. 1.

A neighbourhood is _monotonic_ if $X\in N(w)$ and $X\subseteq Y$ entails $Y\in
N(w)$.

  2. 2.

A neighbourhood is closed under finite intersections provided that for a
family of sets $\\{X_{i}\\}_{i\in J}$ such that for each $i\in J$ ($J$
finite), $X_{i}\in N(w)$, then $\bigcap\\{X_{i}\\}_{i\in J}\in N(w)$.

  3. 3.

A neighbourhood is closed under finite unions provided that for a family of
sets $\\{X_{i}\\}_{i\in J}$ such that for each $i\in J$ ($J$ finite),
$X_{i}\in N(w)$, then $\bigcup\\{X_{i}\\}_{i\in J}\in N(w)$.

  4. 4.

A neighbourhood is closed under complement provided that for each $X\in N(w)$,
$X^{C}\in N(w)$.

  5. 5.

A neighbourhood $N(w)$ _contains its core_ $\cap N(w)$ if the core of the
neighborhood, the intersection of all sets in $N(w)$, is a set in $N(w)$.

  6. 6.

A monotonic neighbourhood that contains its core is said to be _augmented_.

A high-probability modal operator is monotonic ($P(\phi\land\psi)\to
P\phi\land P\psi$ / $P\phi\lor P\psi\to P(\phi\lor\psi)$ is a valid axiom
scheme), where “high probability” refers to a probability higher than a given
threshold. However, this axiom can be generalised for any probability, We will
consider a belief function operator, intended to be a lower probability
operator. To define the neighbourhood semantics of our modal probabilistic
operator, we will add a probabilistic metrics. We will combine the previous
idea of the high probability operator with a set of nested neighbourhoods,
akin to Lewis’ sphere model in lewis1973 (27), one for each probability. We
will also add a belief function.

###### Definition 10

(Belief neighbourhood model.) A tuple $\mathcal{M}^{B}_{N}=\langle W,b,$
$\\{N_{\geqslant\alpha}\\}_{\alpha\in[0,1]},$
$\\{N_{>\alpha}\\}_{\alpha\in[0,1)},$ $v\rangle$ is a belief neighbourhood
model if $W$ is a non-empty, finite set of worlds, $N$ a neighbourhood
function $W\to\wp(\wp(W))$, $b$ a belief function $W\times\wp(W)\to[0,1]$, and
$v\colon\texttt{At}\to W$ a valuation function.

###### Definition 11

(Belief function in $N(w)$.) The function $b:W\times\wp(W)\to[0,1]$ assigns a
value to each $X\in N_{\geqslant 0}(w)$, satisfying:

  1. 1.

$b(w,W)=1$, $b(w,\varnothing)=0$.

  2. 2.

$bel(w,\bigvee_{i=1}^{n}\phi_{n})\geqslant\sum_{i=1}^{n}\sum_{J\subseteq\\{1,\ldots,n\\}:|J|=i}(-1)^{i+1}bel(w,\bigwedge_{j\in
J}\phi_{j})$

###### Definition 12

(Monotonicity of in $N_{\geqslant\alpha}(w)$.) All $N_{\geqslant\alpha}(w)$
are monotonic: If $X\in N_{\geqslant\alpha}(w)$ and $X\subseteq Y$, then
$Y\subseteq N_{\geqslant\alpha}(w)$.

###### Definition 13

($N_{\alpha}(w)$ and $b(w,X).)$ For all $w\in W$, if $b(w,X)\geqslant\alpha$,
then $X\in N_{\geqslant\alpha}(w)$, and if $b(w,X)>\alpha$, then $X\in
N_{>\alpha}(w)$.

###### Proposition 1

(Nesting of neighbourhoods.) From the previous definitions, the system of
nested neighbourhoods is established in this way:

  1. 1.

If $\alpha\geqslant\beta$, then $N_{\geqslant\alpha}(w)\subseteq
N_{\geqslant\beta}(w)$.

  2. 2.

$N_{>\alpha}(w)\subseteq N_{\geqslant\alpha}(w)$.

  3. 3.

If $\alpha>\beta$, then $N_{\geqslant\alpha}(w)\subseteq N_{>\beta}(w)$.

###### Remark 5

(A remark about the relationship between $N_{\geqslant\alpha}(w)$ and
$b(w,X)$.) Analogously to 2, the system of nested neighbourhoods
$N_{\geqslant\alpha}$ is not strictly necessary. We could develop it just by
using the belief measure $b$. If we did so, however, we should redefine
neighbourhood semantics’ concepts in terms of a _neighbourhood measure_ , and
all the concepts we are going to introduce here should be formulated in those
terms.

Since $b(w,\varnothing)=0$ for all $w\in W$, then $\varnothing\in N_{\geqslant
0}(w)$. Therefore, all subsets of $W\in N_{\geqslant\alpha}(w)$. In practice,
we are only interested in the sets that correspond to the truth set of some
$\phi$. Thus, for any $w\in$ and any formula $\phi$,
$\llbracket\phi\rrbracket_{M}\in N_{\geqslant 0}(w)$. If
$\beta=b(w,\llbracket\phi\rrbracket_{M})$, then
$\llbracket\phi\rrbracket_{M}\in N_{\geqslant\alpha}(w)$ for all
$\alpha\leqslant\beta$. In order to do that, we must define the semantics of
the model.

###### Definition 14

(Semantics in belief neighbourhood models.)

Given a belief neighbourhood model $\mathcal{M}^{B}_{N}$, the satisfaction
relation $\models_{N}$ between pointed models and formulas is defined as
follows:

  1. 1.

$\mathcal{M}^{B}_{N},w\models p$ iff $w\in v(p)$.

  2. 2.

$\mathcal{M}^{B}_{N},w\models\neg\phi$ iff
$\mathcal{M}^{B}_{N},w\not\models\phi$.

  3. 3.

$\mathcal{M}^{B}_{N},w\models(\phi\lor\psi)$ iff
$\mathcal{M}^{B}_{N},w\models\phi$ or $\mathcal{M}^{B}_{N},w\models\psi$.

  4. 4.

$\mathcal{M}^{B}_{N},w\models\underline{B}_{\geqslant\alpha}\phi$ iff
$\llbracket\phi\rrbracket\in N(w)$ and
$b(w,\llbracket\phi\rrbracket)\geqslant\alpha$.

  5. 5.

$\mathcal{M}^{B}_{N},w\models\underline{B}_{>\alpha}\phi$ iff
$\llbracket\phi\rrbracket\in N(w)$ and $b(w,\llbracket\phi\rrbracket)>\alpha$.

The following definition derives from the previous one:

  6. 6.

$\mathcal{M}^{B}_{N},w\models B_{\geqslant\alpha}\phi$ iff
$\llbracket\phi\rrbracket\in N(w)$ and
$b(w,\llbracket\phi\rrbracket)\geqslant\alpha$ and
$b(w,\llbracket\neg\phi\rrbracket)_{M}+b(w,\llbracket\phi\rrbracket)_{M}=1$.

A special case of the latter is $\mathcal{M}^{B}_{N},w\models
B_{=\alpha}\phi$, which is $b(w,\llbracket\phi\rrbracket)_{M}=\alpha$.
$b(w,\llbracket\neg\phi\rrbracket)_{M}=1-\alpha$ according to the last
definition.

$\llbracket\phi\rrbracket_{\mathcal{M}^{B}_{N}}$ denotes the set $\\{w\in W\
|\ M,w\models_{N}\phi\\}$. Again, we will denote it by
$\llbracket\phi\rrbracket_{M}$ or $\llbracket\phi\rrbracket$ is there no
possibility of confusion about the semantics we are using.

###### Definition 15

(Logical consequence and logical equivalence in belief neighbourhood models.)
A formula $\psi$ is a logical consequence of $\phi$ if for all belief
neighbourhood pointed models $\mathcal{M}^{B}_{N},w$ that satisfy $\phi$, it
is also that $\mathcal{M}^{B}_{N},w\models_{K}\psi$. $\phi$ and $\psi$ are
logically equivalent provided that, for all pointed belief neighbourhood
models, $\mathcal{M}^{B}_{N},w\models_{K}\phi$ if and only if
$\mathcal{M}^{B}_{N},w\models_{K}\psi$.

###### Remark 6

(Probabilities and belief functions in neighbourhood models.)  In
neighbourhood semantics, $\underline{B}_{\geqslant\alpha}\phi$ is a logical
consequence of $B_{\geqslant\alpha}\phi$. The converse is not true, so
therefore they are not logically equivalent.

###### Proposition 2

Some properties of the set of nested neighbourhoods in the belief
neighbourhood model are the following:

  1. 1.

$N_{\geqslant 0}(w)$ and $N_{1}(w)$ are the only neighbourhoods that contain
their respective cores ($\varnothing$ for $N_{\geqslant 0}(w)$). Since all
neighbourhoods are monotonic, $N_{\geqslant 0}(w)$ and $N_{1}(w)$ are
augmented.

  2. 2.

$N_{\geqslant 0}(w)$ and $N_{1}(w)$ are the only neighbourhoods that are
closed under intersection, complement and union.

  3. 3.

$N_{\geqslant 0}(w)$ is also the only one in which $W$ and $\varnothing$
belong to the neighbourhood.

###### Example 3

(Example 2: A belief neighbourhood model.)

$W=\\{w_{1},w_{2},w_{3},w_{4}\\}$. In the following table, we show the truth
sets in $N_{\geqslant 0}(w_{1})$ and their belief value. For readability, we
write $b(X)$ instead of $b(w_{1},X)$. We define just the neighbourhood of
$w_{1}$:

$b(w_{1},W)$ = 1 |  |  |  |
---|---|---|---|---
$b(W\backslash\\{w_{1}\\})$ = 0.9 |  $b(w_{1},W\backslash\\{w_{2}\\})$ = 0.7 |  $b(W\backslash\\{w_{3}\\})$ = 0.6 |  $b(W\backslash\\{w_{4}\\})$ = 0.6 |
$b(\\{w_{1},w_{2}\\})$ = 0.2 |  $b(\\{w_{1},w_{3}\\})$ = 0.3 |  $b(\\{w_{4}\\})$ = 0.4 |  |
$b(\\{w_{2},w_{3}\\})$ = 0.4 |  $b(,\\{w_{2},w_{4}\\})$ = 0.5 |  $b(w_{3},\\{w_{4}\\})$ = 0.6 |  |
$b(\\{w_{1}\\})$ = 0.1 |  $b(\\{w_{2}\\})$ = 0.1 |  $b(\\{w_{3}\\})$ = 0.2 |  $b(\\{w_{4}\\})$ = 0.3 |
$b(\\{\\})$ = 0 |  |  |  |

Table 1. Example of neighbourhood frame (only $b(w_{1},X)$).

We can verify that $b$ is superadditive: For example,
$b(w_{1},\\{w_{1},w_{2},w_{3},w_{4}\\})=1\geqslant
b(w_{1},\\{w_{1},w_{2}\\})+b(w_{1},\\{w_{3},w_{4}\\})=0.2+0.6$.

If we add a valuation, we obtain a model. Let us make
$\\{w_{3},w_{4}\\}=\llbracket p\rrbracket_{M}$. $b(w_{1},\llbracket
p\rrbracket_{M})=0.7$, and we have that $M,w_{1}\models\underline{B}_{0.7}p$.

##  5 The non-monotonic core of $N_{>0}(w)$

This section provides a characterisation of the sets in the nested
neighbourhoods in terms of disjoint unions of certain sets that we will call
elementary sets. In particular, we will see the relationship between the core
of $N_{1}(w)$ and these sets, which are the sets in $N_{\geqslant 0}(w)$ that
are closed under the inclusion relation in that neighbourhood. This will be
especially useful in the next section for the proofs of the equivalence
between a certain subclass of additive belief neighbourhood models and
probabilistic Kripke frames. The following two definitions are taken from
pacuit2017neighborhood (29):

###### Definition 16

(Non-monotonic core.) The non-monotonic core of a neighbourhood $N(w)$,
denoted $N(w)^{\mathcal{NC}}$, is a subset of $N(w)$ defined as follows:

$N(w)^{\mathcal{NC}}=\\{X\in N(X)\ |\ \text{For all }X^{\prime}\subseteq
W\text{, if }X^{\prime}\subset X,X^{\prime}\notin N(w)\\}$

$N(w)^{\mathcal{NC}}$ contains the subset of minimal elements in $N(w)$ under
the subset relationship. Regarding our system of nested neighbourhoods, we
have the following: From the definition of non-monotonic core, it is immediate
that $N_{\geqslant 0}(w)^{\mathcal{NC}}$ contains just the empty set, whose
belief measure is 0, and $N_{1}(w)^{\mathcal{NC}}$ contains just $\cap
N_{1}(w)$.

###### Definition 17

(Core complete.) A monotonic neighbourhood $N(w)$ is core-complete if for all
$X\in N(w)$, there is some $X^{\prime}\in N(w)^{\mathcal{NC}}$ such that
$X^{\prime}\subseteq X$.

A neighbourhood is core-complete if every set in it has a subset in the non-
monotonic core of the neighbourhood. If a certain $N(w)$ is monotonic and
contains a finite number of sets, it is core-complete pacuit2017neighborhood
(29).

In this work, we are dealing with a finite $W$, so the previous comment
applies in particular to all nested neighbourhoods:

###### Proposition 3

All nested neighbourhoods $N_{\geqslant\alpha)}(w)$ ($\alpha\in[0,1]$) and
$N_{>\alpha)}(w)$ ($\alpha\in[0,1)$) are core-complete.

We are going to use the previous concepts to study the core of $N_{1}(w)$ in
terms of the sets in the non-monotonic core of $N_{>0}(w)$.

$N_{\geqslant 0}(w)^{\mathcal{NC}}$ contains just one set, the empty set.
$N_{>0}(w)^{\mathcal{NC}}$ is the subset of $N_{>0}(w)$ formed by the sets in
$N_{\geqslant 0}(w)$ whose belief function is greater than 0 and do not have
subsets. We will call the sets in $N_{>0}(w)^{\mathcal{NC}}$ _elementary
sets_.

###### Lemma 1

The elementary sets in $N_{>0}(w)^{\mathcal{NC}}$ are pairwise disjoint.

###### Proof

The sets in a non-monotonic core are closed under the subset relation.

The following lemma is immediate, given that $N_{>0}(w)$ is core-complete:

###### Lemma 2

Any $X\in N_{>0}(w)$, have as a subset the disjoint union of some elementary
sets in $N_{>0}^{\mathcal{NC}}(w)$.

We introduce the following definition:

###### Definition 18

(Interior of a set in $N_{\geqslant 0}(w)$.) We define the interior of a set
$X\in N_{\geqslant 0}(w)$ as the union of all the sets in the maximal set of
elementary sets of $X$, that is, the set that contains all elementary sets
that are subsets of $X$:

$\mathtt{int}_{N}(X)=\bigcup_{E_{i}\subseteq X,E_{i}\in
N_{>0}(w)^{\mathcal{NC}}}E_{i}$

We have chosen the name by analogy with the concept of interior in topology,
although the concept is not the same, since the elementary sets mentioned here
are not open spaces. This maximal subset will allow us to define $b(w,X)$ in
terms of the belief functions of the elementary sets in the maximal subset,
given that the belief function is superadditive, and the elementary sets are
pairwise disjoint.

###### Proposition 4

(Belief function of a set $X\in N_{>0}(w)$.) Given some $X\in N_{>0}(w)$,
$b(w,X)\geqslant\mathtt{int}_{N}(X)$

If the maximal subset is empty, $b(w,X)=0$.

###### Proposition 5

$\cap N_{1}(w)$ is equal to the disjoint union of all elementary sets in
$N_{>0}(w)^{\mathcal{NC}}$.

###### Proof

By lemma 2, $\cap N_{1}(w)$ has a a maximal subset of elementary sets, whose
union is $\texttt{int}_{N}(\cap N_{1}(w))$. We must prove that all
$w_{i}\in\cap N_{1}(w)$ belongs to some elementary set. If this were not the
case, then $x_{i}\in A$ for some set $A$ such that $b(w,A)=0$. In this case
$b(w,\cap N_{1}(w)\backslash A)=1$, and being disjoint $A$ and $\cap
N_{1}(w)\backslash A$, then $b(w,A)+b(w,\cap N_{1}(w)\backslash A)=1$. but
this would mean that $\cap N_{1}(w)\subseteq(\cap N_{1}(w)\backslash A)$ and
$(\cap N_{1}(w)\backslash A)\subseteq\cap N_{1}(w)$, that is, $\cap
N_{1}(w)=\cap N_{1}(w)\backslash A$. Therefore, $A$ is empty and all worlds in
$\cap N_{1}(w)$ belong to some elementary set. Now we must prove that all
elementary sets are subsets of $\cap N_{1}(w)$. Let us suppose that there is
an elementary set $E_{i}\not\subseteq\cap N_{1}(w)$. We have that $b(w,\cap
N_{1}(w)\cup E_{i})\geqslant b(w,\cap N_{1}(w))+b(w,E_{i})>1$, because the
sets are disjoint. Therefore, all elementary sets are subsets of $\cap
N_{1}(w)$.

All elementary sets are pairwise disjoint, so $\cap N_{1}(w)$ is the pairwise
union of all elementary sets: $\cap N_{1}(w)=\texttt{int}_{N}(\cap
N_{1}(w))=\texttt{int}_{N}(W)$.

###### Proposition 6

(Belief function of the maximal subset of elementary sets of $N_{1}(w)$.) The
sum of the belief functions of all elementary sets is equal to or less than 1.

###### Proof

From the previous propositions and lemmas, belief function being superadditive
and $b(w,\cap N_{1}(w))=1$.

Lastly, we are going to characterise the class of belief neighbourhood frames
in which beliefs are additive.

###### Definition 19

(Additive belief neighbourhood frame.) A belief neighbourhood frame is
additive if the following holds:

$\text{For all }w\in W,b(w,\bigcup\\{A_{i}\\}_{i\in J})=\sum_{i\in
J}b(w,A_{i})\text{ (All }A_{i}\text{pairwise disjoint)}$

In this case, the belief function reduces to a probability function. To prove
that a neighbourhood is additive, we do not need to verify it for all possible
sets in $N_{\geqslant 0}(w)$. We just need to verify the following
proposition.

###### Proposition 7

(Core complete neigbhourhood of $N_{>0}(w)$ and additive neighbourhoods.) If
and only if the frame is additive, then for all $w\in W$ and, for all $X\in
N_{>0}(w)$, $\sum_{E_{i}\in N_{>0}(w)^{\mathcal{NC}}}$ $b(w,E_{i})=1$.

###### Proof

If the frame is additive, by definition of additivity, proposition 6 and the
elementary sets being pairwise disjoint, the sum of all the elementary sets in
the neighbourhood of all $w\in W$ is 1. If the frame is not additive, for some
$w\in W$ the sum of the belief functions of the elementary sets in its
neighbourhood is less than 1.

We need to provide a condition for a set to be measurable.

###### Definition 20

(Well-defined set.) A set $X$ in $N_{\geqslant\alpha}(w)$ is well-defined if
$X\cap\cap N_{1}(w)=\texttt{int}_{N}(X)$.

In other words, a set is well-defined if it does not insersect any elementary
set which is not its subset. A consequence of this definition, the last
proposition and proposition 4 is the following:

###### Lemma 3

If the frame is additive, if a set $X$ in $N_{\geqslant\alpha}(w)$ is well-
defined, then. $b(w,X)=b(w,\texttt{int}_{N}(X))$.

If the frame is not additive or the set is not well-defined, we only can state
$b(w,X)\geqslant b(w,\texttt{int}_{N}(X))$. When we define a model, sets
corresponding to the truth sets of formulas should be well-defined. Otherwise,
they may not be measurable.

##  6 Relationship between probability and belief models

The relationship between probabilistic Kripke semantics and belief
neighbourhood semantics is akin to the relationship between Kripke semantics
and neighbourhood semantics: a Kripke model has a kind of equivalence called
_modal equivalence_ with an augmented neighbourhood model.

We will ground our proof for probabilistic models in the aforementioned
equivalence between Kripke semantics and a subclass of the neighbourhood
semantics. First, we recall the latter proof, and then we will develop our own
proof for probability and belief. The original proof for the relationship
between Kripke and augmented neighbourhood models can be found in
chellas1980modal (6). Here we will follow Pacuit pacuit2017neighborhood (29),
which is also the source of these definitions:

###### Definition 21

(R-necessity.) Given a Kripke frame $\langle W,R\rangle$, $X\subseteq W$ is
R-necessary at $w$ if $R(w)\subseteq W$. The set $\\{X\subseteq W\ |\
R(w)\subseteq X\\}$ will be denoted by $\mathcal{N}^{R}_{w}$.

###### Definition 22

(Pointwise equivalence.) Given a non-empty set $W$, a Kripke frame $\langle
W,R\rangle$ and a neighbourhood frame $\langle W,N\rangle$ are pointwise
equivalent if, for all $w\in W$ and $X\subseteq W$, $X\in N(w)$ iff
$X\in\mathcal{N}^{R}_{w}$.

###### Definition 23

(Modal equivalence.) Given a modal language $\mathcal{L}$ and two classes of
models for it $M$ and $M^{\prime}$, we say that $M,w$ is $\mathcal{L}$-modally
equivalent to $M,w^{\prime}$ iff the set $\\{\phi\in\mathcal{L}\ |\
M,w\models\phi\\}$ is the same than $\\{\phi\in\mathcal{L}\ |\
M^{\prime},w^{\prime}\models\phi\\}$.

Given models $M$ and $M^{\prime}$, if for every pointed model $M,w$, there is
some $w^{\prime}$ such that $M,w$ and $M,w^{\prime}$ are pointwise equivalent,
then $M$ and $M^{\prime}$ are modally equivalent. More generally, a class of
models $M$ is modally equivalent to a class of models $M^{\prime}$ iff for
each pointed model $M,w$ there is another pointed model
$M^{\prime},w^{\prime}$ such that they are modally equivalent.

Modal equivalence is a concept which encloses other well-known ones, such as
bisimulation. However, bisimulation is defined within structures of the same
kind (for example, bisimulation in Kripke or neighbourhood models). A usual
way of proving that $M$ and $M^{\prime}$ are modally equivalent is showing a
way of transforming $M$ into $M^{\prime}$ and vice versa. The following
propositions are also taken from pacuit2017neighborhood (29):

###### Proposition 8

(Kripke models and augmented neighbourhood models.) Let $\langle W,R\rangle$
be a Kripke frame. Then, there is a modally equivalent augmented neighborhood
frame.

###### Proof

For each $w\in W$, let $N(w)=\mathcal{N}^{R}_{w}$ as described above, and
$\langle W,R\rangle$ is the desired neighbourhood frame, which is augmented.

###### Proposition 9

(Kripke models and augmented neighbourhood models.) Let $\langle W,N\rangle$
be an augmented neighborhood frame. Then, there is a modally equivalent
relational frame.

###### Proof

From an augmented $\langle W,N\rangle$, we define a binary relation
$R_{N}\colon W\times W$ in the following way: For every $w,w^{\prime}\in W$,
let $wR_{N}v$ iff $v\in\cap N(w)$. The frame $\langle W,R_{N}\rangle$ is the
desired Kripke frame.

As a result, we have the following:

###### Proposition 10

(Kripke models and augmented neighbourhood models.) The class of Kripke models
is modally equivalent to the class of augmented neighbourhood models.

###### Proof

If we add a valuation function $v:\texttt{At}\to W$ to the previous
structures, we obtain the corresponding Kripke and neighbourhood models. We
observe that the satisfaction of formulas is maintained in all $w\in W$, by
induction:

  * •

The satisfaction of atomic formulas is the same, since $v$ is the same.

  * •

The satisfaction of the conjunction and negation of formulas is preserved,
since in both semantics their interpretation is the same.

  * •

Satisfaction of the modal formulas:

    * –

If $M,w\models_{K}\square\phi$, all worlds $w_{i}$ such that $wRw_{i}$ satisfy
$\phi$. In the augmented neighbourhood model, all $w_{i}$ are in $\cap N(w)\in
N(w)$ and $\cap N(w)\subseteq\llbracket\phi\rrbracket_{M^{\prime}}\in N(w)$,
and thus $M^{\prime},w\models_{N}\phi$ by the definition of satifaction of
$\square\phi$ in neighbourhood semantics.

    * –

If $M^{\prime},w\models_{N}\square\psi$, by defining a relation $R_{N}\colon
W\times W$ as stated before, we obtain a set of worlds $w_{i}$ such that
$wR_{n}w_{i}$, and all of them satisfy $\phi$. Thus,
$M,w\models_{K}\square\phi$ in the Kripke model.

Fagin and Halpern fagin1991uncertainty (11) show that for every probability
structure, there is an equivalent structure in which belief functions have
been defined, and the converse is not true in general, just under specific
circumstances. Having seen the relationship between Kripke frames and
augmented neighbourhood frames, now we will study this relationship for
probabilistic Kripke frames and a subclass of belief neighbourhood frames,
namely additive ones. We will base our proof in the previous ones and the
results of the previous section.

###### Proposition 11

Let $\mathcal{M}^{P}_{K}=\langle W,\mu,R\rangle$ be a probabilistic Kripke
frame. There is an additive belief neighbourhood frame which is modally
equivalent to $\mathcal{M}^{P}_{K}$.

###### Proof

If we have $\mathcal{M}^{P}_{K}$, we first obtain $\cap N_{1}(w)$ for each
$w\in W$ in an analogous way to the procedure described in proposition 8 for
Kripke and neighbourhood models. It will be the core of an augmented
neighbourhood 1.

Now let us consider all singletons $\\{w_{i}\\}\subseteq R(w)=\cap N_{1}(w)$.
They will be the elementary sets in $N_{>0}(w)^{\mathcal{NC}}$. We want to
define an additive neighbourhood frame, and then we know by proposition 7 that
the following condition has to be met: $\sum_{\\{w_{i}\\}\in
N_{>0}(w)^{\mathcal{NC}}}$ $b(w,\\{w_{i}\\})=1$. Thus, for all singletons
$\\{w_{i}\\}$, we define a function $b_{k}(w,\\{w_{i}\\})=\mu(w,w_{i})$. We
also specify that $b(w,\varnothing)=0$, and thus $\varnothing\in N_{\geqslant
0}(w)$.

We have to define the value of $b$ for the rest of the sets in $N_{\geqslant
0}(w)$. Neighbourhoods are monotonic 12, so for every $A\subseteq W$, we are
going to consider its interior $\texttt{int}_{N}(A)$ 18. We define
$b(w,A)=b(w,\texttt{int}_{N}(A))$ (see lemma 3). If $\texttt{int}_{N}(A)$=0,
then $b(w,A)=0$.

###### Proposition 12

Let $\mathcal{M}^{B}_{N}=\langle
W,b,\\{N_{\geqslant\alpha,\alpha\in[0,1]}\\}\rangle$ be an additive belief
neighbourhood frame. There is a probabilistic Kripke frame which is modally
equivalent to $\mathcal{M}^{B}_{N}$.

###### Proof

For all $w\in W$, we define a binary relationship $R_{N}:W\times W$ in this
way: $wR_{N}w^{\prime}$ iff $w^{\prime}\in\cap N_{1}(w)$. We will denote by
$R_{N}(w)$ the set of all $w^{\prime}$ in this relation.

We know from proposition 5 that $\cap N_{1}(w)$ is equal to the disjoint union
of the elementary sets in $N_{>0}(w)^{\mathcal{NC}}$. The frame is additive,
so the sum of the beliefs of the elementary sets is equal to 1. Thus, we
define a function $\mu_{N}:W\times W\to[0,1]$ such that $\mu_{N}(w,w_{i})=0$
if $w^{\prime}\notin\cap N_{1}(w)$ and $\mu(w,w_{i})>0$ otherwise. The value
of $\mu_{N}(w,w_{i})>0$ in this second case will be determined in the
following step.

Now we must consider each elementary set $E_{i}$. It will correspond to one or
more $w_{i}$ in $R_{N}(w)$. Since each set is disjoint, the exact value of
$\mu(w,w_{i})$ is arbitrary, as long as the sum of $\mu_{N}(w,w_{i})$ for all
$w_{i}$ within a given elementary set $E_{i}$ is equal to $b(w,E_{i})$. We
make this for all elementary sets.

Since the frame is additive and $\cap N_{1}(w)=\bigcup_{i=1}^{n}E_{i}$ for
$\\{E_{i}\\}$ disjoint sets, then $b(w,\cap
N_{1}(w))=1=\sum_{i=1}^{n}b(w,E_{i})$. Thus, $\sum_{w_{i}\in
W}\mu_{N}(w,w_{i})=1$.

As a consequence, we have the following result:

###### Proposition 13

(Equivalence between probabilistic and belief models.) The class of
probabilistic Kripke models is modally equivalent to the class of of additive
belief models.

###### Proof

Analogous to proposition 8. If we add a valuation $v:\texttt{At}\to W$ to the
previous frames, we obtain the corresponding models. We just need to consider
modal operators:

  * •

From Kripke to neighbourhood models: If $\mathcal{M}^{P}_{K},w\models
B_{\geqslant\alpha}\phi$, then there is a subset of $R(w)$ such that the sum
of their probabilities $\mu(w,w_{i})$ is a certain value
$\alpha^{\prime}\geqslant\alpha$, and the analogue value for $\neg\phi$ is a
certain value $\beta$ such that $\alpha^{\prime}+\beta=1$. By applying the
process described in proposition 11, the elementary sets of the modally
equivalent neighbourhood model are formed by a series of singletons, one for
each world in $R(w)$. The union of all the elementary sets corresponding to
worlds in $R(w)$ that satisfy $\phi$ is
$\texttt{int}_{N}(\llbracket\phi\rrbracket_{M})$.
$b(w,\llbracket\phi\rrbracket_{M})=b(w,\texttt{int}_{N}(\llbracket\phi\rrbracket_{M})$
is the sum of the beliefs of the elementary sets corresponding to worlds
satisfying $\phi$. Thus
$b(w,\llbracket\phi\rrbracket_{M})=\alpha^{\prime}\geqslant\alpha$. The same
reasoning applies to $\neg\phi$, giving a value of
$b(w,\llbracket\neg\phi\rrbracket_{M})=\beta$. Therefore
$\mathcal{M}^{B}_{N}\models\underline{B}_{\geqslant\alpha^{\prime}\geqslant\alpha}\phi$
and $\mathcal{M}^{B}_{N}\models\underline{B}_{\geqslant\beta}\neg\phi$. We
know that this logically entails $\mathcal{M}^{B}_{N}\models
B_{\geqslant\alpha}\phi$.

  * •

From additive neighbourhood to Kripke models: Let us have
$\mathcal{M}^{B}_{N},w\models_{N}B_{\geqslant\alpha}\phi$. We first obtain
$R(w)$ from $\cap N_{1}(w)$ as described in proposition 12: We define
$R_{N}\colon W\times W$ such that $wRw_{i}$ if $w_{i}\in\cap N_{1}(w)$. A
subset of the worlds in $\cap N_{1}(w)$ satisfies $\phi$, and this subset is
also a subset of $\llbracket\phi\rrbracket_{M}$. More precisely, this subset,
$\cap
N_{1}(w)\cap\llbracket\phi\rrbracket_{M}=\texttt{int}_{N}(\llbracket\phi\rrbracket_{M})$,
and by lemma 3,
$b(w_{1},\texttt{int}_{N}(\llbracket\phi\rrbracket_{M}))=b(w_{1},\llbracket\phi\rrbracket_{N})$.
Thus, this value is at least $\alpha$, and therefore, the worlds in $R(w)$
that satisfy $\phi$ must sum up a probability of at least $\alpha$. Therefore,
$\mathcal{M}^{P}_{K},w\models_{K}B_{\geqslant\alpha}\phi$.

Not all belief neighbourhood frames have a modally equivalent probabilistic
neighbourhood frame: If the neighbourhood frame is not additive, we cannot
obtain a modally equivalent Kripke frame. Instead, there will be an infinite
family of of probabilistic Kripke frames that are compatible with that belief
neighbourhood model. This means that we can obtain an infinite family of
Kripke models, and the formulas that are satisfied on them logically entail
the formulas of the neighbourhood model, but the converse is not true in
general.

###### Example 4

(Example 4: From a probabilistic Kripke model to a belief neighbourhood model
and back.) From probabilistic Kripke model to belief neighbourhood model: The
$\mathcal{M}^{P}_{K}$ in Example 1 (1) can have a modally equivalent belief
neighbourhood model. Let us study just one world, the process in the other
ones is identical. Let us take $w_{1}$, we recall that in
$\mathcal{M}^{P}_{K}$, $\mu(w_{1},w_{1})=0$, $\mu(w_{1},w_{2})=0.4$,
$\mu(w_{1},w_{3})=0.6$, $\mu(w_{1},w_{4})=0$. We will assign a certain $b$ to
every subset of $R(w_{1})=\\{w_{2},w_{3}\\}$. $b(\varnothing)=0$, and thus
$b(w_{1},\\{w_{3}\\})=\mu(w_{1},w_{3})$=0.6, and
$b(w_{1},\\{w_{2}\\})=\mu(w_{1},w_{2})=0.4$. $b(\\{w_{1}\\}=0$. The belief
function for the rest of the subsets of $W$ is defined from the belief
function of their interior, that it is some of the previous sets. For example,
$b(w_{1},W)=b(w_{1},\\{w_{2},w_{3}\\})=1$, and
$b(w_{1},\\{w_{1},w_{3}\\})=b(w_{1},\\{w_{3}\\})=0.6$.

If we apply the valuation function that we have defined in Example 1,
$\\{w_{1},w_{3}\\}=\llbracket p\rrbracket_{M}$, and thus $b(w_{1},p)=0.6$.
Similarly, $\\{w_{2},w_{4}\\}=\llbracket\neg p\rrbracket_{M}$, and thus
$b(w_{1},\neg p)=0.4$. That is, $b(w_{1},p)+b(w_{1},\neg p)=1$.

From additive belief neighbourhood model to probabilistic Kripke model: Now
let us see the belief neighbourhood model we have obtained. Let us take
$w_{1}$ again, for example, and let us observe that $\cap
N_{1}(w_{1})=\\{w_{2},w_{3}\\}$. Both $\\{w_{2}\\}$ and $\\{w_{3}\\}$ are
elementary sets in $N_{\geqslant 0}(w_{1})$, and we know that
$b,(w_{1},\\{w_{2}\\})+b,(w_{1},\\{w_{3}\\})=1$, and thus the frame is
additive.

Let us define $R_{N}\colon W\times W$ and $\mu_{N}\colon W\times W\to[0,1]$,
and $\mu_{N}(w_{1},w_{2})=0.4$ and $\mu_{N}(w_{1},w_{3})=0.6$. Since each
elementary set $E_{i}$ is formed by a single world, we do not have to
distribute the value of $b(w_{1},E_{i})$ among several worlds. For several
worlds, we should operate in this way: Let us assume that
$E_{1}=\\{w_{2},w_{5}\\}$, then
$\mu_{N}(w_{1},w_{2})+\mu_{N}(w_{1},w_{5})=b(w_{1},E_{1})$, for example
$\mu_{N}(w_{1},w_{2})=0.3$ and $\mu_{N}(w_{1},w_{5})=0.1$. Since $w_{1}$ and
$w_{4}$ are not in $\cap N_{1}(w_{1})$, then $\mu_{N}(w_{1},w_{1})=0$ and
$\mu_{N}(w_{1},w_{4})=0$. We have that $R_{N}(w_{1})=\\{w_{2},w_{3}\\}$, which
is the set of worlds in $\cap N_{1}(w_{1})$. We verify that
$\mu_{N}(w_{1},w_{2})+\mu_{N}(w_{1},w_{3})=1$, which is the expected value.

###### Example 5

(Example 5: Belief neighbourhood model with no modally equivalent
probabilistic Kripke model.) We can take the belief neighbourhood model that
we have created in the previous example and just make two small changes. Let
us make $b(w_{1},\\{w_{2}\\})=0.4$ and $b(w_{1},\\{w_{3}\\})=0.3$, but
$b(w_{1},\\{w_{2},w_{3}\\})=1$. We have that $b(w_{1},\\{w_{2},w_{3}\\})$
$>b(w_{1},\\{w_{2}\\})+b(w_{1},\\{w_{3}\\})$ and thus additivity is not held
7. Thus, there is not a Kripke frame that is modally equivalent to this
neighbourhood frame, but infinite Kripke frames, these with
$\mu_{N}(w_{1},w_{2})\geqslant b(w_{1},\\{w_{2}\\})=0.3$,
$\mu_{N}(w_{1},w_{2})\geqslant b(w_{1},\\{w_{3}\\}=0.4$, and
$\mu_{N}(w_{1},w_{2})+\mu_{N}(w_{1},w_{3})=1$.

Let us suppose a certain Kripke frame such that $\mu(w_{1},w_{2})=0.4$ and
$\mu(w_{1},w_{3})=0.6$, being $R(w_{1})=\\{w_{2},w_{3}\\}$. We have that
$\mathcal{M}^{P}_{K},w_{1}\models_{K}B_{0.4}p$, for example. $B_{0.4}p$
logically entails $\underline{B}_{0.3}p$, which is satisfied in $w_{1}$ in the
neighbourhood model. However, $\underline{B}_{0.3}p$ does not logically entail
$B_{0.4}p$.

##  7 Concluding remarks and future work

Concluding remarks.  It has been shown that every probability can be
understood as an additive belief function 1. In a probability Kripke model, it
is possible to express subjective probabilities, which also are additive
belief functions 4, but it is not possible to express arbitrary belief
functions. In a neighborhood belief model, a probability is a special case of
belief functions, additive ones. Thus, neighborhood models allow for a more
expressive interpretation by distinguishing between probability and belief
functions. In the final section, we have seen how to interpret this in terms
of relationships between models: Every probabilistic Kripke model can be
converted into a modally equivalent neighborhood model, but the reverse is
only possible for additive belief neighbourhood models 13. They form a proper
subclass of of belief neighborhood models.

Future works. In this work we have deliberately omitted the consideration of
conditional probability and conditional belief, which arise as an immediate
logical extension. In future works, an possible line of research is their
study and their connection to basic logical operations, such as probabilistic
deduction and the application of Bayes’ theorem. Specifically, our aim is to
integrate these operations within the framework of belief neighborhood models,
considering these operations on probabilistic Kripke models as equivalent to
their counterparts in a specific subclass of neighbourhood models.

Acknowledgements. Thanks to the two anonymous peer reviewers who greatly
helped with their suggestions to improve the final version of this article.

## References

  * (1) Horacio Arló Costa  “Non-adjunctive inference and classical modalities”  In _Journal of Philosophical Logic_ 34 Springer, 2005, pp. 581–605
  * (2) Robert J Aumann  “Backward induction and common knowledge of rationality”  In _Games and economic Behavior_ 8.1 Elsevier, 1995, pp. 6–19
  * (3) Robert J Aumann  “Interactive epistemology II: probability”  In _International Journal of Game Theory_ 28 Springer, 1999, pp. 301–314
  * (4) Fahiem Bacchus  “Representing and reasoning with probabilistic knowledge: a logical approach to probabilities”  MIT press, 1991
  * (5) Veselka Boeva, Elena Tsiporkova and Bernard De Baets  “Modelling uncertainty with Kripke’s semantics”  In _Artificial Intelligence: Methodology, Systems, and Applications: 8th International Conference, AIMSA’98 Sozopol, Bulgaria, September 21–23, 1998 Proceedings 8_ , 1998, pp. 129–140  Springer
  * (6) Brian F Chellas  “Modal logic: an introduction”  Cambridge university press, 1980
  * (7) Esther Anna Corsi, Tommaso Flaminio and Hykel Hosni  “A logico-geometric comparison of coherence for non-additive uncertainty measures”  In _Annals of Pure and Applied Logic_ Elsevier, 2023, pp. 103342
  * (8) Arthur Dempster  “Upper and Lower Probabilities induced by a Multi-valued Mapping”  In _Annals of Mathematical Statistics_ 38, 1967
  * (9) F Esteva, Lluıs Godo and P Hájek  “Reasoning about probability using fuzzy logic”  In _Neural Network World_ 10.5, 2000, pp. 811–824
  * (10) Ronald Fagin and Joseph Y Halpern  “A new approach to updating beliefs”  In _arXiv preprint arXiv:1304.1119_ , 2013
  * (11) Ronald Fagin and Joseph Y Halpern  “Uncertainty, belief, and probability”  In _Computational Intelligence_ 7.3 Wiley Online Library, 1991, pp. 160–173
  * (12) Ronald Fagin, Joseph Y Halpern and Nimrod Megiddo  “A logic for reasoning about probabilities”  In _Information and computation_ 87.1-2 Elsevier, 1990, pp. 78–128
  * (13) Ronald Fagin, J Halpern, Y Moses and M Vardi  “Reasoning about knowledge”  In _Proceedings of the Second Conference on Theoretical Aspects of Reasoning about Knowledge: March 7-9, 1988, Pacific Grove, California_ , 1988, pp. 277–293  Morgan Kaufmann
  * (14) Terrence L Fine  “Lower probability models for uncertainty and nondeterministic processes”  In _Journal of statistical Planning and inference_ 20.3 Elsevier, 1988, pp. 389–411
  * (15) Tommaso Flaminio, Lluıs Godo and Enrico Marchioni  “Reasoning about uncertainty of fuzzy events: an overview”  In _Understanding Vagueness-Logical, Philosophical, and Linguistic Perspectives, P. Cintula et al.(Eds.), College Publications_ , 2011, pp. 367–400
  * (16) Petr Hájek  “Metamathematics of fuzzy logic”  Springer Science & Business Media, 2013
  * (17) Joseph Y Halpern  “Reasoning about uncertainty”  MIT press, 2003
  * (18) Joseph Y Halpern and Ronald Fagin  “Two views of belief: belief as generalized probability and belief as evidence”  In _Artificial intelligence_ 54.3 Elsevier, 1992, pp. 275–317
  * (19) Aviad Heifetz and Philippe Mongin  “Probability logic for type spaces”  In _Games and economic behavior_ 35.1-2 Elsevier, 2001, pp. 31–53
  * (20) Aviad Heifetz and Philippe Mongin  “The modal logic of probability”  In _Proceedings of the 7th Conference on Theoretical Aspects of Rationality and Knowledge_ , 1998, pp. 175–185
  * (21) Aviad Heifetz and Dov Samet  “Topology-free typology of beliefs”  In _journal of economic theory_ 82.2 Elsevier, 1998, pp. 324–341
  * (22) Andreas Herzig and Dominique Longin  “On modal probability and belief”  In _Symbolic and Quantitative Approaches to Reasoning with Uncertainty: 7th European Conference, ECSQARU 2003 Aalborg, Denmark, July 2-5, 2003 Proceedings 7_ , 2003, pp. 62–73  Springer
  * (23) John Maynard Keynes  “A treatise on probability”  MacmillanCo., 1921
  * (24) Barteld P Kooi  “Probabilistic dynamic epistemic logic”  In _Journal of Logic, Language and Information_ 12 Springer, 2003, pp. 381–408
  * (25) BO Koopman  “The bases of probability”  In _Bull. Amer. Math. Soc._ 46.11, 1940, pp. 763–774
  * (26) Kim G. Larsen and Arne Skou  “Bisimulation through probabilistic testing”  In _Information and Computation_ 94.1, 1991, pp. 1–28
  * (27) D. Lewis  “Counterfactuals”  Oxford: Blackwell Publishers, 1973
  * (28) Nils J Nilsson  “Probabilistic logic”  In _Artificial intelligence_ 28.1 Elsevier, 1986, pp. 71–87
  * (29) Eric Pacuit  “Neighborhood semantics for modal logic”  Springer, 2017
  * (30) Enrique H Ruspini  “The logical foundations of evidential reasoning”  SRI International Menlo Park, CA, 1986
  * (31) Glenn Shafer  “A mathematical theory of evidence”  Princeton university press, 1976
  * (32) Afsaneh Shirazi and Eyal Amir  “Probabilistic modal logic”  In _Proceedings of the 22nd AAAI Conference on Artificial Intelligence_ 7, 2007, pp. 489–495
  * (33) Philippe Smets  “Belief functions versus probability functions”  In _International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems_ , 1988, pp. 17–24  Springer
  * (34) Philippe Smets  “Probability of provability and belief functions”  In _Logique et Analyse_ JSTOR, 1991, pp. 177–195
  * (35) C Sossai  “Belief-functions logic”, 1999
  * (36) Claudio Sossai, Paolo Bison and Gaetano Chemello  “Fusion of symbolic knowledge and uncertain information in robotics”  In _International Journal of Intelligent Systems_ 16.11 Wiley Online Library, 2001, pp. 1299–1320


# Enhancing Scalability of Optimal Kron-based Reduction of Networks (Opti-
KRON) via Decomposition with Community Detection ††thanks:  This work was
supported by the U.S. Department of Energy’s Office of Energy Efficiency and
Renewable Energy under the Enabling Place-Based Renewable Power Generation
using Community Energyshed Design initiative, award number DE-EE0010407. The
opinions expressed in this material are those of the authors and do not
necessarily reflect those of the U.S. Department of Energy or the United
States Government.

Omid Mokhtari
University of Vermont
<EMAIL_ADDRESS>&Samuel Chevalier
University of Vermont
<EMAIL_ADDRESS>&Mads R. Almassalkhi
University of Vermont
<EMAIL_ADDRESS>
###### Abstract

Electrical networks contain thousands of interconnected nodes and edges, which
leads to computational challenges in some power system studies. To address
these challenges, we contend that network reductions can serve as a framework
to enable scalable computing in power systems. By building upon a prior AC
“Opti-KRON” formulation, this paper presents a DC power flow formulation for
finding network reductions that are optimal within the context of large
transmission analysis. Opti-KRON previously formulated optimal Kron-based
network reductions as a mixed integer linear program (MILP), where the number
of binary variables scaled with the number of nodes. To improve scalability of
the Opti-KRON approach, we augment the MILP formulation with a community
detection (CD) technique that segments a large network into smaller, disjoint,
but contiguous sub-graphs (i.e., communities). For each sub-graph, we then (in
parallel) apply MILP-based along with a new cutting plane constraint, thus,
enhancing scalability. Ultimately, the new DC-based Opti-KRON method can
achieve a 80-95% reduction of networks (in terms of nodes) while statistically
outperforming other CD- and Kron-based methods. We present simulation results
for the IEEE RTS-96 and the 2383-bus Polish networks.

#### Keywords:

Optimal network reduction, Kron reduction, community detection, mixed integer
linear programming (MILP), cutting plane.

##  1 Introduction

The growing complexity of power grids, driven by the interconnection of
diverse regions and the integration of new components, presents a significant
challenge for power system studies. Analyzing large-scale power networks,
particularly for planning and operation purposes with numerous scenarios,
often requires simulating a vast number of potential future states.
Unfortunately, the computational demands of these studies can quickly become
intractable. Network reduction in power grids involves simplifying complex
electrical networks by reducing the overall network size while preserving
essential characteristics.

Network reduction methods can be categorized into two primary groups: bus
elimination and bus aggregation. The bus aggregation method clusters buses
that share similar characteristics, such as buses with similar power transfer
distribution factor (PTDF) vectors. These vectors indicate that injections at
these buses have similar effects on branch flows. Thus, the generation and
load at buses that are considered “similar” can be aggregated into a single
bus [1]. For example, [2] uses a Minimum Spanning Tree (MST) algorithm to
identify zones, where within identified zones, nodes are aggregated,
particularly focusing on generation bus aggregation. [3] uses eigenvalue
decomposition to find similar components in the PTDF matrix. The proposed
model in [4] depends on pre-determined zones, where the network is divided
into zones, and the buses within each zone are aggregated. After obtaining the
reduced PTDF, the susceptances are determined using a nonlinear optimization
approach. In [5], bus aggregation is applied to internal zones that are
defined based on a set of pre-determined salient lines. Then, the reduced
admittance matrix is calculated through a quadratic optimization problem where
the objective is minimizing the line flow errors with respect to the full
network.

Bus elimination refers to the process of identifying the buses that are kept
in the full system and eliminating the rest using either Ward [6] or Kron
reduction [7]. Next, the capacities of equivalent branches are determined to
create a reduced system that has transfer capacities similar to the full
network. For example, the methodology in [8] aims to identify critical pairs
of buses that likely represent congested lines or potential new line
installations. The network is partitioned using the multi-cut problem
formulation, which aims to minimize the number of inter-cluster lines by
ensuring critical pairs of buses end up in separate clusters. After
partitioning, non-border buses are eliminated within each cluster using Kron
reduction. [9] proposes a Ward-based reduction model that incorporates
nonlinear load functions to estimate AC power flow across a range of operating
points. Using a mixed integer optimization method, the parameters of the
reduced DC model, including the topology of the external equivalent network
and the allocation of power injections at boundary buses, are obtained. The
framework in [10] is adaptable to generate either Ward reduction, bus-
aggregation-based reduction, or a hybrid of both, where it treats the Ward
reduction as an optimization problem, aiming to preserve the PTDF matrix’s
submatrix that relates to the retained buses and branches.

These methods, however, have used predefined sets of nodes, zones, or lines to
remain in the grid. The problem of which set of nodes and how many nodes
should remain in the reduced network have been solved by the Opti-KRON model
in [11], where an optimization problem is designed to find the optimal network
reduction with minimum voltage deviation from the full network. Even though
based on Kron reduction, this approach can be considered a hybrid
implementation of bus aggregation and bus elimination, where each eliminated
node is assigned to a super-node that remains. As a continuation of the
methods proposed in [11], our paper enhances the scalability of the approach,
and it explores larger instances of optimal network reduction.

To enhance network reduction scalability, strategic network partitioning is
employed, with community detection serving as a crucial method to effectively
partition the network into distinct, manageable segments. Community detection
is a technique used in network science to identify groups or communities
within a network where nodes are more densely connected to each other than to
nodes in other communities [12]. The main goal of community detection is to
find a structure within a large network that helps in understanding the nature
of the connections and interactions among its components. The advantage of
community detection over other network partitioning approaches is that it does
not require a predefined set of nodes or lines for network decomposition;
instead, the network is decomposed based on the natural topological features
of the network.

Building upon the previous Opti-KRON model, this work makes several key
contributions to the field of network reduction:

  * •

Proposing a DC Framework for the Opti-KRON Model: We change the formulation of
Opti-KRON from AC to DC power flow in order to extend applicability to
transmission networks and simplify the computations.

  * •

Embedding Community Detection with Network Reduction: We enhance scalability
by integrating community detection techniques with network reduction
processes, enabling more efficient handling of large-scale networks.

  * •

Using a Cutting Plane and Big-M Linearization: We further improve scalability
by employing a cutting plane restriction and Big-M linearization, which
accelerates the reduction process.

The remaining paper is structured as follows. Section 2 summarize the network
model and Kron reduction. In Section 3, the MINLP formulation for Kron-based
network reduction is presented. Reformulation, scalability, and community
detection are presented in section 4. Experimental results are proposed in
section 5. Finally, the paper concludes in section 6 with a summary and a
brief discussion on future directions and applications.

##  2 Network model and Kron reduction

###  2.1 Network Representation

We model a power system network as a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ with $\mathcal{V}$ and $\mathcal{E}$
representing vertices and edges, where $|\mathcal{V}|=n$ and
$|\mathcal{E}|=m$. The network’s structure is defined by the adjacency matrix
${\Lambda}\in\mathbb{R}^{n\times n}$, where $\Lambda_{ij}$ indicates the
presence or absence of edges, corresponding to transmission lines.
Additionally, the complex nodal admittance matrix, or the $Y$-bus matrix
$\mathbf{Y}_{b}\in\mathbb{C}^{n\times n}$, is utilized to capture the
electrical characteristics of the network.

###  2.2 DC Power Flow Model

DC power flow is an approximate model for calculating power flow in an
electrical network by assuming negligible resistance, small phase angle
differences, and constant voltage magnitudes, resulting in a linear
relationship between power flow and phase angle differences. The power flow
equation is represented as $P=B\boldsymbol{\theta}$, where $P$ is the net
power injection vector, $\boldsymbol{\theta}$ the node phase angles, and
$B={\rm Im}\\{\mathbf{Y}_{b}\\}$ the susceptance matrix, derived from the
$Y$-bus matrix.

###  2.3 Kron Reduction

The Kron reduction of a given graph yields another graph, where the admittance
matrix is derived by taking the Schur complement of the original admittance
matrix with respect to a specified subset of nodes. Thus, a kron-reduced
equivalent of a network with admittance matrix $\mathbf{Y}_{b}$, given a set
of nodes to be kept ($k$) and a set of nodes to be removed ($r$), can be
calculated as follows:

$\displaystyle Y^{\rm kron}=Y_{kk}-Y_{kr}{Y_{rr}}^{-1}Y_{rk}$ (1)

Additionally, instead of calculating the Kron-reduced admittance matrix, the
equivalent impedance matrix of a Kron-reduced network can be directly
calculated by removing the rows and columns corresponding to the eliminated
nodes from the impedance matrix of the full network [11]. This approach
facilitates the direct calculation of power flow for the Kron-reduced network
which has been addressed in the next section.

##  3 Proposed Model

According to [11], in a network reduction problem, in AC environment, the
voltage of the kept nodes ($V$) can be calculated through:

$V=\text{diag}(s)Z_{b}AI,$ (2)

where $s$ is the vector of binary decision variables that selects the nodes to
be kept in the network. When $s_{i}=1$ node $i$ remains in the network as a
super-node, and when $s_{i}=0$ node $i$ will be eliminated. $Z_{b}$ is the
impedance matrix, and $A$ is the matrix binary variable which codifies where
currents from reduced nodes are placed i.e. when $A^{i,j}=1$ injected current
of node $j$ will be added to node $i$. Vector $I$ is the current injection at
each node.

While in a DC environment, $|V|=1$ and the admittance matrix is singular, so
equation (2) cannot be directly used. However, the equivalent of (2) in a DC
power flow context can be expressed as

$\displaystyle\theta=\text{diag}(s)\Psi$ (3a) $\displaystyle B\Psi=AP,$ (3b)

where parameter $P$ is the real power injection at each node, $\theta$ is the
DC voltage angle of the super-nodes, and $B$ is the imaginary part of the
admittance matrix. $\Psi$ is the auxiliary variable vector that contains
voltage angles of all nodes.

With this formulation, each reduced node belongs to a cluster with one super-
node as the representative of that cluster where the power injection of all
nodes in each cluster is assigned to their super-nodes.

In this paper, our goal is to identify nodes to retain in such a way that the
reduced network accurately represents the original grid. Therefore, we need to
define an objective function that, while encouraging a greater level of
reduction, should prevent deviation from the original grid. In order to
accomplish this, Maximum Intra-Cluster Error (MICE) is defined to calculate
the maximum error in each cluster. In this paper, the error of a node is
defined as the difference between its voltage angle in the original grid
(obtained from DC power flow solutions on the original network) with the
voltage angle of its super-node in the cluster it belongs to (obtained from
performing power flow solutions on the reduced network). This formulation
helps us to minimize the maximum error in each cluster. Thus, the objective
function that optimally balances the trade-off between reduction levels and
the deviation can be expressed as

$\displaystyle\mathcal{L}={\sum_{c}\left\|{\hat{\theta}}_{c}-\Theta_{c}\right\|_{\infty}}-\alpha\sum_{i=1}^{n}(1-s_{i}),$
(4)

where the parameter $\alpha$ is a weighting factor that can be used to
determine the network reduction priority e.g., higher values of $\alpha$ lead
to a greater level of reduction with higher error while a smaller $\alpha$
preserves accuracy. $\theta_{c}$ is the given data vector of voltage angles,
and variable $\Theta_{c}$ is the cluster angle of the reduced network.
However, to calculate voltage angles and distinguish them based on their
clusters, we need to reformulate the objective function and utilize the
optimization problem below:

$\displaystyle\min_{\mathbb{E}}\quad$
$\displaystyle{\sum_{i}^{n}\overbrace{\left\|\vec{e}_{i}^{T}X\right\|_{\infty}}^{\text{MICE}}}-\alpha\sum_{i}^{n}(1-s_{i})$
(5a) $\displaystyle{\rm s.t.}\;\;\quad$ $\displaystyle X=A\text{
diag}(\hat{\theta}-\Theta)$ (5b) $\displaystyle\theta=\text{diag}(s)\Psi$ (5c)
$\displaystyle B\Psi=AP$ (5d) $\displaystyle\Theta=A^{T}\theta$ (5e)
$\displaystyle\mathbf{1}^{T}A=\mathbf{1}^{T}$ (5f) $\displaystyle A\leq
s\mathbf{1}$ (5g) $\displaystyle A_{i,i}=s_{i},\ \forall i\ \in N$ (5h)
$\displaystyle A_{i,j}\leq\Lambda_{i,j},\ \forall i,j\ \in N,i\neq j,$ (5i)

where $\mathbb{E}:=\\{X,\Psi,\theta,\Theta,s,A\\}$, $n$ is the number of nodes
in the full grid, $N$ is the set of all nodes, and $\vec{e}_{i}$ is the $i$th
natural basis vector, where all elements are zero except for the $i$-th
element. Equation (5b) calculates the error of all nodes in the clusters. If
node $i$ is a reduced node, row $i$ of $X$ is zero, and if node $i$ is a
super-node, row $i$ represents errors of that cluster. Thus, MICE for each
cluster is equal to the maximum value of each row of matrix $X$. The voltage
angles of super-nodes are determined through (5c) and (5d). Equation (5e)
assigns voltage angles of super nodes to the children nodes within their
clusters. Each node can only be assigned to one cluster, forced by (5f).
According to (5g), reduced nodes can be assigned only to super-nodes. Each
non-reduced bus keeps its own current by equation (5h). Node assignment is
restricted to neighbor nodes in (5i), where $\Lambda$ is the adjacency matrix.

Since (5i) limits the degree of reduction, we need to employ an iterative
algorithm to achieve smaller networks. In the algorithm introduced next, we
use Kron-reduction to update the $Y$-bus and then the adjacency matrix of the
reduced network. However, to calculate MICE for all the nodes in the original
grid, it is necessary to keep track of child-nodes at each iteration. Thus, we
define relations

$\displaystyle\Omega^{k}$ $\displaystyle=A^{k}\Omega^{k-1}$ (6a)
$\displaystyle s^{k}$ $\displaystyle\leq s^{k-1},$ (6b)

where $k$ denotes the iteration index and $\Omega$ is the matrix containing
the cluster information. While matrix $A$ has only the information of the
current iteration (no information about the reduced nodes in the previous
iterations), we track previously reduced nodes through $\Omega$. Specifically,
element $\Omega_{ij}=1$ if reduced node $j$ is assigned to super-node $i$.

For the initial iteration, the setup is as follows: $s^{0}=\mathbf{1}_{n}$,
indicating that every node is considered as a potential super-node.
Concurrently, $\Omega^{0}$ is set to the identity matrix $I$. As the algorithm
progresses, these matrices are updated to reflect the evolving cluster
structures and super-node assignments.

In addition to (6a) and (6b), equations (5e) and (5f) need to be altered as
follows:

$\displaystyle\Theta^{k}$ $\displaystyle=(\Omega^{k})^{T}\theta^{k}$ (7a)
$\displaystyle\mathbf{1}_{n}^{T}A^{k}$ $\displaystyle=(s^{k-1})^{T}.$ (7b)

Thus, the new optimization problem can be expressed as:

$\displaystyle\min_{\mathbb{E}^{k}}\quad$
$\displaystyle{\sum_{i}^{n}\overbrace{\left\|\vec{e}_{i}^{T}X^{k}\right\|_{\infty}}^{\text{MICE}}}-\alpha\sum_{i}^{n}(1-s_{i}^{k})$
(8a) $\displaystyle X^{k}=\Omega^{k}\text{ diag}(\hat{\theta}-\Theta^{k})$
(8b) $\displaystyle(\ref{eq: thet_psi}),(\ref{eq: zap}),(\ref{eq:
assign_limit2}),\eqref{eq: diagA},\eqref{eq: assign_adj},\eqref{eq:
7},\eqref{eq: 8}$ (8c)

Where
$\mathbb{E}^{k}=\\{X^{k},\Psi^{k},\theta^{k},\Theta^{k},\Omega^{k},s^{k},A^{k}\\}$.
Problem (8) is an NP-hard Mixed-Integer Nonlinear Programming (MINLP) problem,
which poses a computational challenges. In the following section, we will
improve scalability of this formulation.

##  4 Scalability

To enhance scalability of the proposed formulation, we first employ Big-M
reformulation for the bi/non-linear expressions. Secondly, a cutting plane is
added to the formulation to reduce space of feasible super-node assignments.
Finally, community detection techniques are applied to segment large networks
into smaller, disjoint, but contiguous sub-graphs (i.e., communities), which
enables us to parallelize the optimization problem for each community. These
techniques are explained in detail in the following sections.

###  4.1 Big-M Reformulation

To reformulate non-linear (5c) and (7a) as a linear expression, we employ the
Big-M method. The equivalent set of inequality constraints for (5c) is as
follows:

$\displaystyle\theta\leq(\mathbf{1}-s)M+\Psi$ (9a) $\displaystyle\theta\leq
sM$ (9b) $\displaystyle\theta\geq(s-\mathbf{1})M+\Psi$ (9c)
$\displaystyle\theta\geq-sM.$ (9d)

To linearize equation (7a), we need to define an auxilary row vector
$\gamma_{i}$ and a selection vector $\vec{e}_{i}$ such that:

$\displaystyle\gamma_{i}={\vec{e}}_{i}^{T}\left({\Omega}\right)^{T},\ \forall
i\ \in N$ (10a)
$\displaystyle\varphi_{i}\leq\left(\mathbf{1}^{T}-\gamma_{i}\right)M+\theta^{T},\
\forall i\ \in N$ (10b) $\displaystyle\varphi_{i}\leq\gamma_{i}M,\ \forall i\
\in N$ (10c)
$\displaystyle\varphi_{i}\geq\left(\gamma_{i}-\mathbf{1}^{T}\right)M+\theta^{T},\
\forall i\ \in N$ (10d) $\displaystyle\varphi_{i}\geq-\gamma_{i}M,\ \forall i\
\in N$ (10e) $\displaystyle\Theta=\varphi\mathbf{1},$ (10f)

where $\varphi_{i}$ denotes row $i$ of $\varphi$. Equation (8b) can also be
linearized in the same way:

$\displaystyle l=(\hat{\theta}-\Theta)$ (11a)
$\displaystyle\zeta_{i}=\vec{e}_{i}^{T}\Omega,\ \forall i\ \in N$ (11b)
$\displaystyle X_{i}\leq\left(\mathbf{1}^{T}-\zeta_{i}\right)M+l^{T},\ \forall
i\ \in N$ (11c) $\displaystyle X_{i}\leq\zeta_{i}M,\ \forall i\ \in N$ (11d)
$\displaystyle X_{i}\geq(\zeta_{i}-\mathbf{1}^{T})M+l^{T},\ \forall i\ \in N$
(11e) $\displaystyle X_{i}\geq-\zeta_{i}M,\ \forall i\ \in N.$ (11f)

Similarly, $X_{i}$ denotes row $i$ of matrix $X$. As too large values for $M$
can cause numerical issues during solving optimization problems, we need to
estimate the smallest values that satisfy the equations. Thus, proper values
of $M$ depend on the operating conditions of each network. For this problem,
we choose $M$ based on the voltage angles, acquired from DC power flow.
However, generally, the ideal value of $M$ lies in the range
$\frac{\pi}{6}\leq M\leq\frac{\pi}{2}$.

Another source of nonlinearity arises from the infinity norm in the objective
function, which is classically reformulated using inequality constraints.
Combining the different Big-M and $\infty$-norm reformulations replaces all
non-linearities with the following MILP:

$\displaystyle\min_{\mathbb{E}^{k}}\quad$
$\displaystyle\sum_{i}^{n}{\mu_{i}^{k}}-\alpha\sum_{i}^{n}(1-s_{i}^{k})$ (12a)
$\displaystyle-\mu_{i}^{k}\leq$
$\displaystyle\vec{e}_{i}X^{k}\leq\mu_{i}^{k},\ \forall i\ \in N$ (12b)
$\displaystyle\begin{split}(\ref{eq: thet_psi}),&(\ref{eq: zap}),(\ref{eq:
assign_limit2}),\eqref{eq: diagA},\eqref{eq: assign_adj},\\\ \eqref{eq:
7},&\eqref{eq: A_supvec},\eqref{eq:
lin1},\eqref{lin_2},\eqref{lin_3}.\end{split}$ (12c)

The new formulation of our problem as a MILP in (12) has no nonlinear terms.
However, a MILP is still NP-hard, which poses computational challenges. This
is in part due to a very large search space, which can significantly challenge
the convergence rate and computational efficiency of the optimization process.
Thus, next, we propose to reduce the size of the feasible set with cutting
planes and community detection.

###  4.2 Cutting Plane

The cutting plane simplifies the problem by reducing the feasible set. The
following equation acts as such a cutting plane by limiting the number of
simultaneous reductions in the network:

$\displaystyle\sum_{i}^{n_{s}^{k}}{s_{i}^{k}}\geq n_{s}^{k}-q.$ (13)

In (13), $n_{s}^{k}$ is the number of super-nodes in the network at iteration
$k$, and parameter $q$ is the number of nodes allowed to be reduced. Adding
this constraint to the MILP problem described earlier, i.e. (12), results in a
more tractable optimization problem, which we refer to as DC Opti-KRON.

###  4.3 Community Detection

Community detection refers to the process of identifying groups of nodes in a
network that are more densely connected internally than with the rest of the
network [12]. By leveraging community detection in electrical networks, we can
efficiently segment the network into distinct communities. For each community,
we then apply DC Opti-KRON in parallel, accelerating the network reduction
method. Hence, based on the nodes belonging to each cluster, admittance,
adjacency, and susceptance matrices of the communities are made from the full
admittance matrix. Additionally, to enforce power balance in each community,
power injections of coupling nodes are updated according to the flow of lines
that connect communities. After reducing decoupled communities, We store
clusters’ information i.e. matrix $\Omega$ and vector $s$, including
information for super-nodes and reduced nodes. We aggregate $s$ vectors and
find the final kron reduce network based on that. Additionally, we use
$\Omega$ matrices to find new power injections. This method enables us to
rebuild a reduced version of the full network from reduced sub-networks.
Algorithm 1 describes the presented optimal network reduction method and is
illustrated with Fig. 1.

Algorithm 1 Community-Detection Based Network Reduction Algorithm

1:Input Data: $Y_{b}$, $P$, $\hat{\theta}$, $\alpha$, $q$

2:Community Detection: Find best possible communities.

3:for each community do

4: Find $Y_{\rm community}$, $P_{\rm community}$, $\hat{\theta}_{\rm
community}$ to use in DC Opti-KRON.

5: Update: $k=0$, $s^{0}=\mathbf{1}$, $\Omega^{0}=I$,

6: while $n_{s}^{k}<n_{s}^{k-1}$ do

7: $k\leftarrow k+1$

8: Solve DC Opti-KRON.

9: Update $n_{s}$, $\Omega$, $\Lambda$, $P$.

10: end while

11: Store final $\Omega$ and $s$ of the reduced community.

12:end for

13:Reconstruct reduced network.

Figure 1: Decomposing the full network (left) with community detection to
detect each disjoint community (colored sub-graphs in middle), and
reconstructing the Kron-reduced network based on applying DC Opti-KRON to each
community in parallel (right).

##  5 Experimental Result

This section presents the simulation results for the proposed model applied to
the IEEE 96-RTS test system and 2383-bus Polish transmission network. To solve
optimization problems we used Gurobi solver with the optimality gap set to 0.
To accurately simulate the varying operational conditions of the network in
our model, we incorporated both high- and low-loading scenarios.

###  5.1 IEEE RTS96 73 bus Test System

The IEEE RTS96 73 bus test system consists of three identical 24-bus systems
with an extra bus to connect Area 1 and Area 3. We applied the proposed
network reduction model to this system with different values for $\alpha$ to
obtain different reduction levels. Fig. 2 represents the distribution of MICE
with different levels of reduction.

Figure 2: Distribution of Maximum Intra-Cluster Error (MICE) with different
reduction levels of RTS96 73 bus system.

Each data point in Fig. 2 represents the maximum error among all nodes that
belong to a cluster. For example, for the 96% reduced network, there are only
3 Super-nodes in the reduced grid and MICE values regarding these Super-nodes
are approximately 0.37, 0.2, and 0.17 respectively. Notably, the network with
a 62% reduction level exhibits the lowest MICE values, aligning with
expectations that lower reduction levels typically yield lower errors.
However, the relationship between reduction level and MICE is not strictly
monotonic. For example, the network reduced by 90% demonstrates lower MICE
values compared to those reduced by 75% and 82%, despite a higher reduction
percentage. This non-monotonic relationship can be attributed to the iterative
nature of our algorithm, which follows different reduction paths for each
scenario.

To investigate the effect of the cutting plane on the solution time and the
accuracy, different values for $q$ have been used in simulations. Table 1
summarize the this investigation. Where $q$ equals the total number of nodes
in each iteration ($n_{s}$), signifies no cutting plane is used, which results
in a minimal number of iterations (3 iterations). Now, we can categorize
values of $q$ into three. For higher $q$ values (4 and 5), iterations
increase, and total time extends compared to no cutting plane, but each
iteration is significantly quicker. This suggests a trade-off between total
duration and speed per iteration. The optimal $q$ value for this network
appears to be 3, striking a balance by substantially reducing the time per
iteration efficiently while maintaining the reduction integrity. In contrast,
lower $q$ values (1 and 2) result in the fastest iteration times but at a
significant cost to reduction accuracy, with levels plummeting below optimal
(with no cutting plane). This highlights that while lower $q$ values enhance
speed, they significantly compromise the quality of network reduction.

Table 1: Optimization problem performance with different cutting planes  $q$ |  Time (s) | Iteration |  Avg Time/Iter (s) |  Red. Level
---|---|---|---|---
$n_{s}$ (no CP) |  2703 | 3 |  901.00 |  96%
5 |  5871 | 15 |  391.40 |  96%
4 |  4105 | 18 |  228.05 |  96%
3 |  677 | 24 |  28.21 |  96%
2 |  485 | 19 |  25.53 |  52%
1 |  478 | 32 |  14.94 |  44%

###  5.2 2383-bus Polish transmission network

To identify communities within this network, we employed 2 approaches:
weighted and unweighted. Fast Greedy Maximization Method [13] has been used to
find the communities based on the unweighted graph Laplacian, which revealed
26 distinct communities. Figure 3 visualizes the network graph, where nodes
belonging to the same community are highlighted with unique colors. The
detected communities yielded a notably high modularity score of 0.9. This
score indicates a strong structure of communities within the network,
signifying that the nodes within each detected community are more densely
interconnected as compared to nodes in different communities [14].

Figure 3: Visualization of the 2383-bus Polish transmission network with
community detection.

Fig. 4 represents the distribution of maximum error inside each cluster with
different levels of reduction for this network. After completing the network
reduction, which includes mapping nodes to super-nodes based on community
detection results, we compile these mappings into a pool that defines the
reduced network’s new structure. This reconstituted network is then subjected
to a power flow analysis to assess the accuracy of the reduction. The MICE
values are calculated by comparing the voltage angles and other power flow
parameters between the original and the reconstructed reduced network,
providing a direct measure of the reduction’s impact on network performance.
The presence of outliers in the MICE distribution can be attributed to certain
communities within the network that, post-reduction, adopt a radial-like
configuration with a limited number of nodes. In these cases, the nature of DC
power flow—where voltage angles are particularly sensitive in radial
structures—can lead to heightened variability in error measures. To address
this, identifying the communities that contribute to these outliers is
critical. Subsequently, revisiting the network reduction process for these
specific communities with modified reduction constraints could help achieve a
more balanced error distribution and enhance the overall effectiveness of the
network reduction.

Figure 4: Distribution of MICE with different reduction levels of Polish
transmission network with unweighted community detection.

To compare how different network reduction approaches can affect MICE, we also
used 2 novel approaches for this purpose. To do so, first, we select the
number of nodes we want to keep in the grid (reduction level), and in the
second step, we find the same number of communities using community detection.
To choose super-nodes in each community as the representative of all the nodes
within the communities, central nodes should be selected, where we aggregate
all nodes in each community into its central node. Then, interconnection among
communities can remain the same as the full network or can be computed through
Kron reduction. Fig. 5 demonstrates MICE for 90% reduction level for these
approaches compared to DC Opti-KRON. ’CD’ represents the error after
aggregating communities into single nodes, while ’CD + Kron’ applies Kron
reduction using the central node of communities. ’Opti-KRON’ is our proposed
optimization technique coupled with community detection. Even though DC Opti-
KRON has some outliers, the average of MICE for this approach is smaller than
the others.

Figure 5: MICE distribution for network reduction of a 90% reduced Polish
network.

In addition to unweighted graph laplacian, weighted graph laplacian is
implemented to be utilized in community detection. In this regard, spectral
Clustering has been used, and based on the modularity metric, 26 communities
have been selected. Fig. 6 represents MICE distribution for approximately 81%
and 92% reduced networks using both weighted and unweighted graph Laplacian.
The weighted approach incorporates physical (line admittances), which
influence power flow, resulting in communities that align more closely with
the physical structure of the network. This consideration leads to smaller
deviations in MICE and a reduction in both the number and magnitude of
outliers compared to the unweighted approach.

Figure 6: MICE comparison for reduced networks based on community detection
with weighted and unweighted graph Laplacian.

While both the weighted and unweighted methods identified 26 communities, they
differ significantly in their characteristics. Communities derived from the
weighted graph Laplacian are more ‘physics-aware’, reflecting actual power
flows and network interactions more accurately. Conversely, the unweighted
approach, while potentially less reflective of the physical network
properties, leads to communities with fewer coupling nodes. This
characteristic can be advantageous as it results in simpler, more defined
community boundaries.

##  6 Conclusion and Future work

This paper has presented a novel approach to enhancing the scalability of
network reduction for large transmission networks. By integrating community
detection techniques in conjunction with a DC-based Opti-KRON formulation, we
have scaled Opti-KRON to optimally reduce a 2000-bus network (past work was
limited to networks with 100s of nodes). This is achieved by having community
detection segment the network into smaller, coherent sub-networks, on which we
can readily (and in parallel) apply Opti-KRON to reduce the overall network.
The experimental results on the IEEE 96-RTS test system and the 2383-bus
Polish transmission network validate the efficacy of our approach. The DC
Opti-KRON model consistently shows lower Maximum Intra-Cluster Error (MICE)
values compared to other reduction methods.

Future work could focus on enhancing community detection by incorporating
external equivalency feedback, allowing each community to be analyzed
independently while still influenced by broader grid dynamics. Another
direction for future work is to integrate community detection and the cutting
plane methodologies with the AC Opti-KRON formulation, which is suitable for
distribution networks. This integration would enable a comprehensive co-
reduction method. These advancements could significantly enhance the
scalability and applicability of the Opti-KRON model in complex power systems.

## References

  * [1] Xu Cheng and T.J. Overbye  “PTDF-based power system equivalents”  In _IEEE Transactions on Power Systems_ 20.4, 2005, pp. 1868–1876  DOI: 10.1109/TPWRS.2005.857013
  * [2] Yanda Jiang et al.  “Network Reduction for Power System Planning: Zone Identification”  In _2023 North American Power Symposium (NAPS)_ , 2023, pp. 1–6  DOI: 10.1109/NAPS58826.2023.10318645
  * [3] HyungSeon Oh  “A New Network Reduction Methodology for Power System Planning Studies”  In _IEEE Transactions on Power Systems_ 25.2, 2010, pp. 677–684  DOI: 10.1109/TPWRS.2009.2036183
  * [4] Philipp Fortenbacher, Turhan Demiray and Christian Schaffner  “Transmission Network Reduction Method using Nonlinear Optimization” arXiv: 1711.01079  In _2018 Power Systems Computation Conference (PSCC)_ , 2018, pp. 1–7  DOI: 10.23919/PSCC.2018.8442974
  * [5] Di Shi and Daniel J. Tylavsky  “A Novel Bus-Aggregation-Based Structure-Preserving Power System Equivalent”  In _IEEE Transactions on Power Systems_ 30.4, 2015, pp. 1977–1986  DOI: 10.1109/TPWRS.2014.2359447
  * [6] J.. Ward  “Equivalent Circuits for Power-Flow Studies”  In _Transactions of the American Institute of Electrical Engineers_ 68.1, 1949, pp. 373–382  DOI: 10.1109/T-AIEE.1949.5059947
  * [7] Florian Dorfler and Francesco Bullo  “Kron Reduction of Graphs With Applications to Electrical Networks”  In _IEEE Transactions on Circuits and Systems I: Regular Papers_ 60.1, 2013, pp. 150–163  DOI: 10.1109/TCSI.2012.2215780
  * [8] Quentin Ploussard, Luis Olmos and Andres Ramos  “An Efficient Network Reduction Method for Transmission Expansion Planning Using Multicut Problem and Kron Reduction”  In _IEEE Transactions on Power Systems_ 33.6, 2018, pp. 6120–6130  DOI: 10.1109/TPWRS.2018.2842301
  * [9] Raul Ribeiro, Alexandre Street, Fernando Mancilla–David and Alejandro Angulo  “Equivalent Reduced DC Network Models With Nonlinear Load Functions: A Data-Driven Approach”  In _IEEE Transactions on Power Systems_ 39.2, 2024, pp. 3021–3032  DOI: 10.1109/TPWRS.2023.3274919
  * [10] Yujia Zhu and Daniel Tylavsky  “An Optimization-Based DC-Network Reduction Method”  In _IEEE Transactions on Power Systems_ 33.3, 2018, pp. 2509–2517  DOI: 10.1109/TPWRS.2017.2745492
  * [11] Samuel Chevalier and Mads R. Almassalkhi  “Towards Optimal Kron-based Reduction Of Networks (Opti-KRON) for the Electric Power Grid”  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 2022, pp. 5713–5718  DOI: 10.1109/CDC51059.2022.9992730
  * [12] Michelle Girvan and Mark EJ Newman  “Community structure in social and biological networks”  In _Proceedings of the national academy of sciences_ 99.12 National Acad Sciences, 2002, pp. 7821–7826
  * [13] Aaron Clauset, Mark EJ Newman and Cristopher Moore  “Finding community structure in very large networks”  In _Physical review E_ 70.6 APS, 2004, pp. 066111
  * [14] Mark EJ Newman and Michelle Girvan  “Finding and evaluating community structure in networks”  In _Physical review E_ 69.2 APS, 2004, pp. 026113