СПОСОБ РАСПРОСТРАНЕНИЯ ИНФОРМАЦИИ И ПРЕДОТВРАЩЕНИЯ РАСПРОСТРАНЕНИЯ ИНФОРМАЦИИ В КОМПЬЮТЕРНОЙ СЕТИ Российский патент 2010 года по МПК H04L12/24 

Область техники, к которой относится изобретение

Настоящее изобретение относится к способам управления сетями (как логическими, так и физическими) в нескольких областях. В частности, настоящее изобретение предлагает способы распространения или предотвращения распространения информации по сети, состоящей из произвольного числа соединенных связями сетевых узлов. Способы, предлагаемые изобретением, основываются на способах анализа сетей, раскрытых в норвежской патентной заявке NO 2003 5852, содержание которой включено в настоящее описание посредством ссылки.

Уровень техники

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

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

Существует множество моделей эпидемического распространения. В возможно наипростейшем классе подобных моделей каждому узлу присваивается только одно из двух возможных состояний: "неинфицированный" или "инфицированный". Если узел незаражен ("восприимчив"), узел полагается подверженным заражению любым зараженным соседним узлом. Соответственно, если узел заражен, узел остается в этом состоянии на протяжении эксперимента и сохраняет способность заразить любой соседний с ним узел. Конечно, за определенный промежуток времени узлы становятся "устойчивыми" к инфекции: человек вырабатывает антитела, машина получает антивирусное программное обеспечение, сплетни устаревают, или новшество становится устаревшим. Настоящая заявка сосредоточена на более коротком промежутке времени, так что состояние приобретенного иммунитета может быть проигнорировано. Данная модель распространения носит техническое обозначение "SI" (Susceptible or Infected, Восприимчивый или Зараженный), поскольку узел может находиться только в двух состояниях: восприимчивом и зараженном.

Поскольку распространение происходит по связям сети, очевидно, что топология сети имеет глубокое влияние на процесс распространения. В частности полагается, что лучшее понимание распространения приходит с точки зрения, основанной на образе всей сети, и на понимании структуры сети. В более ранней работе [1] был представлен подход к анализу структуры сети, применимый к любой сети с симметричными (ненаправленными) связями. Было также предложено, что анализ структуры сети должен быть полезен для понимания распространения по такой сети. Недавно в работе [2] авторами была разработана детальная частично количественная теория процесса распространения в таких сетях. Теория полностью основывается на структурном анализе. Настоящее изобретение обращается к вопросу об активной разработке или управлении сетями с целью управления (содействия или препятствия) распространению. Предложенный анализ предлагает ясные решения для управления распространением в обоих указанных смыслах.

Данный подход отступает от предшествующих работ в том, что сосредотачивается как на временном, так и на пространственном развитии распространения эпидемии. Пространственное разрешение не является микромасштабным, а скорее находится на уровне "областей" - связных подграфов с примерно одинаковой способностью к распространению. Более традиционные подходы, описанные в [4], начинаются с "однородной" аппроксимации, при которой каждый узел может заразить любой другой узел с некоторой вероятностью, в любой момент времени. О таком подходе можно сказать, что он не имеет сетевой перспективы; или можно сказать, что такой подход постулирует граф с чрезвычайно хорошей однородностью, такой как случайный граф высокого порядка или полный граф. В обзоре Ньюмана [4] также обсуждается более поздняя работа, включающая перспективы сетей. Вся подобная работа основывается на свойствах всего графа, таких как распределение порядков узлов; эти подходы также сосредотачиваются либо на получении результатов для всего графа или во времени [5, 6], либо сосредотачиваются на инфицированной части на большом промежутке времени [7]. Последний вопрос, несомненно, интересен только для моделей, превосходящих по сложности модель SI; в самом деле, основная часть работы направлена на поведение модели SIS (Susceptible, Infected, Susceptible again, Восприимчивый, Зараженный, Вновь восприимчивый), в которой узлы перестают быть инфицированными через определенное время, и вновь становятся восприимчивыми, или модели SIR (Susceptible, Infected, Refractory, Восприимчивый, Зараженный, Устойчивый), в которой узлы после избавления от инфекции проходят период устойчивости. Наконец, можно отметить, что работа, анализирующая только свойства всего графа, не может предоставить тех характерных улучшений конструкции, которые осуществлены в настоящем изобретении.

