# Joint Learning of
Network Topology and Opinion Dynamics
Based on Bandit Algorithms

Yu Xing  Xudong Sun  Karl H. Johansson  Division of Decision and Control
Systems, EECS, KTH Royal Institute of Technology; Digital Futures, SE-10044
Stockholm, Sweden
(e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>kallej@kth.se).

###### Abstract

We study joint learning of network topology and a mixed opinion dynamics, in
which agents may have different update rules. Such a model captures the
diversity of real individual interactions. We propose a learning algorithm
based on multi-armed bandit algorithms to address the problem. The goal of the
algorithm is to find each agent’s update rule from several candidate rules and
to learn the underlying network. At each iteration, the algorithm assumes that
each agent has one of the updated rules and then modifies network estimates to
reduce validation error. Numerical experiments show that the proposed
algorithm improves initial estimates of the network and update rules,
decreases prediction error, and performs better than other methods such as
sparse linear regression and Gaussian process regression.

###### keywords:

Social networks, identification, network inference, bandit algorithms

††thanks: This work was supported by the Knut & Alice Wallenberg Foundation,
the Swedish Research Council, and the Swedish Foundation for Strategic
Research.

##  1 Introduction

Opinion dynamics characterize how individuals interact with each other and
change their opinions, which has attracted researchers in various disciplines
from control to physics for decades (Proskurnikov and Tempo (2017)). There is
a growing interest in learning such dynamics (Ravazzi et al. (2021a)). Most
researches formulate the learning problem based on a single model. In real
networks agents may have different update rules, so there is a need to study
how to learn such networked dynamics.

###  1.1 Related Work

This paper considers opinion dynamics with continuous states (Proskurnikov and
Tempo (2017)). A classic example is the DeGroot model (DeGroot (1974)), in
which agents update to the opinion average of their neighbors. Friedkin and
Johnsen (1999) generalize this model by assuming the agents are influenced by
their initial positions. Bounded confidence models, such as the
Hegselmann–Krause (HK) model (Hegselmann et al. (2002)), characterize the case
when agents only interact with those who hold opinions similar to themselves.
Opinion dynamics over signed networks are another important class of models
(Shi et al. (2019)). Signed networks have not only positive but also negative
edges. There has been research on testing opinion dynamics models against
data. Clemm von Hohenberg et al. (2017) find the existence of linear
averaging. The FJ model has been validated in small-group experiments
(Friedkin and Johnsen (1999)). Recent empirical studies based on large-scale
datasets (Kozitsin (2021, 2022)) also suggest the presence of bounded
confidence and negative influence rules.

With the increasing availability of large-scale online datasets, the interest
in learning influence networks has been growing (Ravazzi et al. (2021a)). De
et al. (2014) and Wai et al. (2016) study sparse network learning of the
DeGroot model. Ravazzi et al. (2017) investigate the learning of the FJ model,
and Ravazzi et al. (2021b) consider the case where only partial observations
are available. Wai et al. (2019) study joint learning of network topology and
system parameters for bounded confidence models. Learning based on quantized
observations are studied in Xing et al. (2022); Xie et al. (2023). Most of
these papers assume that the type of the dynamics model to be learned is known
and every agent follows the same update rule. This is often not the case in
real networks, so it is necessary to study learning of networked dynamics
mixing multiple update rules. Automated machine learning (AutoML) is an
emerging domain studing how to design algorithms that automatically build
machine learning (ML) models with optimized hyperparameter settings (He et al.
(2021)). Thornton et al. (2012) introduce the sequential model-based algorithm
configuration to select algorithms and optimize hyperparameters. Li et al.
(2017); Sun et al. (2019) propose methods based on multi-armed bandit and
reinforcement learning algorithms.

###  1.2 Contribution

We study joint learning of network topology and a mixed opinion dynamics,
where agents may have different update rules. In the learning problem, the
network and the types of agent update rules are unknown. We propose a learning
algorithm based on multi-armed bandits to address the problem. The algorithm
starts with initial estimates of the network and the agent update rules. At
each iteration, it either refines the network estimates by exploiting a given
update rule by modifying the adjacency matrix, or examines the validation
error of other update rules with small probability. Numerical experiments show
that the proposed algorithm can improve the initial estimates, with better
network recovery and smaller prediction error. The algorithm provides a search
strategy for learning opinion dynamics models with multiple update rules, and
performs better than linear sparse regression and Gaussian process regression.
Compared with existing network learning methods, the proposed algorithm can
get rid of the assumption of a single model, and can include multiple sets of
constraints. Thus the proposed algorithm can provide better possibility for
learning real dynamics. The algorithm is inspired by AutoML, but the problem
cannot be solved directly by AutoML methods. A multi-agent system is
considered here, and the best model needs be selected for each agent. In
addition, the network and dynamics are coupled.

###  1.3 Outline

The rest of the paper is organized as follows. Section 2 introduces several
opinion dynamics models and defines the mixed model. Section 3 formulates the
learning problem. We propose a learning algorithm for the mixed model in
Section 4. Section 5 presents numerical experiments.

_Notation._ Let $\mathbf{1}_{n}$ be the $n$-dimensional all-one vector, and
$\mathbf{0}_{n,m}$ be the $n\times m$-dimensional all-zero matrix. The
Euclidean norm and the $l_{1}$ norm are $\|\cdot\|$ and $\|\cdot\|_{1}$. For a
vector $x\in\mathbb{R}^{n}$, denote its subvector from $i$-th to $j$-the
component by $x_{i:j}$, $i\leq j$. For a matrix
$A=[a_{ij}]\in\mathbb{R}^{n\times n}$, denote its $(i,j)$-th entry by $a_{ij}$
or $[A]_{ij}$ and denote its $i$-th column (row) by $[A]_{:,i}$ ($[A]_{i,:}$).
The function $\mathbb{I}_{[\textup{property}]}$ is the indicator function. If
the property is stated for a vector, then the function is entry-wise (e.g.,
$\mathbb{I}_{[y>0]}=[\mathbb{I}_{[y_{1}>0]}~{}\cdots~{}\mathbb{I}_{[y_{n}>0]}]^{\text{T}}$
for $y\in\mathbb{R}^{n}$). Denote the entry-wise sign of a vector $y$ by
$\textup{sgn}(y)$. The structure of a network is defined by an undirected
graph $\mathcal{G}=(\mathcal{V},\mathcal{E},A)$, where
$\mathcal{V}=\\{1,\dots,n\\}$ is the agent set, $\mathcal{E}$ is the edge set,
and $A$ is the adjacency matrix. Each edge $\\{i,j\\}\in\mathcal{E}$ has a
sign, either positive or negative. The disjoint sets $\mathcal{E}^{+}$ and
$\mathcal{E}^{-}$ collect all positive and negative edges, respectively. The
positive (negative) neighbors of an agent $i$ is denoted by
$\mathcal{N}_{i}^{+}=\\{j:\\{i,j\\}\in\mathcal{E}^{+}\\}$
($\mathcal{N}_{i}^{-}=\\{j:\\{i,j\\}\in\mathcal{E}^{-}\\}$), and
$\mathcal{N}_{i}:=\mathcal{N}_{i}^{+}\cup\mathcal{N}_{i}^{-}$. An agent $i$
has positive and negative degrees $d_{i}^{+}=|\mathcal{N}_{i}^{+}|$ and
$d_{i}^{-}=|\mathcal{N}_{i}^{-}|$, respectively, and degree
$d_{i}:=d_{i}^{+}+d_{i}^{-}$. The adjacency matrix $A$ satisfies that
$a_{ij}=1$ if $\\{i,j\\}\in\mathcal{E}^{+}$, $a_{ij}=-1$ if
$\\{i,j\\}\in\mathcal{E}^{-}$, and $a_{ij}=0$ if
$\\{i,j\\}\not\in\mathcal{E}$.

##  2 Preliminaries

This section introduces considered models. We assume that each agent $i$ has a
self loop $\\{i,i\\}\in\mathcal{E}^{+}$ and has a state $x_{i}(t)$ at time
$t\in\mathbb{N}$. Denote the state vector by $x(t)\in\mathbb{R}^{n}$.

The DeGroot Model (DeGroot (1974)) is one of the most classic opinion
dynamics. The underlying graph does not have negative edges (i.e.,
$\mathcal{E}^{-}=\emptyset$). Each agent $i$ updates its opinion to the
weighed average of its neighbors’ opinions:

$x_{i}(t+1)=\sum_{j=1}^{n}w_{ij}x_{j}(t)=:f^{\mathcal{M}_{\textup{DG}}}(x(t),\theta^{(\mathcal{M}_{\textup{DG}},i)}),$
(1)

