Микро- и макромодели социальных сетей. Ч. 1. Основы теории

У

правление в социально-экономических системах

УДК 519.8;519.301

МИКРО- И МАКРОМОДЕЛИ СОЦИАЛЬНЫХ СЕТЕЙ. Ч. 1. Основы теории

В.В. Бреер, Д.А. Новиков, АД Рогаткин

Рассмотрены два подхода к построению и исследованию моделей социальных сетей: макро- и микроописания. В соответствии с первым из них структура связей в социальной сети усредняется, и поведение агентов рассматривается «в среднем». В рамках второго подхода принимается во внимание структура графа влияний агентов и их индивидуальное принятие решений. Дано сравнение этих двух подходов на примере пороговой модели коллективного поведения с единым относительным порогом.

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

ВВЕДЕНИЕ

В работе [16] выделены несколько уровней описания и анализа социальных сетей (СС). На первом (нижнем) уровне сеть рассматривается «в целом». Здесь применяются статистические методы, методы семантического анализа и др. Такое агрегированное описание можно условно считать макромоделью СС. На втором уровне с помощью аппарата теории графов анализируются структурные свойства СС. Соответствующее детализированное описание будем называть микромоделью СС. На третьем уровне моделируется информационное взаимодействие агентов. Здесь спектр возможных моделей наиболее широк — марковские модели (в том числе — модели консенсуса), конечные автоматы, модели диффузии инноваций, модели заражения и многие другие (см. обзор в книге [10]). На четвертом уровне с помощью аппарата оптимального управления или дискретной оптимизации ставятся и решаются задачи управления. На третьем и четвертом уровнях оперируют, как правило, микромоделями, отражающими взаимодействие отдельных агентов. И, наконец, на пятом уровне для описания взаимодействия субъектов, воздействующих на социальную сеть каждый в своих интересах, как правило, используется аппарат теории игр, в том числе — рефлексивных игр. Здесь СС как объект управления рассматривается, как правило, на макроуровне.

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

Разнородность (так называемая гетерогенность) описания СС с точки зрения различных интересующих исследователя аспектов ее рассмотрения, с одной стороны, неизбежна как следствие отмеченной выше специфики СС. С другой стороны, хотелось бы уметь преодолевать проблемы больших данных [15]: абстрагироваться — не теряя существенных деталей, переходить от микромоделей к макромоделям, оперирующим агрегированными характеристиками, и формулировать задачи анализа и управления СС в терминах макромоделей. Поэтому в настоящей работе устанавливается связь между микро- и макромоделями СС. Для этого сначала (в § 1) приводится описание одной из наиболее распространенных на сегодня микромоде-

28

СОЫТВОЬ БС!ЕМСЕ8 № 5 • 2014

лей СС, а именно — модели М. Де Гроота [27] в терминах графа коммуникаций отдельных агентов [10]. Затем (в § 2) рассматривается переход к макромодели, оперирующей статистическими характеристиками СС. В § 3 связь микро- и макрохарактеристик обсуждается для случая пороговой модели поведения агентов, принимающих решения с учетом других агентов СС. Продолжением настоящей работы, содержащим результаты идентификации описанных моделей и имитационных экспериментов, служит статья [2].

1. МИКРОМОДЕЛЬ СОЦИАЛЬНОЙ СЕТИ

Пусть N = {1, 2, ..., п} — множество агентов, входящих в социальную сеть, описываемую ориентированным графом R = (Ы, Е), где Е с NsN — множество дуг. Агенты в сети влияют друг на друга — наличие дуги (/, у) от вершины / к вершине у соответствует доверию /-го агента к у-му. Обозначим через N'"(1) = {у е N | 3 (у; /) е Е} множество «соседей» — агентов, влияющих на /-го агента, через №"'(/) = {у е N | 3 (/; у) е Е} — множество агентов, на которых влияет /-й агент, поШ(!) = # №"'(/),

П"(/) = # N"(1), где # означает мощность множества.

Степень влияния агентов друг на друга может задаваться матрицей прямого влияния/доверия

А = ||а ..|| размерности п х п, где а.. > 0 обозначает

. и

