ВВЕДЕНИЕ 3
ПОСТАНОВКА ЗАДАЧИ 7
ГЛАВА 1. СТРУКТУРА ДАННЫХ ГРАФА GOOGLE BOOKS 8
1.1. ОПИСАНИЕ ПРОЕКТА GOOGLE BOOKS NGRAM 8
1.2. ОПИСАНИЕ СТРУКТУРЫ ДАННЫХ GOOGLE BOOKS NGRAM 8
1.3 ПРОБЛЕМЫ ДАННЫХ КОРПУСА GOOGLE BOOKS NGRAM 11
ГЛАВА 2. МОДЕЛИРОВАНИЕ ГРАФА СИНТАКСИЧЕСКИХ
ЗАВИСИМОСТЕЙ 18
2.1 ОПИСАНИЕ МОДЕЛИ ПОСТРОЕНИЯ ГРАФА 18
2.1 РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ ГРАФА 19
ЗАКЛЮЧЕНИЕ 22
СПИСОК ЛИТЕРАТУРЫ 23
ПРИЛОЖЕНИЕ 1. ЛИСТИНГ ПРОГРАММНОГО КОДА 24
НАБОР ФУНКЦИЙ ДЛЯ ВЫДЕЛЕНИЯ ВАРИАБЕЛЬНЫХ КОЛЛОКАЦИЙ 24
ПОЛУЧЕНИЕ МАТРИЦ СМЕЖНОСТИ 27
ПОСТРОЕНИЕ ГРАФА ЗА ЗАДАННЫЕ ПЕРИОДЫ ВРЕМЕНИ 27
Всё большую популярность сегодня набирает междисциплинарное направление в науке под названием network science или же наука о сетях. Предметом исследования данной дисциплины являются сложные сети, встречающиеся в различных областях жизнедеятельности человека. Примерами таких сетей могут служить Интернет, социальные сети «друзей», белок-белковые взаимодействия, семантические сети.
Сложная сеть — это бинарные связи множества (графы) однородных объектов, встречающихся в природе, обладающие нетривиальными топологическими свойствами. Традиционно существует два вида сложных сетей, о которых речь пойдёт далее.
Безмасштабная сеть (scale-free network) — граф, в котором степени вершин распределены по степенному закону:
Р(/с) ос к~а, где Р(к) — доля вершин со степенью к, а а — показатель степенного закона, для которого характерно 2 < а < 3 [2]. К моделям таких сетей относят модель Барабаши-Альберт, модели копирования.
Мир тесен (small-world network) — граф, две произвольно взятые вершины х, у которого с большой вероятностью не являются смежными, однако попасть из х в у возможно путём небольшого числа переходов через другие вершины. Для сетей типа мир тесен характерно следующее свойство:
L ос log(N), где L — среднее расстояние между двумя вершинами, а N — число вершин в графе. Например, известная теория Милгрэма говорит, что каждый человек в мире знаком друг с другом в среднем через шесть рукопожатий. В рамках сети это означает, что в сети, объектами которой являются люди, а связями — факт знакомства между ними, среднее расстояние между узлами равно 6.
Приведем основные характеристики сложных сетей используя терминологию теории графов:
• Средняя степень вершины — среднее число рёбер, инцидентных вершине графа:
N
1=1
где — степень вершины vh N — общее число вершин в графе;
• Распределение степеней вершин— доля вершин Р (/с), имеющих степень вершины к;
• Средняя длина пути — среднее по длинам кратчайших путей по всевозможным парам вершин графа:
ij
где Vj) — кратчайший путь из вершины V; в вершину Vj, N — общее число вершин в графе, 1 < i < N, 1 < j < N, i A j;
• Диаметр графа — максимальная длина кратчайшего пути по всевозможным парам вершин графа:
maxL(ybVj),
где Цуь vj} — кратчайший путь из вершины ту в вершину vp
• Коэффициент кластеризации — показывает, насколько сеть транзитивна. Если вершины х и у — смежные, а у также смежна вершине z, то высока вероятность, что х и z тоже смежны. Также транзитивность можно определить, используя известный афоризм: «друг моего друга — мой друг». Найти коэффициент кластеризации вершины можно следующим образом:
С число треугольников с вершиной ту
1 число вилок с центром в вершине
тогда коэффициент кластеризации сети:
где N — общее число вершин в графе. Есть и другой подход к нахождению
коэффициента кластеризации для сети:
3 х число треугольников в сети
число виВвиду нашего дальнейшего рассмотрения сложных сетей в разрезе лингвистики кратко опишем основные классы лингвистических сетей:
• Семантические сети — отражают семантические (смысловые) отношения между словами. Чаще всего выделяют следующие типы бинарных
отношений: синонимические (бремя - ноша), антонимические (горячо - холодно), иерархические или гипонимические (птица - дрозд), включающие или меронимические (машина - колесо).
Фонологические сети — отражают звуковые отношения между словами. Такие сети строятся по следующему принципу: между словами- вершинами проводится ребро, если путём изменения фонем можно получить из одного слова другое (например, слова стол и стул).
Синтаксические сети — отражают грамматические зависимости между словами как членами предложения. Такие отношения представляются в виде дерева зависимостей, вершиной которого является сказуемое предложения. Ребра между словами-вершинами показывают отношения подчинённости.
Очевидно, что используемая в работе модель является наиболее простой требует доработок. На данный момент идёт обсуждение вероятностной модели копировании связей прототипа. Ставится под сомнение выделение вариабельных слов, чья степень вершины <79, как слишком искусственный метод «очистки».
Вызывает сомнения корректность данных корпуса Google Books Ngram, что приводит к обсуждаемым выше «очисткам». Определение критерия корректности «очистки» - выделения устойчивых синтаксических связей может быть вспомогательной целью дальнейших исследований.
Также следует отметить, что требуется оптимизация работы инструментария моделирования, разработанного на языке Python. Ввиду того, что язык является интерпретируемым, появляются достаточно большие задержки в получение результатов при обработке больших объемов данных. Использование списков смежности для хранения сети оказало положительный эффект на время выполнения скриптов. Таким образом, требуется пересмотр функционала инструментария в пользу использования списков смежности.
