Максимизация распространения влияния в социальной сети

Кемпе Д., Клейнберг Дж., Тардош Э.

Корнелльский университет, Итака, Нью-Йорк, США

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

Мы рассматриваем эту задачу в рамках нескольких наиболее широко изучаемых моделей в анализе социальных сетей. Задача оптимизации по выбору наиболее влиятельных узлов является NP-трудной в этих моделях, и мы предоставляем первые доказуемые гарантии аппроксимации для эффективных алгоритмов. Используя аналитическую основу, основанную на субмодулярных функциях, мы показываем, что естественная жадная стратегия дает решение, которое гарантированно находится в пределах 63% от оптимального для нескольких классов моделей; наша основа предлагает общий подход к рассуждению о гарантиях производительности алгоритмов для подобных задач влияния в социальных сетях.

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

1. Введение

Социальная сеть — граф взаимоотношений и взаимодействий внутри группы индивидов — играет фундаментальную роль как среда для распространения информации, идей и влияния среди её членов. Идея или новшество появляется — например, использование сотовых телефонов среди студентов колледжей, внедрение нового лекарства в медицинском сообществе или рост политического движения в нестабильном обществе — и оно либо быстро исчезает, либо прочно укореняется в популяции. Если мы хотим понять, в какой степени такие идеи принимаются, важно понимать, как динамика принятия, вероятно, развернется в рамках лежащей в основе социальной сети: в какой степени люди, вероятно, подвержены влиянию решений своих друзей и коллег или в какой степени заработают эффекты «сарафанного радио». Такие процессы диффузии в сетях имеют долгую историю изучения в социальных науках. Некоторые из самых ранних систематических исследований были сосредоточены на данных, касающихся внедрения медицинских и сельскохозяйственных инноваций как в развитых, так и в развивающихся частях мира [8, 27, 29]; в других контекстах исследования изучали процессы диффузии для эффектов «сарафанного радио» и «вирусного маркетинга» в успехе новых продуктов [4, 7, 10, 13, 14, 20, 26], внезапное и широкое принятие различных стратегий в игровых теоретических условиях [6, 12, 21, 32, 33] и проблему каскадных сбоев в энергосистемах [2, 3].

В недавней работе, мотивированной приложениями в маркетинге, Домингос и Ричардсон поставили фундаментальную алгоритмическую задачу для подобных систем [10, 26]. Предположим, у нас есть данные о социальной сети с оценками степени, в которой индивиды влияют друг на друга, и мы хотели бы продать новый продукт, который, как мы надеемся, будет принят значительной частью сети. Предпосылка вирусного маркетинга заключается в том, что, изначально воздействуя на нескольких «влиятельных» членов сети — скажем, предоставляя им бесплатные образцы продукта — мы можем запустить каскад влияния, посредством которого друзья будут рекомендовать продукт другим друзьям, и в конечном итоге многие индивиды попробуют его. Но как нам выбрать этих нескольких ключевых индивидов для запуска этого процесса? В [10, 26] этот вопрос рассматривался в вероятностной модели взаимодействия; были предложены эвристики для выбора клиентов с большим общим эффектом на сеть, а также были разработаны методы для вывода данных о влиянии, необходимых для постановки подобных задач.

В данной статье мы рассматриваем проблему выбора влиятельных множеств индивидов как задачу дискретной оптимизации. Оптимальное решение является NP-трудным для большинства изученных моделей, включая модель из [10]. Предложенная в [26] основа, с другой стороны, основана на простой линейной модели, где решение задачи оптимизации может быть получено путем решения системы линейных уравнений. Здесь мы сосредотачиваемся на коллекции связанных, NP-трудных моделей, которые были широко изучены в сообществе социальных сетей, и получаем первые доказуемые гарантии аппроксимации для эффективных алгоритмов в ряде общих случаев. Общность рассматриваемых нами моделей лежит между полиномиально разрешимой моделью [26] и очень общей моделью [10], где задача оптимизации не может быть аппроксимирована даже с нетривиальным коэффициентом.

Мы начинаем с некоторого отхода от основы Домингоса–Ричардсона в следующем смысле: там, где их модели по сути являются описательными, задавая совместное распределение над поведением всех узлов в глобальном смысле, мы сосредотачиваемся на более операционных моделях из математической социологии [15, 28] и системах взаимодействующих частиц [11, 17], которые явно представляют пошаговую динамику принятия. Мы показываем, что аппроксимационные алгоритмы для максимизации распространения влияния в этих моделях могут быть разработаны в общей основе, основанной на субмодулярных функциях [9, 23]. Мы также приводим результаты вычислительных экспериментов на крупных коллаборационных сетях, показывая, что в дополнение к своим доказуемым гарантиям наши алгоритмы значительно превосходят эвристики выбора узлов, основанные на хорошо изученных понятиях центральности по степени и центральности по расстоянию [30] из области анализа социальных сетей.

