«А лохматость у меня повысилась.»
Итак, у нас на руках есть граф. Часто анализ графа сводят к его визуализации, поскольку «глаз — лучший инструмент». Не отрицая полезности вывода графа как картинки, отметим все же, что не все свойства графа можно увидеть. Некоторые надо считать.
Можно взять готовый пакет для работы с графами (например, NetworkX) и воспользоваться уже реализованными в нем функциями. Некоторые параметры графов имеют исключительно комбинаторный характер, и поэтому не подходят для графов с дробными значениями связей. Более универсальными характеристиками являются те, которые имеют метрическую основу. Далее мы приведем несколько таких параметров, способы их расчета и примеры использования.
Параметр графа — это функция, которая возвращает действительное число. Данная функция может зависеть от аргументов. Количество аргументов функции называется арностью. Соответственно, параметры графа тоже характеризуются арностью (или рангом). В качестве аргументов выступают вершины графа.
Параметры 0-й арности характеризуют сам граф в целом, часто такие параметры называют инвариантами. Существуют инварианты, которые позволяют сравнивать между собой разные графы независимо от количества их вершин.
Параметры 1-й арности (1-го ранга, одинарные) характеризуют вершины графа. Наиболее известным из них является степень вершины — суммарное количество ее связей (в направленных графах входящие и исходящие степени будут разными). Другой известной характеристикой вершин является центральность, причем существуют разные центральности. Центральности можно считать разновидностью степеней вершин, адаптированных для оценки центра/периферии графа. Если у вас есть граф сотрудников вашей компании, то ключевые сотрудники скорее всего будут иметь наибольшее значение центральности.
Бинарные параметры зависят от двух вершин. Связь между вершинами — это бинарный параметр графа. На основе матрицы смежности можно сформировать пары вершин с наибольшей связью — это интересный параметр.
Ну и так далее. Можно рассчитать для графа и тернарные характеристики (3-го ранга), значение которых зависит от трех вершин.
Максимальная арность параметров равна количеству вершин графа. Но когда арность превышает половину от общего количества вершин вступает в силу принцип двойственности. Пусть граф имеет вершин. Тогда дополнительной арностью для параметра -ой арности является -я арность. Поскольку вместо того, чтоб указывать, какие аргументы (вершины графа) используются для получения значения параметра, можно указать те, которые не используются. Это и порождает дополнительную арность.
Если параметр имеет максимальную арность (используются все вершины графа), то это эквивалентно дополнительной 0-й арности. Такой параметр характеризует весь граф целиком (а не подмножество его вершин). Если арность параметра на 1 меньше максимальной , то дополнительная арность равна 1. Такой параметр можно рассматривать как свойство вершин. Однако надо иметь в виду, что смысл значения параметра при этом меняется на противоположный. Например, связность всех вершин графа, кроме одной, можно трактовать как несвязность данной вершины.
Рассматриваем ненаправленные графы, величина связей между вершинами которых может быть произвольным действительным числом (обычно положительным). Метрические параметры графа характеризуют либо некую близость, либо дальность вершин графа. Считаем, что связи графа заданы матрицей смежности, которую обозначим как .
Величина близости связана со степенью связи вершин, — чем более вершины связаны, тем они ближе. Количественную оценку степени связи множества вершин назовем связностью. Данный параметр может иметь арность от 2 до . Связность двух вершин — это величина связи между ними, задается его матрицей смежности графа. Связность 3-х вершин можно рассчитать на основе 2-связности:
Связность всех вершин графа называется его остовным числом . Комбинаторная интерпретация остовного числа — это количество остовных деревьев, которые можно построить на связях графа. В соответствии с матричной теоремой о деревьях остовное число можно рассчитать как определитель минора лапласиана графа. Если с какой-либо вершиной графа нет связи (это означает наличие в графе нескольких компонент), то остовное число графа (его общая связность) равно нулю.
В соответствии с принципом двойственности дополнительная арность остовного числа графа равна нулю, поэтому остовное число можно считать характеристикой всего графа.
Отсюда также следует, что связность подмножества вершин графа равна остовному числу подграфа, построенного на данном подмножестве вершин. Например, приведенная выше формула для 3-х вершин — это явное выражение остовного числа графа из 3-х вершин.
Наконец отметим также, что остовное число можно связать обратно пропорционально квадрату объема симплекса, построенного на вершинах графа. Чем больше связность — тем меньше объем:
Здесь — мерность пространства графа из вершин.
Дальность (расстояние, дистанция) является обратным понятием близости, но это не просто обратная величина связности. Как уже отмечалось в предыдущей статье, между любыми вершинами существует резистивная дистанция, даже если эти вершины напрямую не связаны.
Резистивная метрика может иметь различную арность — от двух до максимальной. Резистивная дистанция (эффективное сопротивление) является бинарным параметром, поскольку для определения значения резистивной дистанции надо задать две вершины. Значение резистивной дистанции эквивалентно квадрату линейного расстояния (квадрансу). Но помимо геометрической резистивная дистанция имеет также комбинаторную трактовку. Ее значение в простых графах отражает относительное изменение остовного числа графа при добавлении (или удалении) связи между данными вершинами:
Значение числителя равно детерминанту минора лапласиана, из которого удалены вершины (двойственность — удаляем две вершины из множества, а не извлекаем).
Резистивной метрике 3-ей арности (тристанция?) соответствует квадрат двойной площади треугольника: . Для ее получения можно детерминант минора лапласиана, из которого удалены три вершины, разделить на остовное число графа. Также как и для 3-связности существует выражение 3-дальности через резистивные дистанции. Приведем для справки:
Поскольку граф можно трактовать как базис пространства, то геометрические характеристики данного пространства можно использовать для определения параметров графа. Известно, что вокруг невырожденного симплекса произвольного порядка всегда можно описать сферу. Такая сфера характеризуется: 1) положением центра и 2) радиусом. Положение центра задается барицентрическими координатами относительно вершин симплекса, квадрат радиуса — числом.
Параметры сферы имеют помимо геометрической комбинаторную интерпретацию. Более подробно рассмотрены здесь.
Обратимся к одинарным (унарным) параметрам, — то есть к характеристикам вершин.
Как уже отмечалось, любой граф можно разложить на сумму деревьев (остовов). В каждом таком дереве вершина исходного графа может иметь различную степень. Тогда можно сложить степени вершин по всем деревьям графа и получить среднюю остовную степень вершин, обозначим ее как (обычные степени вершин графа принято обозначать через , degree). Оказывается, что координаты центра описанной сферы и средняя остовная степень связаны между собой соотношением:
Данное выражение связывает геометрию с комбинаторикой. Видим, что координаты центра описанной сферы можно получить, просто считая степени вершин деревьев, на которые можно разложить граф.
С точки зрения прикладного анализа удобнее оперировать с центральностями вершин. Значения центральности можно трактовать как близость (или дальность) положения вершины относительно некоего центра графа. Центральность самых удаленных вершин должна быть нулевой. Из этого требования, а также из свойства барицентрических координат вытекает следующее определение центральности (для того, чтобы отличать ее от других, назовем ее остовной);
Достоинство остовной центральности в том, что ее можно рассчитать на основе стандартных матричных операций. Приведем для справки соответствующие формулы:
Здесь — матрица смежности графа, — матрица резистивных дистанций (сопротивлений), — обозначает адамарово (поточечное) произведение матриц.
На основе остовной центральности можно выделить центральные вершины графа и его периферию. Если значение центральности вершины больше 1, то она относится к центру. Если меньше — к периферии.
К сожалению в пакете networkX расчет остовной центральности не реализован, но зато в нем есть несколько других центральностей, которые тоже можно использовать.
На рисунке показаны для сравнения две центральности для графа из Википедии. Слева a) — остовная центральность вершин, справа b) — betweenness centrality. Значения приведены к целым числам.
Целые значения остовной центральности интерпретируются просто — это разность (превышение) между суммой степеней вершины по всем остовам графа и общим количеством остовов. Рассмотрим, например, фиолетовую вершину. Поскольку она конечная, то ее степень во всех остовах равна 1. Поэтому общая сумма ее степеней совпадает с количеством остовов, в итоге получаем для нее нулевую центральность.
Немного странно, что алгоритм betweenness centrality дает также нулевое значение для красной вершины. Визуально очевидно, что положения красной и фиолетовой вершин совсем не равноправны.
Размер описанной сферы характеризует граф в целом. Поскольку по определению все вершины графа принадлежат сфере, то ее диаметр задает максимально возможное значение резистивных дистанций (а, значит, и эффективных сопротивлений) между вершинами графа. Величину квадрата радиуса сферы назовем резистивной нормой графа .
В отличие от остовного числа, которое имеет мультипликативный характер, норма графов аддитивна. Это проявляется, например, в операции сочленения графов (соединение в вершине). Норма результирующего графа равна сумме исходных графов, а остовное число — произведению.
Поскольку норма любого графа независимо от его порядка всегда является «квадратом расстояния», то нормы можно использовать чтобы сравнивать между собой графы разного порядка.
Однако в качестве топологической характеристики значение резистивной нормы графа не подходит. При увеличении величины связей в k раз его резистивная норма уменьшается во столько же раз, хотя очевидно, что топология (структура связей) при этом не изменилась.
В полном графе несмещенные индексы разреженности и компактности равны 1 — это предельные значения данных параметров. Из этого следует, что плотность (компактность) всех остальных графов будет меньше, чем плотность полного графа, а разреженность соответственно больше.
Например, несмещенная оценка плотности приведенного выше графа из Википедии равна 0.495. Данный граф примерно в два раза менее плотен, чем полный граф.
Особняком стоит анализ графов на основе спектров его матриц. В качестве матрицы обычно используется либо матрица смежности, либо лапласиан. Среди прочего спектр лапласиана используют для поиска кластеров вершин в графе, то есть выделения обособленных (слабо связанных) групп — этому посвящено большое количество работ.
Здесь нет возможности сильно вдаваться в подробности (да тут и не подходящее место для этого). Но считаем нужным отметить следующее для тех, кто будет использовать спектральный анализ для своих графов.
Обычно для поиска кластеров берут слой спектра лапласиана графа с наименьшим весом (наименьшим собственным значением) и формируют кластеры на основе близости значений соответствующего собственного вектора (вектор Фидлера). Но на практике (для графов с различными по величине связями) значение минимального собственного числа будет плохо обусловленным, — зависит от погрешностей данных. Да и вообще большинство слоев спектра обычно «плохо звенит», — направление таких слоев сформировано относительно небольшим числом вершин графа (это те, компоненты которых отличны от нуля в данном слое).
Поэтому для кластеризации надо сначала определить подходящие слои спектра. Такими слоями являются слои с наибольшей поляризацией вершин. Компоненты собственных векторов таких слоев должны быть заметно отличны от нуля (по абсолютному значению). Сами вершины делятся на кластеры по знаку компоненты. Соответственно для одного слоя получим два возможных кластера вершин. Если слоев два, то можно найти 4 кластера и т.д. При этом следует учитывать величину собственного числа слоя — оно определяет его мощность.
Чтобы разбавить унылую теорию веселой практикой, мы опубликовали сервис, который выполняет экспресс-анализ связности букв русского языка на основе заданного текста. Буквы связаны между собой неявным образом посредством слов, которые они образуют. На основании текстового файла сервис строит граф связности букв и выводить некоторые параметры из тех, которые описаны выше.
Используя данный сервис, можно выяснить, как меняются связи букв со временем. Мы сравнили графы букв, полученные по двум сказкам Пушкина «Сказка о мертвой царевне...» и «Сказка о царе Салтане», и более современное произведение Леонида Филатова «Сказ про Федота-стрельца».
Полученные центральности букв близки к общей частотности букв русского языка. Но заметны некоторые исторические особенности. Например, видно, что буква «ф» во времена Пушкина только народилась, — в «Сказке о мертвой царевне...» она вообще не встречается, а в «Сказке о царе Салтане» — только в единственном слове «флот».
Интересно, что значения центральностей букв связаны с их делением на кластеры (группы). Кластерный анализ текстов сказок (на основе спектра лапласиана графа букв) показал, что группы букв просто разбивают множество букв по степени их центральности. При этом существуют три основные группы (слоя) (показаны слои «по Филатову»):
Основная: [о, е, а, т, н, р, и, с, л, д*]
Промежуточная: [у, ь, к, в*, м, п, б, я]
Редкая: [ы, з, г, й, ч, ш, х, ж, ю, ц, ф, щ, э, ъ]
Внутри группы буквы отсортированы по степени убывания остовной центральности. Буквы основной группы можно отнести к центру (их центральности > 1), а промежуточной и редкой (центральность < 0.5) — к периферии.
Буквы «д» и «в» — беглые. За прошедшее время они поменялись местами. Роль буквы «д» повысилась, она перешла из промежуточного слоя в основной. А значимость «в» наоборот — понизилась. У Пушкина она была в основной группе, у Филатова — в промежуточной.
Наиболее связанные пары букв тоже известны. Вот первая десятка пар по степени убывания связи:
[е, н], [о, т], [е, т], [а, н], [а, к], [о, н], [а, р], [о, р], [а, л], [о, д]
Напомним, что граф ненаправленный, поэтому положение буквы внутри пары не имеет значения: [е, н] = [н, е]. Связность пары [о, д] в два раза меньше связности [е, н].
Отметим, что одна буква в парах данного списка всегда гласная, а другая согласная. Первая пара с двумя гласными находится на 11-м месте — это пара [е, о], а первая пара с двумя согласными — на 25-м: [с, т]. Отсюда ясно, что триплеты (три буквы) максимальной связности (см. формулу (1)) будут включать в себя буквы «е» и «о». Вот первые триплеты максимальной связности:
[ето], [оне], [неа], [ато], [нет], [рот], [сто], [она], [тон], [ора], [ока], [вот], [сет],…
От связности 3-й арности перейдем к 0-й и рассмотрим значение плотности/разреженности графа букв. Напомним, что минимальную разреженность (максимальную плотность) имеет полный граф. Все остальные графы намного более разрежены. Анализ показывает, что в современной сказке о Федоте разреженность равна примерно 39, в сказке о Салтане — 112, а в сказке о мертвой царевне — 222. Скорее всего более высокая плотность букв в сказке о Федоте объясняется ее большим объемом, то есть там просто больше разных слов и соответственно больше связей между разными буквами, которых нет у Пушкина.
Конечно, этот экспресс-анализ не претендует на широкие обобщения, поскольку выполнен на базе всего лишь трех текстов. Если взять более широкий корпус, то выводы могут быть другими.
Связность букв — лишь пример возможного анализа графа. Вы можете провести подобный анализ для своей компании на основании собственных данных.
Благодарю Сергея Аверкиева (averkij) за помощь в подготовке и публикации сервиса.
Итак, у нас на руках есть граф. Часто анализ графа сводят к его визуализации, поскольку «глаз — лучший инструмент». Не отрицая полезности вывода графа как картинки, отметим все же, что не все свойства графа можно увидеть. Некоторые надо считать.
Можно взять готовый пакет для работы с графами (например, NetworkX) и воспользоваться уже реализованными в нем функциями. Некоторые параметры графов имеют исключительно комбинаторный характер, и поэтому не подходят для графов с дробными значениями связей. Более универсальными характеристиками являются те, которые имеют метрическую основу. Далее мы приведем несколько таких параметров, способы их расчета и примеры использования.
Общие замечания
Арность
Параметр графа — это функция, которая возвращает действительное число. Данная функция может зависеть от аргументов. Количество аргументов функции называется арностью. Соответственно, параметры графа тоже характеризуются арностью (или рангом). В качестве аргументов выступают вершины графа.
Параметры 0-й арности характеризуют сам граф в целом, часто такие параметры называют инвариантами. Существуют инварианты, которые позволяют сравнивать между собой разные графы независимо от количества их вершин.
Параметры 1-й арности (1-го ранга, одинарные) характеризуют вершины графа. Наиболее известным из них является степень вершины — суммарное количество ее связей (в направленных графах входящие и исходящие степени будут разными). Другой известной характеристикой вершин является центральность, причем существуют разные центральности. Центральности можно считать разновидностью степеней вершин, адаптированных для оценки центра/периферии графа. Если у вас есть граф сотрудников вашей компании, то ключевые сотрудники скорее всего будут иметь наибольшее значение центральности.
Бинарные параметры зависят от двух вершин. Связь между вершинами — это бинарный параметр графа. На основе матрицы смежности можно сформировать пары вершин с наибольшей связью — это интересный параметр.
Ну и так далее. Можно рассчитать для графа и тернарные характеристики (3-го ранга), значение которых зависит от трех вершин.
Двойственность
Максимальная арность параметров равна количеству вершин графа. Но когда арность превышает половину от общего количества вершин вступает в силу принцип двойственности. Пусть граф имеет вершин. Тогда дополнительной арностью для параметра -ой арности является -я арность. Поскольку вместо того, чтоб указывать, какие аргументы (вершины графа) используются для получения значения параметра, можно указать те, которые не используются. Это и порождает дополнительную арность.
Если параметр имеет максимальную арность (используются все вершины графа), то это эквивалентно дополнительной 0-й арности. Такой параметр характеризует весь граф целиком (а не подмножество его вершин). Если арность параметра на 1 меньше максимальной , то дополнительная арность равна 1. Такой параметр можно рассматривать как свойство вершин. Однако надо иметь в виду, что смысл значения параметра при этом меняется на противоположный. Например, связность всех вершин графа, кроме одной, можно трактовать как несвязность данной вершины.
Параметры близости и дальности
Рассматриваем ненаправленные графы, величина связей между вершинами которых может быть произвольным действительным числом (обычно положительным). Метрические параметры графа характеризуют либо некую близость, либо дальность вершин графа. Считаем, что связи графа заданы матрицей смежности, которую обозначим как .
Связность и остовное число
Величина близости связана со степенью связи вершин, — чем более вершины связаны, тем они ближе. Количественную оценку степени связи множества вершин назовем связностью. Данный параметр может иметь арность от 2 до . Связность двух вершин — это величина связи между ними, задается его матрицей смежности графа. Связность 3-х вершин можно рассчитать на основе 2-связности:
Связность всех вершин графа называется его остовным числом . Комбинаторная интерпретация остовного числа — это количество остовных деревьев, которые можно построить на связях графа. В соответствии с матричной теоремой о деревьях остовное число можно рассчитать как определитель минора лапласиана графа. Если с какой-либо вершиной графа нет связи (это означает наличие в графе нескольких компонент), то остовное число графа (его общая связность) равно нулю.
В соответствии с принципом двойственности дополнительная арность остовного числа графа равна нулю, поэтому остовное число можно считать характеристикой всего графа.
Отсюда также следует, что связность подмножества вершин графа равна остовному числу подграфа, построенного на данном подмножестве вершин. Например, приведенная выше формула для 3-х вершин — это явное выражение остовного числа графа из 3-х вершин.
Наконец отметим также, что остовное число можно связать обратно пропорционально квадрату объема симплекса, построенного на вершинах графа. Чем больше связность — тем меньше объем:
Здесь — мерность пространства графа из вершин.
Резистивная метрика
Дальность (расстояние, дистанция) является обратным понятием близости, но это не просто обратная величина связности. Как уже отмечалось в предыдущей статье, между любыми вершинами существует резистивная дистанция, даже если эти вершины напрямую не связаны.
Способ расчета матрицы резистивных дистанций
Определим матричное преобразование дистанции над произвольной матрицей как
Матрица резистивных дистанций может быть получена несколькими способами.
1) Можно использовать псевдообращение лапласиана графа и получить матрицу Грина: , после чего преобразование дистанции над матрицей Грина даст резистивную матрицу: . Минус данного способа в необходимости использовании алгоритма псевдообращения (поскольку лапласиан — вырожденная матрица).
2) Можно использовать обращение минора лапласиана и получить фундаментальную матрицу: . Преобразование дистанции над мажором фундаментальной матрицы также даст резистивную матрицу: . Мажор здесь означает добавление элемента (который удалили для получения минора лапласиана) в базисное множество фундаментальной матрицы. Плюс данного способа — в использовании обычного матричного обращения.
Матрица резистивных дистанций может быть получена несколькими способами.
1) Можно использовать псевдообращение лапласиана графа и получить матрицу Грина: , после чего преобразование дистанции над матрицей Грина даст резистивную матрицу: . Минус данного способа в необходимости использовании алгоритма псевдообращения (поскольку лапласиан — вырожденная матрица).
2) Можно использовать обращение минора лапласиана и получить фундаментальную матрицу: . Преобразование дистанции над мажором фундаментальной матрицы также даст резистивную матрицу: . Мажор здесь означает добавление элемента (который удалили для получения минора лапласиана) в базисное множество фундаментальной матрицы. Плюс данного способа — в использовании обычного матричного обращения.
Резистивная метрика может иметь различную арность — от двух до максимальной. Резистивная дистанция (эффективное сопротивление) является бинарным параметром, поскольку для определения значения резистивной дистанции надо задать две вершины. Значение резистивной дистанции эквивалентно квадрату линейного расстояния (квадрансу). Но помимо геометрической резистивная дистанция имеет также комбинаторную трактовку. Ее значение в простых графах отражает относительное изменение остовного числа графа при добавлении (или удалении) связи между данными вершинами:
Значение числителя равно детерминанту минора лапласиана, из которого удалены вершины (двойственность — удаляем две вершины из множества, а не извлекаем).
Резистивной метрике 3-ей арности (тристанция?) соответствует квадрат двойной площади треугольника: . Для ее получения можно детерминант минора лапласиана, из которого удалены три вершины, разделить на остовное число графа. Также как и для 3-связности существует выражение 3-дальности через резистивные дистанции. Приведем для справки:
Параметры описанной сферы
Поскольку граф можно трактовать как базис пространства, то геометрические характеристики данного пространства можно использовать для определения параметров графа. Известно, что вокруг невырожденного симплекса произвольного порядка всегда можно описать сферу. Такая сфера характеризуется: 1) положением центра и 2) радиусом. Положение центра задается барицентрическими координатами относительно вершин симплекса, квадрат радиуса — числом.
Параметры сферы имеют помимо геометрической комбинаторную интерпретацию. Более подробно рассмотрены здесь.
Остовная степень и центральность
Обратимся к одинарным (унарным) параметрам, — то есть к характеристикам вершин.
Как уже отмечалось, любой граф можно разложить на сумму деревьев (остовов). В каждом таком дереве вершина исходного графа может иметь различную степень. Тогда можно сложить степени вершин по всем деревьям графа и получить среднюю остовную степень вершин, обозначим ее как (обычные степени вершин графа принято обозначать через , degree). Оказывается, что координаты центра описанной сферы и средняя остовная степень связаны между собой соотношением:
Данное выражение связывает геометрию с комбинаторикой. Видим, что координаты центра описанной сферы можно получить, просто считая степени вершин деревьев, на которые можно разложить граф.
С точки зрения прикладного анализа удобнее оперировать с центральностями вершин. Значения центральности можно трактовать как близость (или дальность) положения вершины относительно некоего центра графа. Центральность самых удаленных вершин должна быть нулевой. Из этого требования, а также из свойства барицентрических координат вытекает следующее определение центральности (для того, чтобы отличать ее от других, назовем ее остовной);
Достоинство остовной центральности в том, что ее можно рассчитать на основе стандартных матричных операций. Приведем для справки соответствующие формулы:
Здесь — матрица смежности графа, — матрица резистивных дистанций (сопротивлений), — обозначает адамарово (поточечное) произведение матриц.
На основе остовной центральности можно выделить центральные вершины графа и его периферию. Если значение центральности вершины больше 1, то она относится к центру. Если меньше — к периферии.
К сожалению в пакете networkX расчет остовной центральности не реализован, но зато в нем есть несколько других центральностей, которые тоже можно использовать.
На рисунке показаны для сравнения две центральности для графа из Википедии. Слева a) — остовная центральность вершин, справа b) — betweenness centrality. Значения приведены к целым числам.
Целые значения остовной центральности интерпретируются просто — это разность (превышение) между суммой степеней вершины по всем остовам графа и общим количеством остовов. Рассмотрим, например, фиолетовую вершину. Поскольку она конечная, то ее степень во всех остовах равна 1. Поэтому общая сумма ее степеней совпадает с количеством остовов, в итоге получаем для нее нулевую центральность.
Немного странно, что алгоритм betweenness centrality дает также нулевое значение для красной вершины. Визуально очевидно, что положения красной и фиолетовой вершин совсем не равноправны.
Норма, связность и плотность графа
Размер описанной сферы характеризует граф в целом. Поскольку по определению все вершины графа принадлежат сфере, то ее диаметр задает максимально возможное значение резистивных дистанций (а, значит, и эффективных сопротивлений) между вершинами графа. Величину квадрата радиуса сферы назовем резистивной нормой графа .
В отличие от остовного числа, которое имеет мультипликативный характер, норма графов аддитивна. Это проявляется, например, в операции сочленения графов (соединение в вершине). Норма результирующего графа равна сумме исходных графов, а остовное число — произведению.
Поскольку норма любого графа независимо от его порядка всегда является «квадратом расстояния», то нормы можно использовать чтобы сравнивать между собой графы разного порядка.
Однако в качестве топологической характеристики значение резистивной нормы графа не подходит. При увеличении величины связей в k раз его резистивная норма уменьшается во столько же раз, хотя очевидно, что топология (структура связей) при этом не изменилась.
Конструируем параметры плотности и разреженности графа
Для того, чтобы на основании нормы определить топологическую характеристику, необходимо умножить ее на величину какой-либо связности графа. В качестве такой связности подойдет средняя степень его вершин .
Умножая резистивную норму на связность графа получаем некий безразмерный параметр, который назовем индексом разреженности :
Величину, обратную данному индексу, назовем индексом компактности (плотности):
Но это еще не все. Хорошо бы привязать введенные нами индексы к какому-то стандарту, например, к полному графу. Тогда мы бы могли сказать, насколько отличается плотность (или разреженность) от полного графа. Для этого введем понятие несмещенных оценок. Несмещенная оценка получается умножением инварианта на фактор (подобный трюк есть в статистике при определении дисперсии). Несмещенные оценки пометим звездочкой:
Тогда несмещенная оценка разреженности получается из обычной умножением на квадрат фактора — следствие определения (6):
Наконец-то мы добрались до финального выражения.
Умножая резистивную норму на связность графа получаем некий безразмерный параметр, который назовем индексом разреженности :
Величину, обратную данному индексу, назовем индексом компактности (плотности):
Но это еще не все. Хорошо бы привязать введенные нами индексы к какому-то стандарту, например, к полному графу. Тогда мы бы могли сказать, насколько отличается плотность (или разреженность) от полного графа. Для этого введем понятие несмещенных оценок. Несмещенная оценка получается умножением инварианта на фактор (подобный трюк есть в статистике при определении дисперсии). Несмещенные оценки пометим звездочкой:
Тогда несмещенная оценка разреженности получается из обычной умножением на квадрат фактора — следствие определения (6):
Наконец-то мы добрались до финального выражения.
В полном графе несмещенные индексы разреженности и компактности равны 1 — это предельные значения данных параметров. Из этого следует, что плотность (компактность) всех остальных графов будет меньше, чем плотность полного графа, а разреженность соответственно больше.
Например, несмещенная оценка плотности приведенного выше графа из Википедии равна 0.495. Данный граф примерно в два раза менее плотен, чем полный граф.
Спектральный и кластерный анализ
Особняком стоит анализ графов на основе спектров его матриц. В качестве матрицы обычно используется либо матрица смежности, либо лапласиан. Среди прочего спектр лапласиана используют для поиска кластеров вершин в графе, то есть выделения обособленных (слабо связанных) групп — этому посвящено большое количество работ.
Здесь нет возможности сильно вдаваться в подробности (да тут и не подходящее место для этого). Но считаем нужным отметить следующее для тех, кто будет использовать спектральный анализ для своих графов.
Обычно для поиска кластеров берут слой спектра лапласиана графа с наименьшим весом (наименьшим собственным значением) и формируют кластеры на основе близости значений соответствующего собственного вектора (вектор Фидлера). Но на практике (для графов с различными по величине связями) значение минимального собственного числа будет плохо обусловленным, — зависит от погрешностей данных. Да и вообще большинство слоев спектра обычно «плохо звенит», — направление таких слоев сформировано относительно небольшим числом вершин графа (это те, компоненты которых отличны от нуля в данном слое).
Поэтому для кластеризации надо сначала определить подходящие слои спектра. Такими слоями являются слои с наибольшей поляризацией вершин. Компоненты собственных векторов таких слоев должны быть заметно отличны от нуля (по абсолютному значению). Сами вершины делятся на кластеры по знаку компоненты. Соответственно для одного слоя получим два возможных кластера вершин. Если слоев два, то можно найти 4 кластера и т.д. При этом следует учитывать величину собственного числа слоя — оно определяет его мощность.
Сервис для анализа связности букв на основе корпуса слов
Чтобы разбавить унылую теорию веселой практикой, мы опубликовали сервис, который выполняет экспресс-анализ связности букв русского языка на основе заданного текста. Буквы связаны между собой неявным образом посредством слов, которые они образуют. На основании текстового файла сервис строит граф связности букв и выводить некоторые параметры из тех, которые описаны выше.
Используя данный сервис, можно выяснить, как меняются связи букв со временем. Мы сравнили графы букв, полученные по двум сказкам Пушкина «Сказка о мертвой царевне...» и «Сказка о царе Салтане», и более современное произведение Леонида Филатова «Сказ про Федота-стрельца».
Полученные центральности букв близки к общей частотности букв русского языка. Но заметны некоторые исторические особенности. Например, видно, что буква «ф» во времена Пушкина только народилась, — в «Сказке о мертвой царевне...» она вообще не встречается, а в «Сказке о царе Салтане» — только в единственном слове «флот».
Интересно, что значения центральностей букв связаны с их делением на кластеры (группы). Кластерный анализ текстов сказок (на основе спектра лапласиана графа букв) показал, что группы букв просто разбивают множество букв по степени их центральности. При этом существуют три основные группы (слоя) (показаны слои «по Филатову»):
Основная: [о, е, а, т, н, р, и, с, л, д*]
Промежуточная: [у, ь, к, в*, м, п, б, я]
Редкая: [ы, з, г, й, ч, ш, х, ж, ю, ц, ф, щ, э, ъ]
Внутри группы буквы отсортированы по степени убывания остовной центральности. Буквы основной группы можно отнести к центру (их центральности > 1), а промежуточной и редкой (центральность < 0.5) — к периферии.
Буквы «д» и «в» — беглые. За прошедшее время они поменялись местами. Роль буквы «д» повысилась, она перешла из промежуточного слоя в основной. А значимость «в» наоборот — понизилась. У Пушкина она была в основной группе, у Филатова — в промежуточной.
Наиболее связанные пары букв тоже известны. Вот первая десятка пар по степени убывания связи:
[е, н], [о, т], [е, т], [а, н], [а, к], [о, н], [а, р], [о, р], [а, л], [о, д]
Напомним, что граф ненаправленный, поэтому положение буквы внутри пары не имеет значения: [е, н] = [н, е]. Связность пары [о, д] в два раза меньше связности [е, н].
Отметим, что одна буква в парах данного списка всегда гласная, а другая согласная. Первая пара с двумя гласными находится на 11-м месте — это пара [е, о], а первая пара с двумя согласными — на 25-м: [с, т]. Отсюда ясно, что триплеты (три буквы) максимальной связности (см. формулу (1)) будут включать в себя буквы «е» и «о». Вот первые триплеты максимальной связности:
[ето], [оне], [неа], [ато], [нет], [рот], [сто], [она], [тон], [ора], [ока], [вот], [сет],…
От связности 3-й арности перейдем к 0-й и рассмотрим значение плотности/разреженности графа букв. Напомним, что минимальную разреженность (максимальную плотность) имеет полный граф. Все остальные графы намного более разрежены. Анализ показывает, что в современной сказке о Федоте разреженность равна примерно 39, в сказке о Салтане — 112, а в сказке о мертвой царевне — 222. Скорее всего более высокая плотность букв в сказке о Федоте объясняется ее большим объемом, то есть там просто больше разных слов и соответственно больше связей между разными буквами, которых нет у Пушкина.
Конечно, этот экспресс-анализ не претендует на широкие обобщения, поскольку выполнен на базе всего лишь трех текстов. Если взять более широкий корпус, то выводы могут быть другими.
Связность букв — лишь пример возможного анализа графа. Вы можете провести подобный анализ для своей компании на основании собственных данных.
Благодарю Сергея Аверкиева (averkij) за помощь в подготовке и публикации сервиса.
