Уникальные студенческие работы


Авторефераты и диссертации по социальная сеть

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт системного программирования Российской академии наук Научный руководитель: Воронцов Константин Вячеславович, доктор физико-математических наук, старший научный сотрудник, Федеральное государственное бюджетное учреждение науки Вычислительный центр.

Дородницына Авторефераты и диссертации по социальная сеть академии наук ВЦ РАН Фильченков Андрей Александрович, кандидат физико-математических наук, ведущий инженер, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем управления.

С диссертацией и авторефератом можно ознакомиться в библиотеке и на сайте Федерального государственного бюджетного учреждения науки Институт системного программирования Российской академии наук.

Ученый секретарь диссертационного совета кандидат физ. Общая характеристика работы Актуальность Онлайновые социальные сети Facebook, вКонтакте, LiveJournal и другие являются одним из наиболее популярных типов Интернет-сервисов1.

Социальные графы пользователей таких сервисов обладают модульной структурой, которая во многом определяется склонностью пользователей объединяться в сообщества. Сообщество — это группа пользователей, выполняющая общую роль или функцию и обладающая общими свойствами, ценностями и целями.

С точки зрения сетевого анализа сообщества представляют собой кластеры пользователей, связанных между собой сильнее, чем с другими авторефераты и диссертации по социальная сеть сети. Знание структуры сообществ пользователей находит применение в ряде практических приложений анализа социальных данных: Исследования структурных особенностей групп пользователей в социальных графах показали, что множества пользователей в сообществах имеют тенденцию к значительному пересечению.

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

  • Таким образом, подтверждается предположение о том, что частные трансферты призваны восполнить недостаток государственной поддержки малообеспеченным семьям Кроме того, было доказано влияние сотава семей, а именно переменной, описывающей количество поколений, проживающих в домохозяйстве;
  • A New Notion of Media?
  • Таким образом, очевидно, что ни одна из существующих концепций не позволяет однозначно разделить интернет-сервисы социальных сетей по единому основанию и связать функционирование отдельных ССС в качестве СМИ с типом, к которому принадлежит данный ССС;
  • Современные направления теоретических и прикладных исследований в зарубежной психологии;
  • На страницах сайта могут быть размещены интерактивные элементы, позволяющие наладить связь между пользователем и владельцем сайта гостевые книги, почтовые службы;
  • К вопросу формирования категориально-понятийного яппярятя—Текст.

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

В последние годы были предложены методы как для определения структуры сообществ, так и для тестирования качества таких методов путём генерации случайных социальных графов с заданной структурой сообществ, с которой впоследствии сравниваются алгоритмически найденные сообщества3.

  • Таким образом, в исследовании обозначены наиболее важные положения теории журналистики социальных сетей, дальнейшая разработка которых впереди;
  • Нами были выявлены следующие роли, которые пользователь может играть в этом процессе;
  • Таким образом, тезис о неконсистентности институциональной и сетевой форм социальной организации может быть положен в основу объяснительной модели в различных областях социологии;
  • Сетевой анализ позволяет представить временные изменения подструктур в виде последовательности дискретных состояний и использовать для решения данного круга задач теорию автоматов;
  • Блог как феномен культуры Электронный ресурс;
  • Экспериментальный метод и наука об обществе.

Overlapping community detection in networks: Известные методы генерации тестовых данных не учитывают перечисленных выше свойств структуры сообществ, что требует пересмотра требований к авторефераты и диссертации по социальная сеть методам и разработки новых подходов для авторефераты и диссертации по социальная сеть достоверной оценки качества методов определения структуры сообществ.

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

Целью диссертационной работы является разработка моделей, методов и программных средств для исследования структуры сообществ пользователей в графах онлайновых социальных сетей.

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

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

Метод СКВ позволяет осуществлять распределённую генерацию случайных социальных графов с заданной структурой сообществ пользователей, обладающей характерным для реальных социальных сетей набором свойств. Параметрами метода являются количество пользователей и параметры распределения размеров сообществ и распределения количества сообществ у пользователя.

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

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

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

