Use of Enumerative Combinatorics for Proving the Applicability of an Asymptotic Stability Result on Discrete-Time SIS Epidemics in Complex Networks

Abstract

In this paper, we justify by the use of Enumerative Combinatorics, the applicability of an asymptotic stability result on Discrete-Time Epidemics in Complex Networks, where the complex dynamics of an epidemic model to identify the nodes that contribute the most to the propagation process are analyzed, and, because of that, are good candidates to be controlled in the network in order to stabilize the network to reach the extinction state. The epidemic model analyzed was proposed and published in 2011 by of Gómez et al. The asymptotic stability result obtained in the present article imply that it is not necessary to control all nodes, but only a minimal set of nodes if the topology of the network is not regular. This result could be important in the spirit of considering policies of isolation or quarantine of those nodes to be controlled. Simulation results using a refined version of the asymptotic stability result were presented in another paper of the second author for large free-scale and regular networks that corroborate the theoretical findings. In the present article, we justify the applicability of the controllability result obtained in the mentioned paper in almost all the cases by means of the use of Combinatorics.

1. Introduction

The main aim of the present article is to prove the applicability of an asymptotic stability result on discrete-time SIS epidemics in complex networks by the use of a combinatorial enumeration argument. Here SIS means that the nodes can be susceptible to contagion, can transit to a state of infection and once they are healthy they can become again susceptible to contagion.

The bifurcation analysis that will be presented in Section 4 as well as the criterion for selection of control nodes that will be presented in Section 5 of the present article were unpublished results prior to the more general and refined criterion obtained in the article [1]. During the development of the criterion of selection of nodes to be controlled, presented in Section 5 of the present article, we faced the problem that in the case that the behavior transition and interaction of the nodes were homogenous and the network had a topology of regular type, that is to say that the nodes had the same degree, we would be forced to have to control all the nodes since we could not distinguish them. Due to this drawback, we decided to show through an enumerative combinatorial argument that, even in the case of homogeneous behavior of the nodes, the criterion is applicable in most cases because the probability that a randomly generated graph will be regular tends to zero as the number of nodes grows arbitrarily. Simultaneously, the second author, in collaboration with other colleagues, refined the selection criterion of nodes to be controlled obtained in Section 5 of the present article and tested by simulation that the criterion worked under the hypothesis of non-homogeneity, for scale-free type topologies in the article [1].

Combinatorics is the science of combinations. It is a very important subject in the field of Discrete [2] Among many other things, it helps us to conceive methods for enumerating a wide range of objects that accomplish a certain property of interest in a given domain. In particular, the subfield of analytic combinatorics has as a goal the precise prediction of large structured combinatorial configurations under the approach of analytic methods by the use of generating functions. Analytic combinatorics is the study of finite structures built according to a finite set of rules. Generating functions is an enumerative combinatorics tool that connects discrete mathematics and continuous analysis. One of the applications of the enumerative combinatorics is the probabilisitic method. His rapid development is related with the important role played by randomness in Theoretical Computer Science. The probabilistic method is one of the most simple and beautiful nonconstructive proving methods that has been used in combinatorics in the last sixty years. This method was one of the most important contributions of the great Hungarian mathematician Paul Erdös [3,4]. This method is used for proving the existence of some kind of mathematical object by showing that if we chose some object randomly from a specified class, the probability that the mathematical object is of a prescribed type is more than zero. The method is applied in many fields of the mathematics as can be number theory, combinatorics, graph theory, linear algebra, information theory and computer science.

The second author of the present article, who is also the first author of [1], in a previous result that is less general than the model of the virus spreading on complex networks presented in [1], was interested in establishing the conditions allowing for detecting those nodes of a complex network that should be controlled such that the system can be steered to a stable virus extinction state. In fact, this previous model was presented as an application example of the results obtained in a section of [1]. The criteria obtained in [1] as well as the one obtained in the mentioned previous model, can be considered as a good option when the number of nodes to be controlled with respect to the total number of nodes is small. The number of nodes to be controlled depends on the topology of the complex network as well as on the values of the state transition parameters in each node. If all the nodes have the same degree and the transition parameters are the same for each node, then we can not distinguish the nodes to be controlled from the ones that don’t have to be controlled. In such a situation, we have to control all the nodes. As a consequence, the applicability of the criteria for the detection of the nodes to be controlled obtained in [1] is no longer a good choice given that it becomes very expensive to control the totality of the nodes in the complex network. In [1], the authors avoid this problem giving as an argument that, in the literature of complex networks, the majority of the topolgies that can be found in practice are not regular. Additionally, the authors of [1] generalise the previous model that was referred to, assigning to each node different internal transition probabilities, as well as different rates of interaction among nodes. The first author of the present paper thinks that the situation where each node has the same internal transition probabilities as well as the same rate of interaction among nodes can not be discarded because it is the most common case observed in the behavior of the agents in the social networks and the one which is based on the good predictability of the models used for simulating social phenomena [5,6,7,8,9,10,11,12,13,14]. Because of that, in the present article, we want to give an argument in favor of the applicability of the result obtained in [1], by means of using the mathematical tool of enumerative combinatorics. For that end, we are going to assume that the transitions’ probabilities of each node as well as the rate of interaction among nodes are the same for all of the networks and use an enumerative combinatoric argument to show that, even in that case, the criteria of detection of nodes to be controlled is still applicable.