where $t\in\mathbb{N}$ and $w_{ij}$ is the influence weight of the agent $j$
on the agent $i$ and we denote

$\theta^{(\mathcal{M}_{\textup{DG}},i)}=[w_{i1}~{}\cdots~{}w_{in}]^{\text{T}},~{}i\in\mathcal{V}.$
(2)

The weight $w_{ij}$ satisfies that $w_{ij}>0$ if $a_{ij}=1$, and $w_{ij}=0$ if
$a_{ij}=0$. In addition, $\sum_{i=1}^{n}w_{ij}=1$.

The FJ model generalizes the DeGroot model. Here $\mathcal{E}^{-}=\emptyset$,
and every agent $i$ has susceptibility $\lambda_{i}\in[0,1]$ to others. An
agent $i$ updates according to the following rule

$\displaystyle x_{i}(t+1)$
$\displaystyle=\lambda_{i}\bigg{(}\sum_{i=1}^{n}w_{ij}x_{j}(t)\bigg{)}+(1-\lambda_{i})x_{i}(0)$
$\displaystyle=:f^{\mathcal{M}_{\textup{FJ}}}(x(t),\theta^{(\mathcal{M}_{\textup{FJ}},i)}),$
(3)

where $w_{ij}$ are nonnegative weights such that $\sum_{j}w_{ij}=1$,
$w_{ij}>0$ if $a_{ij}=1$, and $w_{ij}=0$ if $a_{ij}=0$. Here we denote

$\theta^{(\mathcal{M}_{\textup{FJ}},i)}:=[w_{i1}~{}\cdots~{}w_{in}~{}\lambda_{i}]^{\text{T}},i\in\mathcal{V}.$
(4)

Note that $f^{\mathcal{M}_{\textup{FJ}}}$ also depends on $x_{i}(0)$, which is
omitted for notation simplicity. When $\lambda_{i}\not=1$, the opinion of the
agent $i$ is constantly influenced by its initial position $x_{i}(0)$. An
agent $i$ with $\lambda_{i}=0$ is called stubborn and never changes its
opinion. When $\lambda_{i}=1$ for all $i\in\mathcal{V}$, the FJ model (3)
degenerates to the DeGroot model (1).

The repelling negative dynamics (Shi et al. (2019)) can capture the opinion
evolution where the network contains negative edges (i.e.,
$\mathcal{E}^{-}\not=\emptyset$):

$\displaystyle x_{i}(t+1)$
$\displaystyle=x_{i}(t)+\alpha_{i}\sum_{j\in\mathcal{N}_{i}^{+}}(x_{j}(t)-x_{i}(t))-\beta_{i}\sum_{j\in\mathcal{N}_{i}^{-}}(x_{j}(t)-x_{i}(t))$
$\displaystyle=(1-\alpha_{i}d_{i}^{+}+\beta_{i}d_{i}^{-})x_{i}(t)+\alpha_{i}\sum_{j\in\mathcal{N}_{i}^{+}}x_{j}(t)-\beta_{i}\sum_{j\in\mathcal{N}_{i}^{-}}x_{j}(t)$
$\displaystyle=:f^{\mathcal{M}_{\textup{RP}}}(x(t),\theta^{(\mathcal{M}_{\textup{RP}},i)})$
(5)

where $0<\alpha_{i}\leq 1/d_{i}^{+}$ and $\beta_{i}>0$ are the influence
strength of positive and negative neighbors on the agent $i$, respectively.
Here we denote the parameters

$\theta^{(\mathcal{M}_{\textup{RP}},i)}:=[w_{i1}~{}\cdots~{}w_{in}]^{\text{T}},~{}i\in\mathcal{V},$
(6)

where $w_{ii}=1-\alpha_{i}d_{i}^{+}+\beta_{i}d_{i}^{-}$, $w_{ij}=\alpha_{i}$
if $j\in\mathcal{N}_{i}^{+}\setminus\\{i\\}$, $w_{ij}=-\beta_{i}$ if
$j\in\mathcal{N}_{i}^{-}$, and $w_{ij}=0$ if $j\not\in\mathcal{N}_{i}$. When
$\mathcal{N}_{i}^{-}=\emptyset$ or $\beta_{i}=0$ for all $i\in\mathcal{V}$,
the model (5) becomes the DeGroot model (1).

Now we assume $\mathcal{E}^{-}=\emptyset$ again, and introduce the social HK
model (Parasnis et al. (2018)). In the original HK model, the network is
assumed to be complete, which is not realistic because individuals in a large
network cannot know everyone. The social HK model addresses this issue by
introducing an underlying network: At each time $t$, an agent $i$ selects a
set of trusted individuals from its neighbors (i.e., agents that have opinions
similar to $i$),

$\mathcal{I}_{i}(t)=\\{j\in\mathcal{N}_{i}:|x_{j}(t)-x_{i}(t)|\leq c_{i}\\},$

where $c_{i}$ is the confidence bound of $i$. Then the agent updates its
opinions as the average of $x_{j}(t)$:

$x_{i}(t+1)=\frac{1}{|\mathcal{I}_{i}(t)|}\sum_{j\in\mathcal{I}_{i}(t)}x_{j}(t)=:f^{\mathcal{M}_{\textup{HK}}}(x(t),\theta^{(\mathcal{M}_{\textup{HK}},i)}),$
(7)

where

$\theta^{(\mathcal{M}_{\textup{HK}},i)}:=c_{i},~{}i\in\mathcal{V}.$ (8)

Note that $f^{\mathcal{M}_{\textup{HK}}}$ depends on $i$, which is omitted for
notation simplicity. When all $c_{i}$ are larger than the range of $x(0)$, the
model (7) reduces to the DeGroot model (1).

##  3 Problem Formulation

Agents in real networks may have completely different update rules, as
suggested by empirical evidence (Clemm von Hohenberg et al. (2017); Friedkin
and Johnsen (1999); Kozitsin (2021, 2022)). Thus, to learn the real network
and the dynamics, it is natural to consider a mixture of opinion update rules
Dong et al. (2017); Wu et al. (2022). A mixed opinion dynamics is defined as
follows.

###### Definition 1

A mixed opinion dynamics over an undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},A)$ with $|\mathcal{V}|=n$ is a
discrete-time system with states $x(t)\in\mathbb{R}^{n}$, $t\in\mathbb{N}$,
satisfying that

$x_{i}(t+1)=f^{\mathcal{M}_{i}}(x(t),\theta^{(\mathcal{M}_{i},i)}),$

where
$\mathcal{M}_{i}\in\\{\mathcal{M}_{\textup{DG}},\mathcal{M}_{\textup{FJ}},\mathcal{M}_{\textup{RP}},\mathcal{M}_{\textup{HK}}\\}$
is the type of update rule of the agent $i$, $f^{\mathcal{M}_{i}}$ are given
in (1), (3), (5), and (7), and $\theta^{(\mathcal{M}_{i},i)}$ in (2), (4),
(6), and (8).

To make the definition well-posed, we introduce the following assumptions.

###### Assumption 2

(i) The graph $\mathcal{G}$ is undirected and connected.
(ii) There exists a positive constant $\varepsilon_{\lambda}\in(0,1)$ such
that, if $\mathcal{M}_{i}=\mathcal{M}_{\textup{FJ}}$ for some
$i\in\mathcal{V}$, then
$\varepsilon_{\lambda}\leq\theta^{(\mathcal{M}_{\textup{FJ}},i)}_{n+1}\leq
1-\varepsilon_{\lambda}$.
(iii) For $i\in\mathcal{V}$, $\mathcal{N}_{i}^{-}\not=\emptyset$ holds if and
only if $\mathcal{M}_{i}=\mathcal{M}_{\textup{RP}}$.
(iv) If $\mathcal{M}_{i}=\mathcal{M}_{\textup{HK}}$ for $i\in\mathcal{V}$,
then
$\theta^{(\mathcal{M}_{\textup{HK}},i)}<\max_{j\in\mathcal{V}}\\{|x_{j}(0)|\\}$.

###### Remark 3

The second assumption ensures that the susceptibility of an agent $i$ should
be neither too small nor too large. The third assumption guarantees that
agents who have other update rules do not have negative edges. The last
assumption ensures that the agent with a HK update rule cannot be considered
as a DeGroot-type agent.

We consider the joint learning of the network topology and the dynamics for
the mixed model:

Problem. Given a trajectory $\\{x(0),x(1),\dots,x(T)\\}$ of the mixed model,
propose an algorithm jointly learning the network $\mathcal{G}$, the types of
agent update rules $\\{\mathcal{M}_{i}\\}$, and the parameters of each agent
$\\{\theta^{(\mathcal{M}_{i},i)}\\}$, where $T\geq 1$ is the final time step
of the trajectory.

