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

Хорошая, логичная гипотеза. (При желании ее легко можно вписать в теорию социальной укоренённости). Только с её проверкой будут проблемы. Обычной линейной регрессией (OLS) её не проверить, поскольку регрессионный анализ исходит из предположения о независимости наблюдений, а наш пример и гипотеза, наоборот, именно о взаимосвязанных индивидах. Мы хотим узнать, объясняют ли связи одного рода - связи другого рода между одними и теми же узлами. Если проверять нашу гипотезу с нарушением допущения о независимости наблюдений обычной регрессией, то получим ошибки связанные с автокорреляцией остатков: ложноположительный результат, недооценку стандартной ошибки, ненадежные доверителные интервалы, - всё это препятствует однозначному принятию или отклонению гипотезы. Как быть?

К счастью, существует (причем достаточно давно) метод для проверки таких гипотез - QAP-корреляция и QAP-регрессия (или MRQAP). QAP (досл. “процедура квадратичного назначения”) – непараметрический рандомизированный тест для выявления связи между сетями связей с одними и теми же узлами, в основе которого многократная случайная перестановка узлов сети, позволяющая обойти проблему зависимости наблюдений и оценить, является ли связь между ними случайной или закономерной. Иногда подобные QAP-тесты обобщенно называют перестановочными или пермутационными тестами.

Впервые идея QAP-процедуры в качестве пермутационного теста для квадратных матриц появилась и была реализована ещё в 1960-е г. в “тесте Мантеля”. Само название процедуры “QAP”, напоминающей метод Монте-Карло, закрепилось позднее в 1980-е г. вместе с ее усовершенствованием таким образом, чтобы попарная структура узлов при перестановке не искажалась. QAP-регрессия (или MRQAP) - это последующее расширение того же подхода с перестановкой но уже для регрессии, использующее несколько ковариационных матриц и выявляющее влияние одной ковариационной матрицы на другую, контролируя эффекты прочих ковариационных матриц. В настоящее время существует несколько реализаций метода QAP-регрессии. Наиболее широко используется реализация под названием “Double Semi-Partialling” (DSP), разработанная Д. Деккером и соавторами в 2007 г. Её преимущество в том, что она позволяет контролировать не только автокорреляцию, но и коллинеарность наблюдений.

Методы QAP-корреляции и MRQAP реализованы в некоторых статистических пакетах, а также библиотеках для R и Python: UCINet, mrqap, sna, statnet. Разберем ниболее простой и способствующий пониманию вариант - MRQAP в UCINet

UCINet - это ПО для анализа социальных сетей (SNA) на компьютерах с Windows (!только для Windows), разработанное С. Боргатти, М. Эвереттом и Л. Фридманом в 1990-е г. С тех пор UCINet много раз обновлялся. Если вам доводилось читать научные публикации (или что-то еще) об SNA, то имя С. Боргатти вам, скорее всего, встречалось.

По сравнению с широко известным Gephi, UCINet используют гораздо реже. UCINet несколько уступает ему в том, что касается визуализации, и явно превосходит в том, что касается расчетов сетевых метрик и тестирования гипотез о сетях. Интерфейс и устройство UCINet больше напоминают SPSS или Stata. (Есть также командная строка для матричной алгебры).

UCINet - платное ПО, которое, тем не менее, предоставляет пробный период пользования (2 месяца) без каких-либо условий, кроме скачивания. (За это время можно легко рассчитать то, что нужно, и даже больше - все работает очень быстро). Есть некоторые нюансы касаемо версий, а также форматов данных, в которых UCINet принимает и хранит графы (или матрицы). С ними легко разобраться, следуя руководству.

Один из нюансов в том, что UCINet-6 (текущая версия 6.812) принимает только экселевские файлы с расширением .xls. (Предварительно сохраняйте свои графы в этом формате). Еще одно производное ограничение в том, что UCINet-6 может единовременно обрабатывать сети с количеством узлов не более 255. Т.е. в загружаемом графе или матрице может быть не более 255 столбцов (и строк, соответственно). В противном случае столбцы после 255-го будут автоматически обрезаны, а строки останутся. И это создаст проблему для MRQAP, т.к. она требует квадратных матриц.

Большим преимуществом UCINet, способствующим пониманию того, что происходит "под капотом", являются сопроводительные материалы, которые доступны при нажатии на иконку “Help”. В выпадающем списке выбираете "Help Topics", появляется список гиперссылок инструментов доступных в UCINet (их много), щелкаете на название инструмента и открывается статья, описывающая его назначение, требования к данным, которые он принимает “на вход”, вычислительную процедуру в основе, оценку сложности вычислений, также приводится ссылка на научную статью, в которой был предложен описываемый метод (формулы можно найти в статье).

Например, справка о MRQAP методом Double Semi-Partialling выглядит так:

Также очень полезен Hanneman Tutorial из “Help” .

После того как данные о связях (графы) загружены в UCINet, все что остается сделать, пройти вглубь в выпадающем списке открывающемся при нажатии иконки “Tools” -> “Testing Hypotheses” -> “Dyadic (QAP)” -> “MR-QAP Linear Regression” -> “Double Dekker Semi-Partialing MRQP”. (“Double Dekker Semi-Partialing MRQP” - это и есть DSP, разработанная Деккером и соавторами, о которой шла речь выше). И в общем все. Остается только не перепутать независимую переменную с зависимой и правильно проинтерпретировать p-value.

Проверим гипотезу об объяснении одних связей другими, для одного из учебных датасетов UCINet - “PADGETT FLORENTINE FAMILIES”. Во многом именно эти данные и послужили прообразом воображаемого кейса, описанного во вступлении. Это две матрицы 16x16, содержащие данные о связях 16 флорентийских семей Эпохи Возрождения, включая Медичи и Строцци, которые были вовлечены в политическую борьбу за контроль над Флоренцией в 1430 г. Именно эти данные использовались в известной статье 1993 г. Дж. Паджетта и К. Анселя о Медичи и SNA. Данные были собраны из исторических документов. Оба графа невзвешенные, т.к. есть проблема с направлением деловых связей (кто кого кредитовал) и с весами в контексте брачных связей. В матрице PADGB отражены факты наличия или отсутствия деловых связи между семействами, включая займы, кредиты и партнерства, а в матрице PADGM - данные об их брачных союзах.

PADGB: деловые связи 16-и флорентийских семейств

PADGM: брачные союзы 16-и флорентийских семейств

Остается выяснить, объясняли ли брачные союзы семейств во Флоренции Эпохи Возрождения их деловые связи? Рассчитаем MRQAP для PADGB в качестве зависимой переменной и PADGM в качестве независимой, с количеством случайных перестановок в матрицах (No. of random permutations) = 5000. (Количество перестановок важный гиперпараметр MRQAP-модели, по-идее, зависящий от количества узлов в сети - чем больше узлов, тем больше нужно случайных перестановок). Random seed = 42 - фиксируется для воспроизводимости эксперимента.

Результат работы модели

Интерпретируем результат: p-value < 0,05 свидетельствует о статистической значимости полученного результата. В ок. 30% случаев бизнес-связи семейств, действительно, объяснялись их брачными союзами.

Вот так делались дела во Флоренции Эпохи Возрождения!

И вот такой метод проверки гипотез о том, объясняются ли одни связи другими.