Моделирование различных методов раздачи для максимального распространения информации в сети
Переоценены ли влиятельные лица?
Это достаточно интуитивно понятно, поэтому вам нужны влиятельные лица, чтобы распространять информацию о вашем продукте или услуге. Однако на одном из выпускных курсов я натолкнулся на мысль, что влиятельных лиц можно переоценить. Основная идея заключается в том, что влиятельные лица обычно концентрируются в крупных подсетях. Если вы полагаетесь на них в продвижении вашего продукта, вы рискуете пропустить множество более мелких спутниковых сетей (подробнее здесь). Это тревожный сигнал, и многие интуитивные догадки, которые мы считаем само собой разумеющимися, могут не быть исправлены, и, если их внедрить поспешно, в долгосрочной перспективе они могут оказаться дорогостоящими.
На выходных я решил протестировать несколько стратегий посева на разных наборах данных. Оказывается, нет простого ответа на вопрос, переоценены ли влиятельные лица. Динамика роста сильно зависит от структуры кластеров графа, встраивания узлов и того, как влиятельные лица связаны с остальными.
Два набора данных - о политиках в Facebook и потоковая передача музыки Deezer - были особенно показательными. После запуска алгоритма внедрения графа GEMSEC два набора данных визуализируются тремя главными компонентами, как показано выше. Сможете ли вы угадать, какой из следующих методов заполнения лучше всего подходит для каждого набора данных?
- Простой случайный посев: это наивный способ посева, но у него есть свои сторонники. Главное преимущество - просто, дешево и честно.
- Случайная выборка на стратифицированной выборке по размеру кластера: полагаясь на стратифицированную выборку, мы уверены, что не пропустим посев небольших кластеров.
- Посев влиятельных людей: просто выберите лидеров мнений с наибольшим количеством связей.
- Посев влиятельных лиц на основе кластеров: аналогично варианту 2, но мы выбираем наиболее влиятельных лиц в каждом кластере.
Этот пост будет посвящен обсуждению на высоком уровне, а детали реализации оставим до конца.
Наборы данных
Для обучения модели GEMSEC использовались наборы данных реальных социальных сетей. Наборы данных доступны в репозитории. Здесь я сосредоточился на двух наборах данных:
- Сети страниц политиков Facebook: эти графики представляют собой взаимные сети подобных среди проверенных страниц Facebook.
- Сети дружбы пользователей и пользователей Deezer: сети дружбы с сайта потоковой передачи музыки Deezer (здесь мы сосредоточились только на Венгрии).
Вложение графа
Единственная информация, доступная в наборе данных, - это ребра между узлами. Мы знаем, кто с кем связан, но мы не знаем, почему они связаны и насколько они похожи. Если бы мы моделировали распространение информации, нам нужна была бы какая-то мера сходства, чтобы оценить, насколько вероятно, что один человек передаст информацию другому. В музыкальном сервисе подобие может быть музыкальным вкусом. В социальной сети сходство может быть признаком близости (общий разговор, фотографии и т. Д.)
Чтобы обойти это ограничение, я обучил модель встраивания графа GEMSEC непосредственно изучать встраивание узлов при одновременной их кластеризации (отсюда и название G raph EM подстилки с SE lf C глянцевый). Позвольте мне отказаться от математических подробностей, которые имеются в оригинальной статье. Важным моментом является то, что теперь у нас есть структура графа и вложения узлов.
Моделирование
Процесс распространения моделируется как случайное блуждание. Вероятность заражения коррелирует с косинусным сходством между двумя узлами. Я сделал упрощающее предположение, что узлы с отрицательным косинусным сходством не будут заражать друг друга.
Вначале заражены только семенные узлы. Начальные узлы помещаются в очередь. Каждый раз, когда узел удаляется из очереди, он пытается заразить всех своих соседей. Новые зараженные узлы (включая сам старый узел) добавляются в очередь в режиме поиска в ширину.
Наблюдение
Результат представлен на двух графиках ниже.
- Посев на основе кластеров лидеров мнений превзошел прямые посевы влиятельных лиц в наборе данных политиков Facebook, но они не показали больших различий в наборе музыкальных данных Deezer.
- Случайное заполнение на основе кластера превосходит простое случайное заполнение в обоих наборах данных. Это ожидаемо, поскольку мы, по сути, выполняем стратифицированную выборку по размеру кластера.
Что вызывает разницу в посеве влиятельных лиц? Основная причина заключается в том, что влиятельные лица не одинаково сильны во всех кластерах. Если мы выберем только самых влиятельных лиц, только 12 из 20 кластеров будут иметь квалифицированных влиятельных лиц. Посредством стратифицированной выборки мы вынуждаем кластеры, у которых есть менее влиятельные факторы, быть засеяемыми.
Вторая причина связана со структурой графа. Набор данных о политиках имеет очень поляризованные, четко определенные и хорошо разделенные кластеры. Набор данных потоковой передачи музыки Deezer более расплывчатый. Это понятно, люди могут наслаждаться разными музыкальными жанрами, но политики придерживаются определенных (а часто и противоположных) политических позиций. Графики плотности для соседних узлов главных влиятельных лиц ясно демонстрируют поляризованный паттерн: все друзья политиков одинаковы; меломаны завязывают дружеские отношения в кластерах.
Резюме
Графики - одна из самых сложных и прибыльных задач для работы. Цель этого блога - не предлагать какую-либо универсальную истину, а проиллюстрировать некоторые точки зрения, с которых вы могли бы изучить свои собственные наборы данных графов. Некоторые детали, заслуживающие вашего внимания:
- Когда знание графа легко доступно или легко выводится с помощью машинного обучения, выбор влиятельных лиц гораздо предпочтительнее, чем случайный.
- Показатель сходства должен быть хорошим показателем вероятности заражения. У Роналду 161 миллион подписчиков в Instagram, но это не значит, что он может влиять на всех из них (большинство из которых сильно отличаются от него).
- Хорошо ли определены кластеры? Сильно ли поляризованы отдельные узлы? Если это так, то влиятельные лица в определенных кластерах могут быть очень влиятельными.
- Влияния одинаково влиятельны во всех кластерах или сегментах? В противном случае вам может потребоваться стратифицированная выборка для обнаружения небольших спутниковых сетей.
- Вместо того, чтобы полагаться на интуицию, запустите моделирование и включите столько информации, сколько доступно на данный момент. Хотя моделирование часто оказывается крайне неточным, оно помогает поднять ценные вопросы.
Детали эксперимента
Сначала клонируйте репозиторий GEMSEC на свою рабочую станцию. Наборы данных также доступны в репозитории.
Во-вторых, создайте среду с необходимыми пакетами. Вы можете просто запустить мой файл gemsec_env.yml.
conda env create -f gemsec_env.yml
Чтобы повторить мой результат, запустите команды в файле Experiment.sh.
Рекомендуется использовать виртуальную машину с многоядерным процессором. Алгоритм поддерживает многопоточность.
Графики, сводная статистика и коды анимации доступны здесь.
Расширенное чтение
Следующие блоги посвящены темам, относящимся к AB-тестированию, и более глубокому обзору ключевых концепций, упомянутых в этой статье.
- Визуализация бета-распространения и байесовского обновления [ссылка]
- Понимание доверительного интервала [ссылка]
- Возможности A / B-тестирования [ссылка]
- Помимо A / B-тестирования: эксперименты с многорукими бандитами [ссылка]
- Знаете ли вы достоверный интервал [ссылка]
Источник
[1] Б. Роземберчки, Р. Дэвис, Р. Саркар и К. Саттон. GEMSEC: Вложение графов с самокластеризацией. 2018.