##  4 Learning Algorithms

This section presents separate learning algorithms for models
$\\{\mathcal{M}_{\textup{DG}},\mathcal{M}_{\textup{FJ}},\mathcal{M}_{\textup{RP}},\mathcal{M}_{\textup{HK}}\\}$,
and proposes a learning algorithm for the mixed model. Denote the data
matrices by $\bm{X}:=[x(0)~{}x(1)~{}\dots~{}x(T-1)]^{\text{T}}$ and
$b^{(i)}:=[x_{i}(1)~{}\dots~{}x_{i}(T)]^{\text{T}}$, $i\in\mathcal{V}$, and
the estimates of the adjacency matrix $A$, agent update rules
$\\{\mathcal{M}_{i}\\}$, and the parameter
$\\{\theta^{(\mathcal{M}_{i},i)}\\}$ by $\hat{A}$,
$\\{\hat{\mathcal{M}_{i}}\\}$, and $\\{\hat{\theta}^{(\mathcal{M}_{i},i)}\\}$,
respectively.

Algorithm 1
Learn$\mathcal{M}_{\textup{DG}}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: For $y\in\mathbb{R}^{n}$, solve  $\displaystyle\min~{}$
$\displaystyle\|y\|_{1}$ s.t. $\displaystyle\bm{X}y=b^{(i)},$
$\displaystyle\mathbf{1}^{T}y=1,$ $\displaystyle
y_{j}\geq\varepsilon_{w},~{}j\in\mathcal{N}_{i}^{(\textup{neigh})},$
$\displaystyle y_{j}=0,~{}j\in\mathcal{N}_{i}^{(\textup{non})},$
$\displaystyle y_{j}\geq
0,~{}j\in\mathcal{V}\setminus(\mathcal{N}_{i}^{(\textup{neigh})}\cup\mathcal{N}_{i}^{(\textup{non})}).$

2: Return $[\hat{A}]_{i,:}=\mathbb{I}_{[y^{\text{T}}>0]}$,
$\hat{\theta}^{(\mathcal{M}_{\textup{DG}},i)}=y$.

Algorithm 2
Learn$\mathcal{M}_{\textup{FJ}}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: For $y\in\mathbb{R}^{n+1}$, solve  $\displaystyle\min~{}$
$\displaystyle\|y\|_{1}$ s.t.
$\displaystyle[\bm{X}~{}[\bm{X}]_{1,i}\mathbf{1}_{T}]y=b^{(i)},$
$\displaystyle\mathbf{1}^{T}y=1,$ $\displaystyle
y_{j}\geq\varepsilon_{w}\varepsilon_{\lambda},~{}j\in\mathcal{N}_{i}^{(\textup{neigh})},$
$\displaystyle y_{j}=0,~{}j\in\mathcal{N}_{i}^{(\textup{non})},$
$\displaystyle y_{j}\geq
0,~{}j\in\mathcal{V}\setminus(\mathcal{N}_{i}^{(\textup{neigh})}\cup\mathcal{N}_{i}^{(\textup{non})}),$
$\displaystyle\varepsilon_{\lambda}\leq y_{n+1}\leq 1-\varepsilon_{\lambda}.$

2: Return $[\hat{A}]_{i,:}=\mathbb{I}_{[y_{1:n}^{\text{T}}>0]}$,
$\hat{\theta}^{(\mathcal{M}_{\textup{FJ}},i)}_{1:n}=y_{1:n}/(1-y_{n+1})$,
$\hat{\theta}^{(\mathcal{M}_{\textup{FJ}},i)}_{n+1}=1-y_{n+1}$.

Algorithm 3
Learn$\mathcal{M}_{\textup{RP}}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: For $y\in\mathbb{R}^{n}$, solve  $\displaystyle\min~{}$
$\displaystyle\|y\|_{1}$ s.t. $\displaystyle\bm{X}y=b^{(i)},$ $\displaystyle
y_{j}\geq\varepsilon_{w},j\in\mathcal{N}_{i}^{(\textup{neigh})},$
$\displaystyle y_{j}=0,j\in\mathcal{N}_{i}^{(\textup{non})}.$

2: Return $[\hat{A}]_{i,:}=\textup{sgn}(y^{\text{T}})$,
$\hat{\theta}^{(\mathcal{M}_{\textup{RP}},i)}=y$.

###  4.1 Learning of Single Models

Note that $\theta^{(\mathcal{M}_{\textup{DG}},i)}$ satisfies
$\bm{X}\theta^{(\mathcal{M}_{\textup{DG}},i)}=b^{(i)}$, for $i\in\mathcal{V}$
such that $\mathcal{M}_{i}=\mathcal{M}_{\textup{DG}}$. To learn
$\theta^{(\mathcal{M}_{\textup{DG}},i)}$ we look for a sparse solution to the
least $l_{1}$-norm problem given in Algorithm 1. The motivation is that in
practice only a few samples of the process are available ($T<n$) but real
networks are often sparse (Ravazzi et al. (2017)). The parameter constraints
$\mathbf{1}^{T}y=1$ and $y_{j}\geq 0$, $1\leq j\leq n$, are added. The
algorithm has two additional inputs $\mathcal{N}_{i}^{(\textup{neigh})}$ and
$\mathcal{N}_{i}^{(\textup{non})}$, which are subsets of $\mathcal{V}$. We
introduce these two sets to search for other solutions. If an agent $j$ is
considered as a neighbor of the agent $i$
($j\in\mathcal{N}_{i}^{(\textup{neigh})}$), we add the constraint
$y_{j}\geq\varepsilon_{w}$, where $\varepsilon_{w}$ is a small positive
constant. If $j$ is assumed to not be a neighbor
($j\in\mathcal{N}_{i}^{(\textup{non})}$), the constraint $y_{j}=0$ is imposed.

We can similarly solve a system of linear equations to learn the parameters in
the FJ model (3). We search for a sparse solution in Algorithm 2. The
algorithm has two hyperparameters: the lower bound of influence weights
$\varepsilon_{w}>0$, and the bound for the susceptibility
$\varepsilon_{\lambda}\in(0,1)$ given in Assumption 2 (ii).

The expression of the repelling negative dynamics (5) is the same as (1), but
(5) has less constraints. Hence so does Algorithm 3. In Section 5.2 we
introduce more constraints for this algorithm.

Algorithm 4
Learn$\mathcal{M}_{\textup{HK}}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: Set $[\hat{A}]_{i,:}$ such that $[\hat{A}]_{i,j}=1$ if
$j\in\mathcal{N}_{i}^{(\textup{neigh})}$ and $[\hat{A}]_{i,j}=0$ otherwise.

2: for $t$ from $0$ to $T-1$ do

3: Sort the neighbors $j\in\mathcal{N}_{i}^{(\textup{neigh})}$ by the distance
of $x_{j}(t)$ from $x_{i}(t)$ to be $x_{i_{1}}$, $\dots$, $x_{i_{n_{i}}}$,
where $n_{i}:=[\hat{A}]_{i,:}\mathbf{1}$.

4: Compute  $\displaystyle\hat{x}_{i}^{(m)}(t+1)$
$\displaystyle=\frac{1}{m}\sum_{j=1}^{m}x_{i_{j}}(t),~{}1\leq m\leq n_{i},$
$\displaystyle m(t)$ $\displaystyle=\max\bigg{\\{}\underset{1\leq m\leq
n_{i}}{\arg\min}|\hat{x}_{i}^{(m)}(t+1)-x_{i}(t+1)|\bigg{\\}},$ $\displaystyle
c(t)$ $\displaystyle=|x_{i_{m(t)+1}}(t)-x_{i}(t)|-\varepsilon_{c}.$

5: end for

6: Compute  $\displaystyle t^{*}$ $\displaystyle=\underset{0\leq t\leq
T-1}{\arg\min}c(t),$ $\displaystyle c^{*}$ $\displaystyle=c(t^{*}).$

7: Return $[\hat{A}]_{i,:}$,
$\hat{\theta}^{(\mathcal{M}_{\textup{HK}},i)}=c^{*}$.

Algorithm 5 $\varepsilon$-Greedy($\\{x(0),\dots,x(T)\\}$)

1: Choose $\tilde{T}$ and divide the trajectory into a training dataset
$\bm{X}_{\textup{tr}}=[x(0)~{}\cdots~{}x(\tilde{T})]^{\text{T}}$ and a
validation dataset
$\bm{X}_{\textup{val}}=[x(\tilde{T}+1)~{}\cdots~{}x(T)]^{\text{T}}$.

