Эксперимент С. Милграма.

Какова вероятность, что два случайно выбранных человека окажутся знакомы друг с другом? Если они не знакомы, какова вероятность, что существует третий человек, который знает их обоих? Наконец, какова средняя длина цепи знакомств, соединяющей двух произвольно взятых людей?
В 1967 году Стэнли Милграм поставил задачу экспериментальным путем проверить, насколько тесен мир.
Сам он так описывает феномен тесного мира: «Сидя в придорожном кафе в Тунисе и желая закурить, Фред Джонс из Пеории (город в США, шт. Иллинойс) просит спичку у мужчины, сидящего за соседним столиком. У них завязывается разговор. Незнакомец – англичанин, который, как оказалось, провел несколько месяцев в Детройте, изучая работу фабрики, производящей крышки для бутылок. “Я знаю, это глупый вопрос”, - говорит Джонс, - “но не случалось ли Вам случайно встретиться с человеком по имени Бен Аркадиан? Это мой старый друг, управляет сетью супермаркетов в Детройте...”. “Аркадиан, Аркадиан” - бормочет англичанин. “Дайте-ка вспомнить, полагаю, я знаю его! Маленький парень, очень энергичный, поднял на фабрике большой шум по поводу партии бракованных бутылочных крышек”. “Не может быть!” - восклицает удивленный Джонс. “Боже мой! Мир тесен, не так ли?”».
С. Милграм провел эксперимент, состоящий в следующем - добровольцы должны передать письмо определенному человеку («target person»), находящемуся в Бостоне. Добровольцы получают некоторую информацию о получателе, и должны отослать письмо через своего родственника или личного знакомого, который, предположительно, мог бы знать получателя. Этот человек должен передать письмо кому-то из своих личных знакомых, кто предположительно мог бы быть еще ближе к получателю, и так далее, пока письмо не дойдет до своего адресата. Первое письмо достигло цели на четвертый день. Для того чтобы письмо нашло своего адресата, в среднем потребовалось пять промежуточных знакомых: «цепочки варьровали от двух до десяти промежуточных знакомых, с медианой в пяти».
Этот эксперимент многократно повторялся и в последующем оказалось, что средняя длина цепочек – довольно устойчивая величина, что дало основание для так называемой «теории шести рукопожатий» (six degrees of separation) – представления о том, что от любого человека на Земле нас отделяет всего шесть рукопожатий.
В 2006 г. Эрик Хорвиц (Eric Horvitz) и Юре Лесковец (Jure Leskovec) из Microsoft Research провели анализ базы данных, содержавшей информацию о комуникации посредством программы Microsoft Messenger за один месяц (июнь 2006).
Они проанализировали данные 30 млрд. разговоров между 240 мнл. человек. Был построен коммуникационный граф, содержащий 180 млн. узлов (пользователи, участвовавшие хотя бы в одном разговоре за рассматриваемый период) и 1,3 млрд. ненаправленных ребер, (каждое из которых соединяет двух пользователей, обменивавшихся сообщениями друг с другом). На сегодняшний день это самая большая социальная сеть, которая когда-либо исследовалась.
Результаты эксперимента достаточно интересны.

1. 99% разговоров были между 2 людьми, лишь 1% - между большим количеством пользователей. 99,9% пользователей оказались связаны между собой цепочками разной длины.
2. Люди чаще и дольше общаются с теми, кто близок им по социально-демографическим признакам (т.н. «гомофилия»). В наибольшей степени это касается языка пользователя, затем географического местоположения, затем возраста. Единственное исключение – пол: «люди имеют склонность чаще и дольше общаться с представителями противоположного пола».
3. Сеть обладает высокой степенью кластеризации, т.е. процент петель, состоящих из трех пользователей, значительно выше, чем этого можно было ожидать исходя из предыдущих исследований сетей, «люди, имеющие общих друзей, имеют тенденцию быть связанными друг с другом».
4. Средняя длина кратчайших цепочек, связывающих любых двух пользователей, составляет 6,6 (мода 6, медиана 7), что несколько превышает данные, полученные Милграмом.

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

Сам термин "социальные сети" введен в далеком 1954-м. Долгое время соцсети существовали только в теории, которая полностью сформировалась к 1970 году. В 1971-м появилась технология электронной почты в сети ARPA Net, используемой военными. Она стала первой в истории сетью с применением компьютерной техники. Первый ретранслируемый интернет-чат был создан в 1988 году и назывался IRC. Очевидно, что пик развития социальных сетей пришелся на время повсеместного распространения Интернета. Пройдя стадию разноплановых чатов и сервисов наподобие «Живого журнала», общество пришло к созданию соцсетей в таком виде, который есть сейчас. И, по сути дела, начиная с 2003–2004 годов, появляются социальные ресурсы, положившие начало явлению "социальные сети".

Первые соцсети

По всей видимости, первым социально-сетевым ресурсом можно считать Classmates.com. Проект был запущен Рэнди Конрадсом в 1995 году. Classmates.com предоставлял возможность найтись одноклассникам, однокурсникам и сослуживцам.
В современном понимании, этот проект первой социальной сетью считать нельзя. Сайт изначально не давал возможности создать личный профиль, а только открывал доступ к спискам тех, кто обучался в определенном учебном заведении. Тем не менее, Classmates.com существует до сих пор. Он объединяет более 50 миллионов пользователей из США, Канады, Швеции, Франции, Германии и Австрии.
Первой социальной сетью в современном понимании можно считать SixDegrees.com. Она была создана Эндрю Вейнрейхом в 1997 году. Проект изначально позволял пользователям создавать личные профили и списки друзей. К тому же несколько позже, в 1998 году, команда SixDegrees.com добавила поиск по страницам, что дало возможность быстрее и удобнее находить старых знакомых и заводить новых. Но, увы, в 2001 году портал SixDegrees.com был закрыт. Эта соцсеть по своим возможностям значительно опередила время, ведь на тот момент пользователей Интернет было очень мало.

