Some Questions in the Statistical Study of Network Graphs

Yu. N. Efimov

(Presented by the scientific seminar of the Computing Laboratory)

A heuristic algorithm for optimizing the schedule of jobs of a network graph in an SPU system with limited resources [1] leads, in most cases, to practically satisfactory results. However, network graphs may be encountered for which the optimization algorithm gives no effect at all. For such network graphs, the improvement coefficient described in [1] is close to unity. Naturally, in such cases there is no point in carrying out the comparatively laborious optimization procedure. It would therefore be desirable to estimate in advance, at least from a probabilistic point of view, the value of the improvement coefficient \(K_{\text{ul}}\). This article is devoted to questions of a preliminary estimate of the improvement coefficient.

In the general case, \(K_{\text{ul}}\) depends on the topology of the network, the durations of the jobs \(t_{ij}\), and the intensity of resource consumption in the jobs \(v_{ij}\). For example, one can choose such values of \(t_{ij}\) that all jobs of the network graph are “critical,” or choose such values of \(v_{ij}\) that the equipment-load schedule is uniform. It is clear that in these cases there is no point in speaking of optimization of the jobs. \(K_{\text{ul}}\) also depends on the ratio between the number of events \(M\) and the number of jobs \(N\) of the network graph. Indeed, when \(N = M - 1\), the network graph degenerates into a single chain of “critical” jobs. As \(N\) grows with \(M = \mathrm{const}\), i.e., with an increase in the complexity coefficient of the network graph \(\left(K_{\text{sl}} = \dfrac{N}{M}\right)\), branches appear, and with them the possibility of optimization. Moreover, a priori one may assert that as \(K_{\text{sl}}\) grows, the value of \(K_{\text{ul}}\) will tend to decrease. At the maximum possible number of jobs

\[ N_{\max} = \frac{M(M-1)}{2}, \]

the network graph is a complete graph [2], and the maximum effect of applying optimization is achieved. Let us try to estimate the mathematical expectation of the improvement coefficient \(\left(M[K_{\text{ul}}]\right)\) as a function of \(K_{\text{sl}}\).

First of all, we shall be interested in the distribution law of \(K_{\text{ul}}\). Using the notation of [1], we have

\[ K_{\text{ul}} = \frac{\max R_n(t)}{\max R_0(t)}, \]

where

\[ \max R_n(t)=\sum_{(ij)\in F_n(t)} v_{ij}; \]

\[ \max R_0(t)=\sum_{(ij)\in F_0(t)} v_{ij}; \]

\(F_0(t)\) and \(F_n(t)\) are the work fronts (before and after optimization, respectively) at which the maximum amount of the resource is consumed.

Making the substitution

\[ \max R_n(t)=X, \qquad \max R_0(t)=Y, \qquad K_{\text{ul}}=Z, \]

we obtain

\[ Z=\frac{X}{Y}. \tag{1} \]

The intensities of resource consumption by the jobs belonging to a given front are random quantities; consequently, \(X\) and \(Y\) are sums of a random number of random variables. Since the quantities being summed are of the same nature, Lyapunov’s theorem [3] may be applied, according to which the random variables \(X\) and \(Y\) are normally distributed with mathematical expectations \(m_x, m_y\) and variances \(D_x, D_y\). Consequently, the distribution-density functions \(f(x)\) and \(f(y)\) may be regarded as known. The probability density of the function \((Z)\) of two random arguments is determined by the formula [3]

\[ f_z(z)=\int_{-\infty}^{\infty} f(\psi(z,y),y)\left|\frac{\partial \psi(z,y)}{\partial z}\right|\,dy, \]

where \(\psi(z,y)=X=XY\) is the solution of equation (1). Since the quantities \(X\) and \(Y\) are strongly correlated, obtaining an analytical expression for the distribution law of the system of random variables \((X,Y)\), and consequently also \(f_z(z)\), is a very difficult problem. Therefore, to find the distribution law of the random variable \(K_{\text{ul}}\), we shall use the method of statistical trials.