2: Initialize the $Q$-table $Q(0)$, the estimates of update rule types
$\hat{k}(0)$, the estimates of the adjacency matrix for each model
$\hat{A}^{(M[m])}(0)$, and the parameter estimates
$\hat{\theta}^{(M[m],i)}(0)$, $1\leq m\leq 4$, where the look-up table $M$ is
s.t. $M[1]=\mathcal{M}_{\textup{DG}}$, $M[2]=\mathcal{M}_{\textup{FJ}}$,
$M[3]=\mathcal{M}_{\textup{RP}}$, $M[4]=\mathcal{M}_{\textup{HK}}$.

3: for $l$ from $1$ to $n_{\textup{iter}}$ do

4: for $i$ from $1$ to $n$ do

5: With probability (w.p.) $1-\varepsilon_{\textup{M}}$, set
$k_{i}(l)=\underset{1\leq m\leq 4}{\arg\max}[Q(l)]_{i,m}.$

6: W.p. $\varepsilon_{\textup{M}}$, generate $k_{i}(l)\in\\{1,2,3,4\\}$
uniformly.

7: end for

8: W.p. $1-\varepsilon_{\textup{G}}$, let
$[\tilde{A}]_{i,:}:=[\hat{A}^{(k_{i}(l))}(l-1)]_{i,:}$, for $i\in\mathcal{V}$.
W.p. $\varepsilon_{\textup{G}}$, randomly generate an adjacency matrix
$\tilde{A}$.

9: for $i$ from $1$ to $n$ do

10: for $j$ from $1$ to $n$ and $j\not=i$ do

11: If $\tilde{A}_{ij}=0$ set
$\mathcal{N}_{i}^{\textup{(neigh)}}:=\\{q\in\mathcal{V}:\tilde{A}_{iq}=1\\}\cup\\{j\\}$
and $\mathcal{N}_{i}^{\textup{(non)}}:=\emptyset$. If $\tilde{A}_{ij}=1$ set
$\mathcal{N}_{i}^{\textup{(neigh)}}:=\\{q\in\mathcal{V}:\tilde{A}_{iq}=1\\}\setminus\\{j\\}$
and $\mathcal{N}_{i}^{\textup{(non)}}:=\\{j\\}$.
$\displaystyle([\hat{A}_{\textup{temp}_{j}}]_{i,:},\hat{\theta}_{\textup{temp}_{j}}^{(M[k_{i}(l)],i)})$
$\displaystyle=$
$\displaystyle\textup{Learn}M[k_{i}(l)]([\bm{X}_{\textup{tr}}]_{1:\tilde{T}-1,:},[\bm{X}_{\textup{tr}}]_{2:\tilde{T},i},\mathcal{N}_{i}^{\textup{(neigh)}},\mathcal{N}_{i}^{\textup{(non)}})$

12: end for

13: Compute the validation error of $f^{M[k_{i}(l)]}$ based on
$([\hat{A}_{\textup{temp}_{j}}]_{i,:},\hat{\theta}_{\textup{temp}_{j}}^{(M[k_{i}(l)],i)})$,
$j\in\mathcal{V}\setminus\\{i\\}$. Choose the smallest error $p_{i}(l)$ with
respect to $j$, update $[\hat{A}^{(M[k_{i}(l)])}(l)]_{i,:}$,
$\hat{\theta}^{(M[k_{i}(l)],i)}(l)$ accordingly,
$[\hat{A}^{(M[m])}(l)]_{i,:}=[\hat{A}^{(M[m])}(l-1)]_{i,:}$ and
$\hat{\theta}^{(M[m],i)}(l)=\hat{\theta}^{(M[m],i)}(l-1)$ for
$m=\\{1,2,3,4\\}\setminus\\{k_{i}(l)\\}$, and
$[Q(l)]_{i,k_{i}(l)}=(1-\alpha)[Q(l-1)]_{i,k_{i}(l)}-\alpha\log(p_{i}(l)).$

14: end for

15: end for

16: Let $m_{i}:=\underset{1\leq m\leq
4}{\arg\max}[Q(n_{\textup{iter}})]_{i,m}$, $\hat{\mathcal{M}_{i}}:=M[m_{i}]$,
$[\hat{A}]_{i,:}=[\hat{A}^{(\hat{\mathcal{M}_{i}})}(n_{\textup{iter}})]_{i,:}$,
and
$\hat{\theta}^{(\hat{\mathcal{M}_{i}},i)}=\hat{\theta}^{(\hat{\mathcal{M}_{i}},i)}(n_{\textup{iter}})$,
$i\in\mathcal{V}$.

17: Return $\hat{A}$, $\\{\hat{\mathcal{M}_{i}}\\}$, and
$\\{\hat{\theta}^{(\hat{\mathcal{M}_{i}},i)}\\}$.

For the Social HK model, it is only possible to obtain a bound for the
confidence bounds based on finite samples. We provide a heuristic to estimate
the confidence bound. Numerical experiments in Section 5 show that the
proposed algorithm can have relatively small prediction error. Assume first
that the network topology is known. For an agent $i$ with
$\mathcal{M}_{i}=\mathcal{M}_{\textup{HK}}$, sort $i$’s neighbors by their
states’ distance from $x_{i}(t)$ and denote the sorted neighbors by
$i_{1},i_{2},\dots,i_{|\mathcal{N}_{i}|}$, where $i_{1}=i$. Then compute the
averages $(\sum_{j=1}^{m}x_{i_{j}}(t))/m$, $1\leq m\leq|\mathcal{N}_{i}|$, and
find the index such that the average has the smallest distance from
$x_{i}(t$$+1)$, i.e., ${\arg\min}_{1\leq
m\leq|\mathcal{N}_{i}|}|(\sum_{j=1}^{m}x_{i_{j}}(t))/m-x_{i}(t+1)|$. If no
noise exists, there exist $m_{1}<\dots<m_{q}$ such that
$|(\sum_{j=1}^{m_{r}}x_{i_{j}}(t))/m_{r}-x_{i}(t+1)|=0$, where $1\leq r\leq q$
and $q\geq 1$. We then can conclude that $|x_{i_{m_{q+1}}}(t)-x_{i}(t)|$ is a
strict upper bound for the confidence bound
$\theta^{(\mathcal{M}_{\textup{HK}},i)}=c_{i}$. If the topology is unknown, to
obtain a bound we need test all $2^{n-1}$ combinations. We narrow down the
search by introducing testing sets $\mathcal{N}_{i}^{(\textup{neigh})}$ and
$\mathcal{N}_{i}^{(\textup{non})}$, as in the preceding algorithms. In
Algorithm 4, for each sample $(x(t),x_{i}(t+1))$, we obtain an estimate of the
confidence bound $c(t)$ by conducting the process discussed previously. In the
algorithm, $\varepsilon_{c}$ is a small positive number to make sure that the
upper bound is strict. For all $0\leq t\leq T-1$, if the neighbor set is
correct, the confidence bound should be smaller than all $c(t)$. The algorithm
returns an approximation of $i$’s dynamics.

###  4.2 Learning of Mixed Model

After presenting the learning algorithms for each update rule, now we are
ready to introduce the learning algorithm for the mixed model. We propose a
multi-armed bandit algorithm (Algorithm 5) to address the problem, and
consider the four types of update rules as four arms. We introduce a $Q$-table
$Q(l)\in\mathbb{R}^{n\times 4}$ for each iteration $l$. The entry
$[Q(l)]_{i,m}$ indicates the payoff of refining model parameters of the arm
$M[m]$ for the agent $i$ at the iteration $l$, where $1\leq m\leq 4$ and we
define the look-up table $M$ with respect to
$\\{\mathcal{M}_{\textup{DG}},\mathcal{M}_{\textup{FJ}},\mathcal{M}_{\textup{RP}},\mathcal{M}_{\textup{HK}}\\}$
such that $M[1]=\mathcal{M}_{\textup{DG}}$, $M[2]=\mathcal{M}_{\textup{FJ}}$,
$M[3]=\mathcal{M}_{\textup{RP}}$, $M[4]=\mathcal{M}_{\textup{HK}}$. We run
Algorithms 1–4 for each $i$ with $\mathcal{N}_{i}^{(\textup{neigh})}=\\{i\\}$
and $\mathcal{N}_{i}^{(\textup{non})}=\emptyset$, to initialize the estimates
of update rule types $\hat{k}(0)\in\\{1,2,3,4\\}^{n}$, the estimates of the
adjacency matrix for each model $\hat{A}^{(M[m])}(0)$, and the parameter
estimates $\hat{\theta}^{(M[m],i)}(0)$. $[Q(0)]_{i,m}$ is set to be the
negative logarithm of validation error of the model $M[m]$ for $i$ (Line $2$).