Брауэр [8] исследовал модель SI для случая рождения и гибели узлов (организмов, в особенности людей). Из-за добавления этих динамических свойств постоянный уровень заражения не обязательно равен 100%. Эта работа использует однородную аппроксимацию, что порождает парные обыкновенные дифференциальные уравнения. Поэтому данная работа также не может предложить локальные, характерные улучшения конструкции, подобные включенным в настоящее изобретение.

Наиболее близкой является работа Ванга и др. [9]. В этой работе рассматривается модель SIS, в которой узлы могут "излечиваться"; однако модель основана на полностью микромасштабном взгляде на сеть. Действительно, рассматриваемый в данной модели оператор, эволюционирующий во времени, совпадает с разработанным авторами настоящей статьи в [2] с двумя отличиями. Одно заключается в добавлении элемента "излечение". Этот элемент представляет собой кратное единичной матрицы, и тем самым не изменяет доминирующий собственный вектор, который остается вектором матрицы смежности А. Поскольку рассматривается модель SIS, долговременная доля заражения не является очевидной и должна быть найдена. Второе отличие от оператора эволюции во времени в работе Ванга и др. заключается в том, что Ванг и др. пренебрегают перекрестными членами, то есть теми, которые возникают в результате множественных передач на зараженный узел. Эта аппроксимация применима для низкого уровня заражения, хотя, как будет отмечено позже, указанная аппроксимация может оказаться подходящей даже при большом уровне заражения. Ванг и др. сообщают о моделировании, поддерживающем это утверждение.

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

Раскрытие изобретения

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

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

отображение топологии сети;

вычисление значений силы связей между узлами;

вычисление индекса центрированности собственных векторов для всех узлов на основе указанных значений силы связи;

определение узлов, имеющих локальные максимумы индекса центрированности собственных векторов (ЦСВ), как центральных узлов;

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

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

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

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

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

Краткое описание чертежей

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

На фиг.1 представлена схематичная диаграмма сети с точки зрения топографии так, как она используется в настоящем раскрытии изобретения, с двумя "горами" (областями).

На фиг.2 представлено схематичное изображение эпидемического распространения в одной области. Две области на фиг.1 теперь рассматриваются со "стороны", так, как если бы они действительно представляли собой горы.

На фиг.3 представлено схематичное изображение развития заражения.

На фиг.4 представлено схематичное изображение соединения двух узлов с высоким индексом ЦСВ в различных областях при помощи связи.

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

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

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

На фиг.8 представлено схематичное изображение процедуры прививки мостовых узлов с высоким индексом ЦВС.

На фиг.9 представлено схематичное изображение процедуры прививки мостовой связи с высоким индексом ЦВС.

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

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

Осуществление изобретения

1. Топография из топологии.

Существенной особенностью настоящего подхода к анализу структуры сети является определение меры центральности для каждого узла сети. На самом деле существует множество различных мер центральности, большинство которых происходят из социальных наук [10]. Намерение авторов состояло в нахождении меры центральности, подразумевающей связность. Более того, было желательно найти не чисто локальное понятие связности. То есть желательно найти определение связности (центральности) для узла i, сообщающее некоторую информацию о соседних с узлом i узлах. Предположительно, такое понятие центральности может быть полезно для определения хорошо связанных кластеров в сети, и, основываясь на этом, для понимания распространения по той же сети.

Стратегия заключается в выборе центрированности собственных векторов [11] в качестве полезной меры связности. Центрированность собственных векторов (ЦСВ) обладает желательным свойством гладкости как меры на графе (или сети; эти термины взаимозаменяемы), поскольку ЦСВ зависит от свойств соседних узлов данного узла, а не только от самого узла. Это контрастирует с соответствующим свойством «порядок центрированности», который просто подсчитывает исходящие из узла связи, и тем самым связность узла является полностью локальной.

Подробно исследуем эту разницу. Начнем с порядка центрированности. Он измеряет "важность", или связанность, узла при помощи подсчета соседних узлов. Следовательно, относительная центрированность узла i является порядком данного узла, равного k_i. Ясно, что эта величина полностью локальна: заданный узел может иметь очень высокую относительную центрированность, и между тем все его соседние узлы могут иметь очень низкую относительную центрированность - отсутствует связь между данной величиной для узла и его соседних узлов. Индекс центрированности собственного вектора выглядит (по меньшей мере, словесно) только слегка видоизмененным. Для нахождения ЦСВ узла также необходимо подсчитать соседние узлы этого узла, но при этом необходимо взвесить центрированность (ЦВС) соседних узлов. То есть важно не только, сколько людей ты знаешь, но и кого ты знаешь. Математически это выражается формулой