Let a network graph \(G=(I,U)\) be given, having \(M\) events and \(N\) jobs. By a variant \(V\) of the graph \(G\) we shall mean a network graph in which the job durations \(t_{ij}\) and the resource-consumption intensities \(v_{ij}\) have specific values obtained at random. The random numbers \(t_{ij}\) and \(v_{ij}\) in the interval \((\alpha,\beta)\) are most conveniently obtained with the aid of program random-number generators. These generators are based on obtaining a sequence of uniformly distributed numbers in the interval \((0,1)\) by recurrence formulas. The obtained random numbers \(\delta_i\) are reduced to the interval of interest to us according to the relation

\[ \gamma_i=\alpha+\delta_i(\beta-\alpha). \]

Using the relation

\[ \gamma_i=\sigma\left(\sum_{j=1}^{12}\delta_j-6\right)+m, \]

one can form a sequence of numbers \(\gamma\), distributed according to the normal law with parameters \(m\) and \(\sigma\). The numbers \(\gamma_i\) obtained are in fact pseudorandom. But since the properties of a sequence of pseudorandom numbers correspond to the statistical properties of random variables distributed according to the specified law, these numbers can quite well be used for statistical trials.

The initial information on variant \(V\) will be represented in the form of a list of jobs \((ij\, t\, U)\), their durations, and the intensities of resource consumption on these jobs,

\[ ij t_{ij} v_{ij}. \tag{2} \]

We shall carry out a time analysis of the network graph, using the iterative method [4],

\[ t_p(j)=\max \left[t_p(j),\, t_p(i)+t_{ij}\right], \]

\[ t_n(i)=\min \left[t_n(i),\, t_n(j)-t_{ij}\right], \]

where \(t_p\) and \(t_n\) are, respectively, the earliest and latest times of occurrence of events.

We find the floats \((P)\) of jobs by the formula [1]

\[ P=t_p(j)-t_p(i)-t_{ij} \]

and form the information in a form convenient for optimization,

\[ t_n P N t_{ij} v_{ij}, \tag{3} \]

where

\(t_n\) is the start time of a job in the initial schedule, \(t_n=t_p(i)\).

\(N\) is the single-index number of the job.

Then we carry out the optimization procedure and obtain the value \(K_{\mathrm{ul}}\).

Calculation of time parameters
        ↓
Formation of information in the form (3)
        ↓
Optimization of the job schedule
        ↓
Output to the punch of the value K_ul
        ↓
Obtaining a new variant V_i
        ↺

Fig. 1. Flow chart of the program for preparing statistical material

Calculating the value of the improvement coefficient for various variants \(V_i\) \((i=1,2,\ldots,n)\) of the graph \(G\), one can construct a frequency histogram of the quantity \(K_{\mathrm{ul}}\), and then approximate it by the corresponding distribution law. By carrying out similar calculations for network graphs of different complexity, one can determine the dependence of the distribution law of the quantity \(K_{\mathrm{ul}}\) on the value of the complexity coefficient.

According to the described procedure, calculations of network graphs were carried out on a Minsk-1 digital computer. In the program implementing the process of preparing statistical material (Fig. 1), a random-number generator with a uniform distribution in the interval \((1,7)\) was used for \(t_{ij}\) and \((0,7)\) for \(v_{ij}\). The choice of intervals is due to the limited word length of the machine and the accepted assumption of the absence of fictitious jobs. Otherwise it would have been necessary to introduce additional conditions on the random variables formed by the generators. The resulting complexity coefficients were output to the punch for subsequent statistical processing. From the results of the statistical processing, frequency histograms of \(K_{\mathrm{ul}}\) were constructed, the form of which is shown in Fig. 2. As is evident from Fig. 2,