Так как история социальных сетей достаточно коротка, то переходим к современности.

Facebook

Facebook появился в 2004 году. Его создателем является Марк Цукерберг. На данный момент этот ресурс является наиболее популярной социальной сетью во всем мире. Сайт удерживает лидирующие позиции в рейтинге уже много лет. Число пользователей соцсети достигло 2,2 миллиарда, из которых, 1,4 миллиарда человек заходят в фейсбук ежедневно.
Интерфейс синего цвета практически не менялся с момента его создания.
По этому поводу ходят разные слухи, достаточно правдоподобно то, что Марк Цукерберг — дальтоник и синий — это единственный цвет, который он видит без искажений.

Twitter.

Соцсеть, позволяющая делиться короткими сообщениями (преимущественно новостными) и имеющая более 330 000 000 пользователей. Создана Джеком Дорси в 2006 году.

LinkedIn.

Данная сеть позиционируется больше как профессиональная и насчитывает более 510 000 000 пользователей. Социальная сеть LinkedIn была основана Ридом Хоффманом в декабре 2002 года, запущена в мае 2003 года.

Instagram.

Соцсеть, позволяющая делиться фотографиями и видеозаписями. Насчитывает более 375 миллионов пользователей в месяц. Появилась в 2010 году. Instagram была приобретена Facebook в апреле 2012 года примерно за 1 миллиард долларов наличными и акциями.

Google Plus/+

Это социальная сеть, поддерживаемая одноименным поисковиком и имеющая аудиторию более 120 000 000 пользователей. Начало работы – 2011 год.

И, наконец, две социальные сети, популярные в рунете.

ВКонтакте.

Молодежная российская соцсеть, обеспечивающая хорошие мультимедийные возможности (просмотр видео, прослушивание музыки и т. д.), насчитывает более 80 000 000 пользователей. Основана в 2006 году. Изначально соцсеть задумывалась как студенческая. Рабочее название — Studlist.ru. Её основателем является Павел Дуров.

Одноклассники.

Одна из самых популярных российских социальных сетей с количеством пользователей более 290 000 000. Принадлежит Mail.Ru Group. Появилась в 2006 году. Одна из самых популярных социальных сетей в России и странах СНГ. Однако в последние годы она начала терять свои позиции и в ней регистрируется всё меньше новых пользователей.

Статистика популярности социальных сетей в Украине.

Статистика популярности социальных сетей в мире.

