Mean-field dynamics of the non-consensus opinion model

Abstract

In 2009, Shao et al. (Phys Rev Lett 103(1):018701, 2009) introduced the Non-consensus opinion (NCO) model, which allows different opinions to coexist in the steady state. We propose a mean-field-based dynamical model for the NCO model on networks with low degree correlation, which reveals the mechanism of opinion formation in the NCO model. This mean-field model provides a new way of estimating important system properties such as the fraction of a certain opinion F, the critical threshold $f_c$, and the size of the largest connected cluster for a given opinion $s_1$. It offers an accurate estimation in less time than the Monte Carlo simulations. The scale invariance of the NCO model is discussed. The variation in the degree of nodes holding different opinions in the dynamics of the NCO model is investigated. The trends in the dynamics of the NCO model are also revealed. This approach can be applied to real-world social networks, providing a method of analyzing opinion dynamics in human society.

Introduction

In recent years, there has been significant progress in the study of social dynamics and group behavior, with particular focus on the dissemination of opinions within social networks (Aletti et al. 2010; Sîrbu et al. 2016; Sun et al. 2013; Hassani et al. 2022). Opinion dynamics is driven by human behavior and is dependent on many factors, including individual predisposition, the influence of other people (social networks playing a crucial role in this respect), and many others. Different models have been developed, encompassing different elements of the opinion formation process. The study of opinion dynamics was first undertaken by John R. P. et al. in 1956 French (1956). Several models of opinion dynamics with varying rules for forming opinions have emerged over the past decades, including the Galam model (Galam et al. 1982; Galam 2008), Sznajd model (Sznajd-Weron and Sznajd 2000; Katarzyna Sznajd-Weron 2005), the voter model (Lambiotte and Redner 2008; Shang 2018; Redner 2019), the majority rule model (Galam 2002), and, Deffuant model (Shang 2013). These models explore the evolution of competing opinions, which can be mapped to spin models and find applications in the fields of physics, biology, chemistry and social science.

Most spin-type opinion models tend to converge to a consensus state with a single opinion, which does not fully reflect the coexistence of different opinions observed in real life. To address this, Shao et al. introduced a non-consensus opinion model (NCO model) that allows for a stable coexistence state (Shao et al. 2009). Shao et al. discovered that the opinion formation process in the NCO model can be mapped to a percolation problem, which is characterized by the appearance of a large spanning cluster of the minority opinion. This was the first time that a social dynamic model was mapped to percolation (Li et al. 2013).

In the NCO model, when the fraction of nodes holding a particular opinion surpasses a critical threshold, these nodes form a supportive cluster, where each member receives sufficient backing from others within the cluster. This phenomenon mirrors real-life scenarios where certain groups in society uphold extreme opinions that contradict the majority view, yet they persist due to the cohesive support they receive from like-minded individuals. Consequently, these extreme opinions are challenging to eradicate.

Other researchers have extended the NCO model in various directions. Li et al. (2011) proposed the Inflexible Contrarian Opinion (ICO) model, which introduces stubborn nodes that consistently maintain their opinions, regardless of the opinion of their neighbours. Li et al. (2013) incorporated a weight factor w for each node in the NCO model, giving rise to the NCOW model. Liu et al. (2023) extend the NCO model by introducing three types of malicious nodes, that intend to interfere with the NCO dynamics. Ben-Avraham (2011) develops exact solutions of the NCO model in one dimension and in a Cayley tree. These advancements have provided valuable insights into understanding the dynamics of opinion formation and coexistence in complex social networks.

However, a theory explaining the dynamics of the NCO model has been lacking. The main contribution of this paper is the proposal of a mean-field-based theory for the NCO model, along with a series of governing equations used to analyze its dynamics. The mean-field-based theory of the NCO model can be used to estimate important system properties, such as the opinion fraction of a certain opinion, the size of the largest connected component, and the critical threshold. Compared to Monte Carlo simulations, the mean-field method is both accurate and more efficient. The mean-field description offers an analytical approach of studying the behavior of the NCO model. In this paper, we first introduce the basic opinion formation rules of the NCO model and discuss important parameters of interest in “The NCO model” section. In “Mean-field dynamics of NCO model” section, the core of this paper, the mean-field dynamics of the NCO model are presented. The mean-field-based NCO-governing equations are also presented in this section. In “Simulation results and discussions” section, we explain how to use the mean-field-based NCO governing equations to compute the opinion fraction, the size of the largest connected component, and the critical threshold, and compare them with simulation results. The results obtained from the mean-field-based NCO governing equations show high accuracy, indicating that the mean-field theory accurately explains opinion formation in the NCO model. The degree variation and behavioral trends in the NCO model are also discussed. In “Conclusion” section summarizes the paper.

The NCO model

The NCO model describes the opinion formation process of two distinct opinions, labeled as $\sigma _+$ and $\sigma _-$, within a network, where each node adopts one of these two opinions. The network G(V, E) consists of the set V of nodes, representing individual agents, and the set E of links represent the social connections between the agents. The neighborhood of each node v is denoted as ${\mathcal {N}}_v$, encompassing all nodes adjacent to v.

The dynamics of the NCO model are demonstrated in Fig. 1. At each discrete time step t, nodes determine their opinion state $S_v(t)$ (either +1 or -1) based on their own opinion and the opinions of their neighbours. If a node’s local majority opinion aligns with its own, it will keep its current opinion. Conversely, if the local majority opinion differs, the node will change its opinion. This process is represented by the following equation:

$$\begin{aligned} S_v(t) = \text {sign}\left( (1+\varepsilon )\cdot S_v(t-1)+\sum _{u\in {\mathcal {N}}_v}S_u(t-1)\right) \end{aligned}$$

(1)

where ${\mathcal {N}}_v$ represents the set of neighboring nodes of vertex $v\in V$, and $\varepsilon \in (0,1)$ is a parameter that ensures nodes keep their own opinion when a local majority opinion does not exist.

A crucial parameter of the NCO model is the opinion fraction F(t), which is defined as the proportion of nodes holding the $\sigma _{-}$ opinion at a certain time t:

$$\begin{aligned} F(t) = \frac{n_{\sigma _{-}}(t)}{N} \end{aligned}$$

(2)

where $n_{\sigma _{-}}(t)$ is the number of nodes holding the $\sigma _{-}$ opinion at time t, and N is the total number of nodes in the system.

Fig. 1

Dynamics of the NCO model on a network with $N=9$ nodes. a At $t=0$, 4 nodes are assigned with a $\sigma _+$ opinion (red), and the other 5 nodes with a $\sigma _-$ opinion (blue). This makes node 5 to judge its local opinion ratio as $\sigma _+:\sigma _-$ = 3:2. Node 5 converts to $\sigma _+$. b At $t=1$, node 3 judges it local opinion ratio as $\sigma _+:\sigma _-$ = 3:2 and node 6 converts to $\sigma _+$. c At $t=2$, all nodes hold an opinion that they consider to be a local majority. Hence, the network has reached a steady state

