Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 71
Текст из файла (страница 71)
В случае неориентированных сетей P(k , k ') = P(k ', k ) иP(k ' | k ) =k'k ' P(k | k ') P(k ') = kP(k ' | k ) P(k ) .Если сеть ориентированная, то k – это степень предшествующего узла, k ' –степень последующего узла, значения k и k ' могут быть входными , выходными илиполными степенями. В общем случае P(k , k ') = P(k ', k ) .Значения P(k , k ') и P(k | k ') формально описывают корреляции степеней узлов,однако их сложно вычислять экспериментальным путем, что связано с размером сетии малой мощностью выборки узлов с высокими степенями.
Эту проблему можнорешить, вычислив среднюю степень ближайших соседей узлов с заданной степенью kпо формуле:S (k ) = ∑ k ' P(k ' | k ) .k'259Показатель корреляции степеней связности позволяет выделить отдельныеклассы сетей. Если корреляция отсутствует, то S (k ) не зависит от значений k ,S (k ) = k 2 / k . Если S (k ) возрастает при увеличении k , то узлы больших степенейтяготеют к соединениям с узлам больших степеней, и сеть относят к ассортативным(отсюда и феномен «клуба богатых»), тогда как если S (k ) – убывающая функция от k, то вершины больших степеней тяготеют к соединениям с вершинами малыхстепеней, и сеть называют дизассортативной [39].В работе [39] был подсчитан коэффициент корреляции Пирсона для некоторыхреальных и смоделированных сетей.
Было обнаружено, что, несмотря на отображениемоделями специфических особенностей структуры (степенное распределение степенисвязности узлов, свойство «малого мира»), большинство из них не воспроизводитассортативность реальной сети. Например, для модели построения сети со степеннымраспределением степеней связности узлов Барабаши-Альберта [40] значение r = 0 .Тем не менее, социальные сети склонны к ассортативности, а биологические итехнологические часто дизассортативны.Известно, что ассортативные сети менее уязвимы к равновероятным атакам, адизассортативные менее уязвимы к целенаправленным атакам на узлыконцентраторы. Также, например, синхронизация состояния компонент сетипроисходит быстрее в ассортативных сетях. Например, при распространении заразнойболезни социальные сети в идеальном случае должны быть ассортативны: приконтроле малой доли узлов-концентраторов сеть разбивается на изолированныекомпоненты связности, что позволяет эффективно контролировать распространениеинфекции.§ 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 недель.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