The paper is organized as follows: in Section 2, the SIS mathematical model is introduced. In Section 3, we introduce the previous model that was presented as an application example in [1]. In Section 4, we present a bifurcation analysis that allows for obtaining the epidemic transition threshold of the complex network. In Section 5, we propose a method to determine the nodes to be controlled. In order to show the application of the criteria obtained in Section 5, we give some simulations in Section 6. In Section 7, we talk about the enumerative combinatoric argument that allow us to justify the applicability of the criteria for the selection of nodes to be controlled obtained in Section 5 as well as the one obtained in [1]. In Section 8, we make an overview of the graph enumeration problem and also about some results obtained for the enumeration of connected graphs and asymptotic analysis. In Section 9, we talk about some results obtained for the enumeration of regular graphs. Finally, the main results and conclusions are presented in Section 10.

2. Epidemics Spreading in Complex Networks

Many systems have been studied using structures called complex networks due to the number of its elements and their interaction. Each node in the network has associated some variables that represent the state of the node. The edges that connect the nodes are weighted and can be undirected or directed. The resulting graph is an undirected network or a directed network. The state in any node depends on the state and interaction intensity with the nodes in his neighbour. Examples of such systems are the social networks, the computer networks and the electrical systems.

Recently, many researchers have concentrated their efforts on studying the problem of controllability in complex networks [15,16,17,18,19], i.e., to drive the dynamical system from any initial state to some desired state in a finite time.

The controllability problem bring up many questions, and one of the most important is to determine which nodes must be controlled. In [15], the authors propose a method to find the minimum set of driver nodes that control the system. This minimum set, which is equal to the number of inputs, is determined by the maximum matching in the network. This approach of structured control theory makes use of tools of graph theory.

In [16], the authors propose to make use of the maximum matching graph theory concept, but, unlike the approach proposed in [15], where dynamics were considered at node level to control the system, they propose to make use of the dynamic at edges level and associate the state of the system to the state of the edges of the network. In the latter case, the authors of [16] determine the smallest set of control paths and therefore of driver nodes.

The concept of controllability of linear systems has been applied in the context of complex networks. In [18,19], the authors give the requirements that must be satisfied in order to achieve the Kalman’s controllability rank condition [20]. Finally, in [17], the authors propose a control strategy which supposes that the selection of control nodes must be based on the partition of the nodes of the network, defined in terms of the energy to control the network and propose as well a distributed control law to drive the system to a desired state. However, in all the articles mentioned in the previous paragraphs, a node is controlled by an external input that modifies the state of the node, but, in the present paper, a node is controlled only if it meets some property. The purpose of controlling a node consists in stating conditions in order to determine which nodes are the best ones for monitoring and controlling to stabilize the system in the extinction state for stopping the propagation of a virus. In order to verify our theoretical results, we make simulations on a scale free network as well as on a regular network. In contrast with other authors, we consider an undirected network where each node follows the well-known Susceptible-Infected-Susceptible (SIS) model [10], so that the control mechanism brings the system to the extinction state. Of course, we are interested in determining the number of nodes that will be controlled.

3. Control Problem Statement

For us to control the virus spreading in the network will mean to modify in a set of selected nodes one or more of its parameters in such a way that the infection tends to the exctinction. The criteria for selecting will be described in Section 5. The discrete time Markov process dynamical system with the SIS epidemiological model that we will use to illustrate the problem is the one proposed in [10] and was mentioned in a section of [1] as a feedback control example. Consider a discrete time Markov process dynamical system with the SIS epidemiological model as is described in [10]. Transitions between states depend on ${\mu }_i$ that is the recovery probability of each node i, and ${\zeta }_i\left(t\right)$ that is the probability that a node i is not being infected by interaction with their neighbours, as is shown in Figure 1. In each time step, the node i try to get in contact with each of its neighbours, the probability that node i perform at least one contact with its neighbour j is given by $r_{ij}$, and the probability that the node i will be infected by contact with an infected node is ${\beta }_i$. In that case, we consider that ${\beta }_i$ can be tuned in such a way that we can improve the nodes’ health. By considering that the interaction between the node i with each one of its neighbours is independent, the probability that node i is not infected by its neighbours is

$${\zeta }_i\left(t\right)=\prod _{j=1}^N\left[1-a_{ij}{\beta }_i{r}_j{p}_j\left(t\right)\right],$$

(1)

where $a_{ij}$ are the entries of the adjacency matrix $A\in {\mathbb{R}}^{N\times N}$ that represents the existing connections between the N nodes of the undirected network, and $p_i\left(t\right)$ is the probability that a node i is infected. According to the transitions diagram (see Figure 1), the following nonlinear dynamics is obtained:

$$p_i(t+1)=(1-{\mu }_i)p_i\left(t\right)+(1-{\zeta }_i\left(t\right))(1-p_i\left(t\right)).$$

(2)

The purpose of the present work is to identify the nodes to be controlled in the network, so a control mechanism will allow to bring the system to the extinction state from any initial state, i.e., $p_i\left(t\right)\to 0$ as $t\to \infty$, from any state $p_i\left(0\right)=p_{oi}$, $i=1,2,\dots N$. We will assume that $r_{ij}=r_{ji}=r_j$, that is, a node j tries to connect to a node i in the same way that a node i tries to connect to a node j. We will assume that, if a node i reduces the number of connection attempts with the node j, the node j will do the same. We have to mention that, in our work, we will not be considering in advance a particular complex network structure. Moreover, we will consider that not all the parameters in each node have the same value. This means that we will assume non-homogeneity both in the structure and in the properties in our model.

Where SIS in Figure 1 means that the nodes can be susceptible to contagion, can transit to a state of infection and once they are healthy they can become again susceptible to contagion.

4. Bifurcation Analysis

Recently, an important number of scientific works have been dedicated to the study of the dynamics of the spread of epidemics in complex networks [5,10,21], so we have followed the same research path in order to determine under what conditions the epidemic extinction state $p_i=0$ becomes a global attractor for any node i. First, we consider the following bound

$$1-{\zeta }_i\left(t\right)\le \sum _{j=1}^N{a}_{ij}{\beta }_i{r}_j{p}_j\left(t\right)$$

(3)

proved in [5] and then determine a linear dynamics substituting (3) into (2)

$$\begin{array}{ccc}\hfill p_i(t+1)& =& (1-{\mu }_i)p_i\left(t\right)+(1-p_i\left(t\right))\sum _{j=1}^N{a}_{ij}{\beta }_i{r}_j{p}_j\left(t\right)\hfill \end{array}$$

(4)

$$\begin{array}{cc}\le & (1-{\mu }_i)p_i\left(t\right)+\sum _{j=1}^N{a}_{ij}{\beta }_i{r}_j{p}_j\left(t\right).\hfill \end{array}$$

(5)

Therefore, we propose the following bounded linear dynamics that is given by

$$x_i(t+1)=(1-{\mu }_i)x_i\left(t\right)+{\beta }_i\sum _{j=1}^N{a}_{ij}{r}_j{x}_j\left(t\right),p_i\left(t\right)\le x_i\left(t\right).$$

(6)

In matrix notation our system, $X(t+1)=\mathbf{H}X\left(t\right)$ is summarized, where $\mathbf{H}=[I-\mu +\beta \mathbf{R}A]$, $\mathbf{R}=diag\left(r_i\right)$,$\mu =diag\left({\mu }_i\right),\beta =diag\left({\beta }_i\right)$ and $X\left(t\right)={[x_1\left(t\right),x_2\left(t\right),\dots x_N\left(t\right)]}^T$. These linear dynamics given by the matrix $\mathbf{H}$ are asymptotically stable if and only if the spectral radius ($\sigma \left(\mathbf{H}\right)$) of the matrix $\mathbf{H}$ meets the condition that $\sigma \left(\mathbf{H}\right)\in \{\lambda \in \mathbb{C}:|\lambda |<1\}$.

If the contact probabilities ${\mu }_i$ and ${\beta }_i$ belong to the closed interval $[{\mu }_{min},{\mu }_{max}]$ and $[{\beta }_{min},{\beta }_{max}]$, respectively, it is possible to bound the spectral radius as follows:

$$\sigma \left(\mathbf{H}\right)<1.$$

(7)

This equation is similar to that reported in [5,10]. Moreover, from (7), we have several bifurcation parameters given by ${\beta }_{max}$, ${\mu }_{min}$ and r, and, for control purposes, it is appropriate to take $\beta$ as a control parameter. In this case, ${\beta }_i$ will be our control parameter in some nodes, in order to stabilize our system in the epidemic extinction state.

5. Selection of Nodes to Be Controlled

For the selection of the nodes to be controlled, we have to consider (6) as an uncoupled system due to the symmetry of the matrix $\mathbf{R}$. Consider Equation (6) as a sum over all nodes as follows.

The proposed model is

$$p_i(t+1)=(1-{\mu }_i)p_i\left(t\right)+(1-{\zeta }_i\left(t\right))(1-p_i\left(t\right)),$$

(8)

$${\zeta }_i\left(t\right)=\prod _{j=1}^N(1-a_{ij}{\beta }_i{r}_j{p}_j\left(t\right)).$$

(9)

From (8), we can deduce (3) and, by substitution of (3) on (8), we obtain the inequality of (4). This lends us to propose the following new dynamics

$$x_i(t+1)=(1-{\mu }_i)x_i\left(t\right)+{\beta }_i\sum _{j=1}^N{a}_{ij}{r}_j{x}_i\left(t\right),$$

(10)

where $p_i\left(t\right)\le x_i\left(t\right)$. Representing (10) in matrix form, we obtain the following mathematical expression

