-  Упорядочение элементов графа по мере их появления в сюжете песни.

-  Группировка вершин и ребер графа согласно структуре мотивов песни и их функциональному весу.

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

При модификации этого метода будем использовать следующие закономерности:

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

,

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

,

где – расстояние между вершинами и , а – коэффициент жесткости (упругости) пружины.

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

НЕ нашли? Не то? Что вы ищете?

,

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

.

3. Чтобы учитывать порядок появления связей в сюжете песни, для каждого ребра введем дополнительную силу . Эта сила будет стремиться расположить ребра графа как можно ближе к установленным заранее упорядоченным точкам . Точки следует расположить последовательно на одинаковом расстоянии друг от друга по окружности (или полуокружности) с центром в середине экрана. Радиус окружности подбирается таким образом, чтобы полученный граф не выходил за границы экранной области.

Тогда значение для -й координаты силы найдем следующим образом:

,

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

В результате, общая сила , приложенная к вершине , будет находиться как сумма трех сил:

.

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

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

Для того чтобы сравнить матрицы смежности графов и , вводится функционал :

,

где и – элементы матрицы и соответственно. Задача аппроксимации графов состоит в нахождении такого графа и такого соответствия , при которых достигает минимума.

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

.

В противном случае будет равняться нулю. В этом случае можно определить второй функционал «порядка» :

,

где и – элементы матрицы и соответственно.

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

,

где веса и подбираются в зависимости от характера исследования.

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

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3