Здесь е_i обозначает ЦСВ узла i, и j=nn(i) означает сумму по всем ближайшим соседним узлам узла i. Данное определение, несомненно, взаимное - центрированность узла зависит только от центрированности соседних узлов, однако их центрированность также зависит от центрированности данного узла. Однако уравнение (1) легко решается для нахождения ЦСВ, если во взвешенную сумму включена константа (const). Более того, предполагая только связность графа и симметричность соединений, можно сказать, что ЦСВ принимает только положительные значения (хотя значения могут быть "практически нулевыми" для крайних узлов).

Тем самым ЦСВ зависит не только от числа соседних узлов, но и от более широких вопросов, таких как число соседних узлов у соседних узлов и т.п. На самом деле ЦСВ узла зависит от всего графа. Однако для целей настоящего обсуждения более существенны две вещи: (i) ЦСВ несомненно измеряет связность некоторым нелокальным образом, и (ii) в связи со свойством (i) значения ЦСВ узлов, лежащих на любом заданном пути на графе, не изменяются случайно и произвольно. То есть выражение (1) вынуждает ЦСВ любого узла быть положительно связанным с ЦСВ его соседних узлов. Можно перефразировать это следующим образом: ЦСВ "гладкая" при перемещении по графу. Более точное математическое описание этой "гладкости" можно найти в [1].

Гладкость ЦСВ позволяет рассуждать в терминах "топографии" графа. То есть в случае, если узел обладает высокой ЦСВ, содержащая узел область также обладает достаточно высокой ЦСВ (из гладкости). Можно представить ЦСВ как гладко меняющуюся "высоту", с горами, впадинами, вершинами и т.п. Следует быть осторожным с тем, что все стандартные понятия топографии предполагают непрерывность описываемой топографией волнистой поверхности (и обычно двухмерность, как земная поверхность). Граф, с другой стороны, не непрерывен; также граф обычно не обладает четким соответствием с дискретной версией d-мерного пространства для любого d. Тем самым следует осторожно пользоваться топографическими идеями. Тем не менее, топографические идеи будут часто использоваться как вспомогательные средства для интуиции. Определения будут стимулированы данным интуитивным рассмотрением, однако будут математически точными и подходящими для случая дискретной сети.

Сначала будет определена "вершина". Вершиной называется точка, которая выше всех своих соседних точек - такое определение может быть применено неизменным к случаю дискретной сети. То есть, если ЦСВ узла выше ЦСВ любого из соседних узлов (так что наблюдается локальный максимум ЦСВ), этот узел называется центром, или центральным узлом. Затем известно существование горы для каждой вершины. Эти горы будут называться областями и играют существенную роль в настоящем рассуждении. То есть каждый не являющийся центром узел должен либо принадлежать одной из областей с некоторым центром, либо лежать на "границе" между областями. Тем самым определение области позволит получить способ разбиения сети на хорошо соединенные кластеры (области).

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

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

На фиг.1 предложено наглядное представление перечисленных выше идей. Представлен простой граф с 16 узлами. Представлены топографические контуры равной высоты (равной ЦСВ). Два центра и соответствующие им горы (области) легко различимы на фигуре. Фигура настойчиво указывает на то, что две области, как определено настоящим анализом, внутренне связаны лучше, чем между собой. Более того, согласно фигуре правдоподобно, что распространение (например, вируса) гораздо легче произойдет внутри области, чем между областями. Тем самым фиг.1 наглядно выражает две задачи, которые желательно достичь при помощи ЦСВ: (i) обнаружить хорошо соединенные кластеры; и (ii) понять процесс распространения.

2. Топография и эпидемическое распространение

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

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

Основное предположение (А) просто и может быть выражено одним предложением:

Центрированность собственных векторов является хорошей мерой силы распространения. (А)

Данная идея была исследована экспериментально и теоретически [2]. Далее последует перечисление качественных аргументов в поддержку предположения (А); затем будут дополнительно исследованы следствия данного предположения. Будет показано, как может быть разработана достаточно детальная картина распространения эпидемии по сети, основываясь на предположении (А) и разработанном авторами структурном анализе, одним словом, основываясь на идеях, воплощенных на фиг.1.