At each iteration and for each agent, the algorithm tries to fit the data into
the model with the best payoff with probability $1-\varepsilon_{\textup{M}}$.
With exploration probability $\varepsilon_{\textup{M}}$, the algorithm
attempts to refine estimates of other models (Line $4$–$7$). At each
iteration, the algorithm modifies the adjacency matrix corresponding to the
selected models with probability $1-\varepsilon_{\textup{G}}$, and modifies a
randomly generated adjacency matrix with probability
$\varepsilon_{\textup{G}}$ (Line $8$). The algorithm then examines whether
removing or adding an edge can improve validation error (Line $11$). Next, the
algorithm updates the payoff $Q$ with a step-size $\alpha$ and the parameter
estimates (Line $13$). Finally the algorithm returns parameter estimates,
according to the update rule with the best payoff (Line $17$).

(a) $T=10$ (b) $T=15$ (c) $T=20$

Figure 1:  Performance of algorithms IE, $\varepsilon$G, RS, OLS, and SS for
network topology recovery.

(a) $T=10$ (b) $T=15$ (c) $T=20$

Figure 2:  Prediction error of algorithms IE, $\varepsilon$G, RS, OLS, SS, and
GPR.

##  5 Numerical Experiments

###  5.1 Performance of Algorithm 5

This section presents a numerical experiment for illustration of algorithm
performance. We use the CVX toolbox111http://cvxr.com/cvx to find sparse
solutions.

To generate the mixed model, we set the network size to be $n=20$, with four
types of agents and each type with $5$ agents sharing the same model as ground
truth. We generate $10$ graphs and run the model over each graph to get a
trajectory with a final time step $t=20$. The positive graphs are generated
from an Erdös-Rényi graph with link probability $(1.1\log n)/n$ and are
checked to be connected. Generate negative edges between the $5$ agents with
the repelling rule, with the same link probability, and ensure that each agent
has at least one negative edge. The influence weights $\alpha_{i}$ and
$\beta_{i}$ are set to be $0.2/d_{i}$. The susceptibility $\lambda_{i}$ of the
agents with the FJ rule is set to be $0.5$, and the confidence bound $c_{i}$
of the social HK model is set to be $0.25$. The initial opinions of the agents
are generated independently and uniformly from $(-1,1)$.

We compare the proposed algorithm (Algorithm 5, $\varepsilon$G) with an
initial estimate (IE) of the mixed model, random search (RS, Algorithm 5 with
model and topology exploration probabilities $\varepsilon_{M}=1$ and
$\varepsilon_{G}=1$), the ordinary least-squares algorithm (OLS), sparse
solutions (SS) to $\bm{X}y=b$, and Gaussian process regression (GPR). For IE,
we run Algorithm 1–4 (with $\varepsilon_{w}=0.001$,
$\varepsilon_{\lambda}=0.1$, and $\varepsilon_{c}=10^{-6}$) for each agent,
and obtain initial estimates of update rules, model parameters, and the
adjacency matrix. $\varepsilon$G starts with the estimates of IE, the number
of iterations is set to be $20$, both $\varepsilon_{M}$ and $\varepsilon_{G}$
are set to be $0.2$, respectively, and the step size is $0.1$. For OLS, SS,
and GPR, the data matrix for an agent $i$ is
$\begin{bmatrix}x(0)&\cdots&x(T-1)\\\
x_{i}(0)&\cdots&x_{i}(0)\end{bmatrix}^{\text{T}}$, thus including the effect
of initial states in the FJ model. Here $T$ is the number of samples. For OLS
and SS, we search solutions in $[-2,2]^{n+1}$ to avoid large weight estimates.
To investigate the effect of sample number, for each $T=10,15,20$, we apply
the algorithms to the $10$ trajectories $\\{x(0),\dots,x(T)\\}$ (for
$\varepsilon$G, set $\tilde{T}=[4T/5]$), and study the averaged performance.

First, we examine the recovery of adjacency matrices by EI, $\varepsilon$G,
RS, OLS, and SS. The performance of the recovery is characterized by the the
true positive rate (TPR) and the false positive rate (FPR) (see Bishop
(2006)). Fig. 1 shows the pair $(\textup{FPR},\textup{TPR})$ for the
algorithms. As the number of samples increase, all algorithms perform better.
$\varepsilon$G is slightly better then IE when $T$ is small, indicating
refinement of the initial estimates. SS has similar FPR and TPR to IE, which
may be because SS also searches for sparse networks. But SS does not learn the
model well and has large prediction error, as discussed later.

Next, we compute the prediction error for all algorithms. For each graph, we
generate $50$ time-adjecent state pairs $\\{x^{(g)}(0)),(x^{(g)}(1))\\}$,
$1\leq g\leq 50$. The prediction error is defined by the root mean square
error (RMSE)
$[(\sum_{g=1}^{50}\|\hat{x}^{(g)}(1)-x^{(g)}(1)\|^{2})/50]^{\frac{1}{2}}$,
where $\hat{x}^{(g)}(1)$ is the prediction of the states $x^{(g)}(1)$. The
results are shown in Fig. 2 with boxplots. IE, $\varepsilon$G, and RS have
smaller prediction error than the rest, because they are equipped with more
model information. When the number of samples is small ($T=10$),
$\varepsilon$G and RS have better performance for some trajectories but they
do not improve IE too much. Improvement can be observed in the case $T=15$,
where $\varepsilon$G has smaller error than IE and RS. When $T=20$, the
performance of $\varepsilon$G is similar to IE and RS, since there is
sufficient information for all algorithms. OLS cannot capture the nonlinear
dynamics so it performs the worst. SS and GPR has less prediction error than
OLS, because SS finds sparse solutions, resulting in less error, and GPR can
capture nonlinear dynamics.

We illustrate how the estimates of update rule types and parameters are
influenced by the number of samples. Fig. 3 plots the accuracy (the proportion
of correct estimates) of IE, $\varepsilon$G, and RS for each update rule type.
The accuracy increases with the number of samples. $\varepsilon$G has similar
accuracy to RS, so the smaller prediction error may result from the
exploitation for correctly learned update rules.

(a) $T=10$ (b) $T=15$ (c) $T=20$

Figure 3:  Accuracy of algorithms IE, $\varepsilon$G, and RS for learning of
update rule types. Algorithm 6
Learn$\mathcal{M}_{\textup{DG}}^{+}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: For $y\in\mathbb{R}^{n}$, solve  $\displaystyle\min_{y}~{}$
$\displaystyle\|\bm{X}y-b^{(i)}\|^{2}$ s.t. $\displaystyle\mathbf{1}^{T}y=1,$
$\displaystyle
y_{j}\geq\varepsilon_{w},~{}j\in\mathcal{N}_{i}^{(\textup{neigh})},$
$\displaystyle y_{j}=0,~{}j\in\mathcal{N}_{i}^{(\textup{non})}.$

2: Return $[\hat{A}]_{i,:}=\mathbb{I}_{[y^{\text{T}}>0]}$,
$\hat{\theta}^{(\mathcal{M}_{\textup{DG}},i)}=y$.

Algorithm 7
Learn$\mathcal{M}_{\textup{FJ}}^{+}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: For $y\in\mathbb{R}^{n+1}$, solve  $\displaystyle\min_{y}~{}$
$\displaystyle\|[\bm{X}~{}[\bm{X}]_{1,i}\mathbf{1}_{T}]y-b^{(i)}\|^{2}$ s.t.
$\displaystyle\mathbf{1}^{T}y=1,$ $\displaystyle
y_{j}\geq\varepsilon_{w}\varepsilon_{\lambda},~{}j\in\mathcal{N}_{i}^{(\textup{neigh})},$
$\displaystyle y_{j}=0,~{}j\in\mathcal{N}_{i}^{(\textup{non})},$
$\displaystyle\varepsilon_{\lambda}\leq y_{n+1}\leq 1-\varepsilon_{\lambda}.$

2: Return $[\hat{A}]_{i,:}=\mathbb{I}_{[y_{1:n}^{\text{T}}>0]}$,
$\hat{\theta}^{(\mathcal{M}_{\textup{FJ}},i)}_{1:n}=y_{1:n}/(1-y_{n+1})$,
$\hat{\theta}^{(\mathcal{M}_{\textup{FJ}},i)}_{n+1}=1-y_{n+1}$.

Algorithm 8
Learn$\mathcal{M}_{\textup{RP}}^{+}$($\bm{X}$,$b^{(i)}$,$\mathcal{N}_{i}^{(\textup{neigh})}$,$\mathcal{N}_{i}^{(\textup{non})}$)