Две основные модели диффузии

При рассмотрении операционных моделей распространения идеи или новшества через социальную сеть G, представленную ориентированным графом, мы будем говорить, что каждый отдельный узел является либо активным (адептом новшества), либо неактивным. Мы сосредоточимся на условиях, определяемых вышеуказанной мотивацией, в которых склонность каждого узла становиться активным монотонно возрастает по мере того, как все больше его соседей становятся активными. Кроме того, мы пока сосредоточимся на прогрессивном случае, в котором узлы могут переключаться из неактивного состояния в активное, но не наоборот; оказывается, что это предположение можно легко снять позже. Таким образом, процесс будет выглядеть примерно следующим образом с точки зрения изначально неактивного узла v: по мере того как время идет, все больше и больше соседей v становятся активными; в какой-то момент это может привести к тому, что v станет активным, и решение v в свою очередь может запустить дальнейшие решения узлов, с которыми v связан.

Грановеттер и Шеллинг были среди первых, кто предложил модели, описывающие такой процесс; их подход был основан на использовании порогов, специфичных для узла [15, 28]. С тех пор было исследовано множество моделей такого типа (см., например, [5, 15, 18, 19, 21, 25, 28, 29, 31, 32, 33]), но следующая Линейная пороговая модель лежит в основе большинства последующих обобщений. В этой модели узел v испытывает влияние от каждого соседа w в соответствии с весом b_v,w, таким что ∑_{w сосед v} b_v,w ≤ 1. Динамика процесса затем развивается следующим образом. Каждый узел v выбирает порог θ_v равномерно случайно из интервала [0, 1]; это представляет взвешенную долю соседей v, которые должны стать активными, чтобы v стал активным. При случайном выборе порогов и начальном множестве активных узлов A₀ (при этом все остальные узлы неактивны), диффузионный процесс развивается детерминированно дискретными шагами: на шаге t все узлы, которые были активны на шаге t − 1, остаются активными, и мы активируем любой узел v, для которого общий вес его активных соседей составляет по крайней мере θ_v:

∑_{w активный сосед v} b_v,w ≥ θ_v.

Таким образом, пороги θ_v интуитивно представляют различные скрытые склонности узлов к принятию новшества, когда это делают их соседи; тот факт, что они выбираются случайно, предназначен для моделирования нашего незнания их значений — мы, по сути, усредняем по возможным значениям порогов для всех узлов. (Другой класс подходов жестко фиксирует все пороги на известном значении, таком как 1/2; см., например, работы Бергера [5], Морриса [21] и Пелега [25].)

На основе работ по системам взаимодействующих частиц [11, 17] из теории вероятностей, мы также можем рассматривать динамические каскадные модели для процессов диффузии. Концептуально простейшей моделью этого типа является то, что можно назвать Моделью независимых каскадов, недавно исследованной в контексте маркетинга Голденбергом, Либаи и Мюллером [13, 14]. Мы снова начинаем с начального множества активных узлов A₀, и процесс развивается дискретными шагами в соответствии со следующим вероятностным правилом. Когда узел v впервые становится активным на шаге t, ему дается единственный шанс активировать каждого в данный момент неактивного соседа w; он преуспевает с вероятностью p_v,w — параметром системы — независимо от истории до этого момента. (Если у w есть несколько вновь активированных соседей, их попытки упорядочиваются в произвольном порядке.) Если v преуспевает, то w станет активным на шаге t+1; но независимо от того, преуспевает ли v или нет, он не может предпринимать дальнейшие попытки активировать w в последующих раундах. Опять же, процесс продолжается до тех пор, пока не станет возможной дальнейшая активация.

Аппроксимационные алгоритмы для максимизации влияния

Теперь мы можем формально выразить задачу оптимизации в стиле Домингоса–Ричардсона — выбор хорошего начального множества узлов для воздействия — в контексте вышеуказанных моделей. И в модели Линейных порогов, и в модели Независимых каскадов (а также в их обобщениях) участвует начальное множество активных узлов A₀, запускающее процесс диффузии. Мы определяем влияние множества узлов A, обозначаемое σ(A), как математическое ожидание числа активных узлов в конце процесса при условии, что A является этим начальным активным множеством A₀. Задача максимизации влияния формулируется так: при заданном параметре k найти множество из k узлов с максимальным влиянием.