Во-первых, как упомянуто выше, поскольку ЦСВ узла зависит от ЦСВ соседних узлов, изменение значения ЦСВ по сети можно рассматривать как "гладкое изменение". То есть узел с высокой ЦСВ не может быть окружен узлами с очень низкими ЦВС. Конечно, верно, что ЦСВ коррелирует с более простыми мерами центральности, а именно с порядком узла. На самом деле можно сказать, что принципиальная разница между этими мерами заключается в принудительной гладкости ЦСВ по определению самой ЦСВ, в то время как центрированность порядка узла не обладает этим свойством [12]. Однако эта разница может быть нетривиальной. Например, узел с высоким порядком, окруженный большим числом крайних узлов и слабо соединенный с основной массой большой и связной сети, будет иметь низкую ЦВС, несмотря на высокий порядок. Идея состоит в чувствительности ЦСВ к свойствам окрестности, в то время как у порядка узла такая чувствительность отсутствует.

Тем самым, коротко говоря, не существует изолированных узлов с высокой ЦВС. То есть узел с высоким значением ЦСВ находится в области с высоким значением ЦСВ. Однако могут существовать относительно изолированные узлы с низким значением ЦВС, поскольку такая ситуация является самоподдерживающей. Узлы с низким значением ЦСВ могут быть изолированы в смысле обладания малым числом соседних узлов; однако в этом случае соседние узлы все равно не будут иметь большого значения ЦВС. Теперь, если считать основное предположение (А) верным, то не существует изолированных узлов с большой силой распространения. Вместо этого существуют окрестности с большой силой распространения.

Предположим, далее, что инфекция достигла узла с умеренной силой распространения. Предположим также, что данный узел не является локальным максимумом ЦВС; вместо этого у данного узла есть соседний узел или узлы с большей силой распространения. Такое же замечание применимо к этим соседним узлам, до момента достижения одним из узлов локального максимума ЦВС/силы распространения.

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

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

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

На фиг.2 графически выражены перечисленные идеи. Фигура показывает пример с двумя областями по фиг.1, но рассматриваемый со "стороны" - как если бы узел действительно обладал высотой. Начальное заражение возникает в отмеченном черным узле в левой области. Затем инфекция распространяется в первую очередь вверх с увеличивающимся уровнем заражения по мере возрастания "высоты" (=ЦВС, которая определяет согласно предположению силу распространения). Распространение инфекции достигает максимального уровня при достижении центральных узлов области; после этого инфекция "спускается" и заражает оставшуюся часть области. Можно отметить, что данная качественная картина хорошо соответствует различным стадиям классической S-образной кривой инновационной диффузии [13]. Начальная гладкая часть кривой отражает начальное заражение в низких окрестностей, во время данного периода инфекция медленно поднимается в гору. S-образная кривая набирает силу по мере достижения инфекцией более высоких частей горы. Затем наступает период быстрого роста в процессе насыщения вершины горы, одновременно с насыщением склонов. Наконец, уровень заражения замедляется по мере заражения низко лежащих окрестностей.

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

Может возникнуть следующее возражение о простоте картины. Настоящая картина представляет S-образную кривую для одной горы. Тем не менее, известно, что сеть состоит из нескольких областей (гор). Тем самым возникает вопрос о причине возникновения S-образной кривой для сети с несколькими областями.

Предоставленный в данной работе ответ говорит о том, что подобные сети не обязательно проявляют S-образную кривую. То есть приведенные в настоящем рассуждении доводы указывают на наличие S-образной кривой для одной области, образованной вокруг локального максимума ЦВС. Затем, предполагая принадлежность узла единственной области, согласно предпочтительному правилу определения принадлежности области совместная кривая заражения представляет собой сумму кривых заражения для каждой области. Эти кривые для единственной области имеют S-образную форму. Например, в случае начала заражения на крайнем узле, прилежащем только к одной области, данная область может подвергнуться заражению гораздо раньше близлежащих областей. С другой стороны, в случае начала заражения в долине, прилежащей к нескольким вершинам, все эти вершины могут подвергнуться всплеску заражения одновременно, результатом чего окажется сумма примерно синхронизированных S-образных кривых, что в результате даст одну S-образную кривую.

Далее подведены итоги обсуждения и перечислены выводы из данной качественной картины.

а. Каждая область проявляет S-образную кривую.

b. Количество появлений возрастаний/плато на кумулятивной кривой всей сети может превышать единицу; однако данное количество не может превышать количество областей в сети.

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