At the beginning, the two opinions $\sigma _{-}$ and $\sigma _{+}$ are randomly distributed in the network, with a fraction f and $1-f$, respectively. Figure 2a shows how the opinion fraction F(t) changes with $f=0.3$ over time t. When the $\sigma _{-}$ opinion is a minority opinion ($f<0.5$), F decreases with time t according to the dynamics rule of the NCO model. However, the value of F does not go to zero, which is what distinguishes the non-consensus model from other spin-type models.

Figure 2b shows the final opinion fraction F, normalized size of the largest $\sigma _{-}$ cluster $s_1$ and normalized size of the second largest $\sigma _{-}$ cluster $s_2$ for an Erdős–Rényi (ER) graph with N = 10,000 nodes and average degree 4. It is conceivable that steady-state opinion fraction F increases with initial opinion fraction f. Shao et al. found that the NCO model in random networks exhibits a second-order phase transition that belongs to regular mean-field percolation. There exists a critical threshold $f_c$, below which the relative size of the largest cluster $s_1$ tends to 0. Once the initial opinion fraction f is larger than $f_c$, a giant component emerges in the steady state, which is accompanied by a peak in the relative size of the second-largest cluster $s_2$. For the situation in Fig. 2b, the critical threshold $f_c$ roughly occurs at $f_c \approx 0.28$.

Fig. 2

a The fraction of $\sigma _-$ opinion as a function of time t for an ER network with N = 10,000, p = 0.0004, and initial opinion fraction $f = 0.03$. b Normalized size of the largest cluster $s_1$ (blue line), the second largest cluster $s_2$ (green full line) and the fraction of $\sigma _-$ nodes F (red full line) in the steady state for an ER network with N = 10,000 and p = 0.0004

Mean-field dynamics of NCO model

Past research on non-consensus models has primarily been conducted through simulations. These models require calculating the state of each node at the next iteration step based on the states of its neighbors. Here, we introduce a dynamics model based on the mean field approach for the NCO model, which offers another angle for understanding and analyzing the NCO model. The mean-field dynamics of the NCO model can provide deeper insights into the system’s behavior. The mean-field dynamics of the NCO model is based on the assumption that each node in the network selects its interacting neighbors without any preference, which means that the network does not have any degree–degree correlation (or a very low degree–degree correlation). In this model, we define the state of a node by its current opinion and by counting its $\sigma _-$ and $\sigma _+$ neighbors. We then use the fractions of nodes in different states to represent the system’s state as, $s = \{f_{\sigma ,0,0}, \ldots ,f_{\sigma ,i,j}, \ldots \}$. The mean-field dynamics of NCO model investigates the evolution of these fractions.

The basic idea of the Mean-Field-NCO model is that when nodes in the system change their opinions, the opinions of all their neighbors change with the same probability. According to the fraction of nodes that change the opinions, we can compute the probability that the neighbors of nodes in the system changes their opinions. According to this probability, fractions of nodes with composition of neighboring nodes at next time slot are obtained.

We regard networks of nodes holding the same opinion in the system as a subgraph. There are two subgraphs in the network, the $\sigma _-$ subgraph and the $\sigma _+$ subgraph, as shown in the example in Fig. 3.

Instead of considering the state of every node independently, we aggregate nodes holding the same opinion with the same composition of neighboring nodes. Let $f_{\sigma _-}$ and $f_{\sigma _+}$ denote the fractions of nodes holding $\sigma _-$ and $\sigma _+$ opinions, respectively. At time $t=0$, in both the $\sigma _-$ and $\sigma _+$ subgraphs the fraction of nodes that have $d_{\sigma _-}$ $\sigma _-$ neighbors and $d_{\sigma _+}$ $\sigma _+$ neighbors is given by:

$$\begin{aligned} f_{\sigma _-,d_{\sigma _-},d_{\sigma _+}}(t = 0)&= f_{\sigma _-}\cdot \theta _{k = d_{\sigma _-}+d_{\sigma _+}} \cdot \left( {\begin{array}{c}d_{\sigma _-}+d_{\sigma _+}\\ d_{\sigma _-}\end{array}}\right) \cdot f_{\sigma _-}^{d_{\sigma _-}} \cdot f_{\sigma _+}^{d_{\sigma _+}} \nonumber \\ f_{\sigma _+,d_{\sigma _-},d_{\sigma _+}}(t = 0)&= f_{\sigma _+}\cdot \theta _{k = d_{\sigma _-}+d_{\sigma _+}} \cdot \left( {\begin{array}{c}d_{\sigma _-}+d_{\sigma _+}\\ d_{\sigma _-}\end{array}}\right) \cdot f_{\sigma _-}^{d_{\sigma _-}} \cdot f_{\sigma _+}^{d_{\sigma _+}} \end{aligned}$$

(3)

where $\theta _k$ represents the fraction of nodes with degree k, and $\left( {\begin{array}{c}d_{\sigma _-}+d_{\sigma _+}\\ d_{\sigma _-}\end{array}}\right)$ denotes a binomial coefficient.

Fig. 3

State of a NCO system at certain time slot t. A graph with 17 nodes, which 6 nodes holding the $\sigma _-$ opinion and 11 nodes holding the $\sigma _+$ opinion. The graph $G_{\sigma _{-}}$ consists of the $\sigma _-$ subgraph and the graph $G_{\sigma _{+}}$ consists of the $\sigma _+$ subgraph

Fig. 4

State of a NCO system as in Fig. 3, but at time $t=t+1$. Node 2 changes its opinion from $\sigma _-$ to $\sigma _+$, and node 7 changes its opinion from $\sigma _+$ to $\sigma _-$. Sets $S_{\sigma _+}$ and $S_{\sigma _-}$ consist of node 2 and node 7, respectively

According to the opinion formation rule of the NCO model, a $\sigma _-$ ($\sigma _+$) node with more neighbors holding a different opinion with them than neighbors holding the same plus one (the node’s own opinion) will change its opinion. As the opinions of $\sigma _-$ ($\sigma _+$) nodes change, the number of links in $\sigma _-$ ($\sigma _+$) nodes will also change. We denote the sets of nodes that change their opinion from $\sigma _-$ to $\sigma _+$ and from $\sigma _+$ to $\sigma _-$ as $S_{\sigma _+}$ and $S_{\sigma _-}$, like the example in Fig. 4 shows. The fraction of nodes with different composition of neighboring nodes in sets $G_{\sigma _-}|S_{\sigma _+}$, $G_{\sigma _+}|S_{\sigma _-}$, $S_{\sigma _-}$, and $S_{\sigma _+}$ are denoted as $f'_{\sigma _-,d_{\sigma _-},d_{\sigma _+}}$, $f'_{\sigma _+,d_{\sigma _-},d_{\sigma _+}}$, $f''_{\sigma _-,d_{\sigma _-},d_{\sigma _+}}$, and $f''_{\sigma _+,d_{\sigma _-},d_{\sigma _+}}$, respectively, where

