Анализ связей

Ана́лиз свя́зей или анализ ссылок (от англ. «link analysis») — это метод анализа данных, используемый в рамках сетевого анализа для оценки отношений (связей) между узлами (объектами/акторами). Отношения могут быть определены для различных типов узлов: людей, организаций, операций и т. д. Термин «link analysis» (один из вариантов перевода: «анализ взаимосвязей») обозначает процесс анализа совокупности взаимоотношений между разными объектами сети для выявления её характеристик.

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

Данный метод относится к группе методов Data Mining. Это группа итерационных и интерактивных алгоритмов обнаружения, анализа и визуализации различных закономерностей в данных. Анализ связей относится данной группе алгоритмов, и, как большинство методов данной группы, реализуется в рамках следующих шагов^[стиль]: Сбор данных, Обработка данных, Анализ данных и Визуализация данных.

История развития инструментария

Клеркс выделял три периода в развитии инструментария реализации Анализа связей. Первое поколение было представлено в 1975 как Anacpapa Chart Харпером и Харрисом. Этот метод реализуется следующим образом: Исследователь занимается обработкой имеющихся данных, обозначая связи между акторами в виде матрицы взаимодействия. Затем исследователь строит соответствующий граф для визуализации данных и, в конечном итоге, анализирует полученную сеть, определяя показатели центральности (Patterns of interest). Данный метод является чрезвычайно трудоемким при рассмотрении больших объемов данных.

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

Третье поколение инструментов также даёт возможность автоматической визуализации связей между акторами. Более того, появляются средства, дающие возможность визуально ужимать большие объёмы данных в компактные пучки, что упрощает визуальный анализ данных для сложных моделей. Вычисление же основных показателей центральности осуществлялось также автоматически.

Сбор данных

Обзоры и опросы

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

1. дихотомические индикаторы присутствия или отсутствия данных типов взаимодействия, в которых могло фиксироваться число связей между респондентами;
2. шкалы или ряды, дифференцирующие связи по интенсивности;
3. методы парных сравнений различных взаимодействий на прочность.

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

1. атрибуты индивидов (элементов сети);
2. возможные свойства связей между респондентами — частота контактов, интенсивность;
3. интенсивность связей между парами респондентов, которая используется для измерения структурных свойств эгоцентричных сетей (например, определение плотности).

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

Архивы

Для сбора качественных сетевых данных нужны значительные средства. Архивные источники требуют гораздо меньше затрат, и одно из их преимуществ в том, что они позволяют проводить ретроспективные исследования и следить за развитием изучаемых сетей. Здесь Анализ связей как инструмент Data Mining тесно связан с другим направлением анализа данных Text mining.

Процедура анализа связей

Итогом сбора и обработки эмпирических данных являются формализованные матрицы взаимодействия акторов изучаемой сети.

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

Вычисление основных показателей

Ограничения подхода

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

И тем не менее существует ряд общепринятых техник оценки свойств сети и связей между её акторами.

Размер сети

Основной индикатор, представляющий размер сети — число прямых связей, включенных в индивидуальные объединения. Размер сети может изменяться от минимального значения 1 (2 вершины в графе) до максимально возможного значения (g-1), где g— количество вершин графа.

Сетевая плотность

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

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

$\Delta ={\frac {L}{g(g-1)/2}}={\frac {2L}{g(g-1)}}$, где L — количество наблюдаемых связей в данном графе или подграфе.

Плотность связей в ориентированном графе вычисляется по формуле:

$\Delta ={\frac {L}{g(g-1)}}$.

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

Центральность и централизация

Измерение степени центральности

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

$C_{D}(n_{j})=d(n_{i})=x_{i+}=\sum \limits _{j}x_{ij}=\sum \limits _{j}x_{ji}$.

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

$C_{D}'(n_{i})={\frac {d(n_{i})}{g-1}}={\frac {\sum _{j}x_{ij}}{g-1}}$.

Также можно рассчитать степень центральности для всей сети:

$C_{D}={\sum _{i=1}^{g}\left[C_{D}(n^{*})-C_{D}(n_{i})\right] \over max\sum _{i=1}^{g}\left[C_{D}(n^{*})-C_{D}(n_{i})\right]}$.

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

$C_{D}={\sum _{i=1}^{g}\left[C_{D}(n^{*})-C_{D}(n_{i})\right] \over (g-1)(g-2)}$.

Плотность центральности

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

Плотность центральности актора измеряется следующим образом:

$C_{C}(n_{i})=\left[\sum _{j=1}^{g}d(n_{i},n_{j})\right]^{-1}$.

Здесь $d(n_{i},n_{j})$ - число связей между акторами $n_{i}$ и $n_{j}$. Максимальное значение индекса равно $n_{j}(g-1)^{-1}$. Таким образом, нормированный коэффициент плотности центральности актора рассчитывается по следующей формуле:

$C'_{C}(n_{i})={\frac {g-1}{\left[\displaystyle \sum _{j=1}^{g}d(n_{i},\;n_{j})\right]}}=(g-1)C_{C}(n_{i})$

Нормированная плотность центральности сети рассчитывается по формуле:

$C_{C}={\frac {\displaystyle \sum _{i=1}^{g}\left[C'_{C}(n^{*})-C'_{C}(n_{i})\right]}{\left[(g-2)(g-1)\right]/(2g-3)}}$

Центральность как посредничество

В рамках данного подхода центральность рассматривается как контроль связей между определёнными позициями. Так, если кратчайшее расстояние между акторами n₂ и n₃ n₂, n₁, n₄ и n₃, то позиции n₁ и n₄ являются контролирующими по отношению к паре акторов n₂ и n₃.

Центральность посредничества актора можно рассчитать по формуле:

$C_{B}(n_{i})=\sum _{j<k}{\frac {g_{jk}(n_{i})}{g_{jk}}}$

Здесь $g_{jk}(n_{i})$ - число кратчайших путей, которые проходят через актор $n_{i}$. Поскольку максимальное количество связей между всеми вершинами графа равно ${\boldsymbol {(g-1)(g-2)/2}}$, то нормированная оценка центральности посредничества актора вычисляется соответственно по формуле:

$C'_{B}(n_{i})={\frac {C_{B}(n_{i})}{(g-1)(g-2)/2}}$.

Стандартизированная оценка центральности сети можно рассчитывается по следующей формуле:

$C'_{B}={\frac {\displaystyle \sum _{i=1}^{g}\left[C'_{B}(n^{*})-C'_{B}(n_{i})\right]}{(g-1)}}$.

Эквивалентность

Часто при описании структурных свойств сети прибегают к понятиям структурного сходства отдельных акторов. Выявление структурно похожих позиций позволяет упростить граф, объединяя схожие по своим структурным свойствам акторы в новые, корпоративные акторы. Соответственно для выявления эквивалентности между двумя позициями как правило используется следующая формула, предложенная Бёртом:

$d_{ij}={\sqrt {\sum _{k=1}^{g}\left[{(x_{ik}-x_{jk})^{2}+(x_{ki}-x_{kj})^{2}}\right]}}$

См. также

• Интеллектуальный анализ данных
• Социальный граф
• Нейронные сети
• Интеллектуальный анализ текста

Источники

• Градосельская Г. В. Сетевые измерения в социологии: Учебное пособие / Под ред. Г. С. Батыгина. М.: Издательский дом «Новый учебник», 2004.
• Чубукова И.А. Data Mining. М.: Бином, 2008
• Thelwall M. Link Analysis: An Information Science Approach. New York: Academic Press, 2004.