d. При выполнении того же предположения, для каждой области начальный рост заражения будет проходить в сторону более высокого индекса ЦСВ.

е. Для каждой области при достижении заражением окрестности с высокой центрированностью рост замедляется.

f. Наблюдаемым следствием (е) является заражение центрального узла любой области во время или после, но никак не до замедления.

g. Для каждой области конечная стадия роста (насыщение) характеризуется низкой центрированностью.

3. Математическая теория

В работе [2] авторами была разработана математическая теория для выраженных в настоящей работе качественных идей. Работа [2] фокусируется на двух аспектах, которые в настоящей работе будут просто резюмированы.

Определение силы распространения

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

Подобная зависимость выглядит обоснованной. Соединенный с большим числом узлов с хорошей связностью узел должен обладать большей силой распространения и более высоким индексом ЦСВ, чем узел, соединенный с таким же числом узлов с меньшей связностью. В работе [2] авторами предложено точное определение силы распространения. Рассуждения проходят в два этапа: во-первых, определяется "коэффициент заражения" C(i, j) между любой парой узлов i и j. Этот коэффициент представляет собой взвешенную сумму всех нециклических соединений между i и j. Тем самым множество коротких путей между двумя узлами дадут им высокий коэффициент заражения. Данное определение симметрично, так что C(i, j)=C(j, i).

Затем определяется сила распространения узла i как сумма по всем узлам j коэффициентов заражения C(i, j) относительно узла i. До тех пор, пока граф остается связным, каждый узел будет иметь ненулевой коэффициент C(i, j) относительно любого другого узла, внося вклад в сумму. Каждый узел содержит одинаковое число слагаемых в сумме; однако узлы с большим числом высоких коэффициентов заражения, несомненно, будут обладать большей силой распространения.

Затем в работе [2] описывается способ установки связи между определением силы распространения и ЦСВ, в случае игнорирования ограничения на нециклические связи в определении. Сумма ограничивается всеми нециклическими путями, поскольку циклические пути не вносят вклад в распространение инфекции в SI случае. Данное ограничение делает получение аналитических результатов более сложным.

Математическая теория распространения SI

В работе [2] представлены точные уравнения распространения заражения, начинающегося в произвольном узле, в случае распространения SI. В связи с вероятностной моделью распространения через связи уравнения распространения заражения выражены стохастически в терминах вероятностей. Данные уравнения обычно не решаются, даже в невероятностном случае р=1. В последнем случае проблема вновь заключается в исключении всех нециклических путей. Однако авторами было проведено разложение по степеням р для временной эволюции вектора вероятностей заражения. Данное разложение показывает, что доминирующими составляющими являются составляющие, полученные простым применением матрицы смежности (т.е. игнорируя циклические пути, так как они длиннее и тем самым имеют более высокий порядок р). Затем устанавливается связь с ЦСВ: простое применение матрицы смежности дает веса (вероятности заражения), приближающиеся к распределению, пропорциональному ЦСВ. Тем самым получено некоторое подтверждение сделанного в настоящей работе утверждения о том, что на начальных стадиях заражения фронт заражения двигается по направлению к наибольшему индексу ЦСВ.

4. Проектирование и улучшение сетей

В данном разделе рассуждение коснется задачи проектирования сетей [14]. Представленные авторами идеи имеют ясные следствия для проектирования, заключающиеся в изменении топологии сети, одновременно для задачи предотвращения распространения вредоносной информации (такой как вирусы) и для задачи содействия распространению.

Способы улучшения распространения

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

1. Могут быть добавлены дополнительные мостовые связи между областями. Связи между узлами с высокими индексами ЦСВ в каждой области будут, вероятно, наиболее эффективны. Смотри фиг.4.

2. Как частный случай 1 могут быть соединены центры областей. Смотри фиг.5.

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

4. Все или некоторые центральные узлы могут быть соединены при помощи связующего узла, образуя конфигурацию в форме звезды. Смотри фиг.11В.

