ПРОБЛЕМЫ АНАЛИЗА КОМПЬЮТЕРНЫХ СОЦИАЛЬНЫХ СЕТЕЙ

АННОТАЦИЯ

Социальные сети, такие как Twitter, Вконтакте, LinkedIn и Facebook становятся все более популярным средством коммуникации. В последние годы число мультимедийных сетей, таких как Flickr, также растет. Такие социальные сети богаты контентом, и они, как правило, содержат огромное количество информации и данные взаимосвязей, которые можно использовать для анализа. Данные взаимосвязей представляют собой граф, в котором пользователи являются вершинами а связь между ними ребрами графа. Данные контента содержат текст, изображения и другие мультимедийные данные в сети. Все эти данные обеспечивают беспрецедентные возможности для анализа данных в контексте социальных сетей. В данной статье описаны виды социальных сетей и основные проблемы анализа социальных сетей.

Ключевые слова: Социальные сети, анализ социальных сетей, контент сети, динамические сети.

В статье представлено введение в тему социальных сетей и проблемы анализа социальных сетей. Социальные сети стали очень популярными в последние годы из-за растущего и доступности интернет-устройств, таких как персональные компьютеры, мобильные устройства и другие новейшие аппаратные инновации, такие как планшеты и т. д. Об этом свидетельствует растущая популярность многих онлайн-социальных сетей, таких как Twitter, Вконтакте, Facebook и LinkedIn. В таких сетях содержится огромное количество сетевых данных. Социальные сети могут быть как Facebook, которые явно предназначены для социальных взаимодействий, или такие как Flickr, которые предназначены для совместного использования контента, но они также позволяют пользователям взаимодействовать друг с другом в онлайн режиме. В общем, социальная сеть определяется как сеть взаимодействий или отношений, где узлы состоят из актеров, а ребра состоят из отношений или взаимодействий между этими участниками.

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

В статье приведен обзор по проблемам анализа социальных сетей: перечислены основные направления исследований в этой области; описаны полезные при изучении социальных сетей характеристики; приведено описание наиболее популярных социальных сетей; намечены некоторые возможные пути дальнейших исследований.

Проблемы анализа компьютерных социальных сетей

В последние годы в компьютерных социальных сетей наблюдается рост пользователей. Ключевым аспектом многих социальных сетей в Интернете является то, что они богаты данными и дают возможность для интеллектуального анализа данных. Существует два основных вида данных, которые часто анализируются в контексте социальных сетей: анализ на основе связей и структурный анализ: при анализе на основе связей и структурном анализе мы строим анализ поведения связи сети, чтобы определить важные узлы , сообщества, ссылки и развивающиеся регионы сети. Такой анализ дает хороший обзор глобального эволюционного поведения сети. Можно выделить анализ на основе контента. Ммногие социальные сети, такие как Flickr, Message Networks и Youtube, содержат огромное количество контента, которое можно использовать для повышения качества анализа. Например, сайт для обмена фотографиями Flickr, содержит огромное количество информации о тексте и изображении в виде пользова­тельских тегов и изображений. Аналогично, сети блога, сети электронной почты и доски объявлений содержат текстовое содержимое, которое связано друг с другом. Было замечено что, анализ на основе контента с помощью анализа на основе связей обеспечивает более эффективные результаты в самых разных приложениях.

Есть еще проблемы, которые возникают в алгоритмах социальной сети является то, что между это динамическое изменение социальной сети. В случае статического анализа мы предполагаем, что социальная сеть медленно меняется с течением времени, и мы проводим анализ всей сети в пакетном режиме по временным данным. Это такие как библиографические сети, в которых новые события в сети могут происходить только медленно с течением времени. С другой стороны, в случае многих сетей, таких как сети обмена мгновенными сообщениями, взаимодействия непрерывно принимаются с течением времени с очень большой скоростью, что может привести к сетевым потокам. Анализ таких сетей является гораздо более сложным и является предметом недавних исследований [2-5]. Временной аспект сетей часто возникает в контексте динамичных и развивающихся сценариев. Могут быть определены многие интересные временные характеристики сетей, такие как развивающиеся сообщества, взаимодействия между сущностями и временные события в базовой сети.