Теория графов - это изучение графиков, которые являются математическими представление сети, используемой для моделирования парных отношений между объектами. Граф состоит из набора «вершин» или «узлов», с определенными пары этих узлов, соединенные «ребрами» (неориентированные) или «дуги» (направленные). Граф может быть неориентирован, а это означает, что нет различия между двумя вершинами, связанными с каждым ребром, или направленными, что его дуги могут быть направлены от одной вершины до другой.
Традиционно для обозначения отдельного элемента социальной сети используют понятие «узел», если речь идет об исследованиях прикладного математического характера, или «актор», если подразумевается социологические исследования. В целом узел и актор по сути представляет собой отдельного человека (в социальных сетях), выступающего субъектом связей (с точки зрения теории графов - ребер) с другими индивидами.
Матрица смежности: \(a_{ij} = 1\) если существует связь между \(i\) и \(j\). Для ненаправленного графа она симметричная. \[ \left( \begin{array}{ccccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 2 & 1 & 0 & 1 & 0 & 1 & 0 \\ 3 & 0 & 1 & 0 & 1 & 0 & 0 \\ 4 & 0 & 0 & 1 & 0 & 1 & 1 \\ 5 & 1 & 1 & 0 & 1 & 0 & 0 \\ 6 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right) \]

Ненаправленный граф.

Степенью (или валентностью) узла называется число узлов, смежных с данным. При подсчёте степени ребро-петля учитывается дважды. В случае, если граф направленный, то значение в матрице смежности равное единице соответствует тому, что есть связь от узла \(j\) к узлу \(i\). \[ \left( \begin{array}{ccccccc} & 1 & 2 & 3 & 4 & 5 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 1 & 0 \\ 3 & 0 & 1 & 0 & 1 & 0 \\ 4 & 0 & 1 & 0 & 0 & 1 \\ 5 & 0 & 1 & 0 & 0 & 0 \\ \end{array} \right) \]

Направленный граф.

Ввиду ориентированности графа, степень узла может быть входящая и исходящая, в зависимости от того, к скольким узлам есть связь от данного узла и, соответственно, от какого числа узлов есть связь к данному. Расстояние \(d_{i,j}\) (кратчайший путь, геодезический путь) между двумя узлами \(i\) и \(j\) - количество ребер вдоль кратчайший путь, соединяющий их.
Для ненаправленного (неориентированного) графа расстояние от \(i\) до \(j\) равно расстоянию от \(j\) до \(i\) \[ \left( \begin{array}{ccccccc} & 1 & 2 & 3 & 4 & 5 & 6 \\ 1 & 0 & 1 & 2 & 2 & 1 & 3 \\ 2 & 1 & 0 & 1 & 2 & 1 & 3 \\ 3 & 2 & 1 & 0 & 1 & 2 & 2 \\ 4 & 2 & 2 & 1 & 0 & 1 & 1 \\ 5 & 1 & 1 & 2 & 1 & 0 & 2 \\ 6 & 3 & 3 & 2 & 1 & 2 & 0 \\ \end{array} \right) \] Для неориентированного, это не так.
Плотность неориентированного графа- отношение числа имеющихся рёбер графа к максимально возможному количеству рёбер данного графа \[ \Delta=2\frac{L}{g(g-1)}, \] где \(L\) - число связей (ребер), а \(g\) - число акторов (узлов) в графе. Плотность ориентированного графа вдвое меньше.
Ясно, что в пустой сети плотность равна нулю, а в полносвязной – единице.
Компонента связности графа - подграф, в котором любые две вершины могут быть соединены друг с другом посредством связей данного подграфа.

Несвязный граф с тремя компонентами связности.

Кликой неориентированного графа называется подмножество его узлов, такое, что любые два имеют между собой связь, то есть, соединены ребром. Применительно к социальным сетям, клика есть множество акторов (людей), знакомых между собой. Степень центральности равна числу связей актора \(c_i=\sum_{j}a_{i,j}\).
Для сравнения центральности актора между различными сетями, нужно провести нормализацию оценки центральности \[\bar{c}_i=\frac{c_i}{g-1}=\frac{1}{g-1}\sum_{j}a_{i,j},\] где \(g\) - число акторов (узлов) в графе.

Центральность узла.

Нормализовання степень центральности сети вычисляется следующим образом \[ C(G)=\frac{\sum_{i=1}^g\left(\max\left\{c_i|i\right\}-c_i\right)}{(g-1)(g-2)}. \] Центральность по близости актора можно оценить через среднее расстояние от данного актора до других. Расстояние определяется как геодезический путь, который является самым коротким путем через сеть между двумя вершинами. Пусть \(d_ {i, j}\) - длина геодезического пути от \(i \) до \( j \), что равно количеству ребер вдоль этого пути. Тогда среднее геодезическое расстояние для вершины \(i\) равно: \[ l_i = \frac {1}{g-1} \sum_j d_{i, j} \] Эта величина принимает низкие значения для вершин, которые отделены от других небольшим геодезическим расстоянием. Такие акторы могут иметь лучший доступ к информации в других вершинах или имеют большее прямое влияние на другие вершины. Например, в социальной сети мнение человека с более низким средним расстоянием более быстро достигают других в сообществе, чем мнение кого-то с более высоким средним расстоянием.

Среднее расстояние узла.

Среднее расстояние \(l_i\) не является мерой центральности в смысле предыдущих, поскольку оно дает низкие значения более центральным узлам и высокие значения менее центральным, что противоположно другим мерам центральности. Поэтому обычно вычисляют обратную величину - плотность центральности: \[C_i = \frac{1}{l_i} = \frac{g-1}{\sum_j d_{i, j}}. \] Плотность центральности дает возможность оценить насколько близко актор располагается относительно других акторов. Достаточно интересна еще одна мера центральности, которая характеризует сплоченность группы - центральность по посредничеству. Основание этого подхода исходит из эксперимента С. Милграма -"теории шести рукопожатий" (см. самое начало этого раздела). Эта мера (Betweenness Centrality) показывает минимальное количество шагов (или посредников), необходимых, чтобы через установленные связи для любого актора, достичь каждого актора в сети.
Взаимодействие двух не смежных (соседних) акторов может находиться под контролем возможных посредников.
Центральность по посредничеству рассчитывается как доля самых коротких путей, соединяющих все пары вершин в сети, которые проходят через данную вершину: \[ b_i=\sum_j\sum_i\frac{g_{j,k}(i)}{g_{j,k}},i\ne j\ne k, \] где \(g_{j,k}\) – количество кратчайших путей между вершинами \(j\) и \(k\);
\(g_{j,k}(i)\) - количество кратчайших путей между вершинами \(j\) и \(k\), проходящих через вершину i.
Нормализация проводится делением на максимально возможную величину - \((g-1)(g-2)/2\).
Рассмотрим пример

и вычислим \(b_E\): \[ b_E=\sum_j\sum_i\frac{g_{j,k}(i)}{g_{j,k}}= \frac{g_{AB}(E)}{g_{AB}}+\frac{g_{AC}(E)}{g_{AC}}+\frac{g_{AD}(E)}{g_{AD}}+\frac{g_{BC}(E)}{g_{BC}}+\frac{g_{BD}(E)}{g_{BD}}+ \frac{g_{CD}(E)}{g_{CD}}=\frac{1}{2}+\frac{0}{1}+\frac{1}{1}+\frac{0}{1}+\frac{1}{1}+\frac{2}{2}=3.5 \] Для приведенного выше графа имеем

Центральность по посредничеству узла.

Из всего сказанного можно сделать следующий вывод - актор важен не тогда, когда у него много друзей, а если он связан с другими важными акторами.
Центральный собственный вектор пытается обобщить понятие центральности, включая в нее важность соседей. Для отслеживания соседей используется матрица смежности.
Пусть \(\displaystyle {A} = (a_{i, j}) \) - матрица смежности графа. Центральный собственный вектор \( x_{i} \) узла \(i\) задается следующим образом: \[ x_i = \frac {1} {\lambda} \sum_k a_{k, i} \, x_k \] где \( \lambda \neq 0 \) - постоянная, то есть выберем этот вектор так, чтобы он был пропорционален сумме центральностей его соседей.
В матричной форме мы имеем: \( \lambda \mathbf{x} = \mathbf{x A}.\)
Следовательно, вектор центральности \(\mathbf{x}\) является левым собственным вектором матрицы смежности \(\mathbf{A} \), ассоциированным с собственным значением \(\lambda \). Целесообразно выбрать \(\lambda \) как наибольшее собственное значение. В силу теоремы Перрона-Фробениуса этот выбор гарантирует следующее желаемое свойство: если матрица \(A\) невырождена или, что то же самое, если граф (сильно) связен, то решение единственно и \(\lambda \) положительно.
Рассмотрим пример

Выпишем матрицу смежности \[ \mathbf{A}=\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \end{array} \right). \] Собственные значения \(\mathbf{A}\) равны \((-1.74,-1.27,0.00,0.33,2.68)\), наибольшее из которых равно \(2.68\).
Решая систему \[ \left( \begin{array}{ccccc} 0-2.68 & 1 & 0 & 1 & 0 \\ 1 & 0-2.68 & 1 & 1 & 1 \\ 0 & 1 & 0-2.68 & 1 & 0 \\ 1 & 1 & 1 & 0-2.68 & 0 \\ 0 & 1 & 0 & 0 & 0-2.68 \\ \end{array} \right) \left( \begin{array}{ccccc} u_1 \\ u_2 \\ u_3 \\ u_4 \\ u_5 \\ \end{array} \right)= \left( \begin{array}{ccccc} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \end{array} \right) \] получаем собственный вектор центральности \[ \mathbf{x}=\left( \begin{array}{ccccc} 0.4119 \\ 0.5825 \\ 0.4119 \\ 0.5237 \\ 0.2169 \\ \end{array} \right). \] Значение координат собственного ветора дает оценку центральности, таким образом, узел \(b\) является наиболее центральным.
Интересно посмотреть на распределение узлов с точки зрения собственного вектора центральности