степень доверия /-го агентау-му агенту (или, что будем считать эквивалентным, степень влияния у-го агента на /-го агента; V/ £ N'"(1) аи = 0) [11]. Считается, что выполняется условие нормировки:

"

V/ е N X а. = 1.

. = 1

Если /-й агент доверяет у-му, а у-й доверяет к-му, то это означает: к-й агент косвенно влияет на /-го и т. д., т. е. возможны «цепочки» косвенных (опосредованных) влияний.

Предположим, что у каждого агента в начальный момент времени имеется мнение по некоторому вопросу. Мнение всех агентов сети отражает вектор-столбец 9° размерности п действительно значных неотрицательных начальных мнений. Примерами мнений служат степень готовности проголосовать за того или иного кандидата, приобрести тот или иной товар и т. д. — классификация и многочисленные примеры мнений членов социальных сетей приведены в работе [10]. Агенты в социальной сети взаимодействуют, обмениваясь мнениями. Этот обмен приводит к тому, что мнение каждого агента меняется под влиянием мнений агентов, которым данный агент доверяет. Бу-

к 1

дем считать, что мнение /-го агента 9г е ^ в момент времени к [10, 27]

ek = Z аие

j е N

k -1

k = 1, 2,

Обозначим через ek = (ef, ek, ..., ek) состояние социальной сети в момент времени k.

Предположим, что достижим консенсус — в конечном итоге (при многократном обмене мнениями) мнения агентов сходятся к единому результирующему (итоговому) вектору мнений e = lim ek

k ^ ю

(общие необходимые и достаточные условия такой сходимости можно найти в работах [8, 20]). Тогда можно записать соотношение

e = aV,

где Аю = lim А . Известно (см. ссылки в книге [10]),

k ^ ю

что, если достижим консенсус, то строки матри-

лю

цы А одинаковы, соответственно, так как вектор e в этом случае будет состоять из одинаковых элементов, будем считать это обозначение скаляром. Обозначим i-й элемент произвольной строки этой

матрицы через аг- , i е N.

В качестве «альтернативы» модели (2) для определения зависимости общего итогового мнения агентов от их начальных мнений возможно использование репутаций [9, 10] агентов {r; е [0; 1]}. е N,

n

где Z j = 1:

j = 1

n

e = Z j ej0.

j = i

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

2. МАКРОМОДЕЛЬ СОЦИАЛЬНОЙ СЕТИ

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

твенно через Р"(к) и Рош(к), к = 0, п - 1.

Зная вектор начальных мнений агентов, можно определить эмпирическую функцию распределе-

ния этих мнений:

F (x) = i #{i е N | e0 < x}. 0 n

Соответствующее ей вероятностное распределение обозначим P 0 (x).

е"4 7

Макромоделью социальной сети назовем совокупность {n, Pin(k), Pout(k), P 0 (x)}, причем будем

е

предполагать, что структура СС такова, что достижим консенсус.

Возможны различные способы перехода от микроописания к макрохарактеристикам. В частности, по-разному могут определяться влиятельность и репутация агентов. Так, сегодня известны две основные (наиболее распространенные, базовые) модели влияния и распространения («диффузии») активности — информации, мнений и т. п. — в СС: линейная пороговая модель (Linear Threshold Model — LTM) [33] и модель независимых каскадов (Independent Cascade Model — ICM) [32, 34]. В их рамках рассматриваются две ключевые задачи — максимизация результирующего влияния (при ограниченном бюджете выбрать начальное множество возбуждаемых агентов, при котором результирующее возбуждение будет максимальным) и раннее обнаружение внешних воздействий (при ограниченном бюджете выбрать размещение в сети «детекторов», минимизирующее результирующее влияние внешних воздействий) [12, 17, 26, 34]. Например, в работе [34], основываясь на результатах анализа субмодулярных функций множеств [37], было показано, что задачи выбора множества первоначально возбуждаемых агентов NP-трудны для обеих моделей, и был предложен жадный эвристический (1 — 1/е)-опти-мальный алгоритм.

Возможно использование одного или нескольких из следующих предположений. Первый класс предположений (R.1—R.3) позволяет, зная граф G, тем или иным образом определить репутации агентов (иногда также употребляется термин «влиятельность» агентов).

R.1. Репутация агента в СС пропорциональна числу агентов, на которых он оказывает влияние, т. е.

out, .4

r = _n_J£_ , i e n. 1 Z nout

j e N

И.2. Репутация агента в СС, в которой достижим консенсус (см. § 1), определяется тем весом, с которым его начальное мнение входит в итоговое общее мнение, т. е.

да

ri = ai

i е N.

И.Э. Репутация агента в СС определяется алгоритмом Ра§еКапк (см., например, работу [35]), т. е.

вектор репутаций удовлетворяет системе уравнений вида

ri = Z

rj

out

j e Nn

i е N.

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

В математическом смысле класс предположений (Я.1—Я.3) можно проинтерпретировать следующим образом: репутация (3) пропорциональна степени узла графа G, а вектор репутаций представляет собой эмпирическое вероятностное распределение степеней вершин графа; вектор репутации (4) — инвариантное распределение влияний агентов; в рамах выражения (5) репутация пропорциональна степени узла графа G с учетом «опосредованных» влияний.

Второй класс предположений (1.1, 1.2) характеризует независимость микропараметров СС в мак-ростатистическом смысле.

1.1. Репутация агента не зависит от его мнения и наоборот.

1.2. Начальные мнения агентов независимы, и начальное мнение агента I не зависит от N'"(1) и №ш(1).

Третий класс предположений (А.1—А.3) позволяет, зная граф G и/или репутации агентов, находить матрицу A влияния/доверия.

А.1. Агент I одинаково доверяет всем агентам из множества N'"(0, т. е.

aj =

1

in

n

i е N, j е Nin(i).

А.2. Доверие агента I агенту j е N'"(1) пропорционально репутации последнего, т. е.

щ. = I Г , / е N, j е N'"(/).

к е N (') к

Таким образом, вводя те или иные предположения об общих свойствах СС, можно устанавливать количественные связи между их микро- и макромоделями.

В заключение краткого обсуждения макромоделей СС отметим, что одним из адекватных математических инструментов их исследования служит теория случайных графов (см., например, обзоры [13, 18, 36], монографии [14, 25] и учебник [28]), создателями которой являются П. Эрдош и А. Ре-ньи [31]. Этот инструментарий сегодня успешно применяется не только к социальным, но и к телекоммуникационным, информационным, технологическим, биологическим и другим сетям, сетям

научного сотрудничества и др. (см. многочисленные примеры в работах [13, 22, 28, 36]).

Если в графе дуга между любой парой вершин существует или отсутствует с одинаковой (для любых пар) вероятностью (это и подобные свойства могут выводиться из моделирования динамики формирования графа — см. работы [22, 29, 30]), то имеем биномиальное (пуассоновское в предельном случае — при большом числе вершин графа) распределение числа инцидентных дуг. Такие графы называются экспоненциальными, или графами Эрдоша — Реньи.

Оказывается, что большинство социальных сетей описывается не экспоненциальными, а степенными «распределениями»

Р'"(к) и Рш(к) числа инцидентных дуг [22, 23, 24].

Именно этими распределениями (Р'"(к) ~ к-у, где для реальных сетей 1 < у < 4) мы пользуемся в работе [2]. Имея граф, заданный статистическими характеристиками своих основных параметров, можно в рамках введенных в настоящем параграфе предположений определять макрохарактеристики (вероятностные распределения) влияния, репутации, доверия и т. п.

3. ПОРОГОВАЯ МОДЕЛЬ ПОВЕДЕНИЯ АГЕНТОВ

На примере пороговой модели коллективного поведения агентов в СС с теоретической точки зрения рассмотрим эквивалентность микро- и макро-описаний.

Модели динамики мнений агентов в СС (см. § 1) оперируют единственной характеристикой каждого агента — его мнением, а остальные параметры отражают взаимодействие агентов. Так называемые поведенческие модели СС богаче — в них, помимо «внутренних» параметров, присутствуют переменные, характеризующие поведение агента — принимаемые им решения. Решения эти зависят в общем случае как от внутренних параметров агента (его мнения, индивидуальных характеристик), так и, быть может, от мнений и/или действий других агентов (всех, или соседей, или заданной группы агентов). Рассмотрим в качестве примера поведенческой модели модель порогового поведения (см. описание общих теоретико-игровых подходов к моделированию порогового коллективного поведения в работах [3, 4, 5]).

Пусть социальная сеть состоит из множества агентов N = {1, 2, ..., п}, каждый из которых имеет две альтернативные возможности — действовать или бездействовать. Выбор /-го агента обозначим через х1 е {0; 1}, где х1 = 1 означает, что агент действует, а X' = 0 — бездействует. Пусть на решение

агента / влияет множество Б' = N'"(1) других агентов — его соседей. Будем считать, что решение

агента i действовать или бездействовать зависит от его порога 9г- е [0, 1] и доли действующих соседей: если действуют более 9г |D.\ влияющих на i-го агента соседей, то он тоже действует.

Будем считать, что мнением отдельного агента является этот индивидуальный порог 9г е [0, 1]. Пусть структура социальной сети такова, что достижим консенсус, т. е. согласно соотношению (3) существует единое мнение 9, характеризующее в конечном итоге всех агентов социальной сети, как это описано в § 1. Это единое мнение будем в дальнейшем называть единым относительным порогом агентов.

Таким образом, пользуясь подходами теории игр (как это описано в статье [5]), поведение агента на микроуровне можно представить в виде наилучшего ответа (Best Response):

X = BRfxJ =

1, £ x, >9 d{,

j e D

0, £ x, <9 d, i е N,

j e D

где С = 1 число соседей агента / е N. Будем называть модель поведения, которое описывается в виде(11), микромоделью с единым относительным порогом.

Перейдем к вероятностному макроописанию модели порогового поведения. Будем считать, что агенты неразличимы, и число соседей агента — это целое случайное число С:1 < С < п — 1. Мы не рассматриваем сети, в которых нет агентов, не имеющих соседей (с = 0), так как в этом случае такие агенты согласно выражению (11) будут всегда бездействовать. Пусть М(С) = Р'"(С):{1, 2, ..., п — 1} ^ ^ [0, 1] — вероятность того, что число соседей будет равно с . Рассмотрим усредненную динамику взаимодействия агентов в дискретном времени. Пусть на произвольном шаге действует q агентов. Рассчитаем математическое ожидание числа агентов, действующих на следующем шаге, если их поведение описывается наилучшим ответом (11).

Сначала вычислим вероятности С" событий, заключающихся в том, что ровно к соседей агента действуют. Всего существует С"^ 1 вариантов того, что агент имеет С соседей. Число таких вариантов, что именно среди с соседей данного агента будет ровно к < С действующих (из q действующих

во всей сети агентов) равно С^к, а число вариантов того, что среди этих соседей будет С — к из п — 1 — q бездействующих равно С"-^ . Таким образом, вероятность того, что ровно к из С соседей агента

действуют, можно записать в виде гипергеометрического распределения [21]:

Gn(q, й, к) =

,-,к ,-,ё- к СдСп-1-д

с

п - 1

Вычислим вероятность Рп того, что агент будет действовать под влиянием q действующих агентов во всей сети. Для того чтобы агент действовал, согласно выражению (6), необходимо, чтобы более чем 9й его соседей действовали. Искомая вероятность Рп = Рп(д, й, 9) представляет собой сумму вероятностей (7) по всем к:[9й] < к< й([•] обозначает целую часть числа):

ё

Рп(<1, й, 9) = I Gn(q, й, к) = к = [её] + 1 [её] ск Сё- к = 1 _ I сд с п - 1 - д к = 0 С1

Вероятность (8) численно равна доле действующих на следующем шаге агентов с числом соседей й. Значит, математическое ожидание доли действующих на следующем шаге агентов

п - 1

Ч^ 9) =1 Рп{9, й, 9)М(й).

ё = 1

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

qk+1 = [прп^ 9)].

Исследуем поведение функции (9) для случая, когда число агентов п достаточно велико. При этом гипергеометрическое распределение (7) может быть приближено биномиальным распределением с вероятностью р = q/n ([21]):

Gn(q, й, к)1п » 1, р = д/п - Ь(р, й, к) =

= скрк(1 — р)ё -к.

Вероятность того, что для й числа соседей агента более, чем их доля 9 будет действовать, по аналогии с вероятностью (8),

Pn(q, й, 9)1п » 1, р=„щ - в(р> й, 9) =

[её]

= 1 - I Ь(р, й, к).

к = 0

Тогда распределение числа действующих агентов (9) и динамику доли (отметим, что именно до-

ли, а не числа) (10) действующих агентов социальной сети соответственно можно записать в виде:

п -1

Р; (р, 9) = I В(р, й, 9)М(й),

ё = 1

рк

+ 1

= р; &

к

9).

Будем называть модель поведения, которое описывается в виде (12), макромоделью с единым относительным порогом.

Исследования пороговых моделей начались со ставшей классической работы М. Грановеттера [33], которая вкратце состоит в следующем. Все агенты являются соседями друг друга (граф Я коммуникаций — полный), при этом число агентов не оговаривается. Каждый агент характеризуется порогом — если доля действующих агентов больше этого порога, то он действует. Причем значение этого порога описывается функцией распределения Р. Пусть доля действующих агентов на определенном шаге к равна тк. Значит, все агенты, пороги которых меньше гк, а их число по определению равно Щг), будут действовать на следующем шаге. Таким образом, справедливо рекуррентное соотношение:

'к + 1

= ДО.

Макромодель с единым относительным порогом (12) эквивалентна модели Грановеттера (13) в следующем смысле. Предположим, что известно распределение (11). Тогда можно построить соответствующую модель Грановеттера, приняв Р(р) = (р, 9), р е [0, 1]. Обратно, пусть задана модель Грановеттера с функцией распределения порогов Р. Решим численно уравнение (11) относительно М(-)(поиск решения уравнения типа (11) представляет собой отдельную задачу). Распределение М полностью характеризует макро-модель с единым относительным порогом.

В работе [5] было показано, что условия положения равновесия в модели Грановеттера (Р(х) = х) эквивалентны условиям равновесия Нэша в микромодели с единым относительным порогом при условии, что граф влияний агентов является полным: й. = п — 1, V/ е N. Другими словами, имея макромодель порогового поведения агентов в СС, можно легко вычислять ее равновесные состояния.

ЗАКЛЮЧЕНИЕ

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

32

СОЫТВОЬ БС^СЕБ № 5 • 2014

ложенных подходов и вопросы адекватности микро- и макроописаний друг другу «экспериментально» исследуются в работе [2]. Перспективным направлением дальнейших исследований представляется построение и изучение термодинамических и статфизических интерпретаций макромоделей социальных сетей (см. статью [7] и обзор [19]), а также постановка и решение задач управления (например, по аналогии с рассмотренными в работах [1, 10, 17] задачами управления социальными сетями, описываемыми выражениями (1) или (6)).