Идея 2 представляет собой "интенсивную" версию идеи 1. На самом деле, наиболее интенсивная версия идеи 2 заключается в соединении всех центров со всеми, тем самым образуя полный подграф между центрами. Полный подграф между 5 центрами представлен на фиг.11А. Альтернативой данной конструкции является вставка дополнительного связующего узла, отмеченного белым на фиг.11В, соединенного со всеми центральными узлами посредством одной связи для каждого узла. В некоторых случаях, когда физическая прокладка новых соединений является ресурсоемкой, а установка новых узлов осуществима, конструкция в форме звезды может быть более привлекательной, чем создание полного подграфа. При необходимости соединения n центров конструкция в форме звезды требует добавления всего n новых соединений и одного нового узла, в то время как конструкция полного подграфа требует добавления n(n-1)/2 новых соединений. Комбинации двух данных подходов также возможны; одно подмножество центров может быть соединено как полный подграф, в то время как другое подмножество может быть соединено при помощи связующего узла.

Однако подобные интенсивные подходы на практике могут оказаться сложными или невыполнимыми. В таком случае остаются общие идеи 1 и 3 построения большего числа мостов между областями. Однако нет причины выбирать наиболее интенсивный подход при реализации данной идеи. То есть: следует создавать мосты между узлами с высокой центрированностью на обеих сторонах и предпочтительно как можно больше. Проведенный авторами анализ настоятельно предлагает данную стратегию в качестве наилучшей для изменения топологии сети с целью улучшения распространения. Также может быть выполнен выбор подмножеств узлов с наибольшим индексом ЦСВ в каждой области для последующего объединения данных подмножеств, как показано на фиг.10А. И вновь, в случае задачи минимизации числа добавленных соединений добавление связующего узла, образующего конфигурацию звезды, является подходящим решением. Это решение показано на фиг.10В. Соединение всех узлов в одном подмножестве со всеми узлами во втором подмножестве потребует k·g новых связей, где k и g представляют собой количество узлов в первом и втором подмножествах. В подходе со связующим узлом, образующим конфигурацию звезды, количество добавляемых связей существенно меньше: только k+g. Тем самым очевидно преимущество подхода с образующим конфигурацию звезды связующим узлом.

Можно отметить, что наиболее интенсивный подход в результате почти гарантированно приведет к топологии с одной областью (и тем самым с эффективным распространением информации). Обосновывающее данное утверждение рассуждение просто. Во-первых, существующие центры не могут остаться центрами после их соединения между собой - поскольку два прилегающих центра не могут одновременно быть локальными максимумами ЦСВ (или другого индекса). Тем самым либо в результате изменения топологии сети среди нецентральных узлов появляются новые центры, либо в результате модификации сохраняется только один центр. В последнем случае сеть состоит из единственной области. Утверждается, что первый случай маловероятен: можно заметить, что индекс ЦСВ существующих центров (вероятно) увеличивается (растет) после изменения больше, чем индекс ЦСВ других узлов. То есть предполагается "возрастание" существующих центров относительно других узлов при соединении центров в полный подграф, наряду со сближением центров друг с другом. В случае истинности данной идеи "возрастания", в результате изменения топологии будет получена сеть с одним центром и одной областью.

Средства предотвращения распространения

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

1. Могут быть привиты центры (смотри фиг.6), возможно вместе с небольшой окрестностью вокруг них.

2. Вместо этого может быть выбрано кольцо узлов вокруг каждого центра (с радиусом два или три узла), и данное кольцо может быть привито. На фиг.7 представлено привитое кольцо узлов, находящееся в шаге от каждого центра.

3. Могут быть привиты мостовые связи. Смотри фиг.9.

4. Могут быть привиты узлы на концах мостовых соединений. Смотри фиг.8.

Отмечается, что идеи 1 и 2 применимы даже в случае наличия единственной области. Идеи 3 и 4 могут быть использованы при наличии множества областей. Отмечается, что прививка мостовой связи (идея 3) не совпадает с прививкой двух узлов, к которым прилегает мостовая связь (идея 4): прививка узла удаляет данный узел и все соединенные с ним связи, в то время как прививка связи удаляет только данную связь. На фиг.8 привиты два узла на концах мостовой связи, в то время как на фиг.9 привита только сама мостовая связь.

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

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

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

Ссылки

[1] Geoffrey Canright and Kenth Engo-Monsen, "Roles in Networks". Science of Computer Programming, 53 (2004) 195-214.

[2] Geoffrey Canright and Kenth Engo-Monsen, "Spreading on networks: a topographic view", submitted to European Conference on Complex Systems (ECCS05).

[3] Geoffrey Canright, Kenth Engo-Monsen, Asmund Weltzien, and Fahimeh Pourbayat, "Diffusion in social networks and disruptive innovations". IADIS e-Commerce 2004 proceedings. Lisbon 2004.

