Экспресс-Анализ Метрических Параметров Графиков

Эта функция может зависеть от аргументов.

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

Соответственно, параметры графа также характеризуются арностью (или рангом).

Аргументы — это вершины графа.

Параметры 0-й арности характеризуют сам граф в целом; такие параметры часто называют инварианты .

Существуют инварианты, позволяющие сравнивать разные графы друг с другом независимо от количества их вершин.

Параметры 1-й арности (1-го ранга, одиночные) характеризуют вершины графа.

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

Другая известная характеристика вершин — центральность , и существуют разные центральности.

Центральности можно рассматривать как разновидность степеней вершин, адаптированную для оценки центра/периферии графа.

Если у вас есть график сотрудников вашей компании, то ключевые сотрудники, скорее всего, будут иметь наивысшее значение центральности.

Бинарные параметры зависят от двух вершин.

Связь между вершинами является двоичным параметром графа.

На основе матрицы смежности можно формировать пары вершин с наибольшей связностью — это интересный параметр.

И так далее.

Также можно рассчитать троичные характеристики (ранг 3) графа, значение которых зависит от трех вершин.

Но когда арность превышает половину общего числа вершин, это вступает в силу.

принцип двойственности .

Пусть граф имеет



пики Тогда дополнительная арность для параметра



-арность - это



-Я Арити.

Потому что вместо указания того, какие аргументы (вершины графа) используются для получения значения параметра, можно указать те, которые не используются.

Это порождает дополнительную арность.

Если параметр имеет максимальную арность (используются все вершины графа), то это эквивалентно дополнительной 0-й арности.

Этот параметр характеризует весь граф (а не подмножество его вершин).

Если арность параметра на 1 меньше максимальной



, то дополнительная арность равна 1. Этот параметр можно рассматривать как свойство вершин.

Однако необходимо учитывать, что смысл значения параметра обратный.

Например, связность всех вершин графа, кроме одной, можно интерпретировать как бессвязность этой вершины.

Метрические параметры графа характеризуют либо определенную близость, либо расстояние вершин графа.

Будем считать, что связи графа задаются матрицей смежности, которую обозначим как



.

Количественную оценку степени связности множества вершин назовем согласованность .

Этот параметр может иметь арность от 2 до



.

Связность двух вершин — это величина связи между ними, определяемая матрицей смежности графа.

Связность с 3 вершинами можно рассчитать на основе связности с 2 вершинами:



Связность всего



вершин графа называется его основной номер



.

Комбинаторная интерпретация остовного числа — это количество остовных деревьев, которые можно построить из связей графа.

В соответствии с теорема о матричном дереве остовное число можно рассчитать как определитель младшего лапласиана графа.

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

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

Отсюда также следует, что связность подмножества вершин графа равна остовному числу подграфа, построенного на данном подмножестве вершин.

Например, приведенная выше формула для трех вершин является явным выражением остовного числа графа с тремя вершинами.

Наконец, отметим также, что число ядер можно связать обратно пропорциональна квадрату объема симплекса, построенного на вершинах графа.

Как уже отмечалось в предыдущая статья , между любыми вершинами существует резистивное расстояние, даже если эти вершины не связаны напрямую.

Метод расчета матрицы резистивных расстояний Давайте определим матрицу преобразование расстояния над произвольной матрицей



Как



Резистивная матрица расстояний



можно получить несколькими способами.

1) Можно использовать псевдообращение лапласиана графика и получить матрицу Грина:



, после чего преобразование расстояния по матрице Грина даст резистивную матрицу:



.

Недостатком этого метода является необходимость использования алгоритма псевдообращения (поскольку лапласиан является сингулярной матрицей).

2) Вы можете использовать обращение младшего лапласиана и получить фундаментальную матрицу:



.

Преобразование расстояния по основной части основной матрицы также даст резистивную матрицу:



.

Мажор здесь означает добавление элемента (который был удален, чтобы получить минор лапласиана) к базисному набору фундаментальной матрицы.

Преимуществом этого метода является использование традиционной инверсии матрицы.

Резистивная метрика может иметь разную арность – от двух до максимальной.

Резистивное расстояние (эффективное сопротивление) является двоичным параметром, так как для определения значения резистивного расстояния необходимо указать две вершины.

Значение резистивного расстояния эквивалентно квадрату линейного расстояния (квадранов).

Но помимо геометрического резистивного расстояния оно имеет еще и комбинаторную интерпретацию.

Его значение в простых графиках отражает относительное изменение числа ядер графа.

при добавлении (или удалении) связи между этими вершинами:



Значение числителя



равен определителю минора лапласиан , из которого удалены вершины