1: For $y\in\mathbb{R}^{n}$, solve  $\displaystyle\min_{y}~{}$
$\displaystyle\|\bm{X}y-b^{(i)}\|^{2}$ s.t. $\displaystyle\mathbf{1}^{T}y=1,$
$\displaystyle y_{j}=0,~{}j\in\mathcal{N}_{i}^{(\textup{non})}.$

2: Return $[\hat{A}]_{i,:}=\textup{sgn}(y^{\text{T}})$,
$\hat{\theta}^{(\mathcal{M}_{\textup{RP}},i)}=y$.

Algorithm 9 $\varepsilon$-Greedy+($\\{x(0),\dots,x(T)\\}$)

1: Choose $\tilde{T}$ and divide the trajectory into a training dataset
$\bm{X}_{\textup{tr}}=[x(0)~{}\cdots~{}x(\tilde{T})]^{\text{T}}$ and a
validation dataset
$\bm{X}_{\textup{val}}=[x(\tilde{T}+1)~{}\cdots~{}x(T)]^{\text{T}}$.

2: Initialize the $Q$-table $Q(0)$, the estimates of update rule types
$\hat{k}(0)$, the estimates of the adjacency matrix for each model
$\hat{A}^{(M[m])}(0)$, and the parameter estimates
$\hat{\theta}^{(M[m],i)}(0)$, $1\leq m\leq 4$, where
$M[1]=\mathcal{M}_{\textup{DG}}$, $M[2]=\mathcal{M}_{\textup{FJ}}$,
$M[3]=\mathcal{M}_{\textup{RP}}$, $M[4]=\mathcal{M}_{\textup{HK}}$.

3: for $l$ from $1$ to $n_{\textup{iter}}$ do

4: for $i$ from $1$ to $n$ do

5: W.p. $1-\varepsilon_{\textup{M}}$, set  $k_{i}(l)=\underset{1\leq m\leq
4}{\arg\max}[Q(l)]_{i,m}.$

6: W.p. $\varepsilon_{\textup{M}}$, generate $k_{i}(l)\in\\{1,2,3,4\\}$
uniformly.

7: end for

8: W.p. $1-\varepsilon_{\textup{G}}$, let
$[\tilde{A}]_{i,:}:=[\hat{A}^{(k_{i}(l))}(l-1)]_{i,:}$, for $i\in\mathcal{V}$.
W.p. $\varepsilon_{\textup{G}}$, randomly generate an adjacency matrix
$\tilde{A}$.

9: for $i$ from $1$ to $n$ do

10: for $j$ from $1$ to $n$ and $j\not=i$ do

11: If $\tilde{A}_{ij}=0$ set
$\mathcal{N}_{i}^{\textup{(neigh)}}:=\\{q\in\mathcal{V}:\tilde{A}_{iq}=1\\}\cup\\{j\\}$,
and if $\tilde{A}_{ij}=1$ set
$\mathcal{N}_{i}^{\textup{(neigh)}}:=\\{q\in\mathcal{V}:\tilde{A}_{iq}=1\\}\setminus\\{j\\}$.
Set
$\mathcal{N}_{i}^{\textup{(non)}}:=\mathcal{V}\setminus\mathcal{N}_{i}^{\textup{(neigh)}}$.
$\displaystyle([\hat{A}_{\textup{temp}_{j}}]_{i,:},\hat{\theta}_{\textup{temp}_{j}}^{(M[k_{i}(l)],i)})=\textup{Learn}M[k_{i}(l)]^{+}$
$\displaystyle([\bm{X}_{\textup{tr}}]_{1:\tilde{T}-1,:},[\bm{X}_{\textup{tr}}]_{2:\tilde{T},i},\mathcal{N}_{i}^{\textup{(neigh)}},\mathcal{N}_{i}^{\textup{(non)}})$

12: end for

13: Compute the validation error of $f^{M[k_{i}(l)]}$ based on
$([\hat{A}_{\textup{temp}_{j}}]_{i,:},\hat{\theta}_{\textup{temp}_{j}}^{(M[k_{i}(l)],i)})$,
$j\in\mathcal{V}\setminus\\{i\\}$. Choose the smallest error
$p_{i,k_{i}(l)}(l)$ with respect to $j$, update
$[\hat{A}^{(M[k_{i}(l)])}(l)]_{i,:}$, $\hat{\theta}^{(M[k_{i}(l)],i)}(l)$
accordingly. Let $p_{i,m}(l)=\infty$,
$[\hat{A}^{(M[m])}(l)]_{i,:}=[\hat{A}^{(M[m])}(l-1)]_{i,:}$, and
$\hat{\theta}^{(M[m],i)}(l)=\hat{\theta}^{(M[m],i)}(l-1)$ for
$m=\\{1,2,3,4\\}\setminus\\{k_{i}(l)\\}$.

14: end for

15: for $i$ from $1$ to $n$ do

16: Find
$\mathcal{V}_{i}^{(\textup{incst})}:=\\{j\in\mathcal{V}:[\hat{A}^{(M[m_{j}])}(l)]_{ji}\not=[\hat{A}^{(M[k_{i}(l)])}(l)]_{ij}\\},$
where $m_{j}=\arg\min_{1\leq m\leq 4}\min_{1\leq q\leq l}p_{j,m}(q)$.

17: Generate test neighbor sets,
$\tilde{\mathcal{N}}_{i}^{\textup{(neigh,1)}},\dots,\tilde{\mathcal{N}}_{i}^{\textup{(neigh},b_{\textup{G}})}$,
according to a budget $b_{\textup{G}}\in\mathbb{Z}^{+}$, such that if
$u\in\\{j:[\hat{A}^{(M[k_{i}(l)])}(l)]_{ij}\not=0\\}\setminus\mathcal{V}_{i}^{(\textup{incst})}$
then $u\in\tilde{\mathcal{N}}_{i}^{\textup{(neigh},q)}$ and if
$u\in\\{j:[\hat{A}^{(M[k_{i}(l)])}(l)]_{ij}=0\\}\setminus\mathcal{V}_{i}^{(\textup{incst})}$
then $u\not\in\tilde{\mathcal{N}}_{i}^{\textup{(neigh},q)}$ for all $1\leq
q\leq b_{\textup{G}}$. Let
$\tilde{\mathcal{N}}_{i}^{\textup{(non},q)}=\mathcal{V}\setminus\tilde{\mathcal{N}}_{i}^{\textup{(neigh},q)}$.

18: for $q$ from $1$ to $b_{\textup{G}}$ do

19: Compute
$\displaystyle([\hat{A}_{\textup{temp}_{q}}]_{i,:},\hat{\theta}_{\textup{temp}_{q}}^{(M[k_{i}(l)],i)})=\textup{Learn}M[k_{i}(l)]^{+}$
$\displaystyle([\bm{X}_{\textup{tr}}]_{1:\tilde{T}-1,:},[\bm{X}_{\textup{tr}}]_{2:\tilde{T},i},\tilde{\mathcal{N}}_{i}^{\textup{(neigh},q)},\tilde{\mathcal{N}}_{i}^{\textup{(non},q)})$

20: end for

21: Compute the validation error of $f^{M[k_{i}(l)]}$ based on
$([\hat{A}_{\textup{temp}_{q}}]_{i,:},\hat{\theta}_{\textup{temp}_{q}}^{(M[k_{i}(l)],i)})$.
Choose the smallest error with respect to $q$ and update $p_{i,k_{i}(l)}(l)$,
$[\hat{A}^{(M[k_{i}(l)])}(l)]_{i,:}$, $\hat{\theta}^{(M[k_{i}(l)],i)}(l)$
accordingly, and
$[Q(l)]_{i,k_{i}(l)}=(1-\alpha)[Q(l-1)]_{i,k_{i}(l)}-\alpha\log(p_{i,k_{i}(l)}(l)).$

22: end for

23: end for

24: Let $\hat{m}_{i}:=\arg\min_{1\leq m\leq 4}\min_{1\leq q\leq
n_{\textup{iter}}}p_{i,m}(q)$, $\hat{\mathcal{M}_{i}}:=M[\hat{m}_{i}]$,
$[\hat{A}]_{i,:}=[\hat{A}^{(\hat{\mathcal{M}_{i}})}(n_{\textup{iter}})]_{i,:}$,
and
$\hat{\theta}^{(\hat{\mathcal{M}_{i}},i)}=\hat{\theta}^{(\hat{\mathcal{M}_{i}},i)}(n_{\textup{iter}})$,
$i\in\mathcal{V}$.

