Учебники 80212

In[5]:= g = Subgraph[graph, First[WeaklyConnectedComponents[graph]]]; h = Subgraph[graph, Last[SortBy[ConnectedComponents[graph], Length]]];

statGrid[graph, g, h]

Out[5]//TraditionalForm=

Анализ распределения степеней входящих рёбер.

In[6]:= indegree = VertexInDegree[graph]; lndist = EstimatedDistribution[indegree,

LogNormalDistribution[mu, si]]; pdist = EstimatedDistribution[indegree, ParetoDistribution[k, al]];

emdist = EmpiricalDistribution[indegree];

In[7]:= distPlot[emdist, lndist, pdist]

20

Out[7]=

Рис. 5. Визуализация связей участников социальной сети

1.2.5. Кластеризация в сетях «малого мира»

Кластеризацию можно использовать для количественного определения устойчивости сети к возмущениям. Сети «малого мира» по модели Ватса Строгаца обладают высокой степенью кластеризации (рис. 6, 7). В эпидемиологии устойчивая сеть позволяет болезни распространяться схожим образом, даже, если в сеть вводить возмущения.

Нахождение коэффициента глобальной кластеризации случайного графа

Out[1]=

21

Рис. 6. Кластер

In[2] RandomGraph[WattsStrogatzGraphDistribut := ion[40, 0.05, 5]];

GlobalClusteringCoefficient[%]

Out[2]= 333/604

Нахождение коэффициентов глобальной кластеризации множества случайных графов

In[3] {graphs, coeffs} = := Transpose[

SortBy[{#, GlobalClusteringCoefficient[#]} & /@

RandomGraph[WattsStrogatzGraphDistribut ion[30, 0.1, 3], {10000}],

Last]];

Создание тепловой карты полученных графов по значениям коэффициентов

In[4]:= min = Min[coeffs]; max = Max[coeffs];

In[5]:= nf = Nearest[coeffs -> graphs];

In[6]:= values = Range[min, max, (max - min)/(4^2 - 1)];

In[7]:= Grid[Partition[Map[ SetProperty[

First[nf[#]] 1, {VertexStyle -> Directive[White,

EdgeForm[White]], EdgeStyle -> White, Background ->

ColorData[{"SolarColors",

"Reversed"},

Rescale[#, {min, max}]], ImageSize -> {100, 100}}] &, values],

4]]

22

Out[8]=

Рис. 7. Определение устойчивости сети к возмущениям

спомощью кластеризащии

2.ПРИМЕР РЕШЕНИЯ ЗАДАЧИ

2.1.Решения задачи построения эквивалентного графа

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

23

Эквивалентность между вершинами А4 и А8 рассчитаем по формуле 1.14. Тогда эквивалентность определяем как квадратный корень из суммы всех «несовпадений» между4-й и 8-й строкой и 4-м и 8-м столбцом:

Для = 1, 2, 3, 5, 6, 7 слагаемые под корнем будут равны ; для

для – Тогда эквивалентность между 4-й и 8-й вершинами будет составлять:

.

Теперь приступим к более сложной части задания: для построения эквивалентного графа вершины исходного графа необходимо правильно и последовательно пронумеровать.

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

Измененная матрица смежности выглядит следующим образом повторяющиеся элементы выделены) (табл. 1).

Таблица 1

Измененная матрица смежности

25

Эквивалентный граф выглядит так, как показано на

рис. 9

Рис. 9. Эквивалентный граф

Задачи на эквивалентность можно решить и без построения измененных или эквивалентных матриц. Если у исследователя хорошо развито пространственное воображение, он способен заранее предсказать, какие вершины скорее всего окажутся эквивалентными. Тогда матрица эквивалентности потребуется только как доказательство {или проверка) ранее сделанных умозаключений. В «Методических указаниях» задачи подобраны таким образом, чтобы эквивалентные позиции группировались, исходя из разных закономерностей расположения фигуры на плоскости и в пространстве. Но очень часто в реальных ситуациях сложно выделить оси симметрии и заранее предугадать вид эквивалентного графа. Тогда рассчитывают эквивалентность каждой пары вершин графа. Обычно это делается при помощи специальных компьютерных программ. Однако необходимо помнить, что коэффициенты разрабатывались для неориентированных графов, и в большинстве из них невозможно учесть вес связей. Поэтому следует говорить только об эквивалентности структурных позиций.

2.2. Анализ дружеских связей vk с помощью

Wolfram Mathematica

27