Динамические сети также возникают в мобильных приложениях, в которых объекты постоянно взаимодействуют друг с другом. Например, многие мобильные телефоны оснащены приемниками GPS, которые используются приложениями на этих телефонах. Классическим примером такого приложения является приложение Latitude, которое позволяет отслеживать местоположение разных пользователей и выдавать предупреждения, когда данный пользователь находится поблизости. Такие динамические социальные сети могут быть смоде­лированы как динамические графики, для которых ребра постоянно изменяются с течением времени. Такие динамические графики приводят к серьезным проблемам при обработке из-за чрезвычайно большого количества соединений между объектами, которые необходимо отслеживать одновременно. В таких случаях для эффективного онлайн-анализа требуются приложения для обработки потока графа. Такие приложения, как правило, требуют, чтобы они могли суммировать сетевую структуру данных в реальном времени и использовать ее для различных приложений. Некоторые такие исследования описываются в [1, 3].

Наиболее известной структурной проблемой в социальных сетях является проблема обнаружения сообщества. Проблема обнаружения сообщества тесно связана с проблемой поиска структурно связанных групп в сети. Эти структурно связанные группы называются сооб­ществами. Некоторые известные методы обнаружения сообществ предложены в [6, 7, 8]. Проблема обнаружения сообществ возникает как в статической сети, где сеть медленно меняется с течением времени, так и в динамической, в которой структура сети быстро развивается. Хотя эти проблемы были изучены в традиционной литературе в контексте проблемы разделения графов [8].

Социальные сети можно рассматривать как структуру, которая позволяет распространять информацию. Анализ динамики такого взаимодействия является сложной проблемой в области социальных сетей. Например, важные новости распространяются через сеть с использованием взаимодействий между различными объектами. Хорошо известную модель распространения влияния можно найти в [10]. Проблема анализа влияния очень актуальна в контексте социальных сетей, особенно в контексте определения наиболее влиятельных членов социальной сети, которые, скорее всего, будут распространять свое влияние на другие субъекты социальной сети [9]. Наиболее влиятельные члены социальной сети могут быть определены с исполь­зованием моделей потоков, как в [9], или с использованием методов стиля страницы, которые определяют наиболее хорошо связанные объекты в социальной сети.

Наконец, важным классом методов является вывод ссылок, которые еще не известны в социальных сетях. Эта проблема упоминается как проблема ссылки [11]. Проблема прогнозирования ссылок полезна для определения важных будущих связей в базовой социальной сети. Такие будущие связи дают представление о будущих отношениях или отсутствующих отношениях в социальной сети. Прогнозирование ссылок также полезно в ряде вспомогательных приложений, в которых человек не полностью знает связи в вражеской или террористической сети и использует автоматизированные методы интеллектуального анализа данных, чтобы оценить основные характеристики.

Некоторые наиболее известные социальные сети

По числу пользователей к крупнейшим компьютерным социаль­ным сетям относятся [Социальная cеть, 2012; List of social networking websites, 2012]: Twitter, LinkedIn, Facebook, ВКонтакте, YouTube и др.

Facebook. Сеть основана Марком Цукербергом в 2004 году. По данным за апрель 2012 [U. S. Securities and Exchange Commission, 2012] количество пользователей Facebook составляет 901 млн. Каждый день пользователи в сети оставляют 3,2 млрд. комментариев и «лайков» и публикуют 300 млн. фотографий. Facebook позволяет создать профиль с информацией о себе и фотографией, приглашать друзей, обмениваться сообщениями, менять свой статус, оставлять комментарии на своей и чужой «стенах», загружать видеозаписи и фотографии, создавать сообщества (группы по интересам). Есть возможность самим создавать приложения (игры, средства обмена фотографиями и музыкой и т. д.), что повышает посещаемость сайта.

YouTube. Сервис, который предоставляет услуги видеохостинга, основан в 2005 году. Пользователи могут просматривать, комменти­ровать, добавлять видеозаписи, добавлять титры, аннотации к видео, а также можно сделать рейтинг просмотренным видео, если эту возможность предоставил автор. Благодаря простоте и удобству использования YouTube стал популярным видеохостингом и третьим сайтом в мире по количеству посетителей на июнь 2012.

