Жизнь человека в современном обществе неразрывно связано с большим количеством данных, в том числе с социальными сетями. Количество пользователей в различных социальных сетях ежедневно растет, а сами социальные сети являются не только «площадкой» для общения, но и доступным политическим, идеологическим и экономическим инструментом. Именно поэтому анализ данных, представляемых в социальных сетях, порождает большой интерес разных исследователей и в настоящее время является одной из важных тем различных научных работ.
Любая социальная сеть имеет ряд схожих особенностей, которые важны для анализа данных, содержащихся в них. Так как данная статья направлена на анализ сети, представляющей собой связи людей, то важными являются следующие факты о социальных сетях:
1. Большинство графов, формируемых из реальных сетей, являются разреженными, то есть количество ребер пропорционально количеству узлов. Это означает, что большинство пользователей не будут формировать большое количество ссылок, даже если размер сети очень велик.
2. Люди, чаще всего взаимодействуют с похожими людьми. Это может относиться к таким наблюдаемым характеристикам, как пол, возраст, раса, доход, регион проживания и другие данные.
3. Многие социальные сети демонстрируют естественную кластеризацию: если два человека имеют связь с общим другом, вероятно, они тоже связаны друг с другом.
1. Большинство графов, формируемых из реальных сетей, являются разреженными, то есть количество ребер пропорционально количеству узлов. Это означает, что большинство пользователей не будут формировать большое количество ссылок, даже если размер сети очень велик.
2. Люди, чаще всего взаимодействуют с похожими людьми. Это может относиться к таким наблюдаемым характеристикам, как пол, возраст, раса, доход, регион проживания и другие данные.
3. Многие социальные сети демонстрируют естественную кластеризацию: если два человека имеют связь с общим другом, вероятно, они тоже связаны друг с другом.
Обнаружение сообществ важно для анализа социальных сетей, поскольку с большой степенью вероятности можно утверждать, что узлы в одном сообществе имеют одинаковые свойства. Методы обнаружения сообществ в социальных сетях аналогичны методам и алгоритмам, используемым при разбиении графов на кластеры. Сообщества - это функциональные единицы сети, которые имеют тесные связи внутри, но слабо связаны с внешним миром.
Рост объема данных в настоящее время провоцирует развитие различных методов интеллектуального анализа данных. Кластеризация является одним из основных методов обработки данных в data mining и заключается в нахождении оптимального разбиения данных, представленных в определенном виде. Это может быть как текстовая информация или картинки, которые представляется в виде графа. Графовое представление данных является наглядным и удобным способом формализованного представления информации. Субъекты представляются в виде узлов, а связи между ними изображаются в виде ребер.
В статье рассмотрены четыре различных алгоритма кластеризации, проведен их анализ и сравнение, представлено теоретическое описание работы алгоритмов и результаты их применения на примере разделения на сообщества графа, созданного на основе данных, взятых из социальной сети «ВКонтакте».