Для рассматриваемых нами моделей оптимальное решение задачи максимизации влияния является NP-трудным, как мы покажем далее. Наш первый основной результат заключается в том, что оптимальное решение можно эффективно аппроксимировать с точностью до множителя (1 − 1/e − ε) в обеих моделях — Линейных порогов и Независимых каскадов (здесь e — основание натурального логарифма, ε — любое положительное число). Таким образом, гарантия производительности составляет чуть более 63%.

Алгоритм, достигающий этой гарантии, — это естественная жадная стратегия восхождения (greedy hill-climbing), схожая с подходом, рассмотренным в [10]. Основное содержание результата — это аналитическая основа, необходимая для получения доказуемой гарантии, и довольно удивительный факт, что жадное восхождение всегда даёт решение, не хуже чем на 63% от оптимального.

Мы доказываем этот результат в Разделе 2 с использованием техник из теории субмодулярных функций [9, 23], которые, как оказывается, предоставляют естественный контекст для рассуждений о моделях и алгоритмах максимизации влияния.

Общая стратегия доказательства

Рассмотрим произвольную функцию f(·), которая отображает подмножества конечного базового множества U в неотрицательные вещественные числа. Мы говорим, что f субмодулярна, если она удовлетворяет естественному свойству «убывающей отдачи»: предельный выигрыш от добавления элемента к множеству S не меньше, чем предельный выигрыш от добавления того же элемента к надмножеству T ⊇ S.

Формально, субмодулярная функция удовлетворяет неравенству:
f(S ∪ {v}) − f(S) ≥ f(T ∪ {v}) − f(T)
для всех элементов v и всех пар множеств S ⊆ T.

Субмодулярные функции обладают рядом полезных свойств. В частности, результат Немхаузера, Вулси и Фишера [9, 23] показывает, что следующий жадный алгоритм аппроксимирует максимум с точностью до (1 − 1/e):

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

Теорема 2.1 [9, 23]. Для неотрицательной, монотонной субмодулярной функции f, пусть S — множество размера k, полученное выбором элементов по одному, каждый раз выбирая элемент, дающий наибольшее предельное увеличение значения функции. Пусть S* — множество, максимизирующее f среди всех k-элементных множеств. Тогда f(S) ≥ (1 − 1/e) · f(S*).

Наша стратегия будет состоять в том, чтобы показать, что для рассматриваемых моделей функция влияния σ(·) является субмодулярной.

Модель независимых каскадов

Гарантия аппроксимации для модели Независимых каскадов вытекает из следующей теоремы:

Теорема 2.2. Для произвольного экземпляра модели Независимых каскадов соответствующая функция влияния σ(·) является субмодулярной.

Чтобы установить этот результат, мы вводим эквивалентное представление процесса: предположим, что для каждой пары соседей (v, w) исход монетки с вероятностью p_v,w решается заранее, до начала процесса. Ребро объявляется «живым», если монетка выпала удачно, и «заблокированным» — иначе.

Тогда узел x становится активным тогда и только тогда, когда существует путь из живых рёбер от некоторого узла в начальном множестве A до x.

Фиксируя исход всех «монеток» (обозначим такой исход как X), мы получаем детерминированную функцию σ_X(A) — размер объединения множеств достижимых узлов из каждого элемента A. Эта функция субмодулярна. Поскольку σ(A) есть математическое ожидание (средневзвешенное) по всем X, и неотрицательная линейная комбинация субмодулярных функций также субмодулярна, функция σ(·) субмодулярна.

Линейные пороги

Аналогичный результат справедлив и для модели Линейных порогов:

Теорема 2.5. Для произвольного экземпляра модели Линейных порогов функция влияния σ(·) является субмодулярной.

Доказательство аналогично: каждый узел v «выбирает» не более одного входящего ребра как «живое» с вероятностью, пропорциональной весам b_v,w. Тогда активация снова эквивалентна достижимости по живым рёбрам, и субмодулярность следует тем же способом.

Вычислительные эксперименты

Мы провели эксперименты на крупной коллаборационной сети, построенной на основе публикаций в области теоретической физики (10748 узлов). Сравнивались следующие стратегии выбора узлов:

• Жадный алгоритм (наш подход);
• Выбор по степени — узлы с наибольшим количеством соседей;
• Центральность по расстоянию — узлы с наименьшим средним расстоянием до остальных;
• Случайный выбор.

В модели Линейных порогов жадный алгоритм превзошёл эвристику «по степени» на 18%, а «по центральности» — более чем на 40%. Это демонстрирует, что явный учёт динамики распространения информации даёт существенно лучшие результаты, чем использование лишь статических структурных мер.