$$\mathbf{X}(t+1)=[I-\mu +\beta \mathbf{R}A]\mathbf{X}\left(t\right).$$

(11)

We can bound the Equation (11) in terms of the eigenvalues, in order to determine the system stability, as follows:

$$\sigma \left(\right[I-\mu +\beta \mathbf{R}A])<1.$$

(12)

If the condition (12) is satisfied, the system will be asymptotically stable in the extinction state. In order to select those nodes that participate in the spreading process, we have the following result known as the Gerschgorin theorem [22,23]:

$$\rho \left(A\right)\le ma{x}_i\sum _{j=1}^N\left|a_{ij}\right|,$$

(13)

which implies

$$|\lambda -(1-{\mu }_i)|\le \sum _{j=1}^N\left|{\beta }_i{a}_{ij}{r}_j\right|,$$

(14)

whose consequence is

$$\left|\lambda \right|-|1-{\mu }_i|\le |\lambda -(1-\mu -i)|\le \sum _{j=1}^N{\beta }_i{a}_{ij}{r}_j$$

(15)

from where we get

$$\left|\lambda \right|\le |\lambda -1+{\mu }_i|+|1-{\mu }_i|\le \sum _{j=1}^N{\beta }_i{a}_{ij}{r}_j+1-{\mu }_i\le 1$$

(16)

and we conclude that

$${\beta }_i\sum _{j=1}^N{a}_{ij}{r}_j<{\mu }_i.$$

(17)

Note that the last equation does not tell us how to control the spread of the disease but instead tells us which nodes we need to control in order to reach the epidemic extinction state. In this case, the nodes that have to be controlled are those who do not satisfy the inequality (17).

6. Simulations

The purpose of the control design is to make the system reach the extinction state (i.e., $p_i\to 0$, for $t>0$). In this work, we suppose that ${\beta }_i$ can be manipulated in both cases: homogeneous (i.e., ${\beta }_i=\beta$, ${\mu }_i=\mu$ and $r_i=r$) and non-homogeneous for scale-free and regular networks.

Following the results obtained in [1],the selection of nodes to be controlled, for any network topology, is given by (see Equation (25) from [1])

$${\beta }_i\sum _{j=1}^N{r}_j{a}_{ij}<{\mu }_i$$

(18)

for the non-homogeneous case, and

$$\beta \sum _{j=1}^{N}r{a}_{ij}<\mu$$

(19)

for the homogeneous case.

From Equations (18) and (19), it is evident that, in the homogeneous case, it will be necessary to control all nodes of the network because the necessary condition (19) is the same for every node in the network.

In order to verify the above results, we will apply the node selection criteria in the following  cases:

• A scale-free network proposed according to the algorithm in [24], for homogeneous and non-homogeneous cases.
• A regular network for homogeneous and non-homogeneous cases.

6.1. Non-Homogeneous Scale-Free Network

Let ${\mu }_i$, ${\beta }_i$ and $r_i$ be distributed uniformly in $[0.35,0.65]$, $[0.40,0.80]$ and $[0.25,0.65]$, respectively, and $N=$ 100,000 nodes. Simulation results predict that, on average, it will be necessary to control 67,610 nodes. In order to control the selected nodes, let there be

$$\overline{{\beta }_i}=\frac{{\mu }_i}{{\sum }_{j=1}^N{r}_j{a}_{ij}},$$

and the linear control law

$${\beta }_i\left(t\right)=k\overline{{\beta }_i}(1-p_i\left(t\right)),$$

(20)

where $k\in (0,1)$ is the gain that depends on the resources available to the control. The control law is applied just to those nodes that do not satisfy the necessary condition (18). In this case, the gain is set to $k=0.99$. The simulation results are shown in Figure 2.

6.2. Homogeneous Scale-Free Network

In this case, let $\mu =0.35$, $\beta =0.40$, $r=0.25$, and $N=$ 100,000 nodes. Simulations results predict that 33,387 must be controlled. In order to control the selected nodes, let be

$$\overline{{\beta }_i}=\frac{\mu }{{\sum }_{j=1}^{N}r{a}_{ij}},$$

and the linear control law

$${\beta }_i\left(t\right)=k\overline{{\beta }_i}(1-p_i\left(t\right)),$$

(21)

for those nodes i that do not satisfy (19), and ${\beta }_i=\beta$ for those nodes i that satisfy (19). The gain is set again to $k=0.99$. The simulation results are shown in Figure 3.

6.3. Non-Homogeneous Regular Network

Let ${\mu }_i$, ${\beta }_i$ and $r_i$ be distributed uniformly in $[0.35,0.65]$, $[0.40,0.80]$ and $[0.25,0.65]$ respectively, and $N=$ 100,000 nodes with degree 30. Simulation results predict that all nodes must necessarily be controlled.

In order to control the selected nodes, let there be

$$\overline{{\beta }_i}=\frac{{\mu }_i}{{\sum }_{j=1}^N{r}_j{a}_{ij}},$$

and the linear control law