[4] M.E.J. Newman, "The structure and function of complex networks". SIAM Review, 45 (2003), 167-256.

[5] Romualdo Pastor-Satorras and Alessandro Vespignani, " Epidemic Spreading in Scale-Free Networks". Phys. Rev. Lett 86 (2001), 3200-3203.

[6] Romualdo Pastor-Satorras and Alessandro Vespignani, "Epidemic dynamics and endemic states in complex networks". Phys. Rev. E 63, 066117 (2001).

[7] M.E.J. Newman, "Spread of epidemic disease on networks". Phys. Rev. E 66, 016128(2002).

[8] Fred Brauer, "A model for an SI disease in an age- structured population". Discrete and Continuous Dynamical Systems B2 (2002), 257-264.

[9] Yang Wang, Deepayan Chakrabarti, Chenxi Wang, and Christos Faloutsos, "Epidemic spreading in real networks: an eigenvalue viewpoint". Proceedings, 22-nd Symposium on Reliable Distributed Systems (SRDS 2003), 25-34.

[10] Описание многих используемых определений можно найти в: http://www. analytictech.com/networks/centrali.htm.

[11] Р. Bonacich, "Factoring and weighting approaches to status scores and clique identification". Journal of Mathematical Sociology, 2 (1972), 113-120.

[12] Конфигурация звезды до некоторой степени иллюстрирует данную разницу. Предположим, что граф представляет собой звезду с n лучами - то есть граф с одним узлом в центре, соединенный с каждым из n других узлов, и у каждого из этих n узлов нет других соседних узлов кроме центрального. Степень центрированности центрального узла равна n, и у каждого луча звезды степень центрированности равна 1. Индекс ЦСВ центра, однако, только в больше индекса ЦСВ узлов. Тем самым использование ЦСВ, что делает центрированность центра зависящей от соседних узлов, дает снижение (с коэффициентом ) разницы (потенциально большой) в степени центральности между лучами и центром.

[13] Е.М.Rogers, Diffusion of Innovations, 3-rd ed. Free Press, New York (1983).

[14] Обсуждение тесно связанных идей можно найти в М. Burgess, G.Canright, and К.Engo. "A graph theoretical model of computer security: from file access to social engineering". International Journal of Information Security, Volume 3, Number 2, November 2004, pages 70-85.

Изобретение относится к области сетей передачи данных. Технический результат заключается в предотвращении распространения вредоносной информации по сети. Сущность изобретения заключается в том, что способ включает в себя в качестве отличительной характеристики соединение, по меньшей мере, одного узла с высоким индексом центрированности собственных векторов в первой области, по меньшей мере, с одним узлом с высоким индексом центрированности собственных векторов во второй области. Эти соединения могут быть реализованы прямыми связями или при помощи промежуточных узлов, лежащих между соединяемыми узлами. Один способ предотвращения распространения информации или физического потока по сети может включать в качестве отличительной характеристики прививку, по меньшей мере, одного узла с высоким индексом центрированности собственных векторов путем блокирования передачи нежелательной информации по всем связям по направлению к указанному узлу или от него. 4 н. и 8 з.п. ф-лы, 11 ил.

1. Способ распространения информации по сети, включающей в себя множество соединенных связями узлов сети, содержащий следующие операции:
(a) отображение топологии множества узлов сети;
(b) вычисление одного или более значений силы соединений между узлами;
(c) вычисление индексов центрированности собственных векторов (ЦСВ) для множества узлов, причем указанные индексы вычисляют на основе одного или более значений силы соединений;
(d) определение узлов, имеющих локальные максимумы индекса центрированности собственных векторов, причем определенные узлы обозначают в качестве центральных узлов;
(e) определение областей, связанных с центральными узлами, и связывание центральных узлов с соответствующими узлами сети в соответствующих им областях;
отличающийся тем, что дополнительно содержит следующие операции:
(f) подразделение для каждой области соответствующих узлов на первую и вторую группы узлов, причем первая группа узлов включает в себя центральный узел указанной области, а вторая группа узлов имеет индексы центрированности собственных векторов меньше, чем узлы, входящие в первую группу;
(g) соединение, по меньшей мере, одного узла сети из первой группы первой области, по меньшей мере, с одним узлом сети из первой группы второй области.

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

3. Способ по п.1, отличающийся тем, что все или подмножество узлов с индексом ЦСВ из первой группы первой области соединяют со всеми или подмножеством узлов с индексом ЦСВ из первой группы второй области.