Метод EgoLP позволяет определять структуру сообществ пользователей в социальном графе. Основой метода является итеративная пересылка меток сообществ по рёбрам графа в соответствии с установленными правилами взаимодействия вершин. Экспериментально продемонстрировано, что предложенный метод превосходит известные методы по совокупности критериев: Разработанный в диссертационной работе метод EgoLP позволяет определять структуру сообществ пользователей в масштабе всей популяции социальной сети сотни миллионов пользователейобеспечивая при этом возможность решения практических задач, связанных с использованием знаний о сообществах.

Одним из этапов предложенного метода является определение структуры сообществ среди непосредственных контактов каждого пользователя. Полученные сообщества могут использоваться пользователями в качестве замены ручной группировки контактов для оптимизации потоков информации на персональных страницах пользователей.

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

На основе предложенных методов были поданы заявки на патенты: Кроме того, результаты работы обсуждались в рамках семинаров "Распределенные объектно-ориентированные системы" в Институте системного программирования РАН, а также на семинаре по анализу социальных сетей Института проблем управления РАН. Лнчный вклад Все выносимые на защиту результаты получены лично автором. Программные авторефераты и диссертации по социальная сеть выполнены совместно с Кириллом Чихрадзе и Назаром Бузуном.

Публикации Основные результаты по теме диссертации опубликованы в 8 печатных работах, из которых 2 статьи опубликованы в рецензируемых журналах, рекомендованных ВАК РФ [1,2], 4 статьи включены в реферативную базу данных Scopus [2,3,4,8].

В работах [4,5,6] автору принадлежат обзорные разделы и описание основных элементов разработанных методов. В статьях [7,8] автором написаны обзорные разделы.

В статье [1] автору принадлежит раздел, посвящённый генерации случайных социальных графов с сообществами авторефераты и диссертации по социальная сеть, а также поиску сообществ пользователей. В работе [2] автору принадлежит раздел, посвящённый исследованию применимости эго-сообществ 7 пользователей для решения задачи рекомендации пользователям получателей электронных сообщений. Структура и объём диссертации Диссертация состоит из введения, четырёх глав, заключения и двух приложений.

Полный объем авторефераты и диссертации по социальная сеть 134 страницы текста с 92 рисунками и 9 таблицами. Объём приложений составляет 30 страниц. Список литературы содержит 78 наименований. Содержание работы Во введении обосновывается актуальность исследований, проводимых в рамках данной диссертационной работы, формулируется цель, ставятся задачи работы, аргументированы научная новизна и практическая значимость полученных результатов, представлены выносимые на защиту научные положения.

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

В современном понимании онлайновая социальная сеть — это Интернет-сервис, позволяющий пользователям публиковать на своих страницах персональные иные данные и служащий для упрощения коммуникации и обмена информацией между пользователями сети Интернет. Помимо коммуникационной функции, сервисы социальных сетей играют роль баз пользовательских данных, в которых с каждым пользователем ассоциирован набор персональной информации, составляющий его "виртуальную личность".

Данные всех пользователей одного сервиса образуют его социальный граф, — динамическую структуру, полностью описывающую состояние и поведение составляющих её пользователей, а также их отношения между собой и объектами внешнего мира в некоторый момент времени. Вершинами графа принято считать пользовательские аккаунты, а рёбрами — социальные связи типа "дружба", "подписка", "следование", авторефераты и диссертации по социальная сеть пары пользователей явно связывают свои аккаунты.

Являясь по сути виртуальным отражением части человеческого социума, социальные сети во многих случаях наследуют характерную для него структуру социальных групп, или сообществ. Наличие сообществ пользователей является распространённым свойством современных онлайновых социальных сетей вне 8 зависимости от состава аудитории, природы связей и преобладающих сценариев использования: Например, часто можно встретить сообщества, в которых участников объединяют общие интересы, политические и религиозные предпочтения, географическая близость и т.