$${\beta }_i\left(t\right)=k\overline{{\beta }_i}(1-p_i\left(t\right)),$$

(22)

for all nodes in the network. The gain is set to $k=0.99$ and the simulation results are shown in Figure 4.

6.4. Homogeneous Regular Network

In this case, let $\mu =0.35$, $\beta =0.40$, $r=0.25$, and $N=$ 100,000 nodes with degree 30. Simulations results predict that all the nodes must necessarily be controlled. In order to control them, let be

$$\overline{{\beta }_i}=\frac{\mu }{{\sum }_{j=1}^{N}r{a}_{ij}}=\frac{0.35}{0.40\times 0.25\times 30}=0.11667,$$

and the linear control law

$${\beta }_i\left(t\right)=k\overline{{\beta }_i}(1-p_i\left(t\right)),$$

(23)

for all nodes. The gain is again set to $k=0.99$. The simulation results are shown in Figure 5.

Note that, for regular homogeneous networks, it is necessary to control all the nodes in order to stabilize the network in the extinction state.

7. The Applicability of the Result

The applicability of the result obtained in Section 5 of the present article has the drawback that, if the topology of the network is regular, which means that each node has the same degree, and the transition/interaction probabilities are the same for all the nodes in the network, and then we cannot detect what are the nodes that have to be controlled and then we have to control all the nodes. The authors of [1] tested the applicability of a similar result by simulation under the assumption of heterogeneity of the transition probabilities inside each node as well as in the interaction rates among the nodes. Another claim made in [1] is that the regular topology seldom arise in practice because the data available show that the real world computer networks are not homogeneous and follow a power law topology [24,25]. The point of view of the first author of the present article is that the homogeneus case cannot be discarded because in many mathematical models applied successfully to social phenomena [6,7,8,11,14] as well as to virus spreading phenomena [5,12,13,26] the models were homogeneus. The assumption of homegeneity in the aforementioned models is based on the behavior of individuals in social networks. Because of that, in the present article, we are assuming that the model is homogeneus and we will justify under such circumstances that the result of Section 5 is still applicable by proving with a combinatorial enumerative argument that the regular topology of a network is extremely unfrequent.

8. Enumeration and Generating Functions

Enumeration in Combinatorics is one of the must fertile and fascinating topics of Discrete Mathematics [2,27]. The purpose of this field has been to count the different ways of arranging objects under given constraints. With the combinatorial enumerative methods, words, permutations, partitions, sequences and graphs can be counted. One of the mathematical tools that is frequently used for this end is the generating functions or formal power series. The generating functions represent a bridge between discrete mathematics and continuous analysis (particularly complex variable theory). When we face a problem whose answer is a sequence of numbers $a_0,a_1,a_2,\dots$ and we want to know what the closed mathematical expression is that enables us to obtain the element $a_n$ of that sequence. Sometimes, we can do it at first sight by inspection. For example, if the numerical sequence $1,3,5,7,9,\dots$ we recognize at first sight that it is a sequence of odd numbers and the n-th element is $a_n=2n-1$. In other cases, it is unreasonable to expect a simple formula as can be the case of the sequence $2,3,5,7,11,13,17,19,\dots$, whose $a_n$ is the n-th prime number. For some other sequences, it is very hard to obtain directly a simple formula, but it can be very helpful to transform it in a power series whose coefficients are the elements of that sequence as follows:

$$\sum _{i=0}^{\infty }{a}_i{x}^i.$$

(24)

The expression (24) is called ordinary generating function. This kind of series can be easily algebraically manipulated. In this paper, we are particularly interested in the application of the mentioned mathematical tools for the enumeration of graphs accomplishing some given properties. Many questions about the number of graphs that have some specified property can be answered by the use of generating functions. Some typical questions about the number of graphs that fulfill a given property are for example: How many different graphs can I build with n vertices? How many different connected graphs with n vertices exists? How many binary trees can be constructed with n vertices? [28,29] etc. For some of these questions, the application of generating functions allows us to easily obtain a simple formula. For some other questions, the answer is an asymptotic estimation formula. The most commonly used generating functions are the Ordinary Generating functions and the Exponential Generating functions. The generating functions are the tool used for enumerating graphs. From the point of view of the generating functions, they are to type of graph enumerating  problems:

• Labeled graphs problems,
• Unlabeled graphs problems.

The labeled graphs problems can be easily solved with the direct application of the exponential generating functions. The case of the unlabeled enumeration problems can be solved by using ordinary generating functions but require the use of more combinatorial theory and the application of Pólya’s  theorem. For more details on generating functions subject, consult Appendix A.

9. Enumerating Regular Graphs

As we mentioned in Section 8, some enumerating problems can be solved easily using generating tools for obtaining a closed formula. Some other problems are more hard to deal with for obtaining a closed mathematical expression, but we can resort in such a case to the asymptotic approximation of the coefficients of the power series [30,31,32,33]. It was also mentioned in Section 8 that there are some graph enumerating problems where the nodes are labelled and in such a case the use of the exponential generating functions is well adapted for these kinds of problems. The other case of graph enumerating problems is when we are dealing with graphs whose nodes does not have an assigned label. Then, we can resort in such case to Polya’s enumerating method [34,35] and the best choice is to use ordinary generating functions. It should also be mentioned that the edges of the graphs to be enumerated can be directed or undirected.