Интересно, что в модели Независимых каскадов с высокой вероятностью активации (10%) стратегия случайного выбора в конечном итоге превосходила эвристики по степени и центральности. Причина в том, что центральные узлы быстро активируются первым же выбранным узлом, и их последующий предельный вклад близок к нулю. Жадный алгоритм учитывает это, тогда как эвристики — нет.

Обсуждение сложности

Задача максимизации влияния NP-трудна уже в модели Независимых каскадов (сводится к задаче Покрытия множества) и в модели Линейных порогов (сводится к задаче Вершинного покрытия).

Однако в очень общей модели Домингоса–Ричардсона [10] задача не может быть аппроксимирована даже с нетривиальным коэффициентом (если P ≠ NP). Таким образом, наши модели лежат в «золотой середине»: они достаточно богаты, чтобы моделировать реальные процессы, но достаточно структурированы, чтобы допускать эффективные аппроксимации.

Обобщённая модель распространения влияния

Авторы предлагают единую теоретическую основу, объединяющую модели Линейных порогов и Независимых каскадов. Эта основа имеет два эквивалентных представления:

• Обобщённая пороговая модель. Каждый узел v имеет монотонную пороговую функцию f_v(S), отображающую подмножество S его активных соседей в число из [0,1]. Узел становится активным, если f_v(S) ≥ θ_v, где θ_v — случайный порог.
• Обобщённая каскадная модель. Вероятность, с которой активный узел u активирует неактивного соседа v, зависит от множества S соседей, которые уже пытались (и не смогли) активировать v. Эта вероятность задаётся функцией p_v(u, S).

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

Модель триггеров

Чтобы определить условия, при которых функция влияния остаётся субмодулярной, авторы вводят триггерную модель (Triggering Model):

Каждый узел v независимо выбирает случайное «триггерное множество» T_v из своих соседей. Узел v становится активным, как только хотя бы один из его соседей из T_v активируется. Это эквивалентно тому, что каждое входящее ребро помечается как «живое» или «заблокированное», и активация происходит по живым рёбрам.

Теорема 4.2. В любой триггерной модели функция влияния σ(·) является субмодулярной.

Эта модель включает в себя как линейные пороги, так и независимые каскады, и даже такие модели, как «Слушай только первый раз» (Only-Listen-Once), где узел реагирует только на первую попытку активации.

Непрогрессивные процессы

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

Рассмотрим процесс, который развивается в течение τ временных шагов. На каждом шаге узел может активироваться или деактивироваться в зависимости от текущего состояния соседей. Задача — выбрать k вмешательств (активаций в определённый момент времени), чтобы максимизировать суммарное время активности всех узлов за τ шагов.

Эта задача сводится к прогрессивному случаю на слоистом графе G_τ, в котором каждому узлу исходного графа сопоставляется τ копий — по одной на каждый временной шаг.

Теорема 5.1. Задача максимизации влияния в непрогрессивной модели эквивалентна задаче в прогрессивной модели на слоистом графе.

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

Обобщённые маркетинговые стратегии

В реальном маркетинге мы редко можем «гарантированно активировать» узел. Чаще у нас есть m маркетинговых действий (реклама, email-рассылка, скидки), и мы можем распределить бюджет k между ними. Каждое действие i увеличивает вероятность активации узла v на величину h_v(x), где x — вектор инвестиций.

Предполагается, что функция h_v(·) обладает свойством «убывающей отдачи»: дополнительное вложение в маркетинг даёт меньший прирост, если пользователь уже «насыщен» рекламой.

Целевая функция — ожидаемое число активных узлов в конце процесса — оказывается композицией субмодулярной функции σ(·) и монотонных функций h_v(·). Авторы показывают, что и эта составная функция обладает свойством «убывающей отдачи».

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

Теорема 6.1. Этот приближённый градиентный алгоритм даёт гарантию, близкую к (1 − 1/e), при условии, что функции h_v(·) удовлетворяют свойству убывающей отдачи.

Заключение

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

Важность результатов заключается не только в практической применимости жадного подхода, но и в выявлении границы разрешимости: в слишком общих моделях (как у Домингоса и Ричардсона) задача не может быть аппроксимирована, а в «структурированных» моделях — может.

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

Литература

1. Kempe D., Kleinberg J., Tardos É. Maximizing the Spread of Influence through a Social Network // KDD ’03. – 2003.
2. Domingos P., Richardson M. Mining the Network Value of Customers // KDD ’01. – 2001.
3. Richardson M., Domingos P. Mining Knowledge-Sharing Sites for Viral Marketing // KDD ’02. – 2002.
4. Granovetter M. Threshold models of collective behavior // American Journal of Sociology. – 1978.
5. Nemhauser G., Wolsey L., Fisher M. An analysis of the approximations for maximizing submodular set functions // Mathematical Programming. – 1978.