$$\begin{aligned} \begin{array}{l} G_{\sigma _-}: d_{\sigma _+}>d_{\sigma _-}+1:f'_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} = 0, \quad f''_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} = f_{\sigma _-,d_{\sigma _-},d_{\sigma _+}}\\ G_{\sigma _+}: d_{\sigma _-}>d_{\sigma _+}+1:f'_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} = 0, \quad f''_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} = f_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} \\ G_{\sigma _-}: d_{\sigma _+}\le d_{\sigma _-}+1:f'_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} = f_{\sigma _-,d_{\sigma _-},d_{\sigma _+}}, \quad f''_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} =0 \\ G_{\sigma _+}: d_{\sigma _-}\le d_{\sigma _+}+1:f'_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} = f_{\sigma _+,d_{\sigma _-},d_{\sigma _+}}, \quad f''_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} =0 \end{array} \end{aligned}$$

(4)

Fig. 5

Schematic representation of the neighbor opinion changing process of the $G_{\sigma _-}$ subgraph. The colors of the links shows whether the link is connecting to a $\sigma _-$ node (blue) or a $\sigma _+$ node (red). a State of the $G_{\sigma _-}$ subgraph at time t. b State of the $G_{\sigma _-}$ subgraph at time $t+1$. Node 2 changes its opinion and be removed from $G_{\sigma _-}$ subgraph. Node 7 changes its opinion and be added to $G_{\sigma _-}$ subgraph

In the $G_{\sigma _-}$ and $G_{\sigma _+}$ subgraphs, the process of nodes changing their opinions involves removing some nodes and links, while adding new ones. For both subgraphs, the fractions of links that fail are described as follows:

$$\begin{aligned} f_{\sigma _-,fail} = \frac{\sum f''_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _-}}{\sum f_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _-}} \end{aligned}$$

(5)

and

$$\begin{aligned} f_{\sigma _+,fail} = \frac{\sum f''_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _+}}{\sum f_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _+}} \end{aligned}$$

(6)

The fractions of links between the $G_{\sigma _-}$ and $G_{\sigma _+}$ subgraphs becoming links in the $G_{\sigma _-}$ and $G_{\sigma _+}$ subgraphs are respectively

$$\begin{aligned} f_{\sigma _-,add} = \frac{\sum f''_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _-}}{\sum f_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _-}} \end{aligned}$$

(7)

and

$$\begin{aligned} f_{\sigma _+,add} = \frac{\sum f''_{\sigma _+,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _+}}{\sum f_{\sigma _-,d_{\sigma _-},d_{\sigma _+}} \cdot d_{\sigma _+}} \end{aligned}$$

(8)

Figure 5 shows an opinion changing process of $G_{\sigma _-}$ subgraph. In Fig. 5a, there are $N_{\sigma _-} = 6$ nodes and $L = 9$ links in the $G_{\sigma _-}$ subgraph. Node 2 has 6 links, two of them are connecting to $\sigma _-$ nodes, the others are connecting to $\sigma _+$ nodes. In Fig. 5b, as node 2 changes its opinion, node 2 and link a, b are removed from the $G_{\sigma _-}$ subgraph. Node 7 and link c, d join the $G_{\sigma _-}$ subgraph. The fractions $f_{\sigma _-,fail}$ and $f_{\sigma _-,add}$ in this example are respectively $\frac{2}{9}$ and $\frac{2}{13}$.

Suppose there is a node $l_-$ in $G_{\sigma _-}|S_{\sigma _+}$ and $S_{\sigma _+}$, and following one of its link l, node $l_+$ holding opinion $\sigma _-$ is found, and $l_-$ knows nothing about $l_+$ other than $l_+$’s opinion. Since the nodes have no preference for neighbor, from $l_-$’s view, the probability that node $l_+$’s opinion change equals to the fractions of link that are fail $f_{\sigma _-,fail}$. When $l_+$’s opinion is $\sigma _+$, the probability is $f_{\sigma _-,add}$. Then we know for a node with m $\sigma _-$ neighbors and n $\sigma _+$ neighbors. Both for the $\sigma _-$ and $\sigma _+$ nodes, their number of $\sigma _-$ and $\sigma _+$ neighbors changes according to the binomial distribution. For nodes in $G_{\sigma _-}|S_{\sigma _+}$ and $S_{\sigma _+}$ with m $\sigma _-$ neighbors and n $\sigma _+$ neighbors, probabilities that $e_-$ of its $\sigma _-$ neighbors change their opinion and that $e_+$ of its $\sigma _+$ neighbors change their opinion are:

$$\begin{aligned} p_{\sigma _-,m}(e_-) & = \left( {\begin{array}{c}m\\ e_-\end{array}}\right) \cdot f_{\sigma _-,fail}^{e_-} \cdot (1-f_{\sigma _-,fail}^{e_-})^{m-e_-} \end{aligned}$$

(9)

$$\begin{aligned} p_{\sigma _-,n}(e_+) & = \left( {\begin{array}{c}n\\ e_+\end{array}}\right) \cdot f_{\sigma _-,add}^{e_+} \cdot (1-f_{\sigma _-,add}^{e_+})^{n-e_+} \end{aligned}$$

(10)

Similarly, for nodes in $G_{\sigma _+}|S_{\sigma _-}$ and $S_{\sigma _-}$, the probabilities are:

$$\begin{aligned} p_{\sigma _+,m}(e_-) & = \left( {\begin{array}{c}m\\ e_-\end{array}}\right) \cdot f_{\sigma _+,add}^{e_-} \cdot (1-f_{\sigma _+,add}^{e_-})^{m-e_-} \end{aligned}$$

(11)

$$\begin{aligned} p_{\sigma _+,n}(e_+) & = \left( {\begin{array}{c}n\\ e_+\end{array}}\right) \cdot f_{\sigma _+,fail}^{e_+} \cdot (1-f_{\sigma _+,fail}^{e_+})^{n-e_+} \end{aligned}$$

(12)

Fig. 6

An example of computing the probability that a $\sigma _-$ node with 2 $\sigma _-$ neighbors and 2 $\sigma _+$ neighbors changing to a $\sigma _-$ node with 3 $\sigma _-$ neighbors and 1 $\sigma _+$ neighbor. a Probabilistic neighbors state transition of a $\sigma _-$ node with 2 $\sigma _-$ neighbors and 2 $\sigma _+$ neighbors. b Probabilistic state transition of a $\sigma _-$ node with 2 $\sigma _-$ neighbors and 2 $\sigma _+$ neighbors

Given a node in $G_{\sigma _-}|S_{\sigma _+}$ and $S_{\sigma _+}$ with m neighbors sharing its opinion and n $\sigma _+$ neighbors, the probability that this node evolves to have $d_{\sigma _-}$ $\sigma _-$ neighbors and $d_{\sigma _+}$ $\sigma _+$ neighbors is:

$$\begin{aligned} p_{\sigma _-,m,n\rightarrow d_{\sigma _-},d_{\sigma _+}} = \sum _{e_- \le m,e_+ \le n, m-e_-+e_+ = d_{\sigma _-}} p_{\sigma _-,m}(e_-) \cdot p_{\sigma _-,n}(e_+) \end{aligned}$$

(13)

Similarly, for a node in $G_{\sigma _+}|S_{\sigma _-}$ and $S_{\sigma _-}$ with m $\sigma _-$ neighbors and n neighbors sharing its opinion, the probability that it transitions to have $d_{\sigma _-}$ $\sigma _-$ neighbors and $d_{\sigma _+}$ $\sigma _+$ neighbors is:

$$\begin{aligned} p_{\sigma _+,m,n\rightarrow d_{\sigma _-},d_{\sigma _+}} = \sum _{e_- \le m,e_+ \le n, m-e_-+e_+ = d_{\sigma _-}} p_{\sigma _+,m}(e_-) \cdot p_{\sigma _+,n}(e_+) \end{aligned}$$

(14)

Figure 6 shows an example of computing the probability that a $\sigma _-$ node with certain neighborhood opinion composition to another. In Fig. 6a, for a node in the $\sigma _-$ subgraph the probability that its $\sigma _+$ neighbor change opinions is $\frac{1}{4}$. Accoridng to this probability, we can computer the probabilities that its two $\sigma _+$ neighbor keep their opinion, one keep its opinion and another change opinion, and both of this two neighbors change opinions. The probabilities are respectively $\frac{9}{16}$, $\frac{3}{8}$, and $\frac{1}{16}$. Base on the same computation, we can get the probabilities for its $\sigma _-$ neighbors. In Fig. 6b, a $\sigma _-$ node with 2 $\sigma _-$ neighbors and 2 $\sigma _+$ neighbors can become a $\sigma _-$ node with 3 $\sigma _-$ neighbors and 1 $\sigma _+$ neighbor in two ways: 1. One of its $\sigma _+$ neighbor become $\sigma _-$ neighbor, and the $\sigma _-$ opinion neighbors keep their opinion. 2. Both of the $\sigma _+$ neighbors change their opinion, and one of its $\sigma _-$ neighbor change its opinion. The probability that a $\sigma _-$ node with 2 $\sigma _-$ neighbors and 2 $\sigma _+$ neighbors become a $\sigma _-$ node with 3 $\sigma _-$ neighbors and 1 $\sigma _+$ neighbor equals to the probability that one of these two events happens, which is $p_{\sigma _-,2,2\rightarrow 3,1}=\frac{3}{8}\times \frac{16}{25}+\frac{1}{16}\times \frac{8}{25}=\frac{13}{50}$.

Finally, the ratio of $\sigma _-$ nodes and $\sigma _+$ that have m $\sigma _-$ neighbors and n $\sigma _+$ neighbors after one iteration to the number of nodes that hold the $\sigma _-$ opinion at the initial state are:

$$\begin{aligned} f_{\sigma _-,d_{\sigma _-},d_{\sigma _+}}(t+1) & = \sum _{m+n=d_{\sigma _-}+d_{\sigma _+}} f'_{\sigma _-,m,n}(t) \cdot p_{\sigma _-,m,n\rightarrow d_{\sigma _-},d_{\sigma _+}} + \sum _{m+n=d_{\sigma _-}+d_{\sigma _+}} f''_{\sigma _-,m,n}(t) \cdot p_{\sigma _+,m,n\rightarrow d_{\sigma _-},d_{\sigma _+}} \end{aligned}$$

(15)

$$\begin{aligned} f_{\sigma _+,d_{\sigma _-},d_{\sigma _+}}(t+1) & = \sum _{m+n=d_{\sigma _-}+d_{\sigma _+}} f'_{\sigma _+,m,n}(t) \cdot p_{\sigma _+,m,n\rightarrow d_{\sigma _-},d_{\sigma _+}} + \sum _{m+n=d_{\sigma _-}+d_{\sigma _+}} f''_{\sigma _+,m,n}(t) \cdot p_{\sigma _-,m,n\rightarrow d_{\sigma _-},d_{\sigma _+}} \end{aligned}$$

(16)

Figure 7 illustrates the entire flow of mean-field dynamics for the NCO model.

• (A) Given the fractions of nodes in different states of the system at a given time t, we calculate the fractions of nodes that change their opinions.

• (B) With the change of opinions of nodes in $\sigma _-$ and $\sigma _+$ subgraphs, we get the fraction of links removed from (and added to) $\sigma _-$ and $\sigma _+$ subgraphs.

• (C) Based on the changes of links in the $\sigma _-$ and $\sigma _+$ subgraphs, we get the probability that the neighbors of a node in $\sigma _-$ and $\sigma _+$ subgraphs change their opinions.

• (D) According to the probability that a node’s neighbor changes their opinion, we obtain the probability that nodes in certain state changes to other state.

• (E) Fractions of nodes in different states at time $t+1$ are calculated according to the probability that the nodes in certain state change to other state.

We refer to the set of equations used to describe the dynamics of the NCO model in this section as the Mean-Field NCO governing equation.

Fig. 7

Flowchart of mean-field dynamics for the NCO model

Simulation results and discussions

The time complexity of the Monte-Carlo simulation of NCO model is $O(MD_{\max }N)$, where M is the number of repetitions of the simulation, $D_{\max }$ is the maximum degree in the network and N is the number of nodes in the network. Estimating the opinion fraction through simulation is clearly very time-consuming. The mean-field dynamics of the NCO model provide a faster way to estimate the opinion fraction F at time t for a specific random graph. The time complexity of this method is $O(D_{\max }^2)$. For the Monte Carlo simulation method, to achieve high simulation accuracy, we need to perform the simulation many times. However, for the mean-field method, only a single numerical integration is required. Theoretically, the maximum degree in a network can be $N-1$, but the probability of nodes with extremely large degrees is very low. Considering this low probability, we disregard these nodes in practical calculations. We set a degree truncation threshold (DTT) $D_{\max }$ according to the following truncation criterion inequality:

$$\begin{aligned} & \frac{\sum ^{D_{\max }}_{k=0} \theta _k \cdot k}{\sum _{k=0}^{N-1} \theta _k \cdot k}>1-\eta \end{aligned}$$

(17)

$$\begin{aligned} & D_{\max } = \min _{d \in {\mathbb {Z}}} \left\{ d \, \ \frac{\sum ^{d}_{k=0} \theta _k \cdot k}{\sum _{k=0}^{N-1} \theta _k \cdot k}>1-\eta \right\} \end{aligned}$$

(18)

where $\theta _k$ represents the fraction of nodes with degree k. The accuracy of the prediction results increases as $\eta$ decreases. For Erdős–Rényi (ER) graphs, the degree truncation threshold (DTT) $D_{\max }$ equals:

$$\begin{aligned} D_{\max } = \left\lceil \mu +\sigma \Phi ^{-1}\left( \sigma \left( 1-\eta \right) +\frac{\sigma }{\mu \sqrt{2\pi }}exp\left( -\frac{\mu ^2}{2\sigma ^2}\right) +\Phi \left( -\frac{\mu }{\sigma }\right) \right) \right\rceil \end{aligned}$$

(19)

where $\mu = (N-1)p$, $\sigma = \sqrt{Np(1-p)}$, and $\Phi$ is the cumulative distribution function of the standard normal distribution. For Barabási-Albert (BA) models, the degree truncation threshold (DTT) $D_{\max }$ equals:

$$\begin{aligned} D_{\max } = \left\lceil \frac{N - m - 1 + 2N - 2m - 2\eta N + 2\eta m}{1 + \eta N + m - \eta m} \right\rceil \end{aligned}$$

(20)

The derivation of these two DTTs is given in Appendix . In this paper, we set $\eta = 10^{-5}$ for ER graphs, and $\eta = 10^{-3}$ for BA models. We set a larger $\eta$ for BA models because BA models have more heterogeneous degree distributions.

Opinion fraction F

We first investigate the NCO governing equations described in “Mean-field dynamics of NCO model” section on Erdős–Rényi (ER), Barabási-Albert (BA) and configuration models by comparing the Monte–Carlo simulation results and the estimation results of the opinion fraction F at time t.

The $\sigma _{-}$ opinion fraction at time t is denoted as:

$$\begin{aligned} F(t) = \sum _{d_{\sigma _-}+d_{\sigma _+}=0}^{D_{\max }} f_{\sigma _{-},d_{\sigma _-},d_{\sigma _+}}(t) \end{aligned}$$

(21)

Theoretically, there is always a possibility that the system will continue to iterate. We set the iteration to stop when the rate of change of the final opinion fraction is less than a tiny value $\epsilon$, denoted as:

$$\begin{aligned} |F(t+1)-F(t)|<\epsilon \end{aligned}$$

(22)

In this paper, we set $\epsilon = 10^{-5}$. Figure 8 presents the simulation and estimation results of Erdős–Rényi graphs (N = 10,000, $p=0.0004$), Barabási-Albert graphs (N = 10,000, $k_{\min } = 2$), and configuration models (with degree distribution $D = [0.0, 0.147, 0.106, 0.045, 0.153, 0.158, 0.089, 0.124, 0.039, 0.138]$). Averages over 1000 realizations are shown for all curves. Figure 9 illustrates the simulation and estimation results for the degree distribution of the $\sigma _{-}$ nodes at time t. As shown in the figures, the NCO governing equations provide a good estimate of the opinion fraction in the non-consensus model.

Although the estimated results of final opinion fraction F are very close to the simulation results, there are still some differences between them. Two factors may contribute to this discrepancy:

• Some nodes with very large degrees are ignored when performing the estimation, which can be improved by reducing the value of $\eta$.

• The size of the network used for simulation may not be sufficiently large. Limited by computer resources, the maximum network size used in our experiments is only 10,000, which may not be sufficiently large to approximate the asymptotic result of the NCO mean-field model.

Fig. 8

Simulation results and mean-field estimations of the final opinion fraction F as a function of initial opinion fraction f for different network models

Fig. 9

The simulation result and mean-field estimation of the opinion fraction F(t) as a function of time t

Critical threshold of NCO model

The critical threshold of the NCO model is defined as a specific initial opinion fraction, denoted as $f_c$. Below this threshold, only scattered clusters exist in the steady state. However, once the initial opinion fraction surpasses $f_c$, the system can exhibit a giant component. The emergence of giant components implies that nodes holding a minority opinion in the steady state form non-invasive clusters, whose size is proportional to the size of the network, allowing the minority opinion to stably exist in the steady state. The critical threshold is marked by the peak in the relative size of the second largest cluster. The NCO governing equations described in “Mean-field dynamics of NCO model” section offer a method for determining this critical threshold. Through iterative computations, we obtain the fractions of $\sigma _-$ nodes with different neighbor compositions in the steady state. Based on these fractions we can get the degree distribution of nodes within the $\sigma _{-}$ subgraph by

$$\begin{aligned} P_{D = d_{\sigma _-}} = \sum _{j=0}^{D_{\max }-d_{\sigma _-}}f_{\sigma _-,d_{\sigma _-},j} \end{aligned}$$

(23)

Additionally, by calculating the first and second-order moments of the degree distribution, we can identify the presence of giant components. For random graphs where giant components exist, the following criteria apply (Van Mieghem et al. 2014):

$$\begin{aligned} E[k^2]-2 \cdot E[k]>0 \end{aligned}$$

(24)

Figure 10 presents the degree distributions of the $\sigma _-$ subgraph at two steady states of an NCO system in an ER network with N = 10,000 and $p = 0.0004$. Figure 10a shows the degree distribution of the $\sigma _-$ subgraph at steady state for an initial opinion fraction of $f = 0.25$, and Fig. 10b for $f = 0.35$. The values of $E[k^2]-2 \cdot E[k]$ for the two cases are respectively $-0.1898$ and 0.8768. For an initial opinion fraction of $f = 0.25$, there is no giant component of the $\sigma _-$ opinion in the steady state, while for $f = 0.35$, a giant component will form.

Fig. 10

The degree distributions of the $\sigma _-$ subgraph at two steady states with different initial opinion fraction f of a NCO system in ER networks with N = 10,000, $p = 0.0004$

Fig. 11

Simulation results of the normalized second largest cluster $s_2$ and the value of $E[k^2]-2 \cdot E[k]$ obtained from mean-field estimations. $\epsilon = 1\times 10^{-5}$. The intersection of the $E[k^2]-2 \cdot E[k]$ curve with the $y=0$ curve is the estimate of the critical threshold $f_c$

Figure 11 presents the values of $E[k^2]-2 \cdot E[k]$ and the second largest cluster as functions of the initial opinion fraction f for ER, BA model, and configuration model networks. The red star marks the zero-crossing point of the $E[k^2]-2 \cdot E[k]$ curve, which shows the critical threshold $f_c$ derived through NCO governing equation. According to Fig. 11, the critical thresholds $f_c$, obtained through the NCO governing equation are very close to the critical thresholds derived through simulations.

Size of the largest cluster

The size of the largest $\sigma$ cluster can also be obtained using the NCO governing equation. Newman et al. (2001), Van Mieghem et al. (2014) proposed a method to estimate the size of the giant component in random graphs with arbitrary degree distributions, employing the probability generating function (pgf). The degree distribution of the $\sigma _-$ subgraph at the steady state is obtained in the same manner as described in “Critical threshold of NCO model” section. Given this degree distribution, we define the degree generating function as follows:

$$\begin{aligned} \varphi _D(z) = {\mathbb {E}}[z^D] = \sum _{j=0}^{N-1} \Pr [D = j] \cdot z^j \end{aligned}$$

(25)

Here, $\varphi _D(z)$ denotes the degree generating function, where ${\mathbb {E}}[z^D]$ represents the expected value of z raised to the power of degree D, and $\Pr [D = j]$ is the probability of a node having degree j.