One of the seminal articles of enumerating graphs is [36], where a fundamental theorem was proved in the theory of random graphs on n unlabelled nodes and with a given number q of edges.

In [36], the authors obtained a necessary and sufficient condition for relating asymptotically the number of unlabelled graphs with n nodes and q edges with the number of labelled graphs with n nodes and q edges. Let $T_{nq}$ be the number of different graphs with n nodes and q edges, $F_{nq}$ the corresponding number of labelled graphs, $N=\frac{n(n-1)}{2}$ the possible edges and $F_{nq}=\left(\genfrac{}{}{0pt}{}{N}{q}\right)=\frac{N!}{q!(N-q)!}$. The result obtained in [36] can be stated as the following theorem:

Theorem 1.

The necessary and sufficient conditions that

$$T_{nq}\sim \frac{F_{nq}}{n!}$$

(25)

as $n\to \infty$ is that

$$min(q,N-q)/n-(logn/2)\to \infty .$$

(26)

The formal result expressed in Theorem 1 for unlabelled graphs is a starting point on the enumeration of regular graphs because it allows for enumerating those unlabelled graphs that have some number of edges. In fact, the author of [36] proved that, if a graph with $\left|E\right|=E\left(n\right)$ edges, where n is the number of vertices or order of such a graph, has no isolated vertices or two vertices of degree $n-1$, then the number of unlabelled graphs of order n and number of edges $\left|E\right|$ divided by the number unlabelled graphs is asymptotic to $n!$.

Another interesting article on asymptotic enumeration of labelled graphs having a given degree sequence was [37]. The authors of [37] obtained their asymptotic result for $n\times n$ symmetric matrices subject to the following constraints:

(i)

each row sum is specified and bounded,

(ii)

the entries are bounded,

(iii)

a specified sparse set of entries must be zero.

The authors of [37] mentioned that their results can be interpreted in terms of incidence matrices for labelled graphs. The results of [37] can be stated as follows. Let $\mathcal{M}(n,z)$ be the set of all $n\times n$ symmetric $(0,1)$ matrices with at most z zeroes in each row, $\mathbf{r}$ a vector over $\left[d\right]=\{0,1,\dots d\}$ and $G(M,\mathbf{r},t)$ the number of $n\times n$ symmetric matrices $\left(g_{ij}\right)$ over $\left[t\right]=\{0,1,\dots t\}$ such that

(i)

$g_{ij}=0$ if $m_{ij}=0$,

(ii)

${\sum }_j{g}_{ij}=r_i$.

Theorem 2.

For given $d,t$ and z,

$$G(M,\mathbf{r},t)\sim \frac{T(f,\delta )e^{ϵa-b}}{\prod r_i!}.$$

(27)

Uniformly, for $(M,\mathbf{r})\in {\bigcup }_{n=1}^{\infty }(\mathcal{M}(n,z)\times {[0,d]}^n)$ as $f\to \infty$, where $f={\sum }_i{r}_i,ϵ=-1ift=1and+1ift>1$, for $a={\left(\frac{{\sum }_i\left(\genfrac{}{}{0pt}{}{r_i}{2}\right)}{f}\right)}^2+\left(\frac{{\sum }_{m_{ij}}\left(\genfrac{}{}{0pt}{}{r_i}{2}\right)}{f}\right),b=\left({\sum }_{m_{ij}=0,i<j}{r}_i{r}_j+{\sum }_i\frac{\left(\genfrac{}{}{0pt}{}{r_i}{2}\right)}{f}\right),\delta ={\sum }_{m_{ij}=0}{r}_i$ and $T(f,\delta )$ being the number of involutions on $[1,f]$ such that no element in some specified set of size δ is fixed.

Three years later, the article [38] appeared giving a different approach of [37] allowing for obtaining a more general asymptotic formula without reference to an exact formula. The asymptotic result obtained by Bela Bollobas in [38] for enumerating labelled regular graphs is proved by a probabilistic method. This result can be stated as follows. Let $\Delta$ and n be natural numbers such that $\Delta n=2m$ is even and $\Delta \le {(2logn)}^{\frac{1}{2}}$, where n is the number of vertices and m is the number of edges of the graph G. Then, as $n\to \infty$, the number of labelled $\Delta$-regular graphs on n vertices is asymptotic to

$$e^{-\lambda -{\lambda }^2}\frac{\left(2m\right)!}{m!2^m{(\Delta !)}^m},$$

(28)

where $\lambda =\frac{(\Delta -1)}{2}$.

The authors of [38] affirm that the asymptotic Formula (28) holds not only for $\Delta$ constant but also for $\Delta$ growing slowly as $n\to \infty$ and summarized this in the following theorem.

Theorem 3.