Наибольшие собственные значения центральности узлов.

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

Меры центральности.

Транзитивность, или коэффициент кластеризации, - одна из важнейших метрик сетевого анализа. Этот коэффициент рассчитывается как отношение числа замкнутых триад по отношению ко всем возможным (замкнутым и незамкнутым) триадам. Замкнутые триады — это случай, при котором между тремя вершинами существуют все возможные связи.

Типы триад.

Соответственно, значения его колеблются от 0 (случай, когда замкнутых триад в графе нет) до 1 (случай полного графа, когда все триады замкнуты).
Когда говорим о «коэффициенте кластеризации», то обычно подразумеваем глобальный коэффициент (global clustering coefficient), характеризующий склонность вершин формировать замкнутые триады. При этом не принимаем во внимание неоднородную природу сетей – ведь в ней могут быть одновременно как тесно связанные между собой кластеры, так и отдельные изолированные вершины.
Для более детального описания используется локальный коэффициент кластеризации, вычисляемый как отношение числа треугольников, в котором состоит актор, к числу треугольников в котором он бы мог состоять, если бы все его друзья были бы знакомы между собой. Если друзья актора не знают друг друга, то этот коэффициент оказывается равным 0, если все знакомы между собой – то 1. Таким образом, локальный коэффициент кластеризации может быть использован в качестве одной из характеристик отдельного актора.
Когда коэффициент кластеризации высокий – это означает, что граф чрезвычайно плотно сгруппирован вокруг нескольких узлов; когда он низкий – это значит, что связи в графе относительно равномерно распространены среди всех узлов.
Например, на следующей картинке коэффициент кластеризации равен 1/3 - потому что там могло бы быть три треугольника, а сложился только один.
Рассмотрим пример: Вершины A, B, C, D и O тесно связаны друг с другом, в то время как вершины H, J и F не связаны напрямую между собой. Таким образом, в графе выделяется один тесно связный кластер с высокими локальными коэффициентами показателей вершин, а также один мало связный кластер.

В анализе социальной сети основной единицей является диада. В неориентированных сетях диада - пара узлов, которые могут составлять социальные отношения друг с другом. В направленных графах, диада состоит из пары узлов, которые могут составлять социальные отношения через взаимные связи, невзаимное отношение или отсутствие отношения. Неприсоединение означает, что один узел интересуется другим узлом, но не наоборот. Триада - это набор из трех сторон, состоящих из трех диад.
Триада «замкнута», если все узлы связаны, в некотором роде, между собой. Закрытую триаду также называют треугольником.
Ранее было описано использование триад для анализа кластеризации графа, теперь же их можно использовать для анализа ссылок.

Типы открытых триад.

На приведенной иллюстрации все шаблоны взаимодействия - это открытые триады, где \(z\) - общий сосед \(u\) и \(v\). Вопросы, касающиеся прогнозирования ссылок, можно сформулировать следующим образом:

• Какова вероятность того, что \(u\) установит ссылку на \(v\)?
• Есть ли в частично наблюдаемой сети недостающее звено, указывающее на связь от \(u\) к \(v\)?

Замкнутые триады.