LinkedIn. Социальная сеть основана в декабре 2002 года Ридом Хоффманом, запущена в мае 2003 года. Сеть используется для поиска и установления деловых контактов. По данным на февраль 2012 года [LinkedIn – Press Center, 2012] в LinkedIn зарегистрировано свыше 160 млн. пользователей.

ВКонтакте. Социальная сеть основана Павлом Дуровым в 2006 году. На март 2012 года [ВКонтакте, 2012] аудитория ВКонтакте около 150 млн. пользователей, около 70 % проживают в России. Как и Facebook, пользователи ВКонтакте могут обмениваться сообще­ниями публично (с помощью записей на «стене», а также через механизм групп и встреч) и приватно (через личные сообщения), отслеживать через ленту новостей активность друзей и сообществ. В сети также есть возможность обмена и загрузки файлов большого объема, т. к. используется технология распределенного распространения файлов BitTorrent, что делает ВКонтакте одним из крупнейших медиа-архивов Рунета. Facebook,

Twitter. Создана социальная сеть Джеком Дорси в 2006 году. По состоянию на начало 2012 года, сервис насчитывает более 140 млн. пользователей [Twitter, 2012]. Ежедневно участники отправляют около 340 млн. сообщений. Система позволяет отправлять короткие текстовые сообщения (до 140 символов), используя web-интерфейс, SMS, средства мгновенного обмена сообщениями или сторонние клиент-программы. Отличительной особенностью Twitter является публичная доступность размещенных сообщений, что позволяет называть его микроблогом. С 2011 года Twitter перешел с MySQL на Lucene и с Ruby on Rails на Java и Scala для повышения производительности и масштабируемости.

Выводы и будущие направления

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

Контент-анализ: многие из прошлых исследований в этой области были основаны на структурном анализе социальных сетей. Такой анализ в основном использует структуру связей только для того, чтобы вывести интересные характеристики базовой сети. Некоторые недавние исследования [10] показали, что включение информации о контенте может дать ценную информацию о базовой социальной сети. Например, контент на данном узле может предоставить больше информации об экспертизе и интересах соответствующего субъекта.

Временный анализ. Большинство исследований в социальных сетях основаны на статических сетях. Однако ряд недавних исследо­ваний [6, 7, 8] показали, что включение временной эволюции в сетевой анализ значительно улучшает качество результатов. Поэтому предстоит еще немалая работа по динамическому анализу социальных сетей, которые быстро развиваются с течением времени.

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

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

Список литературы:

1. C.C. Aggarwal, H. Wang. Managing and Mining Graph Data, Springer, 2010.
2. C.C. Aggarwal.P. Yu. Online Analysis of Community Evolution over Data Streams, SIAM Conference on Data Mining, 2005, P.81-93.
3. C.C. Aggarwal, Y. Zhao, P. Yu. On Clustering Graph Streams, SIAM Conference on Data Mining, 2010, P.478-489.
4. C.C. Aggarwal, Y. Li, P. Yu, R. Jin. On Dense Pattern Mining in Graph Streams, VLDB Conference, 2010. P.975-984.
5. C.C. Aggarwal, Y. Zhao, P. Yu. Outlier Detection in Graph Streams, ICDE Conference, 2011. P.399-409.
6. D. Chakrabarti, R. Kumar, A. Tomkins. Evolutionary Clustering, ACM KDD Conference, 2000. P. 554-560.
7. Y. Chi, X. Song, D. Zhou, K. Hino, B.L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. KDD Conference, 2007. P. 153-162.
8. Y.-R. Lin, Y. Chi, S. Zhu, H. Sundaram, B.L. Tseng. FacetNet: A framework for analyzing communities and their evolutions in dynamic networks. Refereed Track: Social Networks & Web 2.0 - Discovery and Evolution of Communities, 2008. P. 685-694.
9. D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Infuence in a Social Network, ACM KDD Conference, 2003. P.137-146. 
10. B.W. Kernighan, S. Lin, An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal, 1970.P. 291 - 307.
11. D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. In LinkKDD, 2004.P.110-122.
12. M.E. J. Newman. The spread of epidemic disease on networks, Phys.Rev. E 66, 016128, 2002.
13. Y. Zhou, H. Cheng, and J.X. Yu. Graph clustering based on structural/ attribute similarities. PVLDB, 2(1): 2009. P. 718–729.