25: Return $\hat{A}$, $\\{\hat{\mathcal{M}_{i}}\\}$, and
$\\{\hat{\theta}^{(\hat{\mathcal{M}_{i}},i)}\\}$.

###  5.2 Improvement of Learning Algorithm

In this section, we modify the learning algorithm to exploit the assumptions
more efficiently.

First, note that in Line 11 of Algorithm 5 the non-neighbor set is only set to
be empty or $\\{j\\}$. Learn$M[k_{i}(l)]$ can thus return new unexpected
neighbors, possibly worsening the performance of network recovery. To address
this issue, we completely fix the neighbor and the non-neighbor sets and run
constrained least-squares (Algorithms 6–8), rather than Algorithms 1–3. For
the learning of signed network, note from (5) that
$\mathbf{1}^{\text{T}}\theta^{(\mathcal{M}_{\textup{RP}},i)}=1$, so another
constraint $\mathbf{1}^{\text{T}}y=1$ is added.

In addition, we take advantage of the assumption that the underlying graph is
undirected to fix possible inconsistent adjacency estimates (that is, for
$\hat{A}$ obtained by Algorithm 5, $\hat{A}_{ij}\not=\hat{A}_{ji}$). To this
end, at each iteration $l$ and for each agent $i$, we collect all estimates
$[\hat{A}^{(M[m_{j}])}(l)]_{ji}$ with $j\in\mathcal{V}$ and $m_{j}$ the
candidate update rule of $j$ with smallest validation error up to and
including iteration $l$ (see Algorithm 9). That is, the estimate of $a_{ji}$
given by the candidate update rule of $j$ with the smallest validation error.
Then we compare them with $[\hat{A}^{(M[k_{i}(l)])}(l)]_{ij}$ at the current
iteration to get all $j\in\mathcal{V}$ such that
$[\hat{A}^{(M[m_{j}])}(l)]_{ji}\not=[\hat{A}^{(M[k_{i}(l)])}(l)]_{ij}$ and
collect them in the set $\mathcal{V}_{i}^{(\textup{incst})}$. The algorithm
tests if keeping the edges connecting these agents to $i$ can improve the
validation error for the agent $i$. The detailed procedure is summarized in
Lines 15–22 of Algorithm 9. For notation simplicity and consistency, in
Algorithm 9 we denote Learn$\mathcal{M}_{\textup{HK}}^{+}:=$
Learn$\mathcal{M}_{\textup{HK}}$, and set each algorithm
$\textup{Learn}\mathcal{M}_{i}^{+}$ to return $[\hat{A}]_{i,:}$, which has
indeed been determined by the algorithm’s input
$(\mathcal{N}_{i}^{\textup{(neigh})},\mathcal{N}_{i}^{\textup{(non})})$.

To illustrate the performance of Algorithm 9 (denoted by $\varepsilon$G+), we
apply it to the same data set as previously. The algorithm starts with an
initial estimate (denoted by IE+), the same to IE except that for
$\mathcal{M}_{\textup{RP}}$ the constraint $\mathbf{1}^{\text{T}}y=1$ is
added. The hyperparameters of the algorithm are set to be the same as
Algorithm 5. Fig. 4 shows that IE+, equipped with the new constraint for
$\mathcal{M}_{\textup{RP}}$, performs better than IE in topology recovery.
Moreover, $\varepsilon$G+ improves IE+ significantly in topology recovery
because of the introduction of an edge fixing step. Fig. 5 illustrates that
$\varepsilon$G+ reduces the prediction error of IE+, and that the error of
both IE+ and $\varepsilon$G+ decreases with the length of trajectories.

##  6 Conclusion

In this paper, we studied joint learning of topology and dynamics for a mixed
opinion dynamics model and proposed a learning algorithm. The proposed
algorithm can improve the initial estimates of the network and the update
rules, and reduce prediction error. Future work will study improvement and
generalization of the proposed algorithm.

(a) $T=10$ (b) $T=15$ (c) $T=20$

Figure 4:  Performance of algorithms IE+ and $\varepsilon$G+ for network
topology recovery. Figure 5:  Prediction error of algorithms IE+ and
$\varepsilon$G+, where the subscripts indicate the length of trajectories used
by the algorithms.

## References

  * Bishop (2006) Bishop, C.M. (2006).  _Pattern Recognition and Machine Learning_.  Springer.
  * Clemm von Hohenberg et al. (2017) Clemm von Hohenberg, B., Maes, M., and Pradelski, B. (2017).  Micro influence and macro dynamics of opinion formation.  _SSRN 2974413_.
  * De et al. (2014) De, A., Bhattacharya, S., Bhattacharya, P., Ganguly, N., and Chakrabarti, S. (2014).  Learning a linear influence model from transient opinion dynamics.  In _Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management_ , 401–410.
  * DeGroot (1974) DeGroot, M.H. (1974).  Reaching a consensus.  _Journal of the American Statistical association_ , 69(345), 118–121.
  * Dong et al. (2017) Dong, Y., Ding, Z., Chiclana, F., and Herrera-Viedma, E. (2017).  Dynamics of public opinions in an online and offline social network.  _IEEE Transactions on Big Data_ , 7(4), 610–618.
  * Friedkin and Johnsen (1999) Friedkin, N.E. and Johnsen, E.C. (1999).  Social influence networks and opinion change.  _Advances in Group Processes_ , 16, 1–29.
  * He et al. (2021) He, X., Zhao, K., and Chu, X. (2021).  AutoML: A survey of the state-of-the-art.  _Knowledge-Based Systems_ , 212, 106622.
  * Hegselmann et al. (2002) Hegselmann, R., Krause, U., et al. (2002).  Opinion dynamics and bounded confidence models, analysis, and simulation.  _Journal of Artificial Societies and Social Simulation_ , 5(3).
  * Kozitsin (2021) Kozitsin, I.V. (2021).  Opinion dynamics of online social network users: A micro-level analysis.  _The Journal of Mathematical Sociology_ , 1–41.
  * Kozitsin (2022) Kozitsin, I.V. (2022).  Formal models of opinion formation and their application to real data: Evidence from online social networks.  _The Journal of Mathematical Sociology_ , 46(2), 120–147.
  * Li et al. (2017) Li, L., Jamieson, K., DeSalvo, G., Rostamizadeh, A., and Talwalkar, A. (2017).  Hyperband: A novel bandit-based approach to hyperparameter optimization.  _The Journal of Machine Learning Research_ , 18(1), 6765–6816.
  * Parasnis et al. (2018) Parasnis, R., Franceschetti, M., and Touri, B. (2018).  Hegselmann-Krause dynamics with limited connectivity.  In _IEEE Conference on Decision and Control_ , 5364–5369.
  * Proskurnikov and Tempo (2017) Proskurnikov, A.V. and Tempo, R. (2017).  A tutorial on modeling and analysis of dynamic social networks. Part I.  _Annual Reviews in Control_ , 43, 65–79.
  * Ravazzi et al. (2021a) Ravazzi, C., Dabbene, F., Lagoa, C., and Proskurnikov, A.V. (2021a).  Learning hidden influences in large-scale dynamical social networks: A data-driven sparsity-based approach, in memory of Roberto Tempo.  _IEEE Control Systems Magazine_ , 41(5), 61–103.
  * Ravazzi et al. (2021b) Ravazzi, C., Hojjatinia, S., Lagoa, C.M., and Dabbene, F. (2021b).  Ergodic opinion dynamics over networks: Learning influences from partial observations.  _IEEE Transactions on Automatic Control_ , 66(6), 2709–2723.
  * Ravazzi et al. (2017) Ravazzi, C., Tempo, R., and Dabbene, F. (2017).  Learning influence structure in sparse social networks.  _IEEE Transactions on Control of Network Systems_ , 5(4), 1976–1986.
  * Shi et al. (2019) Shi, G., Altafini, C., and Baras, J.S. (2019).  Dynamics over signed networks.  _SIAM Review_ , 61(2), 229–257.
  * Sun et al. (2019) Sun, X., Lin, J., and Bischl, B. (2019).  Reinbo: Machine learning pipeline conditional hierarchy search and configuration with Bayesian optimization embedded reinforcement learning.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , 68–84.
  * Thornton et al. (2012) Thornton, C., Hutter, F., Hoos, H.H., and Leyton-Brown, K. (2012).  Auto-WEKA: Automated selection and hyper-parameter optimization of classification algorithms.  _CoRR, abs/1208.3719_.
  * Wai et al. (2019) Wai, H.T., Scaglione, A., Barzel, B., and Leshem, A. (2019).  Joint network topology and dynamics recovery from perturbed stationary points.  _IEEE Transactions on Signal Processing_ , 67(17), 4582–4596.
  * Wai et al. (2016) Wai, H.T., Scaglione, A., and Leshem, A. (2016).  Active sensing of social networks.  _IEEE Transactions on Signal and Information Processing over Networks_ , 2(3), 406–419.
  * Wu et al. (2022) Wu, Z., Zhou, Q., Dong, Y., Xu, J., Altalhi, A.H., and Herrera, F. (2022).  Mixed opinion dynamics based on DeGroot model and Hegselmann-Krause model in social networks.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 53(1), 296–308.
  * Xie et al. (2023) Xie, X., Katselis, D., Beck, C.L., and Srikant, R. (2023).  Finite sample analysis for structured discrete system identification.  _IEEE Transactions on Automatic Control_ , Early Access.
  * Xing et al. (2022) Xing, Y., He, X., Fang, H., and Johansson, K.H. (2022).  Recursive network estimation for a model with binary-valued states.  _IEEE Transactions on Automatic Control_ , Early Access.