For an arbitrarily chosen link l and its endpoint $l^+$, the pgf of the degree $D_{l^+}$ minus 1 is:

$$\begin{aligned} \varphi _{D_{l^+} - 1}(z) = {\mathbb {E}}[z^{D_{l^+}-1}] = \frac{\varphi '_D(z)}{\varphi '_D(1)} \end{aligned}$$

(26)

This equation, $\varphi _{D_{l^+ - 1}}(z)$, represents the pgf for the degree at endpoint $l^+$, decreased by 1. Here, $\varphi '_D(z)$ is the first derivative of $\varphi _D(z)$, and $\varphi '_D(1)$ is its value at $z=1$.

Finally, the normalized size of the largest cluster, $s_1$, can be derived using:

$$\begin{aligned} u = \varphi _{D_{l^+} - 1}(u), \quad s_1 = 1 - \varphi _D(u) \end{aligned}$$

(27)

In this formulation, u is the solution to the equation involving the pgf, and once found, it allows for calculating the normalized size of the largest component $s_1$.

Figure 12 shows the relative size of the largest connected cluster at steady state, as obtained by simulation and the NCO governing equation. From these figures, we find that the size of the largest cluster can be accurately derived through the NCO governing equation.

Fig. 12

The simulation result and estimation of the relative size of the largest $\sigma _-$ cluster $s_1$

Scale invariance of the NCO model

In the mean-field NCO model, the state of the system is represented by the fractions of nodes in different states in the system as $s = \{f_{\sigma ,0,0}, \ldots ,f_{\sigma ,i,j}, \ldots \}$. For NCO systems with different numbers of nodes, if the initial states $s(0)$ are the same, the subsequent states $s(t)$ will also be the same. The fractions of nodes in different states in the initial state depend on the degree distribution of the network. For networks with different numbers of nodes, as long as their degree distributions are the same, the initial state $s(0)$ will be the same, and thus the subsequent states will also be the same.

Fig. 13

Monte–Carlo simulation of the final opinion fraction $F$ as a function of initial opinion fraction $f$ for two ER graphs with $N=100$, $p = 0.04$ and $N$ = 10,000, $p = 0.0004$

The degree distribution of an ER graph follows a binomial distribution $\text {B}(N, p)$. The binomial distribution $\text {B}(N, p)$ can be approximated by a Poisson distribution $\text {Poisson}(\lambda )$ when $N$ is large and $p$ is small, such that the mean $\lambda = Np$ remains sufficiently small (Ross 2014).

Under these conditions, the binomial distribution $\text {B}(N, p)$ can be approximated by a Poisson distribution with $\lambda = Np$:

$$\begin{aligned} \text {B}(N,p) \sim \text {Poisson}(\lambda ) \end{aligned}$$

Thus, when $N$ is large, the degree distribution of an ER graph approximately equals the probability mass function (PMF) of a Poisson distribution:

$$\begin{aligned} P[D = k] = \frac{\lambda ^k e^{-\lambda }}{k!} \end{aligned}$$

(28)

If the average degree ${\overline{k}}=Np$ of two ER networks is the same, the degree distributions of these two networks are approximately equal, which is $\text {Poisson}({\overline{k}})$. Figure 13 shows the Monte Carlo simulation results of the final opinion fraction $F$ as a function of the initial opinion fraction $f$ for two ER graphs with different numbers of nodes $N$ and the same average degree ${\overline{k}}$. As we expect, the final opinion fractions of two ER graphs with different numbers of nodes $N$ but the same average degree ${\overline{k}}$ are highly similar.

Degree variation in the NCO model

Nodes with different degrees have different behaviors in the NCO model. To study the behavior of nodes with varying degrees, we conduct simulations on the configuration model graph with a uniform degree distribution, where the fractions of nodes at each degree are the same. This graph was chosen as the experimental network due to the ease of observation. Figure 14 shows how the fractions of $\sigma _-$ nodes with different degrees change over time. From Fig. 14, we find that

• Among the $\sigma _-$ opinion nodes, nodes with higher degree are more likely to change their opinions to $\sigma _+$.

• Odd-degree nodes ($d = 2n+1$) are more resistant to opinion change compared to even-degree nodes ($d = 2n$).

Fig. 14

The fraction of $\sigma _-$ nodes as a function of node degree in the configuration model network based on a uniform degree distribution (N = 10,000, $d_{\min } = 1, d_{\max } = 16$) for different time slot t. The intial opinion fraction $f = 0.45$

For nodes with high degrees, their individual opinions count less weight within their local opinions, making them more responsive to the prevailing global consensus. Consequently, nodes with high degrees are more likely to change their opinions.

According to the analysis in “Mean-field dynamics of NCO model” section, the probability of the number of $\sigma _-$ neighbors of a node becoming $\sigma _+$ neighbors follows the binomial distribution. Normally, those minority opinion $\sigma _-$ nodes with higher degree has more $\sigma _-$ neighbors than those with lower degree. This means $\sigma _-$ nodes with high degree are more likely to lose $\sigma _-$ neighbors, and more likely to become a node with more $\sigma _+$ neighbors than $\sigma _-$ neighbors. Thus nodes with higher degree are more likely to change their opinions.

Another intriguing phenomenon we have noticed is that odd-degree nodes ($d = 2n+1$) are more resistant to opinion change compared to even-degree nodes ($d = 2n$). Surprisingly, despite odd-degree nodes having one more neighbor compared to even-degree nodes with one less neighbor, the probability of odd-degree nodes being influenced is lower than that of even-degree nodes.

The probability of opinion change for even-degree $\sigma _{-}$ nodes with $d = 2n$ and ${\mathcal {N}}_{\sigma _{-},v} = i$, and odd-degree $\sigma _{-}$ nodes with $d = 2n+1$ and ${\mathcal {N}}_{\sigma _{-},v} = i$ can be expressed as follows:

$$\begin{aligned}&p_{\text {even}, i, 2n+1-i} = \sum _{e_-< i} \sum _{\begin{array}{c} i - e_- + e_+ < n \end{array}} p_{\sigma _{-}, i}(e_-) \cdot p_{\sigma _{+}, 2n+1-i}(e_+), \end{aligned}$$

(29)

$$\begin{aligned}&p_{\text {odd}, i, 2n-i} = \sum _{e_-< i} \sum _{\begin{array}{c} i - e_- + e_+ < n \end{array}} p_{\sigma _{-}, i}(e_-) \cdot p_{\sigma _{+}, 2n-i}(e_+). \end{aligned}$$

(30)

Now, we analyze the difference between $p_{\text {odd},i}$ and $p_{\text {even},i}$:

$$\begin{aligned} \begin{array}{l} p_{\text {odd},i,2n+1-i}-p_{\text {even},i,2n-i} \\ \quad = \sum _{e_-<i} p_{\sigma _{-},i}(e_-) \cdot \left( \Pr [X_1<n-i+e_-]-\Pr [X_2<n-i+e_-]\right) \\ \quad <0 \end{array} \end{aligned}$$