4. Способ распространения информации по сети, включающей в себя множество соединенных связями узлов сети, содержащий следующие операции:
(a) отображение топологии множества узлов сети;
(b) вычисление одного или более значений силы соединений между узлами;
(c) вычисление индексов центрированности собственных векторов (ЦСВ) для множества узлов, причем указанные индексы вычисляют на основе одного или более значений силы соединений;
(d) определение узлов, имеющих локальные максимумы индекса центрированности собственных векторов, причем определенные узлы обозначают в качестве центральных узлов;
(e) определение областей, связанных с центральными узлами, и связывание центральных узлов с соответствующими узлами сети в соответствующих им областях;
отличающийся тем, что дополнительно содержит следующие операции:
(f) подразделение для каждой области соответствующих узлов на первую и вторую группы узлов, причем первая группа узлов включает в себя центральный узел указанной области, а вторая группа узлов имеет индексы центрированности собственных векторов меньше, чем узлы, входящие в первую группу;
(g) добавление, по меньшей мере, одного нового узла и соединение, по меньшей мере, одного существующего узла из первой группы в первой и второй областях с указанным, по меньшей мере, одним новым узлом.

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

6. Способ по п.4, отличающийся тем, что все или подмножество узлов с индексом ЦСВ из первой группы указанных первой и второй областей соединяют с указанным новым узлом, формируя тем самым граф в форме звезды.

7. Способ предотвращения распространения информации по сети, включающей в себя множество соединенных связями узлов сети, содержащий следующие операции:
(a) отображение топологии множества узлов сети;
(b) вычисление одного или более значений силы соединений между узлами;
(c) вычисление индексов центрированности собственных векторов (ЦСВ) для множества узлов, причем указанные индексы вычисляют на основе одного или более значений силы соединений;
(d) определение узлов, имеющих локальные максимумы индекса центрированности собственных векторов, причем определенные узлы обозначают в качестве центральных узлов;
(e) определение областей, связанных с центральными узлами, и связывание центральных узлов с соответствующими узлами сети в соответствующих им областях;
отличающийся тем, что дополнительно содержит следующие операции:
(f) подразделение для каждой области соответствующих узлов на первую и вторую группы узлов, причем первая группа узлов включает в себя центральный узел указанной области, а вторая группа узлов имеет индексы центрированности собственных векторов меньше, чем узлы, входящие в первую группу;
(g) прививка, по меньшей мере, одного узла с индексом центрированности собственных векторов из первой группы путем блокирования любой передачи нежелательной информации по всем связям по направлению к указанному узлу и/или от него.

8. Способ по п.7, отличающийся тем, что прививают все или подмножество центральных узлов.

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

10. Способ по п.7, отличающийся тем, что прививают все или подмножество мостовых узлов из первых групп указанных областей.

11. Способ предотвращения распространения информации по сети, включающей в себя множество соединенных связями узлов сети, содержащий следующие операции:
(a) отображение топологии множества узлов сети;
(b) вычисление одного или более значений силы соединений между узлами;
(c) вычисление индексов центрированности собственных векторов (ЦСВ) для множества узлов, причем указанные индексы вычисляют на основе одного или более значений силы соединений;
(d) определение узлов, имеющих локальные максимумы индекса центрированности собственных векторов, причем определенные узлы обозначают в качестве центральных узлов;
(e) определение областей, связанных с центральными узлами, и связывание центральных узлов с соответствующими узлами сети в соответствующих им областях;
отличающийся тем, что дополнительно содержит следующие операции:
(f) подразделение для каждой области соответствующих узлов на первую и вторую группы узлов, причем первая группа узлов включает в себя центральный узел указанной области, а вторая группа узлов имеет индексы центрированности собственных векторов меньше, чем узлы, входящие в первую группу;
(g) определение связей, соединяющих две области, в качестве мостовых связей;
(h) определение мостовых связей, имеющих узлы с индексом центрированности собственных векторов из первой группы на каждом конце указанных связей, в качестве связей с высоким индексом центрированности собственных векторов;
(i) прививка, по меньшей мере, одной связи с высоким индексом центрированности собственных векторов путем блокирования любой передачи нежелательной информации по указанной связи с высоким индексом центрированности собственных векторов.

12. Способ по п.11, отличающийся тем, что прививают все или подмножество мостовых связей с высоким индексом центрированности.