Let $d_1\ge d_2\ge \dots d_n$ be natural numbers with ${\sum }_{i=1}^n{d}_i=2m$ even. Suppose $\Delta =d_1\le {(2logn)}^{\frac{1}{2}}-1$ and $m\ge max\{ϵ\Delta n,(1+ϵ\left)n\right\}$ for some $ϵ>0$. Then, the number $L\left(\mathbf{d}\right)$ of labelled graphs with degree sequence $\mathbf{d}={\left(d_i\right)}_1^n$ satisfies

$$L\left(\mathbf{d}\right)\sim e^{-\lambda -{\lambda }^2}\frac{{\left(2m\right)}_m}{\{2^m{\prod }_{i=1}^n{d}_i!\}},$$

(29)

where $\lambda =\frac{1}{2m}{\sum }_{i=1}^n\left(\genfrac{}{}{0pt}{}{d_i}{2}\right).$

In the next year, the author on [38] extended this result to the case of unlabelled graphs in [39]. The result of Theorem 3 extended for the case of unlabelled graphs can be summarized in the following theorem.

Theorem 4.

If $\Delta \ge 3$ and $L_{\Delta }=e^{-\lambda -{\lambda }^2}\frac{\left(2m\right)!}{m!2^m{(\Delta !)}^m}$, then

$$U_{\Delta }\sim \frac{L_{\Delta }}{n!}\sim e^{-\frac{({\Delta }^2-1)}{4}}\frac{\left(2m\right)!}{2^{m}m!}\frac{{(\Delta !)}^{-n}}{n!},$$

(30)

where $m=\frac{\Delta n}{2}.$

For the details of the proof of Theorems 3 and 4, see [38,39], respectively.

10. Combinatorial Proof of Applicability of the Result on Control Node Selection

As was mentioned in Section 1, the case of homogeneity in the behavior of the nodes and their interaction can not be discarded given what has been observed in the reaction of the agents in the context of social networks is that they try to minimize the conflict. Many successful models can, for example [5,6,11,12], base their predicting effectiveness on the homogeneity of the behaviour of the nodes and their interaction. By other side, in Section 5 of the present paper, we have obtained a criteria for selecting the nodes to be controlled, but such criteria fails if we have homogeneity in the behavior of the nodes and, at the same time, the topology of the network is regular. Then, what we want to do here is to justify the applicability of obtained in Section 5, keeping the homogeneity of the nodes and try to compare the number of regular graphs with n vertices with the total of graphs that can be constructed with n vertices. For this end, based on the results on combinatorial graph enumeration mentioned on the Theorems 3 and 4, we can state our main result as follows. First of all, we suppose that our graph is labelled, that $G=(V,E)$ is $r$—regular with $r\ge 3$ constant and $rn=2m$, where $n=\left|V\right|$ corresponds to the number of vertices and $m=\left|E\right|$ corresponds to the number of edges. Let $L_r$ the number of labelled regular graphs of degree r whose asymptotic value is ([38])

$$L_r\sim e^{-\frac{r^2-1}{4}}\frac{\left(2m\right)!}{2^{m}m!}{(r!)}^n.$$

(31)

Let $G_n$ be the number of all possible graphs with n vertices whose value is

$$G_n=2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}.$$

(32)

Theorem 5.

If $r\ge 3$ and $nr=2m$, then

$$\underset{n\to \infty }{lim}\frac{L_r}{G_n}=0.$$

(33)

Proof of Theorem 5.

If $nr=2m$ and r is constant of value $c_1$, then we can deduce that $m=\frac{r}{2}n=\frac{c_1}{2}n$ and this implies that $m=O\left(n\right)$ so lets say that $m=c_{2}n$; then,

$$\begin{array}{cc}\hfill \underset{n\to \infty }{lim}\frac{L_r}{G_n}=& {lim}_{n\to \infty }\frac{e^{-\frac{c_1^2-1}{4}}\frac{\left(2c_{2}n\right)!{(c_1!)}^{-n}}{2^{c_{2}n}\left(c_{2}n\right)!}}{2^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)}}\\ \hfill =& {lim}_{n\to \infty }\frac{\frac{e^{-\frac{c_1^2-1}{4}}}{{(c_1!)}^n}\frac{\left(2c_{2}n\right)!}{2^{c_{2}n}\left(c_{2}n\right)!}}{2^{\frac{n(n-1)}{2}}},\end{array}$$

applying the approximation Stirling formula $n!\sim \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$

$$\begin{array}{cc}\hfill {(c_1!)}^n=& {\left(\sqrt{2\pi c_1}{\left(\frac{c_1}{e}\right)}^{c_1}\right)}^n\\ \hfill then\\ \hfill =& {lim}_{n\to \infty }\frac{\frac{e^{-\frac{c_1^2-1}{4}}}{{\left(\sqrt{2\pi c_1}{\left(\frac{c_1}{e}\right)}^{c_1}\right)}^n}\frac{\left(2c_{2}n\right)!}{2^{c_{2}n}\left(c_{2}n\right)!}}{2^{\frac{n(n-1)}{2}}}\\ \hfill simplifying\\ \hfill =& {lim}_{n\to \infty }\frac{\frac{1}{{\left(\sqrt{2\pi c_1}\right)}^n{\left(c_1\right)}^{c_{1}n}{e}^{\frac{c_1^2+4c_{1}n+1}{4}}}\frac{\left(2c_{2}n\right)!}{2^{c_{2}n}\left(c_{2}n\right)!}}{2^{\frac{n(n-1)}{2}}},\end{array}$$