Определим триадную близость акторов \(u\) и \(v\) в направленном графе следующим образом \[ TC_{uv}=\sum\left\{\left.w^P(u,v,z)\times w(z)\right|z\in\Gamma(u)\bigcap\Gamma(v)\right\}, \] здесь оценка рассчитывается по всем общим соседям, причем для данного соседа \(z\), берется произведение веса \(w^P (u, v, z)\) на вес \(w (z)\) соседа. Вес триады \(w^P (u, v, z)\) определяется следующим образом: \[ w^P (u, v, z) = \frac{F (\bar{T} (u, v, z)) + F (\widetilde{T} (u, v, z))}{F (T (u, v, z))}, \] где функция \(T (u, v, z)\) возвращает идентификатор шаблона триады, который соответствует триаде с вершинами \(u\), \(v\) и \(z\). \(\bar{T}(u, v, z)\) идентификатор замкнутой триады, если замкнуто через u на v, аналогично, \(\widetilde{T}(u, v, z)\) в случае, если триада замкнута по взаимным связям между \(u\) и \(v\). Функция \(F (\cdot)\) возвращает частоту данного шаблона триады.
Вес \(w (z)\) устанавливается с учетом специфики конкретных социальных сетей, в общем случае берем \( w (z) = 1\).
Используя в качестве веса разные метрики сходства, мы можем решать разные задач, так, если установить больший вес менее связным соседям, то \(w(z)=\frac{1}{k_z}\) и тогда \[ TC_{uv}=\sum\left\{\left.w^P(u,v,z)\times \frac{1}{k_z}\right|z\in\Gamma(u)\bigcap\Gamma(v)\right\}. \] В этом случае популярные акторы (с высокой степенью \(k_z\)) не имеют большого значения для закрытия триад.

Пример.

Данная сеть.

ID	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Шаблон	\(u\leftrightarrow z \leftrightarrow v\)	\(u\leftrightarrow z\leftrightarrow v\leftrightarrow u\)	\(u\leftrightarrow z\rightarrow v\)	\(u\rightarrow z\leftrightarrow v\)	\(u\rightarrow z\rightarrow v\)	\(u\leftrightarrow z\leftarrow v\)	\(u\leftarrow z\leftrightarrow v\)	\(u\leftarrow z\leftarrow v\)	\(u\leftrightarrow z\leftarrow v\)	\(u\leftrightarrow z\rightarrow v\leftarrow u\)	\(u\leftarrow z\leftrightarrow v\rightarrow u\)	\(u\rightarrow z\leftarrow v\leftrightarrow u\)	\(u\leftrightarrow z\leftrightarrow v\leftarrow u\)	\(u\leftrightarrow z\leftrightarrow v\rightarrow u\)	\(u\rightarrow z\leftrightarrow v\leftrightarrow u\)	\(u\leftrightarrow z\leftarrow v\leftrightarrow u\)	\(u\leftarrow z\leftrightarrow v\leftrightarrow u\)
Частота	10	6	2	2	2	2	2	2	2	2	2	1	1	1	1	1	1

Вычислим значение триадной близости \(TC_{gh}\). Тогда \[ w^P(g,h,f)=\frac{6+1}{10}=0.7 \] и если \(w(f)=\frac{1}{k_f}=\frac{1}{4},\) то \(TC_{gh}=0.7\times \frac{1}{4}=0.175,\) тогда вероятность того, что триада от \(u\) до \(v\) будет замкнутой (ссылка от \(g\) дойдет до \(h\)), равна 0.175.

Процентное количество триад в популярных ориентированных (направленных) социальных сетях.

Данная модель опирается на следующий постулат: авторитет пользователя в сети определяется уровнем его знаний в данной области и это признается сообществом сети.
Рассмотрим задачу определения списка из \(k\) пользователей, наиболее авторитетных для данного актора, то есть, тех, к мнению которых данный актор будет прислушиваться.
В качестве исходных данных имеем информационный запрос \(Q\) данного пользователя \(P\). Приведем общую схему определения авторитетности пользователя относительно информационного запроса.

\(Q\leftarrow \) создание запроса пользователем \(Q\)
\(D\leftarrow \) получить профиль интересов пользователя \(Q\)
Для каждого пользователя \(u\in U\)
если интересы \(u\) лежат в профиле интересов \(D\), то
\(A(u)\leftarrow \) вычислить авторитетность пользователя \(u\) относительно запроса \(Q\)
Результат - список наиболее авторитетных людей, рекомендациям которых нужно следовать.

Персонализированный рейтинг.

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

Модель пользователь-репозитарий.

Пусть сообщество состоит из набора пользователей \(U = \{a, b, c\}\) и набора репозиториев \(R = \{e, f, g\}\). Взаимодействие пользователь-репозиторий можно смоделировать в виде ориентированного двудольного графа \(G_B (V_U, V_R, E_B)\), где \(V_U\) представляет собой набор пользователей и \(V_R\) - набор репозиториев. Ребро \((u, r) \in E_B\) устанавливается из \(u\) в \(r\), если \(u\) выполняет действие в \(r\). Вес \(w_{ur}\) ребра между \(u\) и \(r\) определяется на основе выполненных действий пользователя с данным репозиторием. Каждый репозиторий связан той или иной темой (это может быть направление увлечения - вязание, вышивание или тема научного исследования - математика, физика и пр.). Проводя действия с репозиторием, пользователь получает опыт в сфере интересов данной темы. Тогда,

• \(\{a, b\}\) - набор пользователей, которые приобрели опыт работы в направлении темы 1, потому что у них есть выполняемые действия в репозиториях \(e\) и \(f\).
• Пользователь \(b\) имеет опыт работы с темой 1 и темой 2, поскольку \(b\) выполнил действия в \(\{e, f, g\}\).
• Пользователи \(a\) и \(c\) - имеют опыт работы только с темой 1 и темой 2, соответственно.