(двойственность – мы удаляем две вершины из множества, а не извлекаем их).

Резистивная метрика 3-й арности (тристанции?) соответствует квадрату двойной площади треугольника:



.

Чтобы его получить, можно разделить определитель минорного лапласиана, из которого удалены три вершины, на остовное число графа.

Как и в случае с 3-связностью, для 3-диапазона существует выражение в терминах резистивных расстояний.

Известно, что сферу всегда можно описать вокруг невырожденного симплекса произвольного порядка.

Такая сфера характеризуется: 1) положением центра и 2) радиусом.

Положение центра задается барицентрическими координатами.

относительно вершин симплекса радиус в квадрате



- по номеру.

Параметры сферы имеют, помимо геометрической, комбинаторную интерпретацию.

Обсуждается более подробно Здесь .

Как уже отмечалось, любой граф можно разложить на сумму деревьев (скелетов).

В каждом таком дереве вершина исходного графа может иметь разную степень.

Затем мы можем сложить степени вершин по всем деревьям графа и получить среднюю степень охвата вершин, обозначим ее как



(обычные степени вершин графа обычно обозначаются через



, степень).

Оказывается, координаты центра описанной сферы



и средняя степень ядра связаны соотношением:



Это выражение связывает геометрию с комбинаторикой.

Мы видим, что координаты центра описанной сферы можно получить, просто посчитав степени вершин деревьев, на которые можно разложить граф.

С точки зрения прикладного анализа удобнее оперировать центральностями вершин.

Значения центральности можно интерпретировать как близость (или расстояние) положения вершины относительно определенного центра графа.

Центральность крайних вершин должна быть равна нулю.

Из этого требования, а также из свойства барицентрических координат



следует следующее определение центральности (чтобы отличить его от других, назовем его основной );



Преимущество охватывающей центральности состоит в том, что ее можно вычислить с помощью стандартных матричных операций.

Для справки приведем соответствующие формулы:



Здесь



— матрица смежности графов,



— матрица резистивных расстояний (сопротивлений),



— обозначает адамарово (точечное) произведение матриц.

На основании охватывающей центральности мы можем идентифицировать центральные вершины графа и его периферию.

Если значение центральности вершины больше 1, то она принадлежит центру.

Если меньше – на периферию.

К сожалению, пакет networkX не реализует расчет охватывающей центральности, но в нем есть несколько других центральностей, которые также может быть использован .

На рисунке для сравнения показаны две центральности для графика из Википедии.

Слева а) — охватывающая центральность вершин, справа б) — промежуточная центральность.

Значения преобразуются в целые числа.

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

Рассмотрим, например, фиолетовую вершину.

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

Немного странно, что алгоритм централизации по посредничеству также дает нулевое значение для красной вершины.

Визуально очевидно, что положения красной и фиолетовой вершин совсем не равны.

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

Назовем квадрат радиуса сферы норма резистивного графика



.

В отличие от остовного числа, которое является мультипликативным, норма графов аддитивна.

Это проявляется, например, в операции соединения графов (объединение по вершине).

Норма полученного графа равна сумме исходных графов, а остовное число равно произведению.

Поскольку норма любого графа, независимо от его порядка, всегда равна «квадрату расстояния», нормы можно использовать для сравнения графов разных порядков.

Однако, как топологические характеристики значение резистивной нормы графика не подходит. При увеличении размеров связей в k раз норма ее сопротивления уменьшается во столько же раз, хотя очевидно, что топология (структура связей) не изменилась.

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

В качестве такой связи подойдет средняя степень ее вершин.

.

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



:



Мы называем обратный этому индексу индекс компактности (плотность) :



Но это еще не все.

Было бы неплохо привязать введенные нами индексы к какому-нибудь стандарту, например к полный график .

Тогда мы могли бы сказать, насколько плотность (или разреженность) отличается от полного графика.

Для этого введем понятие несмещенных оценок.

Несмещенная оценка получается умножением инварианта на коэффициент



(похожий прием есть и в статистике при определении дисперсии).

Звездочкой отмечены несмещенные оценки:



Тогда несмещенная оценка разреженности получается из обычной умножением на квадрат множителя – следствие определения (6):



Мы наконец достигли окончательного выражения.

Полный график



несмещенные индексы разреженности и компактности равны 1 — это предельные значения этих параметров.

Из этого следует, что плотность (компактность) всех остальных графов будет меньше плотности полного графа, а разреженность соответственно будет больше.

Например, несмещенная оценка плотности для приведенного выше графика из Википедии составляет 0,495. Этот граф примерно в два раза менее плотен, чем полный граф.

Матрица обычно представляет собой либо матрицу смежности, либо матрицу Лапласа.

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

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