applying the approximation Stirling formula

$$\begin{array}{cc}& \left(2c_{2}n\right)!=\sqrt{2\pi \left(2c_{2}n\right)}{\left(\frac{\left(2c_{2}n\right)}{e}\right)}^{\left(2c_{2}n\right)}\\ \hfill \mathrm{and}& \\ & \left(c_{2}n\right)!=\sqrt{2\pi \left(c_{2}n\right)}{\left(\frac{\left(c_{2}n\right)}{e}\right)}^{\left(c_{2}n\right)}\\ \hfill \mathrm{we}\mathrm{get}& \\ \hfill =& {lim}_{n\to \infty }\frac{\frac{1}{{\left(\sqrt{2\pi c_1}\right)}^n{\left(c_1\right)}^{c_{1}n}{e}^{\frac{c_1^2+4c_{1}n+1}{4}}}\frac{\sqrt{2\pi \left(2c_{2}n\right)}{\left(\frac{\left(2c_{2}n\right)}{e}\right)}^{\left(2c_{2}n\right)}}{2^{c_{2}n}\sqrt{2\pi \left(c_{2}n\right)}{\left(\frac{\left(c_{2}n\right)}{e}\right)}^{\left(c_{2}n\right)}}}{2^{\frac{n(n-1)}{2}}},\end{array}$$

simplifying

$$\begin{array}{cc}\hfill =& {lim}_{n\to \infty }\frac{\frac{\sqrt{2}}{{\left(\sqrt{2\pi c_1}\right)}^n{c}_1^{c_{1}n}{e}^{(c_1^2+4c_{1}n+1)/4}}{\left(\frac{c_{2}n}{e}\right)}^{c_{2}n}}{2^{\frac{n(n-1)}{2}}},\end{array}$$

(34)

given that $r\ge 3$, for which we assumed that r is a constant $c_1$ and that $nr=2m$, then we have that $c_1=2c_2$ and replacing that, in (34), we can express it in terms of $c_1$, which is the regular degree r assumed as fixed; then, we get

$$\underset{n\to \infty }{lim}\frac{\frac{\sqrt{2}}{{\left(\sqrt{2\pi c_1}\right)}^n{c}_1^{c_{1}n}{e}^{(c_1^2+4c_{1}n+1)/4}}{\left(\frac{c_{1}n/2}{e}\right)}^{c_{1}n/2}}{2^{\frac{n(n-1)}{2}}},$$

(35)

and, replacing $c_1$ by r in (36), we get

$$\underset{n\to \infty }{lim}\frac{\frac{\sqrt{2}}{{\left(\sqrt{2\pi r}\right)}^n{r}^{rn}{e}^{(r^2+4rn+1)/4}}{\left(\frac{rn/2}{e}\right)}^{rn/2}}{2^{\frac{n(n-1)}{2}}}.$$

(36)

Therefore, if the degree r is constant, the ${lim}_{n\to \infty }\frac{L_r}{G_n}=0$. □

Now, our main result can be stated as a consequence of Theorem 5.

Theorem 6.

If we assume that all graphs are uniformly distributed and that the nodes have homogeneous behavior, then the criteria for selecting nodes to be controlled obtained in Section 5 is almost always applicable.

Proof of Theorem 6.

As a consequence of Theorem 5, we know that the probability that a regular graph appears tends to zero as $n\to \infty$. Then, the mentioned criteria is almost always applicable. □

11. Conclusions

In the present article, we have applied the techniques of combinatorial enumeration to prove the applicability of a selection result of nodes to be controlled in a regular network modeled by a graph under the hypothesis of homogeneity in the behavior of the nodes. This allowed us to explore the application of combinatorial techniques to control problems in networks and thus verify the goodness of said methods for network analysis and the control of virus propagation in them. This still needs to be studied by applying the combinatorial methods discussed above, if there are any other types of topologies that prevent the application of the selection criteria of nodes to be controlled under the hypothesis of behavior of partially heterogeneous nodes, that is, if in the network we have subsets of nodes with the same behavioral parameters. The selecting node criteria described in Section 5 is based on the combination of the parameter values of the selected nodes as well as their degrees. In many recent publications [40,41,42,43,44,45,46,47], interesting and elaborated methods for detecting the influencer nodes in complex networks have been proposed that we will try to apply in combination with our criteria in the future in order to reduce the number of nodes to be controlled. We must mention as another contribution of the present article that the simulations of Section 6 allowed us to illustrate the application of the criterion obtained in Section 5 for scale-free as well as 30-regular topologies under conditions of both homogeneity and heterogeneity and obtain the number of nodes to be controlled in each case.