Обратная связь
crowdsourcing DARPA Enterprise 2.0 facilitator Gartner Google IBM idea management Imaginatik knowledge management open innovation social business Social Organization Social Platforms Spigit tacit knowledge wit-проект Witology Агенство стратегических инициатив бизнес-лига Деятельное сообщество инвестиции инновации кейсы коллективный интеллект команда Witology краудрекрутинг краудсорсеры краудсорсинг краудсорсинг-проект краудсорсинг-проекты краудфандинг менеджмент идей метаразум методология мотивация Национальная предпринимательская инициатива НПИ облачное предприятие облачные предприятия общественное благо открытые инновации отчеты предсказания приз производство знаний публикации краудсорсеров рынки предсказаний Сбербанк семинар синтеллектуальный краудсорсинг Социально-семантические сети Социальное предприятие социальные платформы социальные сети социальные технологии Социальный бизнес социо-семантическая сеть ТеМП фасилитатор футбол эпоха социализации и коллаборативизации

Сказ о том, как Леша граф нашел

Просмотров2774
Комментариев0

d36e68c4fa441f48dda121af5eaac55b.jpg
Билибин И. Я. Иллюстрация к «Сказке об Иване-царевиче, Жар-птице и о Сером волке», фрагмент


В последнее время сложно найти четверг, в который бы не был проведен семинар отдела моделей и алгоритмов компании Witology. Восьмого сентября такой семинар был посвящен анализу графов социальных связей. Один из стажеров отдела, Алексей Милованов, анализировавший графы, построенные по данным группы «В Контакте», рассказал о результатах, которые ему удалось получить и которые вообще можно получить, анализируя графы социальных сетей. А прямо перед этим слушатели узнали также об алгоритмах самого анализа и характеристиках графов, которые могут быть полезны при изучении социальных связей, еще от одного стажера, Анастасии Беззубцевой.

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

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

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

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

PageRank – это, вообще говоря, один из алгоритмов Google, применяющихся при ранжировании страниц в поиске. Согласно ему каждой странице (вершине графа в данном случае) присваивается вещественное значение от 0 до 10, вычисляемое по формуле, которую Google никому не говорит. Известно только, что в PageRank страницы помимо числа ссылок на нее (степени вершины) учитывается качество самих ссылающихся страниц (вершин, связанных с ней). Алексей же воспользовался одной из вариаций примерной формулы индекса:

166bc6c94a3543bf8127844ef114dbb5.png
где константа 0,15 – поправка на то, что пользователь может попасть на страницу совершенно случайно и необъяснимо, v – вершина, для которой вычисляется индекс, ti – вершины, связанные с v , PR ( ti ) – PageRank вершины ti , С( ti ) – число ссылок со страницы ti , т.е. степень ti по исходящим дугам, n – число вершин ti , N – число вершин  в графе.

Другой нетривиальный показатель важности вершин графа – центральность по посредничеству (betweenness centrality). Такая центральность, в отличие от центральности по степени (нормированному по размеру графа значению степени вершины) или престижа вершины (нормированному значению in-degree, степени по входящим дугам), показывает, насколько важен участник как посредник при взаимодействии остальных. Индекс центральности по посредничеству в ненормированном виде выглядит так:

f006cb9fb7f8f2434e6da04d450a244d.png
σ st — число кратчайших путей из некой вершины s в вершину t графа V, а σ st ( v ) – число таких путей, проходящих через  вершину v. Существуют мнения, что показатель центральности по посредничеству нормировать вредно, так как участник может являться важным посредником по абсолютному значению индекса (например, он знает 11 врачей), но непонятно кем после нормировки, особенно если граф очень большой (11 человек – капля в море всех существующих врачей). Однако при наличии нескольких графов разного размера можно делить абсолютный показатель центральности на acf746e15313b18e201c6c21379f8e61.png где n – число вершин, и сравнивать уже нормированные индексы вершин разных графов, если возникнет такая потребность.
Помимо центральных вершин были выделены также точки сочленения графа сообщений (всего 144) – такие вершины, при удалении которых нарушается связность графа (граф связен, если из любой вершины существует путь в любую другую вершину, в зависимости от того, ориентирован этот путь или нет, связность может быть сильной, односторонней и слабой). В итоге, с учетом всех подходов к выделению особенных вершин, в графе обнаружилось несколько «важных» участников.