Авторитетность можно оценить следующим образом \[ A(u)=\sum_{(u,r)\in E_B}H(r), H(r)=\sum_{(v,r)\in E_B}A(v). \] Пользователь \(u \in V_U\) имеет высокий авторитет, если \(u\) вносит вклад в важные репозитории. Репозиторий \(r \in V_R\) более важный, если авторитетные пользователи вносят в него свой вклад. Значение хранилища определяется значением \(H (r)\). Таким образом, чем важнее «хаб», тем больше он привлекает авторитетных пользователей.
Это рекурсивное определение важности пользователя и хранилища обеспечивает основу подхода к ранжированию. Однако, описанные оценки неустойчивы к малым возмущениям, что можно исправить, применяя следующую конструкцию \[ A(u)=(1-\lambda_a)p(u)+\lambda_a\sum_{(u,r)\in E_B}H(r), \] \[ H(r)=(1-\lambda_h)p(r)+\lambda_h\sum_{(v,r)\in E_B}A(v). \] Здесь \(p (u)\) и \(p (r)\) представляют собой параметры персонализации, которые могут быть назначены равномерно для каждого узла \[p (u) =\frac{1}{| V_U |} , p (r) = \frac{1}{ |V_R |}.\] А вот неравномерные параметры персонализации приводят к персонализированному ранжированию.
Параметры λ_a и λ_h позволяют балансировать между полномочиями / весами концентратора и весами персонализации. Типичное значение \(\lambda\) (0 ≤ λ ≤ 1) составляет 0,85. Присвоение меньших значений λ означает, что большее значение имеют веса персонализации, тем самым уменьшая «сетевой эффект» ранжирования.
Идея подхода к персонализированному авторитету - это вычисление рейтинга оценки в отношении определенных областей интересов. Определение области интересов передается через ключевой запрос \(Q = \{q_1, q_2, ..., q_n\}\) алгоритму ранжирования. Каждое ключевое слово \(q_n\) запроса соответствует интересующей области, например, \(Q =\) {"социальные сети", "data mining"}. Запрос возвращает ранжированный список людей на основе требуемого набора интересов.
Тогда, с учетом областей интересов, определяемых информационным запросом, имеем \[ A(u,Q)=(1-\lambda_a)p(u,Q)+\lambda_a\sum_{(u,r)\in E_B}H(r,Q), \] \[ H(r,Q)=(1-\lambda_h)p(r,Q)+\lambda_h\sum_{(v,r)\in E_B}A(v,Q). \] Важность репозитория \(r\) относительно запроса Q, при максимальной важности персонализации, то есть, при \(\lambda_h=1\), вычисляется следующим образом \[ H(r,Q)=\sum_{(v,r)\in E_B}w_{v,r}A(v,Q) \] и, соответственно, \[ A(u,Q)=(1-\lambda)p(u,Q)+\lambda\sum_{(u,r)\in E_B}\sum_{(v,r)\in E_B}w_{u,r}w_{v,r}A(v,Q). \] Тогда, учитывая вес каждого ключевого слова информационного запроса, получаем \[ A(u,Q)=(1-\lambda)\sum_{q\in Q}w_{q}p(u,q)+\lambda\sum_{(u,r)\in E_B}\sum_{(v,r)\in E_B}\sum_{q\in Q}w_{q}w_{u,r}w_{v,r}A(v,q). \] Вес \(w_q\) связан с конкретным ключевым словом \(q\), к примеру, \(w_q = \frac{1}{| Q|}\) для случая равномерных весов и \(\sum_qw_q=1\).
Отсюда получаем цепочку соотношений \[ A(u,Q)=\sum_{q\in Q}w_{q}(1-\lambda)p(u,q)+\sum_{q\in Q}\lambda\sum_{(u,r)\in E_B}\sum_{(v,r)\in E_B}w_{q}w_{u,r}w_{v,r}A(v,q)= \] \[ =\sum_{q\in Q}w_{q}\left[(1-\lambda)p(u,q)+\lambda\sum_{(u,r)\in E_B}\sum_{(v,r)\in E_B}w_{u,r}w_{v,r}A(v,q)\right]= \] \[ =\sum_{q\in Q}w_{q}A(u,q). \] Вес \(w_{u,r}\), который не является персонализированным или «зависимым от контекста», рассчитывается следующим образом: \[ w_{u,r}=\frac{\sum_{t\in T}f(u,r,t)}{\sum_{z\in R(u)}\sum_{t\in T}f(u,z,t)}. \] Множество T обозначает типы событий (т.е. тип действия пользователя). Множество \(R (u)\) представляет собой все репозитории \(u\), которые связаны с \(G_B\) (соседей \(u\)). Функция \(f (u, r, t)\) извлекает счетчик реализации пользователем \(u\) в репозитории \(r\) события типа \(t\).
Пусть α - область интересов, а p(u,α) - соответствующий параметр персонализации для пользователей. Далее, пусть R(u,α) = match (u,α) - множество репозиториев u, соответствующих области интереса α.
Определим параметр персонализации p(u,α) следующим образом \[ p(u,\alpha)=w_1\sum_{r\in R(u,\alpha)}w_{u,r}+w_2\frac{k_{i,n}(u,G)}{\sum_{v\in V_U}k_{i,n}(v,G)}, \] где \(w_1 + w_2 = 1\).
Первая часть этого соотношения \(\sum_{r\in R(u,\alpha)}w_{u,r}\) определяет вес области интересов к p (u; α). Если данный пользователь выполняет много действий в репозиториях, связанных с областью интересов (то есть с R (u, α)), то вес области будет больше. Если одна область интересов будет более важной, чем другая, то, соответственно, \(w_1> w_2\).
Вторая часть \({k_{i,n}(u,G)}/{\sum_{v\in V_U}k_{i,n}(v,G)}\)- удельный вес областей, лежащих вне интереса информационного запроса. Здесь \(k_{i,n} (u, G)\) - степень неопределенности \(u\) (число пользователей, связанных с актором) в графе \(G.\) Этот вес повышает вероятность того, что если данная область интересна пользователям с высокой репутацией, то это будет важно и для конкретного пользователя.
Таким образом, имея информационный запрос и зная, для каждого ключевого слова, важность хранилища (хаба) и авторитетность пользователей, использующих данное хранилище, мы можем оценить их влияние на конкретного пользователя.