Авторефераты и диссертации по социальная сеть образом, с точки зрения сетевого анализа сообщества представляют собой кластеры пользователей, связанных между собой сильнее, чем с другими авторефераты и диссертации по социальная сеть сети. С функциональной точки зрения сообщество — это группа пользователей, выполняющая общую роль или функцию и обладающая общими свойствами, ценностями и целями. Ввиду отсутствия общепринятой формализации приведённого определения сообщества, важно выделить некоторые особенности сообществ пользователей, характерные для социального графа на уровне связей между пользователями.

Формализация задачи и метода поиска сообществ на уровне сетевых данных позволяет использовать общепринятую терминологию теории графов и соответствующие инструменты. Покрытием С социального графа G V, Е будем называть множество сообществ пользователей, заданных для G: Степень ти вершины и равна количеству сообществ, в которых состоит пользователь.

По результатам исследований были выявлены следующие свойства социальных графов с сообществами: Связь пользователей и сообществ: Интуитивная ассоциация сообщества пользователей с кластером вершин социального авторефераты и диссертации по социальная сеть приводит к естественному предположению о том, что вершины "хорошего" сообщества компактно связаны между собой и одновременно хорошо отделены от остальных вершин графа. В диссертационной работе используется предложенный Yang et al подход к оценке соответствия произвольного подграфа интуитивным свойствам сообщества пользователей.

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

Подграф А имеет 6 внутренних и 5 внешних рёбер, в силу чего обладает более низкой отделимостью по сравнению с другими кластерами. В подграфе В представлены 8 из 10 возможных рёбер между его вершинами, что говорит о его высокой плотности по сравнению с подграфом А и особенно подграфом С.

При этом в подграфе С достаточно удалить 2 ребра, чтобы разделить его на компоненты связности, что говорит о его низкой сплочённости. Данный подграф также обладает самым низким коэффициентом кластеризации, поскольку ни одна тройка его вершин не образует 3-клику.

Следовательно, подграфы С и В по совокупности значений метрик качества являются "худшим" и "лучшим" сообществами соответственно. Подграф с большим значением какой-либо метрики качества не обязательно соответствует сообществу. Однако сообщество, найденное алгоритмически, должно иметь высокие показатели по одной или более метрик качества.

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

Эти классы включают методы, основанные на вероятностных моделях, методы локальной оптимизации и методы распространения авторефераты и диссертации по социальная сеть. Однако большинство методов из первых двух классов обладают значительной вычислительной сложностью, а распределённая реализация их затруднена в силу различных причин.

В рамках работы был детально исследован метод SLPA Speaker-listener Label Propagation Algorithm 1 из класса распространения меток как обладающий оптимальным сочетанием качества, временной сложности и масштабируемости. Метод заключается в итеративном распространении по рёбрам меток сообществ, которые накапливаются в памяти каждой вершины и по завершении итераций определяют её принадлежность к сообществам.

  1. Например, становится возможным анализ структуры связей всего социального графа, определение целевых сообществ пользователей и детальный анализ путей распространения информации в соответствующих им подграфах.
  2. Взаимодействие устной и письменной формы существования языка в Интернет-коммуникации Текст.. Попытка представителей акторно-сетевой теории сделать темой своих исследований взаимобусловливаемые определения "вещей" и "идей", "реальности" и "конструкции" является, на наш взгляд интересной и перспективной особенностью акторно-сетевой теории, несмотря на критическую полемику некоторых французских авторов, также представленную в третьем параграфе.
  3. В течение всего жизненного цикла человека сопровождает его социальная сеть, помогает справляться с задачами, встающими перед ним.

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

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

Современные исследователи в области идентификации социальных сообществ широко применяют социальные графы авторефераты и диссертации по социальная сеть эталонной структурой сообществ для оценки методов определения структуры сообществ.

Такие шаблонные сети англ.

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

Для того, чтобы установить близость известного и найденного покрытий, в диссертационной работе используется значение нормализованной взаимной информации англ. Normalized Mutual Information, NMIкоторое показывает, в какой степени информация о структуре одного покрытия уменьшает неопределённость о другом покрытии.

VK
OK
MR
GP