the most appropriate law for approximating the histogram is the normal law. The agreement of the hypothesis of a Gaussian distribution with the experimental data was assessed by the \(\chi^2\) criterion. For this purpose, from the statistical data the mathematical expectation \(\left(M[K_{\mathrm{ul}}]\right)\), the variance \(\left(D[K_{\mathrm{ul}}]\right)\), and the root-mean-square deviation \(\sigma\) of the quantity \(K_{\mathrm{ul}}\) were found by the formulas [3]:

\[ M[K_{\mathrm{ul}}]=\sum_{i=1}^{n}\frac{K_{\mathrm{ul}}^{\,i}}{n}; \]

\[ D[K_{\mathrm{ul}}]= \frac{\sum_{i=1}^{n}\left(K_{\mathrm{ul}}^{\,i}-M[K_{\mathrm{ul}}]\right)^2}{n-1}; \]

Fig. 2. Example of the distribution of the quantity \(K\):
a) frequency histogram of the quantity \(K\)
b) probability-distribution graph of an ideal Gaussian process having the same parameters.

Fig. 3. Graph of the dependence \(M[K_{\mathrm{ul}}]=f(K_{\mathrm{sl}})\)

\[ \sigma=\sqrt{D[K_{\mathrm{ul}}]}. \]

The measure of discrepancy \(\chi^2\) was calculated by the formula

\[ \chi^2=\sum_{i=1}^{k}\frac{(m_i-np_i)^2}{np_i}, \]

where

\(m_i\) is the number of values falling in the \(i\)-th class,
\(k\) is the number of classes,
\(p_i\) is the probability that the random variable \(K_{\mathrm{ul}}\) falls in the \(i\)-th class, which is found by the formula

\[ p_i=\frac{1}{2}\left[\Phi\left(\frac{K_{\mathrm{ul}\,i+1}-M[K_{\mathrm{ul}}]}{\sigma\sqrt{2}}\right)-\Phi\left(\frac{K_{\mathrm{ul}\,i}-M[K_{\mathrm{ul}}]}{\sigma\sqrt{2}}\right)\right], \]

and \(\Phi(x)\) is the well-known Laplace function,

\[ \Phi(x)=\frac{2}{\sqrt{\pi}}\int_{0}^{x} e^{-t^2}\,dt . \]

From the value of \(\chi^2\) and \(r=k-s\) (with approximation by the normal law, \(s=3\)), using the tables in [3] we find the probability \((p)\) that a quantity having a \(\chi^2\) distribution with \(r\) degrees of freedom will exceed the obtained value of \(\chi^2\). The resulting probabilities \(p=(0.5 \div 0.8)\) are sufficiently large and indicate that the hypothesis of a Gaussian distribution of \(K_{\mathrm{ul}}\) does not contradict the data.

Fig. 4. Graph of the dependence \(D[K_{\mathrm{ul}}]=f(K_{\mathrm{sl}})\).

Using data obtained as a result of calculations of network graphs of various complexity, the dependences

\[ M[K_{\mathrm{ul}}]=f(K_{\mathrm{sl}}),\quad D[K_{\mathrm{ul}}]=f(K_{\mathrm{sl}}) \]

(Figs. 3 and 4) have been constructed; they can be used for a preliminary estimate of \(K_{\mathrm{ul}}\) from the known complexity coefficient of a network graph.

As is evident from Figs. 3 and 4, as the complexity of the network graph decreases, the probability-distribution curve shifts toward an increase in \(M[K_{\mathrm{ul}}]\), with a simultaneous increase in variance. The decrease in variance at improvement coefficients close to unity is evidently explained by the influence of the condition:

\[ K_{\mathrm{ul}}\leqslant 1. \]

References

1. Yu. N. Efimov. Optimization of the plan for distributing work in a project management system with limited resources. (The present collection).

2. K. Berge. Graph Theory and Its Applications. Moscow, Foreign Literature Publishing House, 1962.

3. E. S. Venttsel. Probability Theory. Moscow, 1958.

4. Yu. N. Efimov. Analysis of Network Graphs on the Minsk-1 Computer. Scientific Report No. R-767, 1967.