Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика, страница 72

Например, при распространении заразнойболезни социальные сети в идеальном случае должны быть ассортативны: приконтроле малой доли узлов-концентраторов сеть разбивается на изолированныекомпоненты связности, что позволяет эффективно контролировать распространениеинфекции.§ 3.3.Сложные сети и задачи компьютерной лингвистикиПервым шагом при применении теории сложных сетей к анализу текста являетсяпредставление этого текста в виде совокупности узлов и связей, построение сетиязыка (language network) [41].Существуют различные способы интерпретации узлов и связей, что приводит,соответственно, к различным представлениям сети языка.Узлы могут бытьсоединенны меду собой, если соответствующие им слова стоят рядом в тексте[42; 43], принадлежат одному предложению [44], соединены синтаксически [45; 46]или семантически [47; 48].Сохранение синтаксических связей между словами приводит к изображениютекста в виде направленной сети (dіrected network), где направление связисоответствует подчинению слова.Поставим в соответствие каждому слову узел сети.

Соединим каждые два узласвязью, если соответствующие им слова стоят в предложении рядом. Такоепредставление называют L-пространством. В L-пространстве, равно как и в другихприведенных ниже представлениях, при возникновении кратных связей принятосохранять лишь одину из них.a. L-пространство. Связываются соседние слова, которые принадлежат к одномупредложению.

Количество соседей для каждого слова (окно слова)определяется радиусом взаимодействия R, чаще всего рассматривается случайR = 1.260b. B-пространство. Рассматриваются узлы двух видов, соответствующиепредложениям и словам, которые им принадлежат.c. P-пространство. Все слова, которые принадлежат одному предложению,связываются между собой.d. C-пространство. Предложения связываются между собой, если в нихупотреблены одинаковые слова.В случае L-пространства связи могут учитывать не только «ближайшихсоседей», но и группы из нескольких слов, которые находятся на определенномрасстоянии друг от друга.

Для этого вводится поняте «радиуса действия» R : при R =1 связь существует лишь между ближайшими соседями, при R = 2 – междуближайшими и следующими близкими соседями и т. д. Переменная R можетпринимать значения от R = 1 до Rmax , где Rmax + 1 – общее количество слов впредложении.Еще один способ представить текст в виде сети заключается в использованиидвудольных (bіpartіte) графов. В таком предсталеннии (B-просторанство)рассматриваются узлы двух видов. Один вид соответствует предложениям, второй –словам. Связь между различными узлами означает, что слово принадлежитпредложению.В P-просторанстве все слова, принадлежащие одному предложению, считаютсясвязанными между собой.

В C-просторанстве узлы соответствуют предложением, асвязь между узлами-предложениями устанавливается в том случае, если у них естьобщие слова.В случае рассмотрения L-пространства языка количество соседних слов, междукоторыми строятся связи, определяется параметром R : при R = 1 связаны междусобой лишь ближайшие соседи, при R = 2 связи строятся между узлом-словом, егоближайшими и предшествующими близкими соседями и т. д. Рост «радиусавзаимодействия» R приводит к росту количества связей, достигая насыщения при R= Rmax .Для сети, построенной на основании Британского национального корпуса,оказалось, что данная сеть английского языка безмасштабна, а поведение степени P(k)характеризуется двумя режимами степенного распределения со значением степенногопоказателя γ = 1,5 для k < 2000 и γ = 2,7 для k > 2000 соответственно.Согласно определению, если средняя длина кратчайшего пути растет сразмером (количеством узлов) сети медленнее любой функции степени, то сетьявляется «малым миром».

Сети малого мира чрезвычайно компактны. Дляупомянутой выше сети английского языка длина кратчайшего пути составляет всего< l >= 2, 63 . Поскольку рост R приводит лишь к добавлению новых связей, то < l >уменьшаются с ростом R.Специфической формой корреляции в сетях является образование кластеров.Коэффициент кластерности C характеризует склонность сети к образованиюсоединенных троек узлов. Известно, что для полного графа C = 1, а для сети в формедерева C = 0.

Отношение среднего коэффициента кластерности исследуемых сетей ккоэффициенту кластерности классического случайного графа свидетельствует о том,что сети языков являются хорошо коррелированными структурами. Такие корреляциирастут с ростом «радиуса взаимодействия» R . Для Британского национального261корпуса на основании анализа текстов, которые содержали ≈ 107 слов, полученозначение коэффициента кластености < C >= 0,687. hCі = 0:687 [42].В случае рассмотрения P –пространства каждое слово-узел связано со всемидругими словами, которые принадлежат общему предложению. Таким образом,каждое предложение текста входит в сеть как полный граф – клика взаимосвязанныхузлов.

