Построение и анализ графов с помощью матрицы смежности: вычисление центральности и кластеризации по Бейтману

Матричное представление графа и степени вершин

Работу начинают с формализации исходной сети в виде квадратной матрицы смежности $A$ размера $n \times n$. Для ненаправленного графа без петель матрица симметрична относительно главной диагонали, а диагональные элементы строго равны нулю. Степень вершины $k_i$ вычисляется простым суммированием элементов соответствующей строки или столбца. При нормализации эту величину делят на максимально возможное число связей $n - 1$, получая значение центральности по степени (degree centrality) в диапазоне от 0 до 1.

В расчетной части показывают связь степеней матрицы со структурой путей. Произведение матрицы $A$ на саму себя дает число путей длины 2 между каждой парой вершин, а элемент $(A^k)_{ij}$ отражает количество маршрутов длины $k$ между узлами $i$ и $j$. Этот фундаментальный факт связывает линейную алгебру с топологией сети и служит математической базой для доказательства дальнейших свойств связности.

Алгоритмы расчета близости и промежуточности

Второй блок требует вычисления длин кратчайших путей $d(i, j)$ между всеми парами вершин. Для невзвешенного графа используют поиск в ширину (BFS), повторяемый из каждого узла, либо алгоритм Флойда — Уоршелла со сложностью $O(n^3)$. Центральность по близости (closeness centrality) определяется как величина, обратная сумме кратчайших расстояний от выбранного узла до всех остальных. Чем меньше суммарная дистанция, тем выше показатель и тем быстрее узел передает информацию по всей сети.

Центральность по промежуточности (betweenness centrality) измеряет долю кратчайших путей между всеми парами узлов, проходящих через заданную вершину. Для эффективного расчета этого показателя на практике применяют алгоритм Брандеса, который снижает вычислительную сложность до $O(nm)$ шагов. В теоретической главе выводят формулы нормализации, деля абсолютный показатель промежуточности на коэффициент $(n - 1)(n - 2) / 2$ для ненаправленного случая.

Вычисление коэффициента кластеризации

Локальный коэффициент кластеризации показывает вероятность того, что два соседа одной вершины соединены ребром между собой. Алгебраически число треугольников, содержащих вершину $i$, вычисляется через диагональный элемент куба матрицы смежности $(A^3)_{ii}$, деленный на 2. Затем это значение делится на число всех возможных ребер между соседями, равное $k_i(k_i - 1) / 2$. Если степень узла меньше 2, локальный коэффициент полагают равным нулю.

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

Экспериментальная часть на данных социальной сети

Для практического блока берут реальный фрагмент графа взаимодействий, например сеть друзей или совместных публикаций. Программа считывает список смежности или ребер, формирует матрицу и запускает расчет всех введенных метрик. Итоговые результаты оформляют в виде сводной таблицы, где для топ-10 узлов сопоставляются значения степени, близости, промежуточности и кластеризации.

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