Другая большая часть анализа графа, проведенного Лешей, – выделение групп участников. Самое нестрогое понятие группы – это компонента связности (связный подграф несвязного графа). Не только граф сообщений, но и граф друзей оказались несвязными, однако в обоих присутствуют одна большая компонента связности и несколько мелких (размером от 2 до 10 вершин). Самая же строгая группа, которую можно выделить в графе, – клика (полный подграф, т.е. подграф, в котором любые две вершины связаны ребром), клику легко разрушить, удалив любое ребро, что далеко не всегда верно для предыдущего понятия группы. Максимальными кликами графа сообщений стали 6 клик с 7 вершинами в каждой, причем оказалось, что все они пересекаются в как минимум трех вершинах. Группами можно также считать k-ядра графа (максимальные подграфы, степени вершин в которых  не меньше k). Максимальное k, для которого в графе сообщений нашлось такое ядро, равно 7, а число вершин в ядре – 23. Интерпретировать такое ядро можно как компанию людей, каждый из которых общается не менее чем с семью другими членами этой компании – что-то вроде очень дружного школьного класса или рабочего отдела.

Ну а самый популярный способ искать группы где бы то ни было – кластеризация, выделение объектов, сходным по каким-либо характеристикам. Методов кластеризации очень много, и Алексей опробовал некоторые на графе сообщений:

– по компонентам связности (получилось 6 кластеров – компонент связности);
– по матрице расстояний: были взяты 10 наиболее далеких друг от друга вершин (расстояние – не меньше 5), вокруг которых формировались кластеры величиной от 6 до 250 из ближайших к ним вершин;
– минимальным разрезом Штор-Вагнера: в графе были найдены разрезы (разбиения графа на два множества вершин), такие, что сумма весов ребер, по которым проходит разрез, минимальна. После обнаружения очередного минимального разреза Леша менял веса ребер, по которым разрез проходил, на бесконечность, и продолжал резню.  В итоге граф разрезало на 91 кластер с числом вершин от 2 до 13, таким образом выделились группы, которые активно общаются внутри себя (веса ребер внутри велики), но не особо интересуются остальными (веса ребер границы разреза малы).

Не были оставлены без внимания Алексеем и такие общие характеристики графов и их структуры, как, например, диаметр и коэффициент кластеризации. Диаметр наибольшей компоненты связности графа сообщений, равный 13 (а в общем случае наибольшему расстоянию между двумя вершинами), расходится с теорией шести рукопожатий и с данными, согласно которым «В Контакте» длины цепочек, связывающих любых людей, даже короче, чем 6. Однако, в процессе обсуждения этого вопроса на семинаре было решено, что, возможно, бессмысленно сравнивать граф обсуждения в группе и граф связей через знакомых. Кроме того, вообще говоря, диаметр всего графа обсуждения равен бесконечности из-за несвязности, и не стоит увлекаться поиском смысла числа 13.

Коэффициент кластеризации – понятие, слабо связанное с кластеризацией – показывает долю клик размера три в общем числе связанных троек вершин. Иными словами, он считает вероятность того, что люди, имеющие общего друга, дружат между собой. Коэффициенты графов друзей и сообщений в данном случае оказались равными 0,03 и 0,02, что мало, но все-таки говорит о неслучайности взаимодействия участников.

Как же выводы,  полученные Лешей, можно распространить на гипотетический граф взаимоотношений в рамках платформы Witology? Из диаграммы ниже видно, что более половины тех, кто комментировал в группе с указанием адресата, общались с помощью единственного сообщения, а заметную активность проявляли не более 5% этих людей. Такие величины ожидаемы для группы «В Контакте», общение же в социальной сети внутри организации должно быть более интенсивным. Из-за того же более тесного взаимодействия сотрудников организации меньшим должен оказаться диаметр графа, большими – коэффициенты кластеризации (в том числе из-за того, что граф, скорее всего, окажется связным).

d50aed94a799231309b54e8983a09a03.png

Автор текста: Анастасия Беззубцева

  • Опубликовать в Facebook
avatar

Darya Goncharova

Senior Analyst, Project Department