Рассмотрим взаимодействие между партнерами сообщества. Заметим, что партнерами могут быть не только конкретные пользователи, но и группы пользователей, объединенные общностью интересов.

Партнерская (коллаборативная) модель.

Пусть имеем набор партнеров \(\{o_1, o_2, o_3\}\) и набор проектов (темы областей интересов) \(\{p_1, p_2, p_3\}\). Каждый проект связан с определенной темой, которая определяет контекст сотрудничества. Партнеры, участвующие в проектах, выполняют определенные роли. Роли включают координатора (модератора) проекта и партнера по проекту. Степень участия определяется весом. Например, \(o_1\) участвует в проектах \(p_1\) и \(p_2\) с весами \(w_{1,1}\) и \(w_{2,1}\) соответственно.
Построим модель взаимоотношений на основе совместных проектов, осуществляемых партнерами. Поскольку \(o_1\) и \(o_2\) были вовлечены в совместные проекты \(p_1\) и \(p_2\), то между \(o_1\) и \(o_2\) установлена связь сотрудничества (пунктирная линия). Аналогично, \(o_2\) и \(o_3\) участвуют в совместных проектах \(p_2\) и \(p_3\) и, следовательно, установлена связь между \(o_2\) и \(o_3\). Также существует сотрудничество между \(o_1\) и \(o_3\), потому что они совместно работали над \(p_2\).
Для построения модели партнерского взаимодействия, используем тот же подход, что и в предыдущем случае.
Проект считается важным, если партнеры, вносящие вклад в развитие этого проекта, также считаются важными (знающими, авторитетными). В свою очередь, важность партнера основывается на его участии в важных проектах. Это рекурсивное определение важности и может быть смоделировано с использованием интуитивного представления о концентраторах и полномочиях. \[ A(o)=\sum_{(p,o)\in E_P}H(p), \] \[ H(p)=\sum_{(p,u)\in E_P}A(u). \] Здесь партнер \(o\) получает оценку \(A (o)\), а проект \(p\) оценку хаба \(H (p)\). Недостатком этой модели является «стабильность» ранжирования, то есть алгоритм возвращает аналогичные результаты при малых возмущениях, поэтому рассмотрим обобщение этой модели: \[ A(o)=(1-\lambda_a)\delta_O(o)+\lambda_a\sum_{(p,o)\in E_P}H(p), \] \[ H(p)=(1-\lambda_h)\delta_P(p)+\lambda_h\sum_{(p,u)\in E_P}A(u). \] Здесь \(\delta_O(o)\) и \(\delta_P(p)\) представляют собой параметры персонализации, которые в равномерном случае для каждого узла равны \[\delta_O(o) =\frac{1}{| V_O |} , \delta_p(P) = \frac{1}{ |V_P |}.\] Неравномерные параметры персонализации приводят к персонализированному ранжированию. Параметры λ_a и λ_h с 0 ≤ λ ≤ 1 позволяют балансировать между полномочиями / концентраторами веса и веса персонализации. Типичное значение для λ равно 0,85. Применение малых значений λ означает, что более важная роль придается персонализации.
Определим критерии, зависящие от информационного запроса: \[ A(o,Q)=(1-\lambda_a)\delta_O(o,Q)+\lambda_a\sum_{(p,o)\in E_P}H(p,Q), \] и \[ H(p,Q)=(1-\lambda_h)\delta_P(p,Q)+\lambda_h\sum_{(p,u)\in E_P}A(u,Q). \] Веса \(w_{p,o}\) и \(w_{p,u}\) определяют степень участия партнеров в проекте. В частности, вес \(w_{p,o}\) основан на вкладе (финансировании, количестве участников и их квалификации) партнера \(o\) в проекте \(p\): \[ w_{p,o}=\frac{вклад(p,o)}{\sum_{v\in Adj(p)}вклад(p,v)}, \] где \(Adj (p)\) множество узлов, смежных (adjacent) с \(p\) (т.е. множество партнеров, принимающих участие в проекте \(p\)).
Найдем оценку авторитетности, для чего подставим в \(A(o,Q)\) значение \(H(p,Q\): \[ A(o,Q)=(1-\lambda_a)\delta_O(o,Q)+\lambda_a(1-\lambda_h)\sum_{(p,o)\in E_P}w_{p,o}\delta_P(p,Q)+ \lambda_a\lambda_h\sum_{(p,o)\in E_P}\sum_{(p,u)\in E_P}w_{p,o}w_{p,u}A(u,Q) \] и определим параметр персонализации \(\tilde{\delta}_O(o,Q)\) следующим образом \[ \tilde{\delta}_O(o,Q)=\frac{1-\lambda_a}{1-\lambda_h}\delta_O(o,Q)+\lambda_a\sum_{(p,o)\in E_P}w_{p,o}\delta_P(p,Q). \] Если будем считать, что влияние важности партнера равно влиянию важности проекта, то есть \(\lambda_a=\lambda_h=\lambda\), то \[ \tilde{\delta}_O(o,Q)=\delta_O(o,Q)+\lambda\sum_{(p,o)\in E_P}w_{p,o}\delta_P(p,Q) \] и \[ A(o,Q)=(1-\lambda)\tilde{\delta}_O(o,Q)+\lambda^2\sum_{(p,o)\in E_P}\sum_{(p,u)\in E_P}w_{p,o}w_{p,u}A(u,Q). \] Пусть каждое ключевое слово информационного запроса \(Q=\{q_1,q_2,...,q_n\}\) ассоциировано с весом \(w_q=\frac{1}{|Q|}\) и \(\sum_{q\in Q}w_q=1\), тогда \[ A(o,Q)=(1-\lambda)\tilde{\delta}_O(o,Q)+\lambda^2\sum_{(p,o)\in E_P}\sum_{(p,u)\in E_P}w_{p,o}w_{p,u}A(u,Q)= \] \[= (1-\lambda)\sum_{q\in Q}w_q\tilde{\delta}_O(o,q)+\lambda^2\sum_{(p,o)\in E_P}\sum_{(p,u)\in E_P}\sum_{q\in Q}w_qw_{p,o}w_{p,u}A(u,q)= \] \[= \sum_{q\in Q}w_q(1-\lambda)\tilde{\delta}_O(o,q)+\sum_{q\in Q}w_q\lambda^2\sum_{(p,o)\in E_P}\sum_{(p,u)\in E_P}w_{p,o}w_{p,u}A(u,q)= \] \[ =\sum_{q\in Q}w_q\left((1-\lambda)\tilde{\delta}_O(o,q)+\lambda^2\sum_{(p,o)\in E_P}\sum_{(p,u)\in E_P}w_{p,o}w_{p,u}A(u,q)\right)= \sum_{q\in Q}w_qA(o,q). \] Заметим, что полученные модели не зависят от поведения пользователей по отношению к временной шкале. Но этот недостаток легко исправить, если сделать веса зависимыми от активности пользователей в разное время (как правило, единицей измерения является год).

Задача 1.

Каратэ-клуб Захари (Zachary's karate club) - социальная сеть, описанная в статье Уэйн У. Захари "An Information Flow Model for Conflict and Fission in Small Groups".
Социальная сеть клуба каратэ изучалась Уэйном У. Захари в течение трех лет с 1970 по 1972 год. Сеть захватывает 34 члена клуба каратэ через описание 78 парных связей между членами, которые взаимодействовали вне клуба. В ходе исследования возник конфликт между администратором «Джон А» и инструктором «Мистер Хи» (псевдонимы), что привело к расколу клуба на два.
Узел 1 обозначает инструктора, узел 34 -администратора/президента клуба.

[2 1]
[3 1] [3 2]
[4 1] [4 2] [4 3]
[5 1]
[6 1]
[7 1] [7 5] [7 6]
[8 1] [8 2] [8 3] [8 4]
[9 1] [9 3]
[10 3]
[11 1] [11 5] [11 6]
[12 1]
[13 1] [13 4]
[14 1] [14 2] [14 3] [14 4]
[17 6] [17 7]
[18 1] [18 2]
[20 1] [20 2]
[22 1] [22 2]
[26 24] [26 25]
[28 3] [28 24] [28 25]
[29 3]
[30 24] [30 27]
[31 2] [31 9]
[32 1] [32 25] [32 26] [32 29]
[33 3] [33 9] [33 15] [33 16] [33 19] [33 21] [33 23] [33 24] [33 30] [33 31] [33 32]
[34 9] [34 10] [34 14] [34 15] [34 16] [34 19] [34 20] [34 21] [34 23] [34 24] [34 27] [34 28] [34 29] [34 30] [34 31] [34 32] [34 33]

Социальная сеть карате-клуб.

Найти наиболее вероятное разбиение членов клуба на два коллектива и сравнить с тем, как все произошло в реальности.
Замечание. Модель, полученная Захари, неправильно распределила участника сети под номером 9.

Задача 2.

• Отдел 1 (D1) состоит из Snopp, Gukrishnan, Leon и Kabutz. Snopp отчитывается перед Chapman.
• Отдел 2 (D2) состоит из Oliver, Gotti, Patrick и Zhuo. Oliver отчитывается перед Chapman.
• Отдел 3 (D3) состоит из Gotti, Leon и Kabutz. Gotti отчитывается перед Chapman.
• Отдел 4 (D4) состоит из следующих проектных групп, которые отчитываются перед Yu. Yu отчитывается перед Chapman об этом проекте.
  • Группа 4a (D4a) состоит из Polark, Chang, Weng и Angel. Polark отчитывается перед Yu.
  • Группа 4b (D4b) состоит из Christoph, Nardo, Gotti и Zhuo. Christoph отчитывается перед Yu.
  • Группа 4c (D4c) состоит из Graffe, Zhuo и Hund. Graffe отчитывается перед Yu.

Группы проектов в исследовательском отделе.

Распределить сотрудников по степени влияния.

Задача 3.

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

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