Разные предложения-клики объединяются в сеть благодаря общим словам. ВL-просторанстве слова связываются в пределах окна, размеры которогохарактеризуются переменной R . Когда размер этого окна становится ровным размерупредложения, то представление этого предложения в L- и в P -просторанствахсовпадают. Соответственно, когда размер окна становится ровным размеру самогодлинного предложения текста ( R = Rmax ), то представление всего текста в L- и в Pпространствах совпадают.Полученны результаты, которые убедительно свидетельствуют о том, что сетьязыка яляется сильно коррелирующим безмасштабным малым миром (scale - freesmall world).Существует ряд трудов, в которых сделана попытка объяснить свойства сетейязыка с помощью сценария подавляющего присоединения (preferentіal attachment[49]), рассматривая их как результат процесса роста, когда новые узлы-слова сбольшей вероятностью присоединяются к узлам-хабам, имеющим много связей.§ 3.4.Моделирование сложных сетейМодель слабых связейСуществует класс сложных сетей, которым присущи так называемые «слабые»связи.

Аналогом слабых социальных связей являются, например, отношения сдалекими знакомыми и коллегами. В некоторых случаях эти связи оказываются болееэффективными, чем связи «сильные». Так,группой исследователей изВеликобритании, США и Венгрии, был получен концептуальный вывод в областимобильной связи, заключающийся в том, что «слабые» социальные связи междуиндивидуумами оказываются наиболее важными для существования социальной сети[50].Для исследования были проанализированы звонки 4.6 млн. абонентов мобильнойсвязи, что составляет около 20% населения одной европейской страны. Это былпервый случай в мировой практике, когда удалось получить и проанализироватьтакую большую выборку данных, относящихся к межличностной коммуникации.В социальной сети с 4.6 млн.

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

Если же неучитывать сильных связей, то связность сети нарушится (рис. 6.13).262123Рис. Часть VI.13. Структура сети:1) полная карта сети социальных коммуникаций; 2) социальная сеть, из которойизъятые слабые связи; 3) сеть, из которой изъятые сильные связи: структурасохраняет связностьОказалось, что именно слабые связи являются тем феноменом, который связываетсеть в единое целое.

Надо полагать, что данный вывод справедлив и для вебпространства, хотя исследований в этой области до сих пор не проводилось.Модель малых мировНесмотря на огромные размеры некоторых сложных сетей, во многих из них (ввеб-пространстве, в частности) существует сравнительно короткий путь между двумялюбыми узлами – геодезическое расстояние. В 1967 г. психолог С. Милгран врезультате проделанных масштабных экспериментов вычислил, что существуетцепочка знакомств, в среднем длиной шесть, практически между двумя любымигражданами США [51].Д.

Уаттс и С. Строгатц обнаружили феномен, характерный для многих реальныхсетей, названный эффектом малых миров (Small Worlds) [52].Сетевые структуры, соответствующие свойствам малых миров обладаютследующими типичными свойствами: малая средняя длина пути относительнодиаметра сети (что характерно также для случайных сетей) и большой коэффициенткластеризации (что присуще сетям с регулярной структурой).При исследовании этого феномена ими была предложена процедура построениянаглядной модели сети, которой присущ этот феномен.Чтобы построить сеть «малого мира», следует начать с регулярной циклическойрешетки с N вершинами, каждая из которых соединена с k (в частности, k = 2)ближайшими соседями в каждом направлении.

Для каждой вершины задается 2 kсвязей, где N >> log 2 ( N ) >> 1 . Затем каждое ребро пересоединяется со случайнойпарой вершин с вероятностью p .При условии p = 0 получается упорядоченная решетка с большим количествомциклов и большими расстояниями, а при условии p → 1 сеть становится случайнымграфом с короткими расстояниями, и малым количеством циклов. В некоем среднемслучае присутствуют и короткие расстояния, и большое количество циклов.Три состояния этой сети представлены на рис. 6.14: регулярная сеть – каждыйузел которой соединен с четырьмя соседними, та же сеть, у которой некоторые«ближние» связи случайным образом заменены «далекими» (именно в этом случаевозникает феномен «малых миров») и случайная сеть, в которой количествоподобных замен превысило некоторый порог.263Рис.