Линейная алгебра в теории графов: матрица смежности и лапласиан

Матрица смежности и маршрутизация

Самый базовый способ описать граф математически — составить матрицу смежности (обозначается буквой A). Если в графе n вершин, это будет квадратная матрица размера n на n. Элемент матрицы, стоящий на пересечении i-й строки и j-го столбца, равен 1, если между вершинами i и j есть ребро, и 0, если ребра нет. Для неориентированных графов эта матрица всегда симметрична (A = A^T), что гарантирует наличие у нее вещественных собственных значений. Но самое интересное начинается при возведении матрицы смежности в степень. Элемент матрицы A^k (А в степени k) в позиции (i, j) показывает в точности количество уникальных путей длиной ровно k шагов, ведущих из вершины i в вершину j. Это свойство широко используется в сетевой безопасности для анализа уязвимостей и маршрутизации пакетов.

Алгоритм PageRank: марковские цепи на графах

В конце 1990-х годов Ларри Пейдж и Сергей Брин основали компанию Google, опираясь на один из самых успешных в истории алгоритмов линейной алгебры — PageRank. Интернет представляется как гигантский ориентированный граф, где веб-страницы — это вершины, а гиперссылки — направленные ребра. Матрица смежности этого графа модифицируется в матрицу вероятностей переходов (стохастическую матрицу). PageRank сводится к поиску собственного вектора этой огромной матрицы, соответствующего собственному значению, равному 1. Координаты этого собственного вектора показывают важность (вес) каждой веб-страницы в сети. Нахождение этого вектора осуществляется итерационным степенным методом, который прекрасно параллелится на вычислительных кластерах.

Степени вершин и Лапласиан графа

Для более глубокого анализа структуры сети используется Лапласиан графа (матрица Кирхгофа). Для его построения сначала формируется диагональная матрица степеней D, где на диагонали записано количество связей для каждого узла. Лапласиан вычисляется как разность матрицы степеней и матрицы смежности: L = D - A. Матрица Лапласа обладает уникальными алгебраическими свойствами: сумма элементов в каждой строке и столбце строго равна нулю, а сама матрица является положительно полуопределенной. Это означает, что все ее собственные значения неотрицательны, а самое маленькое собственное значение всегда равно нулю (его собственный вектор состоит из одних единиц). Алгебраическая кратность нулевого собственного значения в точности равна количеству изолированных (несвязных) кусков графа.

Вектор Фидлера и спектральная кластеризация

Особый интерес в анализе данных представляет второе по величине наименьшее собственное значение Лапласиана, называемое алгебраической связностью графа. Соответствующий ему собственный вектор носит имя американского математика Мирослава Фидлера (вектор Фидлера). Этот вектор содержит невероятно ценную информацию о внутренней топологии сети. Знаки координат вектора Фидлера позволяют разделить весь граф на два ярко выраженных кластера, минимизируя количество разрываемых связей (решая задачу минимального разреза графа). Этот подход, известный как спектральная кластеризация, применяется в машинном обучении для сегментации изображений, анализа социальных групп и выявления аномалий в поведении сложных многокомпонентных систем.