#  Note on the First Part of Borel-Cantelli Lemma

Alexei Stepanov Higher School of Computer Science and Applied Mathematics,
Education and Research Cluster ”Institute of High Technology“, Immanuel Kant
Baltic Federal University, A. Nevskogo 14, Kaliningrad, 236041 Russia; email:
<EMAIL_ADDRESS>
###### Abstract

In this short note, we briefly discuss the Borel-Cantelli lemma and propose a
new generalization of the first part of it.

Keywords and Phrases: Borel-Cantelli lemma; limit laws.

MSC2020-Mathematical Sciences Classification System 60, 62.

##  1  Introduction

Suppose $A_{1},A_{2},\ldots$ is a sequence of events on a common probability
space and that $A^{c}_{i}$ denotes the complement of event $A_{i}$. The Borel-
Cantelli lemma, presented below as Lemma 1.1, is used for producing strong
limit results.

######  Lemma 1.1.

  1. 1.

If, for any sequence $A_{1},A_{2},\ldots$ of events,

$\sum_{n=1}^{\infty}P(A_{n})<\infty,$ (1.1)

then $P(A_{n}\ i.o.)=0$;

  2. 2.

If $A_{1},A_{2},\ldots$ is a sequence of independent events and if
$\sum_{n=1}^{\infty}P(A_{n})=\infty$, then $P(A_{n}\ i.o.)=1$.

The independence condition in the second part of Lemma 1.1 has been weakened
by a number of authors, including Chung and Erdos (1952), Erdos and Renyi
(1959), Lamperti (1963), Kochen and Stone (1964), Spitzer (1964), Chandra
(1999, 2008), Petrov (2002, 2004) and others.

The first part of Borel-Cantelli lemma has been generalized in Barndorff-
Nielsen (1961) and Balakrishnan and Stepanov (2010). For a review on the Borel
-Cantelli lemma, one may refer to the book of Chandra (2012). The result of
Barndorff-Nielsen is presented below as Lemma 1.2.

######  Lemma 1.2.

Let $A_{n}\ (n\geq 1)$ be a sequence of events such that $P(A_{n})\rightarrow
0$. If

$\sum_{n=1}^{\infty}P(A_{n}A^{c}_{n+1})<\infty,$ (1.2)

then $P(A_{n}\ i.o.)=0$.

Observe that condition (1.2) in Lemma 1.2 is weaker than condition (1.1) in
the Borel-Cantelli lemma. It should be noted that Lemma 1.2 was proposed in
Barndorff-Nielsen (1961) with the wrong proof. For explanations and the
correct proof of Lemma 1.2, see Balakrishnan and Stepanov (2021) and Stepanov
and Dembinska (2022). We also present here the result of Balakrishnan and
Stepanov (2010).

######  Lemma 1.3.

Let $A_{1},A_{2},\ldots$ be a sequence of events such that
$P(A_{n})\rightarrow 0$. If, for some $m\geq 0$,

$\sum_{n=1}^{\infty}P(A^{c}_{n}A_{n+1}^{c}\ldots
A_{n+m-1}^{c}A_{n+m})<\infty,$

then $P(A_{n}\ i.o.)=0$.

##  2 New Result

The following result holds true.

######  Lemma 2.1.

Let $A_{1},A_{2},\ldots$ be a sequence of events such that
$P(A_{n})\rightarrow 0$. If, for some $m\geq 0$,

$\sum_{n=1}^{\infty}P(A_{n}A_{n+1}^{c}\ldots
A_{n+m-1}^{c}A_{n+m}^{c})<\infty,$

then $P(A_{n}\ i.o.)=0$.

  * Proof

For a large fixed $k$ and some $n\geq 1$, we have

$\displaystyle P(A_{n}+A_{n+1}+\ldots+A_{n+k})=P(A_{n}A^{c}_{n+1}\ldots
A_{n+k}^{c})+P(A_{n+1}+\ldots+A_{n+k})$ $\displaystyle=$ $\displaystyle
P(A_{n}A_{n+1}^{c}\ldots A^{c}_{n+k})+P(A_{n+1}A_{n+2}^{c}\ldots
A_{n+k}^{c})+P(A_{n+2}+\ldots+A_{n+k})$ $\displaystyle=$ $\displaystyle\ldots$
$\displaystyle=$ $\displaystyle P(A_{n}A^{c}_{n+1}\ldots
A_{n+k}^{c})+P(A_{n+1}A^{c}_{n+2}\ldots
A_{n+k}^{c})+\ldots+P(A_{n+k-1}A_{n+k}^{c})+P(A_{n+k}).$

Then, for a small $m\geq 0$, we get that

$\displaystyle P(A_{n}+A_{n+1}+\ldots+A_{n+k})$ $\displaystyle\leq$
$\displaystyle P(A_{n}A^{c}_{n+1}\ldots
A_{n+m}^{c})+P(A_{n+1}A^{c}_{n+2}\ldots
A_{n+m+1}^{c})+\ldots+P(A_{n+k-m}A_{n+k-m+1}^{c}\ldots A_{n+k}^{c})+o_{n}(1).$

Letting $k\rightarrow\infty$, we obtain

$P\left(\sum_{i=n}^{\infty}A_{i}\right)\leq
o_{n}(1)+\sum_{i=n}^{\infty}P(A_{i}A^{c}_{i+1}\ldots A_{i+m}^{c}).$

The result readily follows. $\\!\Box$

Observe that Lemma 2.1 generalizes Lemma 1.2.

## References

Balakrishnan, N., Stepanov, A. (2010). Generalization of Borel-Cantelli lemma.
The Mathematical Scientist, 35, 61–62.

Balakrishnan, N., Stepanov, A. (2021). A note on the Borel -Cantelli lemma.
arXiv:2112.00741v2, [math.PR].

Barndorff-Nielsen, O. (1961). On the rate of growth of the partial maxima of a
sequence of independent identically distributed random variables. Math.
Scand., 9, 383–394.

Chandra, T.K. (1999). A First Course in Asymptotic Theory of Statistics.
Narosa Publishing House Pvt. Ltd., New Delhi.

Chandra, T.K. (2008). Borel-Cantelli lemma under dependence conditions.
Statist. Probab. Lett., 78, 390 -395.

Chandra, T.K., (2012). The Borel -Cantelli Lemma. Springer Briefs in
Statistics.

Chung, K.L. and Erdos, P. (1952). On the application of the Borel-Cantelli
lemma. Trans. Amer. Math. Soc., 72, 179–186.

Erdos, P. and Renyi, A. (1959). On Cantor’s series with convergent $\sum
1/q_{n}$. Ann. Univ. Sci. Budapest. Sect. Math., 2, 93–109.

Kochen, S.B. and Stone, C.J. (1964). A note on the Borel-Cantelli lemma.
Illinois J. Math., 8, 248–251.

Lamperti, J. (1963). Wiener’s test and Markov chains. J. Math. Anal. Appl., 6,
58–66.

Petrov, V.V. (2002). A note on the Borel-Cantelli lemma. Statist. Probab.
Lett., 58, 283–286.

Petrov, V.V. (2004). A generalization of the Borel–Cantelli lemma. Statist.
Probab. Lett., 67, 233–239.

Spitzer, F. (1964). Principles of Random Walk. Van Nostrand, Princeton, New
Jersey.

Stepanov A. (2014). On the Use of the Borel-Cantelli Lemma in Markov Chains,
Statist. Probab. Lett., 90, 149–154.

Stepanov, A., Dembinska, A. (2023). Limit Theorems for the Uppermost $m$-th
Spacing Based on Weak Geometric Records, Statist. Probab. Lett., published
online 2022, doi.org/10.1016/j.spl.2021.109351.