Обычно для поиска кластеров берут слой спектра лапласиана графа с наименьшим весом (наименьшим собственным значением) и формируют кластеры на основе близости значений соответствующего собственного вектора ( Вектор Фидлера ).

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

И вообще, большинство слоев спектра обычно «плохо звенят» — направление таких слоев формируется сравнительно небольшим количеством вершин графа (это те, компоненты которых в данном слое ненулевые).

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

Эти слои являются слоями с наибольшим вершинная поляризация .

Компоненты собственных векторов таких слоев должны заметно отличаться от нуля (по абсолютной величине).

Сами вершины разбиваются на кластеры по знаку компонента.

Соответственно, для одного слоя мы получаем два возможных кластера вершин.

Если слоев два, то можно найти 4 кластера и т. д. При этом следует учитывать значение собственного номера слоя – оно определяет его толщину.

Буквы связаны друг с другом неявно через слова, которые они образуют. На основе текстового файла сервис строит граф связности букв и отображает некоторые описанные выше параметры.

С помощью этого сервиса вы сможете узнать, как меняются связи букв с течением времени.

Мы сравнили буквограммы, полученные из двух сказок Пушкина «Сказка о мертвой царевне.

» и «Сказка о царе Салтане» и более современного произведения Леонида Филатова «Сказка о Федоте-стрельце».

Полученная центральность букв близка к общей центральности.

частоты букв Русский язык.

Но заметны некоторые исторические особенности.

Например, ясно, что буква «ф» еще только зарождалась во времена Пушкина — в «Сказке о мертвой царевне…» она вообще не фигурирует, а в «Сказке о царе Салтане» - только в одном слове «флот».

Интересно, что значения центральности букв связаны с их разделением на кластеры (группы).

Кластерный анализ текстов сказок (на основе спектра лапласиана буквенного графа) показал, что группы букв просто разбивают множество букв по степени их центральности.

При этом выделяют три основные группы (слоя) (показаны слои «по Филатову»): Базовый: [о, е, а, т, н, р, я, с, л, д*] Промежуточный: [y, b, k, v*, m, p, b, i] Редкие: [s, z, g, j, h, w, x, g, yu, c, f, sch, e, b] Внутри группы буквы сортируются по убыванию степени централизации.

Буквы основной группы можно отнести к центральным (их центральность > 1), а также к промежуточным и редким (центральность < 0.5) - to the periphery. Буквы «д» и «в» беглые.

За прошедшее время они поменялись местами.

Роль буквы «д» возросла; он переместился из промежуточного слоя в основной.

Наоборот, значимость «в» снизилась.

У Пушкина она была в основной группе, у Филатова – в промежуточной.

Известны также наиболее родственные пары букв.

Вот первая десятка пар в порядке убывания соединения: [e, n], [o, t], [e, t], [a, n], [a, k], [o, n], [a, p], [o, p], [a , л], [о, д] Напомним, что граф неориентированный, поэтому положение буквы внутри пары не имеет значения: [e, n] = [n, e].

Связь пары [о, d] в два раза меньше связи [e, n].

Обратите внимание, что одна буква в парах этого списка всегда гласная, а другая — согласная.

Первая пара с двумя гласными находится на 11-м месте – это пара [э, о], а первая пара с двумя согласными – на 25-м месте: [с, т].

Отсюда понятно, что тройки (три буквы) максимальной связности (см.

формулу (1)) будут включать в себя буквы «е» и «о».

Вот первые тройки максимальной связности: [это], [один], [неа], [ато], [нет], [рот], [сто], [она], [тон], [ора], [ока], [здесь], [ набор ],… Перейдем от связности 3-й арности к 0-й арности и рассмотрим значение плотности/разреженности буквенного графа.

Напомним, что полный граф имеет минимальную разреженность (максимальную плотность).

Все остальные графики гораздо более разрежены.

Анализ показывает, что в современной сказке о Федоте разреженность составляет примерно 39, в сказке о Салтане - 112, а в сказке о погибшей царевне - 222. Скорее всего, более высокая плотность букв в сказке.

о Федоте объясняется его большим объёмом, то есть просто больше разных слов и, соответственно, больше связей между разными буквами, чего нет у Пушкина.

Конечно, этот экспресс-анализ не претендует на широкие обобщения, поскольку проведен всего на основе трех текстов.

Если взять более широкий корпус, выводы могут быть иными.

Связность букв — это лишь пример возможного анализа графа.

Вы можете провести аналогичный анализ для своей компании на основе собственных данных.

Благодарю Сергея Аверкиева ( аверкий ) за помощь в подготовке и публикации услуга .