Учебное пособие по ТСиСА

Вычисление ранга по зависимости (4.9) позволяет получить достаточно точное значение, что совсем необязательно для определения типа элемента. Поэтому представляется целесообразным воспользоваться приближенной формулой для нахождения ранга вершины:

		n
	∑ aij( k )
ri =	i =1		,	(4.10)
	n	n
	∑ ∑ aij( k )
	i =1	j =1

где aij(k ) - элемент матрицы смежности, возведенной в сте-

пень 3...4.

Вершины с равными рангами и будут составлять определенный тип.

Для оценки однородности связей выражение (4.7) примет следующий вид:

	1		t
Kосв =			∑ (ni ρ) 2 ,	(4.11)
	4m	2
			i=1

где ρi - действительная степень вершин i-го типа.

Дополнительными характеристиками гомогенности структуры могут являться:

для оценки однородности вершин - степень упорядоченности вершин графа

ξ = max{ p1 , p2 , . .. , ph } = max{ pi }, i =		,	(4.12)
	1, h

где pi = ni n ;

h - количество уровней в упорядоченном графе;

ni - число вершин на i-м уровне упорядоченного графа,

для оценки однородности ребер - средняя степень вершин графа

		=	2m	.	(4.13)
	ρ
			n

При этом под упорядоченным графом понимается граф, построенный по исходному, для которого справедливо:

1 − й уровень − ρ(1): {n (1) }; 2 − й уровень − ρ(2): {n (2) };

. .. .. .. . .. .. .. . .. .. .. .. . .. .. .. . .. .. .;

(n − 1) − й уровень − ρ(n − 1): {n ( n−1) },

где ρ(i) - действительная степень вершин, равная i;

n (i ) - подмножество n, элементы которого имеют действительную степень i.

Для количественной оценки компактности структуры вводится параметр, отражающий «близость» вершин графа между собой, которая определяется через минимальную длину цепи d ij

между вершинами i и j. Тогда величина

n	n
Q = ∑ ∑ d ij , i ¹ j		(4.14)
i =1	j =1

отразит абсолютную компактность [8].

Однако наиболее удобно использовать относительный показатель

Q = 2n(n − 1) . (4.15)

отн	n(n − 1)	+ Q

Учитывая, что Qmin = n(n - 1) и если Q ¹ Qmin , то всегда Q > Qmin . В этом случае

Qотнmin =	3n(n - 1) + Qmax	- 1,	Qотнmax = 1,
	n(n - 1) + Qmax
n−1 n− i
где Qmax = 2∑ ∑ ji .
i =1 j =1

Свойство компактности можно также характеризовать диаметром графа

d = max{d ij }	(4.16)
i , j

или относительным диаметром

d отн =	d		(4.17)
		,
	n − 1

− n) ,

и, кроме того, порядком графа

		1	n
	π =		∑ ei ,	(4.18)
		n i =1

где ei = max{d ij }- эксцентриситет i-й вершины, т.е. макси-

j

мальная из его минимальных цепей. Цикломатическое число графа, определяющее его циклома-

тичность, находится из выражения

ψ = m − n + 1.

Показателями централизации являются степень централизации

δ = (n − 1)(2zmax zmax (n − 2)

			Q
где	zmax = max			;
			n
	i		2∑ dij
			j =1

(4.19)

(4.20)

неравномерность распределения ребер графа по вершинам

ε 2

ε 2 = a , (4.21)

εmax2

				1		n		4m2
εa2		=				∑ρi2 −				;
				n
где						i=1		n
							3m2
ε	2		= (n−1)2 −						.
	max
								n2

Ацикличность графа можно оценить по формуле

ψ (− ) =	n(n − 1) − 2m	.	(4.22)
	m(n − 2)

Необходимо отметить, что все показатели топологических свойств являются функциями от числа вершин и ребер графа, формализующего структуру. Если граф содержит n вершин, то mmin =(n-1). Добавляя случайным образом новое ребро (при усло-

вии, конечно, что его появление возможно между несмежными вершинами) в граф, нетрудно получить зависимости основных показателей от числа ребер в графе. Очевидно, что распределение ребер по вершинам графа будет носить случайный характер, что свидетельствует о стохастической природе получаемых зависимостей. Для равновероятного появления ребра между любой парой несмежных вершин и n=10, характер изменения показателей топологических свойств показан на рис.4.3.

C	1
	0.8
	0.6
	0.4
	0.2
	0	9	18	27	36	45	m
	0
		a) Относительная связность

R	1
	0.8
	0.6
	0.4
	0.2
	0	9	18	27	36	45	m
	0
		б) Структурная избыточность

Коэ 1

0.8

0.6

0.4

0.2

0	9	18	27	36	45	m
0

в) Коэффициент структурной однородности элементов

Косв 1

0.8

0.6

0.4

0.2

0	9	18	27	36	45	m
0

г) Коэффициент структурной однородности связей

δ 1

0.8
0.6
0.4
0.2
0	9	18	27	36	45	m
0

д) Степень централизации

Qотн 1

0.8
0.6
0.4
0.2
0	9	18	27	36	45	m
0

е) Относительная структурная компактность

ψ(-) 1

0.8
0.6
0.4
0.2
0	9	18	27	36	45	m
0

ж) Ацикличность структуры

ε2 1

0.8
0.6
0.4
0.2
0	9	18	27	36	45	m
0

з) Неравномерность распределения связей в структуре

Рис. 4.3. Характер изменения показателей топологических свойств в зависимости от числа ребер в графе структуры

Из рис.4.3 видно, что целостность структуры прямо пропорциональна числу ребер, описывающего ее графа. Гомогенность носит параболический характер, а плотность и радиальность могут быть аппроксимированы гиперболической функцией.

Приведенные показатели топологических свойств количественно оценивают первичные топологические свойства, что позволяет осуществлять оценку организации структуры, представленной графом. В связи с эти необходимо иметь комплексный показатель, который учитывал бы интенсивность проявления определяющих организацию свойств.

4.3.Комплексный показатель качества организации структуры

Нетрудно заметить, что большая часть рассмотренных показателей топологических свойств коррелированна. Действительно, увеличение централизации ведет к уменьшению избыточности (обратное неверно), а повышение однородности вершин графа отрицательно сказывается, например, на ацикличности. Поэтому формирование обобщенного показателя на основе метрик линейного пространства, нецелесообразно.

С другой стороны, известные виды сверток (аддитивная, мультипликативная, гармоническая и др.) предполагают определение вектора весовых коэффициентов соответствующих показателей, что вызывает наибольшую трудность, в силу известной субъективности при построении комплексного показателя, и тре-