ЛИТЕРАТУРА

1. Барабанов И.Н., Коргин Н.А., Новиков Д.А., Чхартишвили А.Г. Динамическая модель информационного управления в социальных сетях // Автоматика и телемеханика. — 2010. — № 11. — С. 172—182.

2. Батов А.В., Бреер В.В., Новиков Д.А., Рогаткин А.Д. Микро- и макромодели социальных сетей: идентификация и имитационные эксперименты // Проблемы управления. — 2014. — № 6 (в печати).

3. Бреер В.В. Модели конформного поведения. Ч. 1. От философии к математическим моделям // Проблемы управления. — 2014. — № 1. — С. 2—13.

4. Бреер В.В. Модели конформного поведения. Ч. 2. Математические модели // Проблемы управления. — 2014. — № 2. — С. 2—17.

5. Бреер В.В. Теоретико-игровые модели конформного коллективного поведения // Автоматика и телемеханика. — 2012. — № 10. — С. 111—126.

6. Бреер В.В., Новиков Д.А. Модели управления толпой // Проблемы управления. — 2012. — № 2. — С. 38—44.

7. Бреер В.В. Стохастические модели социальных сетей // Управление большими системами. — 2009. — № 27. — С. 169—204.

8. Гантмахер Ф.Р. Теория матриц. — 4-е изд. — М.: Наука, 1988.

9. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Модели репутации и информационного управления в социальных сетях // Управление большими системами. — 2009. — № 26.1. — С. 209—234.

10. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети: модели информационного влияния, управления и противоборства. — М.: Физматлит, 2010. — 244 с.

11. Губанов Д.А. Обзор онлайновых систем репутации/доверия // Интернет-конференция по проблемам управления / ИПУ РАН. — М., 2009. — URL: www.mtas.ru/forum (дата обращения: чч.мм.гггг).

12. Губанов Д.А., Чхартишвили А.Г. Акциональная модель влиятельности пользователей в социальной сети // Проблемы управления. — 2014. — № 4. — С. 20—25.

13. Евин И.А. Введение с теорию сложных сетей // Компьютерные исследования и моделирование. — 2010. — Т. 2, № 2. — С. 121—141.

14. Колчин В.Ф. Случайные графы. — 2-е изд. — М.: Физмат-лит, 2004. — 256 с.

15. Новиков Д.А. Большие данные: от Браге к Ньютону // Проблемы управления. — 2013. — № 6. — С. 15—23.

16. Новиков Д.А. Иерархические модели военных действий // Управление большими системами. — 2012. — № 37. — C. 25—62.

17. Новиков Д.А. Модели управления возбуждением сети // Тр. XII Всероссийского совещания по проблемам управления / ИПУ РАН. — М., 2014.