(31)

where $X_1,X_2$ follows binomial distributions $B(2n+1-i,p_{\sigma _{-},add}),B(2n-i,p_{\sigma _{-},add})$.

For the two binomial distribution with same p and same required successes number, the larger the number of Bernoulli trials, the higher the probability, and thus $\Pr [X_1<n-i+e_-]-\Pr [X_2<n-i+e_-]<0$. Therefore, we can conclude that, for nodes with the same number of $\sigma _{-}$ neighbors, even-degree nodes are more likely to change their opinions compared to odd-degree nodes. This explains to some extent why the opinions of nodes of odd degree are more stable.

Behavioural trends in NCO models

The behavioral logic of nodes in the NCO model is to adopt the local majority opinion. From each node’s perspective, this results in a decrease in the number of neighboring nodes that hold a different opinion. Generally, from a global perspective, the consequence of each node adopting this behavior is a decrease in the number of links connecting nodes with dissenting opinions after each opinion change. This trend is realized in two ways:

• The decrease in the number of nodes holding the minority opinion. Like the example in Fig. 15 shows, the number of minority opinion (red) nodes decrease from 4 to 1. The number of links connecting red and blue opinion nodes decreases from 12 to 1.

• The formation of separated $\sigma _-$ and $\sigma _+$ clusters in the network, where nodes in each cluster have more connections to each other than to other clusters. As illustrated in Fig. 16, nodes 1–5 form a blue opinion cluster, while nodes 6–11 form a red opinion cluster. The number of links connecting red and blue opinion nodes decreases from 14 to 1.

Fig. 15

Dynamics of the NCO model on a network with $N=11$ nodes. a At $t=0$, 4 nodes are assigned with a red opinion, and the other 7 nodes with a blue opinion. The local majority opinion for node 1, 5, 8 are blue, and they will change their opinions. b At $t=1$, all nodes in the system are holding a local majority opinion. The system has reached a steady state

To study the behavioral trends in the NCO model for large-sized graphs, we perform simulations on a configuration model network with a uniform degree distribution (N = 10,000, $d_{\min } = 1$, and $d_{\max } = 16$) with initial opinion fractions $f = 0.45$ and $f = 0.5$. When the fractions of $\sigma _-$ and $\sigma _+$ are the same at the initial state, as shown in Fig. 17, the fraction of $\sigma _-$ nodes F(t) does not change over time. However, the number of links between $\sigma _-$ and $\sigma _+$ subgraphs $l_{\sigma _- \sigma _+}$ decreases as time progresses. Figure 18 shows that after each iteration both the the fraction of $\sigma _-$ nodes F(t) and the number of links between $\sigma _-$ and $\sigma _+$ subgraphs $l_{\sigma _- \sigma _+}$ decrease. Additionally, in first several time slots, $l_{\sigma _- \sigma _+}$ doesn’t decrease proportionally with F(t), which means minority opinion nodes with more majority opinion neighbors are more likely to change their opinions. These figures also illustrate how the number of links between the $\sigma _-$ and $\sigma _+$ subgraphs changes over time for these two cases.

Fig. 16

Dynamics of the NCO model on a network with $N=11$ nodes. a At $t=0$, 6 nodes are assigned with a red opinion, and the other 5 nodes with a blue opinion. The local majority opinion for node 1, 5, 6, 10 are different with their own current opinion, and they will change their opinions. b At $t=1$, all nodes in the system are holding a local majority opinion. The system has reached a steady state

Fig. 17

Number of links between $\sigma _-$ and $\sigma _+$ subgraphs $l_{\sigma _- \sigma _+}$ and the opinion fraction F(t) as functions of time t of the dynamics of the NCO model in the Configuration Model network with a uniform degree distribution (N = 10,000, $d_{\min } = 1, d_{\max } = 16$) and $f=0.5$

Fig. 18

Number of links between $\sigma _-$ and $\sigma _+$ subgraphs $l_{\sigma _- \sigma _+}$ and the opinion fraction F(t) as functions of time t of the dynamics of the NCO model in the Configuration Model network with a uniform degree distribution (N = 10,000, $d_{\min } = 1, d_{\max } = 16$) and $f=0.45$

Conclusion

To enhance further understanding of the Non-Consensus Opinion (NCO) model, we derived in this paper a mean-field-based description for the NCO model under the assumption of low degree–degree correlation. The mean-field NCO equations merely require knowledge on a node’s own current opinion and the number of its $\sigma _-$ and $\sigma _+$ neighbors but does not require any knowledge on the exact network structure. The basic assumption of the mean-field dynamics in the configuration model of the NCO model is that, at each iteration, the $\sigma _-$ ($\sigma _+$) neighboring nodes of a node change its opinion according to a certain probability. This probability can be obtained from the fractions of nodes in different states. Important parameters such as the fraction of a certain opinion $F$, the critical threshold $f_c$, and the size of the largest connected cluster for a given opinion $s_1$ can be derived using this mean-field method. Simulation results show that this mean-field dynamics can effectively approximate $F$, $f_c$, and $s_1$. This mean-field description provides an analytical way to explain some phenomena observed in the NCO model. The scale invariance of the NCO model is discussed. The variation in the degrees of nodes with different opinions in the dynamics of the NCO model is also investigated. We explain why nodes with minority opinions and greater degrees are more likely to change their opinions in the NCO model. We also explain why nodes with minority opinions and even degrees are more likely to change their opinions than those with odd degrees. Additionally, we reveal that, in most cases, the dynamics of the NCO model tends toward a decrease in the number of links connecting nodes with different opinions.

The mean-field description given in this study can be used in studies of other spin-type opinion models. In particular, the mean-field equations are beneficial in spin-type opinion models where exact solutions are scarce and simulations time-consuming. Analysing phase transitions and other key properties of the opinion models are much easier and insightful with the help of our mean-field method. An open question is whether a similar method can be derived for networks with a large degree–degree correlation.

Appendix 1: Degree truncation threshold (DTT)

Appendix 1.1: Erdős–Rényi (ER) Graph

For an Erdős–Rényi (ER) graph, the degree distribution $\theta _k$ follows a binomial distribution:

$$\begin{aligned} \theta _k = \left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k(1-p)^{N-1-k} \end{aligned}$$

(32)

Then we obtain that:

$$\begin{aligned}&\frac{\sum ^{D_{\max }}_{k=0} \theta _k \cdot k}{\sum _{k=0}^{N-1} \theta _k \cdot k} \nonumber \\&\quad = \frac{\sum _{k=0}^{D_{\max }} k\left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k (1 - p)^{N-1-k}}{\sum _{k=0}^{N-1} k \left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k (1 - p)^{N-1-k}} \end{aligned}$$

(33)

The term $\left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k (1-p)^{N-1-k}$ is the probability density function (PDF) of the binomial distribution. According to the Central Limit theorem(Van Mieghem et al. 2014; Walker and Helen 1985), the binomial distribution approximately equals the normal distribution for large N. The truncation criterion function of ER graph can then be approximated as follows:

$$\begin{aligned}&\frac{\sum _{k=0}^{D_{\max }} k\left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k (1 - p)^{N-1-k}}{\sum _{k=0}^{N-1} k \left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k (1 - p)^{N-1-k}}\nonumber \\&\quad =\frac{\sum _{k=0}^{D_{\max }} k\left( {\begin{array}{c}N-1\\ k\end{array}}\right) p^k (1 - p)^{N-1-k}}{\mu }\nonumber \\&\quad =\frac{\int _{0}^{D_{\max }} k \frac{1}{\sqrt{2\pi }\sigma } \exp \left( -\frac{(\mu - k)^2}{2\sigma ^2}\right) \, dk}{\mu } \end{aligned}$$

(34)

where $\mu = (N-1)p$ and $\sigma = \sqrt{(N-1)p(1-p)}$.

To get $D_{\max }$, we need to solve the following truncation criterion inequality:

$$\begin{aligned} \frac{\int _{0}^{D_{\max }} k \frac{1}{\sqrt{2\pi }\sigma } \exp \left( -\frac{(\mu - k)^2}{2\sigma ^2}\right) \, dk}{\mu } > 1-\eta \end{aligned}$$

(35)

Next, rearrange to solve for the integral:

$$\begin{aligned} \int _{0}^{D_{\max }} k \frac{1}{\sqrt{2\pi }\sigma } \exp \left( -\frac{(\mu - k)^2}{2\sigma ^2}\right) \, dk > \left( 1-\eta \right) \mu \end{aligned}$$

(36)

Let Z be the standard normal variable:

$$\begin{aligned} Z = \frac{k - \mu }{\sigma } \end{aligned}$$

Then,

$$\begin{aligned} dk = \sigma \, dZ \quad \text {and} \quad k = \mu + \sigma Z \end{aligned}$$

Substitute k and dk into the integral:

$$\begin{aligned} \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} (\mu + \sigma Z) \frac{1}{\sqrt{2\pi }\sigma } \exp \left( -\frac{Z^2}{2}\right) \, \sigma \, dZ > \left( 1-\eta \right) \mu \end{aligned}$$

(37)

This simplifies to:

$$\begin{aligned} \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} \left( \frac{\mu }{\sigma } \frac{1}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) + \frac{\sigma Z}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) \right) \, dZ > \left( 1-\eta \right) \mu \end{aligned}$$

(38)

Recognize the integrals:

$$\begin{aligned} \frac{\mu }{\sigma } \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} \frac{1}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) \, dZ + \sigma \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} \frac{Z}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) \, dZ > \left( 1-\eta \right) \mu \end{aligned}$$

(39)

The first integral:

$$\begin{aligned} \frac{\mu }{\sigma } \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} \frac{1}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) \, dZ =\frac{\mu }{\sigma } \left( \Phi \left( \frac{D_{\max } - \mu }{\sigma }\right) - \Phi \left( -\frac{\mu }{\sigma }\right) \right) \end{aligned}$$

(40)

where $\Phi$ is the cumulative distribution function of the standard normal distribution.

The second integral:

$$\begin{aligned} &\sigma \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} \frac{Z}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) \, dZ \\&\quad =-\frac{\sigma }{\sqrt{2\pi }}exp\left( -\frac{Z^2}{2}\right) \bigg |^{\frac{D_{\max } - \mu }{\sigma }}_{Z= -\frac{\mu }{\sigma }}\\&\quad =\frac{\sigma }{\sqrt{2\pi }}\left( exp\left( -\frac{\left( D_{\max }-\mu \right) ^2}{2\sigma ^2}\right) -\exp \left( -\frac{\mu ^2}{2\sigma ^2}\right) \right) \end{aligned}$$

In general $D_{\max }$ is large, thus $\exp \left( -\frac{\left( D_{\max }-\mu \right) ^2}{2\sigma ^2}\right) \approx 0$. Then we obtain:

$$\begin{aligned} &\sigma \int _{-\frac{\mu }{\sigma }}^{\frac{D_{\max } - \mu }{\sigma }} \frac{Z}{\sqrt{2\pi }} \exp \left( -\frac{Z^2}{2}\right) \, dZ \approx -\frac{\sigma }{\sqrt{2\pi }}\exp \left( -\frac{\mu ^2}{2\sigma ^2}\right) \end{aligned}$$

Finally, the truncation criterion inequality becomes:

$$\begin{aligned} \frac{\mu }{\sigma } \left( \Phi \left( \frac{D_{\max } - \mu }{\sigma }\right) - \Phi \left( -\frac{\mu }{\sigma }\right) \right) -\frac{\sigma }{\sqrt{2\pi }}\exp \left( -\frac{\mu ^2}{2\sigma ^2}\right) > \left( 1-\eta \right) \mu \end{aligned}$$

(41)

Solve for $D_{\max }$:

$$\begin{aligned} D_{\max } = \left\lceil \mu +\sigma \Phi ^{-1}\left( \sigma \left( 1-\eta \right) +\frac{\sigma }{\mu \sqrt{2\pi }}\exp \left( -\frac{\mu ^2}{2\sigma ^2}\right) +\Phi \left( -\frac{\mu }{\sigma }\right) \right) \right\rceil \end{aligned}$$

(42)

Appendix 1.2: Barabási-Albert (BA) model

For an Barabási-Albert (BA) model, the degree distribution $\theta _k$ follows a binomial distribution (Pósfai and Barabási 2016):

$$\begin{aligned} \theta _k = \frac{2m(m+1)}{k(k+1)(k+2)} \end{aligned}$$

(43)

Then we obtain that:

$$\begin{aligned}&\frac{\sum ^{D_{\max }}_{k=0} \theta _k \cdot k}{\sum _{k=0}^{N-1} \theta _k \cdot k} \nonumber \\&\quad =\frac{\sum _{k=m}^{D_{\max }}\frac{2m(m+1)}{(k+1)(k+2)} }{\sum _{k=m}^{N-1}\frac{2m(m+1)}{(k+1)(k+2)}}\nonumber \\&\quad = \frac{\frac{1}{m+1}-\frac{1}{D_{\max }+2}}{\frac{1}{m+1}-\frac{1}{N+1}}\nonumber \\&\quad =\frac{(D_{\max } + 1 - m)(N+1)}{(D_{\max } + 2)(N - m)} \end{aligned}$$

(44)

Then we obtain the truncation criterion inequality:

$$\begin{aligned}&\frac{(D_{\max } + 1 - m)(N+1)}{(D_{\max } + 2)(N - m)}>1-\eta \end{aligned}$$

(45)

Finally, solve for $D_{\max }$:

$$\begin{aligned} D_{\max } = \left\lceil \frac{N - m - 1 + 2N - 2m - 2\eta N + 2\eta m}{1 + \eta N + m - \eta m} \right\rceil \end{aligned}$$

(46)