18. Райгородский А.М. Модели случайных графов и их применения // Тр. МФТИ. - 2010. - Т. 2. - № 4. -С. 130-140.

19. Словохотов Ю.Л. Физика и социофизика. Ч. 1-3 // Проблемы управления. - 2012. - № 1. -С. 2-20; № 2. -С. 2-31; № 3. - С. 2-34.

20. Чеботарев П.Ю., Агаев Р.П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов // Автоматика и телемеханика. - 2009. - № 3. -С. 136-151.

21. Ширяев А.Н. Вероятность: учеб. пособие для вузов. - М: Наука, 1989.

22. Albert R., Barabasi A.-L. Statistical mechanics of complex networks // Rev. Mod. Phys. - 2002. - N 74. - P. 47-97.

23. Barabasi A., Albert R. Emergence of scaling in random networks // Science. - 1999. - № 286. - P. 509-512.

24. Barabasi A. Scale-free Networks // Scientific American. -2003. - № 5. - P. 50 - 59.

25. Bollobas B. Random Graphs. - Cambridge: Cambridge University Press, 2001. - 520 p.

26. Chen N. On the Approximability of Influence in Social Networks // SIAM J. Discrete Math. - 2009. - Vol. 23. -P. 1400-1415.

27. De Groot M. Reaching a Consensus // Journal of American Statistical Assotiation. - 1974. - N 69. - P. 118-121.

28. Dorogovtsev S. Lectures on Complex Networks. - Oxford: Oxford University Press, 2010. - 144 p.

29. Dorogovtsev S., Mendes J. Evolution of Networks. - Oxford: Clarendon Press, 2010. - 264 p.

30. Durett R. Random Graph Dynamics. - Cambridge: Cambridge University Press, 2007. - 212 p.

31. Erdos P., Renyi A. On random graphs // Publ. Math. Debrecen. - 1959. - N 6. - P. 290-297.

32. Goldenberg J., Libai B., Muller E. Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-mouth // Marketing Letters. - 2001. - Vol. 12, N 3. -P. 211-223.

33. Granovetter M. Threshold Models of Collective Behavior // The American Journal of Sociology. - 1978. - Vol. 83, N 6. -P. 1420-1443.

34. Kempe D., Kleinberg J., Tardos E. Maximizing the Spread of Influence through a Social Network // Proc. 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2003. -P. 137-146.

35. Lin Y., Shi X., Wei Y. On Computing PageRank via Lumping the Google Matrix // Journal of Computational and Applied Mathematics. - 2009. - Vol. 224, N 2. - P. 702-708.

36. Newman M. The Structure and Function of Complex Networks // SIAM Review. - 2003. - Vol. 45, N 2. -P. 167-256.

37. Nemhauser G., Wolsey L., Fisher M. An Analysis of the Approximations for Maximizing Submodular Set Functions // Mathematical Programming. - 1978. - Vol. 14. -P. 265-294.

Статья представлена к публикации членом редколлегии Ф.Т. Алескеровым.

Бреер Владимир Валентинович - бизнес-аналитик, ЗАО «Авиахэлп Групп», г. Москва, И breer@live.ru,

Новиков Дмитрий Александрович - чл.-корр. РАН, зам. директора, Институт проблем управления им. В.А. Трапезникова РАН, г. Москва,  (495) 334-75-69, И novikov@ipu.ru,

Рогаткин Андрей Дмитриевич - мл. науч. сотрудник, Институт проблем управления им. В.А. Трапезникова РАН, г. Москва, И andreyrogatkin@gmail.com.