Способи поширення і запобігання поширенню інформації в мережі

1. Спосіб поширення інформації в мережі, причому зазначена мережа містить у собі кілька мережних вузлів, з'єднаних зв'язками, причому зазначений спосіб включає наступні стадії: (a) стадію, на якій відображають топологію зазначених декількох вузлів зазначеної мережі; (b) стадію, на якій розраховують одне чи кілька значень міцності зв'язку між зазначеними вузлами; (c) стадію, на якій для зазначених декількох вузлів розраховують індекси центральності власного вектора, причому зазначені індекси розраховують по зазначеному одному чи декількох значеннях міцності зв'язку; (d) стадію, на якій ідентифікують вузли, що є локальними максимумами зазначених індексів, причому зазначені ідентифіковані вузли позначають як центральні вузли; (e) стадію, на якій ідентифікують області, зв'язані з зазначеними центральними вузлами, і зв'язують зазначені центральні вузли з відповідними вузлами мережі в їх відповідних галузях, який відрізня 2 (19) 1 3 (f) стадію, на якій для кожної області ідентифікують відповідні вузли в першу і другу групи вузлів, причому в зазначену першу групу вузлів включають зазначений центральний вузол зазначеної області, а в зазначену другу групу вузлів включають вузли з меншими індексами центральності власного вектора, ніж у вузлів, які включають у зазначену першу групу; і (g) стадію, на якій додають щонайменше, один новий вузол і з зазначеним, щонайменше, одним новим вузлом з'єднують щонайменше один існуючий вузол з першої групи в першій і другій областях. 5. Спосіб по п. 4, який відрізняється тим, що зазначений спосіб включає стадію, на якій усі чи деяку підмножину центральних вузлів зазначених декількох областей з'єднують прямим зв'язком із зазначеним новим вузлом, у такий спосіб, утворюючи граф у формі зірки. 6. Спосіб по п. 4, який відрізняється тим, що зазначений спосіб включає стадію, на якій усі чи деяку підмножину вузлів із ЦВВ зазначеної першої групи зазначених першої і другої областей з'єднують із зазначеним новим вузлом, у такий спосіб, утворюючи граф у формі зірки. 7. Спосіб запобігання поширенню інформації в мережі, причому зазначена мережа містить у собі кілька мережних вузлів, з'єднаних зв'язками, причому зазначений спосіб включає наступні стадії: (а) стадію, на якій відображають топологію зазначених декількох вузлів зазначеної мережі; (b) стадію, на якій розраховують одне чи декілька значень міцності зв'язку між зазначеними вузлами; (c) стадію, на якій для зазначених декількох вузлів розраховують індекси центральності власного вектора, причому зазначені індекси розраховують по зазначеному одному чи декількох значеннях міцності зв'язку; (d) стадію, на якій ідентифікують вузли, що є локальними максимумами зазначених індексів, причому зазначені ідентифіковані вузли позначають як центральні вузли; (e) стадію, на якій ідентифікують області, зв'язані з зазначеними центральними вузлами, і зв'язують зазначені центральні вузли з відповідними вузлами мережі в їх відповідних галузях, який відрізняється тим, що зазначений спосіб включає також наступні стадії: (f) стадію, на якій для кожної області ідентифікують відповідні вузли в першу і другу групи вузлів, причому в зазначену першу групу вузлів включають зазначений центральний вузол зазначеної області, а в зазначену другу групу вузлів включають вузли з меншими індексами центральності власного вектора, ніж у вузлів, які включають у зазначену першу групу; і (g) стадію, на якій щонайменше один вузол з індексом центральності власного вектора з зазначеної першої групи прищеплюють шляхом блокування будь-якої передачі небажаної інформації з усіх зв'язків у зазначений вузол і з нього. 88963 4 8. Спосіб по п. 7, який відрізняється тим, що зазначений спосіб включає стадію, на якій прищеплюють усі чи деяку підмножину центральних вузлів. 9. Спосіб по п. 7, який відрізняється тим, що зазначений спосіб включає стадію, на якій прищеплюють кільце вузлів на відстані мережних сегментів, щонайменше одного мережного сегмента, від зазначеного центрального вузла. 10. Спосіб по п. 7, який відрізняється тим, що зазначений спосіб включає стадію, на якій прищеплюють усі чи деяку підмножину мостових вузлів зазначених перших груп зазначених областей. 11. Спосіб запобігання поширенню інформації в мережі, причому зазначена мережа містить у собі кілька мережних вузлів, з'єднаних зв'язками, причому зазначений спосіб включає наступні стадії: (a) стадію, на якій відображають топологію зазначених декількох вузлів зазначеної мережі; (b) стадію, на якій розраховують одне чи кілька значень міцності зв'язку між зазначеними вузлами; (c) стадію, на якій для зазначених декількох вузлів розраховують індекси центральності власного вектора, причому зазначені індекси розраховують по зазначеному одному чи декількох значеннях міцності зв'язку; (d) стадію, на якій ідентифікують вузли, що є локальними максимумами зазначених індексів, причому зазначені ідентифіковані вузли позначають як центральні вузли; (є) стадію, на якій ідентифікують області, зв'язані з зазначеними центральними вузлами, і зв'язують зазначені центральні вузли з відповідними вузлами мережі в їх відповідних областях, який відрізняється тим, що зазначений спосіб включає також наступні стадії: (f) стадію, на якій для кожної області ідентифікують відповідні вузли в першу і другу групи вузлів, причому в зазначену першу групу вузлів включають зазначений центральний вузол зазначеної області, і зазначену другу групу вузлів з меншими індексами центральності власного вектора, ніж у вузлів, які включають у зазначену першу групу; (g) стадію, на якій зв'язки, що з'єднують дві області, ідентифікують як мостові зв'язки; (h) стадію, на якій мостові зв'язки з вузлами з центральністю власного вектора з перших груп на кожному кінці зазначених зв'язків ідентифікують як зв'язки з високою центральністю власного вектора; і (і) стадію, на якій щонайменше один зв'язок з високою центральністю власного вектора прищеплюють шляхом блокування будь-якої передачі небажаної інформації по зазначеному зв'язку з центральністю власного вектора. 12. Спосіб по п. 11, який відрізняється тим, що зазначений спосіб включає стадію, на якій прищеплюють усі чи деяку підмножину мостових зв'язків з високою центральністю зв'язку. 5 Даний винахід відноситься до ряду способів керування мережами (як логічними, так і фізичними) у декількох галузях. Зокрема, у даному винаході розкриті способи поширення або запобігання поширення інформації в мережі, де мережа складається з будь-якого числа вузлів, з'єднаних зв'язками. Ці способи, що відповідають вимогам патентоспроможності "винахідницький рівень", засновані на способі аналізу мереж, розкритому в норвезькій патентній заявці NO 2003 5852; зміст цієї заявки посиланням включається в даний опис. Добре відомим фактом цього сторіччя є те, що електронна інформація може розсилатися великому числу людей за дуже короткий час. Для деяких людей (спамерів, блоггерів) цей факт є позитивним, однак для тих осіб, що відповідають за безпеку - це негативний фактор. Битва з вірусами, спамами й іншими видами шкідливої чи небажаної інформації, що самопоширюється, нескінченна. У подальшому описі винаходу проблема поширення інформації розглядалася з погляду мережного аналізу. Даний винахід охоплює як способи допомоги більш ефективному поширенню інформації, так і способи перешкоджання поширенню небажаної інформації (наприклад, вірусів). Більша частина обговорення передумов в описі даного винаходу відноситься до будь-якої мети (допомога бажаній інформації або перешкоджання небажаній інформації). У цьому документі ми будемо часто використовувати термінологію ("епідемія", "інфекція" і т.п.), що звичайно використовується для опису поширення небажаної інформації. Однак у цьому документі, якщо не зазначене інше, ця орієнтована на епідемію термінологія імпліцитно відноситься як до бажаної, так і до небажаної інформації; вона використовується лише для зручності. Існує багато видів моделей поширення епідемій. У можливо найпростішому класі цих моделей кожному вузлу привласнюється лише один із двох можливих станів: "неінфікований" чи "інфікований". Якщо ви не інфіковані ("сприйнятливі"), вважається, що ви можете легко бути інфікованим будьякими інфікованими сусідами. Відповідно, якщо ви інфіковані, ви залишаєтеся , таким протягом експерименту - і залишаєтеся здатним інфікувати будь-яких чи усіх своїх сусідів. Зрозуміло, після закінчення визначеного часу вузли стають "імунними" до інфекції: людина виробляє антитіла, машина отримує антивірусне програмне забезпечення, плітки стають нецікавими, або новинка виходить з моди. У даному випадку основну увагу ми приділяємо більш короткому проміжку часу для того, щоб ми могли ігнорувати стан придбаного імунітету. Технічна назва нашої моделі поширення - "СІ", оскільки вузли мають лише два стани: Сприйнятливе чи Інфіковане. Оскільки поширення відбувається по зв'язках мережі, зрозуміло, що топологія мережі може мати величезний вплив на процес поширення. Зокрема, на нашу думку, найкраще розуміння поширення дає концепція, заснована на огляді всієї системи і на розумінні структури цієї мережі. У більш ранній 88963 6 роботі [1] ми представили один з підходів до аналізу мережної структури, що може бути застосованим до будь-якої мережі із симетричними (ненаправленими) зв'язками. Ми також припустили, що цей аналіз може бути корисним для розуміння поширення по цій мережі. Недавно [2] ми розробили детальну напівкількісну теорію того, як проходить поширення по цих мережах. Ця теорія цілком заснована на нашому структурному аналізі. Даний винахід відноситься до питання активного проектування чи мереж керування ними з метою контролю (допомога чи перешкоджання) поширення. Наш аналіз дає чіткі пропозиції щодо того, як контролювати поширення в обох значеннях. Наш підхід відступає від попередньої роботи в тому, що основну увагу ми приділяємо як тимчасовій, так і просторовій послідовності поширення епідемії. Ми приймаємо просторове розділення, що є не мікроскопічним, а на рівні "околиць" - зв'язкових підграфів із приблизно однаковою здатністю поширення. При більш традиційних підходах (проаналізованих у роботі [4]) починають з "добре змішаної" апроксимації, що кожен вузол з визначеною імовірністю може в будь-який час інфікувати кожен інший вузол. Про цей підхід можна сказати, що він не має мережної перспективи; чи можна сказати, що він постулює граф із украй високим змішуванням, такий, як випадковий граф з високим ступенем чи повний граф. В огляді Newman [4] також обговорюються більш недавні роботи з залученням мережної перспективи. Усі ці роботи засновані на властивостях повного графа, таких, як розподіл за ступенем вершини; крім того, ці підходи були звернені на одержання результатів для повного графа або згодом [5,6], чи з приділенням особливої уваги інфікованій частині протягом дуже тривалого часу [7]. Це останнє питання, безсумнівно, є дуже цікавим для моделей, більш складних, ніж СІ-модель; і велика частина роботи насправді спрямована на поводження СІС-моделі (у якій вузли через деякий час утрачають свою інфекцію й у такий спосіб знову стають Сприйнятливими) або СІР-модель (у якій вузли після утрати своєї інфекції проходять через рефракторний період). Нарешті, слід зазначити, що роботи, у яких аналізуються лише властивості повного графа, не можуть дати ті види конкретних удосконалень, що втілені в даному винаході. У роботі Brauer [8] досліджена СІ-модель для випадку, коли вузли (організми, особливо люди) народжуються і вмирають. Через додавання цих динамічних ознак ступінь стійкої інфекції не обов'язково дорівнює 100%. У цій роботі використовується добре змішана апроксимація, що дає зв'язані звичайні диференціальні рівняння. Тому і вона не може запропонувати локальні конкретні конструктивні удосконалення типу, включеного в даний винахід. Робота, що є, ймовірно, найбільш близькою до дійсної роботи, - це робота Wang et al [9]. Моделлю авторів цієї роботи є СІС-модель у якій вузли можуть бути "вилікуваними"; однак вона заснована на цілком мікроскопічному баченні мережі. Факти 7 чно, їхній оператор тимчасової еволюції - це той же оператор, що і розроблений нами в роботі [2], із двома відмінностями. Одне з них - це їхнє додавання члена "вилікування". Цей член - це просто кратне одиничної матриці і, таким чином, не змінює домінуючий власний вектор - який залишається таким матриці суміжності А. Оскільки їхньою моделлю є СІС-модель, довгострокова частка інфекції не є очевидною, і її необхідно обчислювати. Друга відмінність оператора тимчасової еволюції Wang et al полягає в тому, що автори цієї роботи зневажають перехресними членами, тобто тими, що виникають у результаті багаторазових передач в інфікований вузол. Ця апроксимація є дійсною для малої частки інфекції, тоді як (на чому ми зупинимося нижче) вона може бути також досить гарною апроксимацією, навіть якщо частка інфекції стає великою. Автори цієї роботи Wang et al повідомляють про моделювання, якоюсь мірою підтверджуючих справедливість цього твердження. Варто підкреслити, що в нашій роботі, подібно роботі Wang et al [9], при моделюванні тимчасової еволюції інфекції використовується матриця повної суміжності А. Таким чином, ми починаємо з мікроскопічної основи. Однак ми швидко звертаємося до 'мезоскопічної' картини, на якій обґрунтовано і доцільно говорити про околиці і їхні властивості. Наскільки нам відомо, у цьому відношенні наша робота є унікальною. Ця картина околиць є основою для способів (удосконалення проектування мереж), що складають даний винахід. Метою даного винаходу є створення способу поліпшеного поширення інформації в мережі і відповідного способу з протилежною метою, а саме: перешкодити поширенню шкідливої інформації в мережі. Ці цілі досягаються завдяки способам, розкритим у прикладеній формулі винаходу. У першому аспекті даного винаходу пропонується спосіб допомоги поширенню інформації чи фізичного трафіку в мережі, причому зазначена мережа включає деяку кількість вузлів мережі, з'єднаних зв'язками, причому зазначений спосіб включає наступні стадії: стадію, на якій відображають топологію мережі; стадію, на якій розраховують значення для міцності зв'язку між вузлами; стадію, на якій за зазначеним значенням міцності зв'язку розраховують індекс центральності власного вектора для усіх вузлів; стадію, на якій ідентифікують вузли, що є локальними максимумами індексу центральності власного вектора, як центральні вузли; стадію, на якій групують вузли в області, що оточують кожен ідентифікований центральний вузол; і, як свою відмітну ознаку, стадію, на якій, щонайменше, один вузол з високим індексом центральності власного вектора в першій області з'єднують щонайменше з одним вузлом з високим індексом центральності власного вектора в другій області. Другий аспект винаходу відноситься до способу поширення інформації чи фізичного трафіка в 88963 8 мережі, який, у якості своєї відмітної ознаки, включає стадію, на якій додають, щонайменше, один новий вузол, і стадію, на якій з цим зазначеним вузлом з'єднують, щонайменше, один існуючий вузол з високим індексом центральності власного вектора в кожній з першої і другої областей. У своєму третьому аспекті даний винахід відноситься до способу перешкоджання поширення інформації чи фізичного трафіка в мережі, що відрізняється тим, що щонайменше один вузол з високим індексом центральності власного вектора прищеплюють шляхом блокування будь-якої передачі небажаної інформації з усіх зв'язків у зазначений вузол і з нього. У своєму четвертому аспекті даний винахід відноситься до способу запобігання поширення інформації чи фізичного трафіка в мережі, причому зазначений спосіб відрізняється тим, що щонайменше один зв'язок з високим індексом центральності власного вектора, що з'єднує дві області, прищеплюють шляхом блокування будьякої передачі небажаної інформації по зазначеному зв'язку. Для того щоб зробити винахід більш зрозумілим, нижче наводиться його докладний опис з посиланнями на прикладені фігури, на яких: на Фіг.1 приведене схематичне представлення, на якому показаний топографічний вид мережі, використовуваної при даному розгляді винаходу, із двома "горами" (областями); на Фіг.2 приведена схематична картина, на якій показане поширення інфекції в одній області; дві області на Фіг.1 тепер показані "збоку", так якби вони дійсно були горами; Фіг.3 являє собою схематичну картину протікання інфекції; Фіг.4 являє собою схематичну картину з'єднання зв'язком двох вузлів з високим індексом центральності власного вектора в різних областях; Фіг.5 являє собою схематичну картину з'єднання зв'язком центрів; Фіг.6 являє собою схематичну картину процедури прищеплення центральних вузлів в областях; Фіг.7 являє собою схематичну картину процедури прищеплення кільця (з центром у центральному вузлі області) вузлів, що відстоять від центрів областей на мережний сегмент; Фіг.8 являє собою схематичну картину процедури прищеплення мостових вузлів з високим індексом центральності власного вектора; Фіг.9 являє собою схематичну картину процедури прищеплення мостового зв'язку з високим індексом центральності власного вектора; Фіг.10 являє собою схематичну картину двох різних шляхів з'єднання двох підмножин вузлів; в А усі вузли в одній множині з'єднані з усіма вузлами в іншій множині; у В вставлений додатковий вузол, і цей новий вузол має з'єднання з усіма чи деякими вузлами в кожній підмножині вузлів; новий вузол має зіркоподібну топологію; і Фіг.11 являє собою схематичну картину двох різних шляхів з'єднання множини центральних вузлів; в А всі центральні вузли з'єднані з всіма іншими центральними вузлами; у В вставлений додатковий вузол, і цей новий вузол має з'єднання 9 з усіма вузлами чи з деякою підмножиною центральних вузлів; новий вузол має зіркоподібну топологію. 1. Топографія з топології Істотним аспектом нашого підходу до аналізу структури мережі є визначення показника центральності для кожного вузла мережі. Існують фактично багато різних показників центральності, більшість з який приходять із соціології [10]. Нашою метою було знайти показник центральності, що припускає гарну зв'язність.Крім того, нам потрібно поняття гарної зв'язності, що не є чисто локальною. Тобто, нам потрібно визначення гарної зв'язності (центральності) для вузла і, що дещо розповідає нам про околицю вузла і. Ми думаємо, що цей вид центральності може виявитися корисним для визначення добре зв'язних кластерів у мережі, і, виходячи з цього, для розуміння поширення по цій же мережі. Наша стратегія - вибрати як корисний показник гарної зв'язності центральність власного вектора [11]. Центральність власного вектора (ЦВВ) має необхідну властивість, що полягає в тому, що, оскільки вона залежить від властивостей околиці вузла, а не тільки самого вузла, вона є досить "плавною" по графу (чи мережі; ми використовуємо ці терміни взаємозамінно). Цим вона відрізняється від родинного параметра центральності за ступенем, що просто підраховує зв'язки, що виходять з вузла, і тому є цілком локальним. Конкретизуємо цю відмінність. Почнемо з центральності за ступенем. Вона оцінює "важливість" чи зв'язність вузла просто шляхом підрахунку сусідніх вузлів вузла. Отже, центральність за ступенем вузла і - це його ступінь вершини кі. Зрозуміло, що цей параметр є цілком локальним: даний вузол може мати дуже високу центральність за ступенем, але при цьому всі його сусідні вузли можуть мати дуже низьку центральність за ступенем - кореляція між цим параметром для одного вузла і його сусідніх вузлів відсутня. Центральність власного вектора здається (щонайменше, на словах) лише невеликою модифікацією. Для того щоб визначити ЦВВ вузла, підраховують (знову) сусідні вузли цього вузла, але зі зважуванням підрахунку на центральність (ЦВВ) сусідніх вузлів. Тобто: важливо не те, скільки людей ви знаєте, а кого ви знаєте. Математично це можна представити в такий спосіб: e i = (const ) ´ å ej j =nn(i) Де ei. - ЦВВ вузла і, і j=nn(і) - позначає лише суму для найближчих сусідніх вузлів вузла i. Це визначення є чітко круговим: моя центральність залежить від такої моїх сусідів, але і їх центральності залежать від моєї. Але при цьому рівняння (1) легко вирішується для перебування ЦВВ, поки в зважену суму включена постійна (const). Далі, приймаючи лише те, що граф є зв'язаним, і зв'язки є симетричними, ми знаємо, що значення ЦВВ усі будуть позитивними (хоча для найбільш периферійних вузлів вони можуть бути "практично нулем"). 88963 10 Таким чином, ми бачимо, що ЦВВ залежить не тільки від того, скільки сусідніх вузлів має вузол, але і від подальших питань, таких, як скільки сусідніх вузлів сусідні вузли вузла мають, і т.п. Фактично, у принципі, ЦВВ вузла залежить від повного графа. Однак для наших цілей більш релевантними є дві речі: (1) ЦВВ, безсумнівно, оцінює гарну зв'язність визначеним нелокальним образом, і (2) через (1), значення ЦВВ вузлів на будь-якому даному шляху через мережу не можуть змінюватися випадково і довільно. Тобто, по рівнянню (1) ЦВВ будь-якого вузла повинна бути позитивно зв'язаною з ЦВВ сусідніх вузлів цього вузла. Нам подобається перефразувати це в такий спосіб: якщо рухатися по графу, ЦВВ є 'плавною'. (Більше математичних доводів по відношенню до цієї "плавності" приведено в роботі [1]). Плавність ЦВВ дозволяє міркувати мовою "топографії" графа. Тобто, якщо вузол має високу ЦВВ, його околиця (через плавність) теж буде мати більш-менш високу ЦВВ; тобто, ЦВВ можна представити як плавно мінливу "висоту", з горами, долинами, гірськими вершинами і т.п. Хочемо попередити читача, що всі стандартні поняття топографії припускають, що хвиляста "поверхня", яку описує топографія, є безперервною (і звичайно двомірною, такою, як поверхня Землі). Граф, з іншого боку, не є безперервним; так само як не має (у цілому) чіткої відповідності з дискретними версіями d-мірного простору для будь-якого d. Тому топографічними поняттями варто користуватися з обережністю. Проте, ми будемо часто звертатися до топографічних понять у допомогу інтуїції. Наші визначення будуть надихатися цією інтуїцією, але при цьому будуть математично точними і будуть відповідати реаліям дискретної мережі. Спочатку дамо визначення терміну "гірська вершина". Це точка, що знаходиться вище всіх її сусідніх точок - визначення, яке для випадку дискретної мережі можна застосовувати незмінним. Тобто, якщо ЦВВ вузла вище ЦВВ кожного з його сусідніх вузлів (так, що це локальний максимум ЦВВ), ми називаємо цей вузол Центром. Потім, ми знаємо, що для кожної гірської вершини повинна бути гора. Будемо називати ці гори областями; і вони є важливими об'єктами в нашому аналізі. Тобто, кожен вузол, що не є Центром, повинен або відноситися до гори (області) деякого Центра, або лежати на "границі" між областями. Фактично, наше переважне визначення приналежності області власне кажучи не включає вузлів на границях між областями. Таким чином, наше визначення обіцяє дати нам саме те, що нам було потрібно: спосіб розбити мережу на добре зв'язні кластери (області). От наше краще визначення приналежності області: усі вузли, самий крутий шлях підйому яких закінчується в одному й тому самому локальному максимумі ЦВВ, належать до однієї і тієї ж області. Тобто, будь-який даний вузол може визначити, до якої області він належить, знайшовши свій найвищий сусідній вузол і попросивши цей найвищий сусідній вузол знайти свій найвищий сусідній вузол, і так далі, поки самий крутий шлях підйому не 11 закінчиться в локальному максимумі ЦВВ (тобто, у Центрі). Усі вузли на цьому шляху належать області цього Центра. Крім того, кожен вузол буде належати тільки одному Центру за винятком малоймовірної події, коли вузол має два чи більше найвищих сусідніх вузлів, які мають точно таку ж ЦВВ, але приналежних різним областям. Нарешті, розглянемо поняття "долин" між областями. Грубо кажучи, топографічно долина визначається як не приналежна жодному з гірських схилів, між якими вона пролягає. Отже, при нашому визначенні приналежності області, істотним чином, у долинах не лежить жоден вузол. Але не можна забувати про "простір" між горами: як ніяк, цей "простір" зв'язує області і, отже, відіграє важливу роль у поширенні. Однак цей "долинний простір" звичайно складається лише з міжобласних зв'язків. Ми називаємо ці міжобласні зв'язки мостовими зв'язками. (А будь-який вузол, що лежить точно на границі, може називатися мостовим вузлом). На Фіг.1 приведене наочне представлення цих понять. Ми показуємо простий граф з 16 вузлами. Накреслюємо топографічні контури рівної висоти (ЦВВ). На цій фігурі чітко видні два Центри і гори (області), зв'язані з кожним з них. На фігурі чітко показано, що дві області, визначені нашим аналізом, є краще зв'язними внутрішньо, ніж між собою. Крім того, судячи з цієї фігури, є інтуїтивно імовірним, що поширення (наприклад, вірусу) буде легше відбуватися в межах області, чим між областями. Отже, фігура 1 наочно представляє дві цілі, які ми прагнемо досягти з використанням ЦВВ: (1) знайти добре зв'язні кластери і (2) зрозуміти поширення. 2. Топографія і поширення інфекції Для того щоб зрозуміти поширення з погляду мережі, необхідно якимось чином оцінити вузли в мережі в частині їх "здатності поширення". Тобто, ми знаємо, що деякі вузли відіграють важливу роль у поширенні, у той час як інші відіграють менш важливу роль. Потрібно лише уявити собі крайній випадок зірки: центр зірки є абсолютно критичним для поширення інфекції по зірці; крайові вузли цілком маловажні, маючи лише один аспект (загальний для кожного вузла в будь-якій мережі) у тому, що вони можуть інфікуватися. Зрозуміло, що випадок зіркоподібної топології дає очевидну відповідь на питання, які вузли відіграють важливу роль у поширенні (мають високу здатність поширення). Тоді виникає питання, як можна одержати в однаковій мірі змістовні відповіді для загальної і комплексної топології, для яких відповідь зовсім не очевидна? У цьому розділі ми запропонуємо і розів'ємо якісну відповідь на це питання. Наше основне припущення (А) є простим і може бути виражено одним реченням: Гарним показником здатності поширення є центральність власного вектора (ЦВВ). (А) Ми перевірили це допущення як шляхом моделювань, так і теоретично [2]. Зараз ми приведемо якісні доводи, що підтверджують справедливість допущення (А); потім перейдемо до аналізу висновків цього допущення. Ми побачимо, що мо 88963 12 жемо розробити досить докладну картину того, як у мережі відбувається поширення інфекції, виходячи з (А) і нашого структурного аналізу - коротше, заснованого на ідеях, утілених на Фіг.1. Спочатку згадаємо, що оскільки ЦВВ вузла залежить від ЦВВ його сусідніх вузлів, можна вважати, що значення ЦВВ по мережі є "плавно мінливими" по мережі. Тобто, вузол з дуже високою ЦВВ не може бути оточений вузлами з дуже низькою ЦВВ. Природно, справедливим є і те, що ЦВВ прагне до позитивної кореляції з більш простим показником центральності, а саме, зі ступенем вершини. Фактично, можна сказати, що основне розходження між цими двома показниками полягає в тому, що ЦВВ відповідно до її визначення повинна бути плавною, у той час як центральність за ступенем не повинна [12]. Це розходження може бути, однак, нетривіальним. Наприклад, вузол з високим ступенем, оточений багатьма крайовими вузлами і лише слабко зв'язаний з масивом великої і добре зв'язної мережі, буде мати низьку ЦВВ, незважаючи на свій високий ступінь. Справа в тому, що ЦВВ є чуттєвою до властивостей сусідніх вузлів, у той час як ступінь вершини є нечуттєвим. Таким чином, коротше кажучи, ізольованих вузлів з високою ЦВВ немає. Тобто, будь-який вузол з високою ЦВВ вбудований в околиці з високою ЦВВ. (Можуть бути, однак, відносно ізольовані вузли з низкою ЦВВ, якщо ця ситуація є незалежною. Вузли з низкою ЦВВ можуть бути ізольованими в тому сенсі, що мають дуже мало сусідніх вузлів; але як і раніше залишається в силі те, що їхні сусідні вузли не будуть мати набагато більш високу ЦВВ.) Тепер, якщо приймемо, що наше основне допущення (А) є правильним, то ізольованих вузлів з високою здатністю поширення немає. Навпроти, є околиці з високою здатністю поширення. Тепер припустимо, що інфекція досягла вузла з помірною здатністю поширення. Припустимо також, що цей вузол не є локальним максимумом ЦВВ; навпроти, він буде мати сусідній вузол чи вузли навіть з більш високою здатністю поширення. Це ж зауваження стосується і цих сусідніх вузлів, поки не дійдемо до локального максимуму ЦВВ/здатності поширення. Тепер, з огляду на те, що є околиці, можемо розглянути поширення у випадку околиць, а не одиночних вузлів. Зі змісту здатності поширення випливає, що околиця, що характеризується високою здатністю поширення, буде мати більш швидке поширення, чим околиця, що характеризується низькою здатністю поширення. Відзначимо далі, що ці різні типи околиць (високі і низькі) плавно з'єднуються зонами з проміжною здатністю (і швидкістю) поширення. З цього усього випливає, що, якщо інфекція починається в околиці з низькою здатністю поширення, вона буде прагнути поширюватися до околиці з більш високою здатністю поширення. Тобто: поширення убік околиць з більш високою здатністю поширення швидше, оскільки в цих околицях поширення швидше. Потім при досягненні околиці найближчого локального максимуму здатності поширення і швидкість інфекції досягне максимуму (у 13 відношенні часу). Нарешті, при насиченні високої околиці інфекція повертається "по схилу", поширюючись у всіх "напрямках" з майже насиченої високої околиці і насичуючи низькі околиці. Слід зазначити, що цей розгляд природно підходить до нашої топографічної картини топології мережі. Переклавши попередній абзац на цю мову, одержимо наступне: інфекція на схилі гори буде прагнути рухатися нагору по схилу, у той час як з висотою швидкість інфекції наростає. Вершина гори при її досягненні швидко інфікується; і інфікована вершина потім ефективно інфікує всі інші прилягаючі схили. Нарешті, і з меншою швидкістю, насичується підніжжя гори. Ці ідеї наочно представлені на Фіг.2. На цій фігурі показаний приклад із двох областей на Фіг.1, але якщо дивитися "збоку", немов кожен вузол дійсно має висоту. Початкова інфекція виникає в чорному вузлі лівої області. Потім вона поширюється нагору по схилу зі швидкістю поширення, що росте зі збільшенням "висоти" (= ЦВВ, що говорить нам, відповідно до нашого допущення, про здатність поширення). Поширення інфекції досягає максимальної швидкості при досягненні найбільш центральних вузлів області; потім вона "злітає" і інфікує іншу частину області. Як бачимо, ця якісна картина точно відповідає різним стадіям класичної S-подібної кривої поступового поширення нововведень [13]. Перша, плоска частина S-подібної кривої - це рання інфекція нижньої зони; протягом цього періоду інфекція рухається нагору по схилу, але повільно. При досягненні інфекцією більш високої частини гори Sподібна крива починає злітати. Потім наступає період швидкого наростання з насиченням вершини гори разом із прилягаючими схилами. Нарешті, у міру того, як стають інфікованими зони, що залишаються неінфікованими, які лежать нижче, швидкість інфекції знову сповільнюється. Знову підсумуємо ці ідеї за допомогою графічного матеріалу. На Фіг.3 представлена типова Sподібна крива для інфекції в тому випадку (який ми вивчаємо в цій роботі), коли імунітет неможливий. Над цією S-подібною кривою креслимо графік очікуваної центральності знову інфікованих вузлів залежно від часу. Відповідно до наших доказів, приведених вище, до досягнення найбільш центрального вузла інфікуються відносно мало вузлів навіть притому, що центральність фронту інфекції стійко росте. Зліт інфекції потім приблизно збігається з інфекцією найбільш центральної околиці. Отже, частина Фіг.3 лівіше пунктирної лінії відповідає лівій половині Фіг.2; аналогічно, відповідають один одному праві частини цих двох фігур. Нам можуть заперечити, що ця картина занадто проста в наступному сенсі. Наша картина дає Sподібну криву для одиночної гори. Однак ми знаємо, що мережа часто складається з декількох областей (гір). Тоді виникає питання, чому такі мережі з декількох областей повинні мати єдину Sподібну криву? Відповідаємо: ці мережі не обов'язково повинні мати єдину S-подібну криву. Тобто, наші доводи пророкують, що кожна область - визначена навколо локального максимуму ЦВВ- буде мати єдину 88963 14 S-подібну криву. Потім-приймаючи, що кожен вузол належить одній області згідно з нашим переважним правилом приналежності області - сукупна інфекція / крива інфекції для всієї мережі - це просто сума кривих інфекції для кожної області. Ці останні криві для окремих областей будуть Sподібними кривими. Таким чином, у залежності від відносного часу цих різних кривих для окремих областей, мережа в цілому може мати чи може не мати єдину S-подібну криву. Наприклад, якщо первісна інфекція починає своє поширення з периферійного вузла, що є близьким тільки до однієї області, то ця область може злетіти набагато раніше сусідніх областей. З іншого боку, якщо первісна інфекція починає своє поширення в долині, що прилягає до декількох гір, то усі вони можуть демонструвати зліт майже одночасно причому результат є сумою приблизно синхронізованих Sподібних кривих, отже, єдиної S-подібної кривої. Тепер підсумуємо і перелічимо прогнози, що беремо з цієї якісної картини. а. Кожна область має S-подібну криву. b. Число злетів/плоских ділянок на сукупній кривій для всієї мережі може бути більше одного; але воно не буде більше числа областей у мережі. c. Для кожної області - приймаючи (що буде типовим), що початкова інфекція приходиться не на самий центральний вузол - наростання спочатку буде повільним. d. Для кожної області (при тому ж допущенні) початковий ріст буде в напрямку більш високої ЦВВ. є. Для кожної області, коли інфекція досягає околиці з високою центральністю, ріст "злітає". f. Наслідок, що спостерігається, є для (e) потім таким, що для кожної області найбільш центральний вузол буде інфікований у момент злету чи після нього, але не до нього. g. Для кожної області остаточна стадія росту (насичення) буде характеризуватися низькою центральністю. 3. Математична теорія У роботі [2] ми розробили математичну теорію для якісних ідей, представлених у даному описі. Основну увагу в ній ми приділили двом аспектам, що нижче просто підсумуємо. 3.1 Визначення здатності поширення Перша задача - дати кількісну оцінку й уточнити наше допущення (А). Оскільки (А) відноситься до двох параметрів - здатність поширення і ЦВВ - і остання точно визначена, задача тепер полягає в тому, щоб визначити першу, а потім знайти залежність між цими двома параметрами. Ця залежність інтуїтивно правдоподібна. Вузол, зв'язаний з багатьма добре зв'язними вузлами, повинен мати більш високу здатність поширення і більш високу ЦВВ, ніж вузол, зв'язаний з таким же числом вузлів, але слабко зв'язкових. У роботі [2] ми запропонували точне визначення здатності поширення. Наше міркування включає дві стадії: спочатку визначаємо "коефіцієнт інфекції" C(i,j) між будь-якою парою вузлів i і j. Це просто зважена сума всіх шляхів без зворотного трасування між i і j, причому більш довгим шляхам надається менша вага. Таким чином, велике число 15 коротких шляхів між двома вузлами додають їм високий коефіцієнт інфекції. Наше визначення симетричне, так що C(i,j)=C(i,j). Потім визначаємо здатність поширення вузла і як просто суму по всіх інших вузлах j його коефіцієнта інфекції C(i,j) відносно j. Поки граф зв'язний, кожна вершина буде мати з кожної іншої ненульовий C(i,j), тим самим, вносячи свій внесок у цю суму. Отже, кожен вузол має однакове число членів у сумі, але вузли з багатьма великими коефіцієнтами інфекції будуть мати, природно, більш високу здатність поширення. Потім у роботі [2] ми показуємо, що можна провести міцний зв'язок між цим визначенням здатності поширення і ЦВВ, якщо в цьому визначенні можна зневажити обмеженням до шляхів без зворотного трасування. Ми обмежуємо суму шляхів без зворотного трасування, оскільки у випадку ВІмоделі шляхи зі зворотним трасуванням не сприяють інфекції. Це обмеження затрудняє одержання аналітичних результатів. 3.2 Математична теорія поширення для ВІмоделі У роботі [2] ми дали точні рівняння для поширення інфекції для довільного вихідного вузла у випадку ВІ-моделі. Ці рівняння є стохастичними вираженими мовою ймовірностей - через імовірнісну модель для поширення по зв'язках. Вони звичайно не розв'язувані, навіть у детермінованому випадку при р=1. Проблемою в останньому випадку знову є необхідність виключити шляхи без зворотного трасування. Однак ми виконали розкладання в ступені р для тимчасової еволюції вектора ймовірностей інфекції. Це розкладання показує, що головні члени - це члени, отримані шляхом наївного застосування матриці суміжності (тобто, зневажаючи шляхами зі зворотним трасуванням, оскільки вони довші, отже, з більш високим порядком у р). Потім здійснюється з'єднання з ЦВВ: наївне застосування матриці суміжності дає навантаження (імовірності інфекції), що наближаються до розподілу, пропорційному ЦВВ. Отже, одержуємо деяке підтвердження нашому твердженню, що на початкових стадіях інфекції фронт рухається убік більш високої ЦВВ. 4 Проектування і поліпшення мереж У цьому розділі ми йдемо далі від проблеми аналізу і звертаємося до проблеми проектування мереж [14]. Наші ідеї мають чіткі імплікації для проектування - як для цілі перешкодити поширенню шкідливої інформації (такий, як віруси), так і для цілі допомогти поширенню - у кожнім випадку шляхом зміни топології даної мережі. 4.1 Заходи для поліпшення поширення Ми додаємо своїм концепціям вид нашої топографічної картини. Тепер припустимо, що хочемо запроектувати мережу чи змінити її проект для того, щоб підвищити її ефективність у частині поширення. Виходячи з нашої картини, розумно прийняти, що оптимальною топологією для ефективного поширення є одиночна область. Отже, включаємо в даний винахід чотири концепції, що, як очікується, поліпшать інформаційний потік у мережі, шляхом зміни даної (міжобласної) тополо 88963 16 гії мережі, щоб зробити її більш подібною одиночній області: 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 нових зв'язків, де к і g - число вузлів у кожній підмножині. При підході з зіркоподібним вузлом число доданих зв'язків може бути значно меншим: лише k+g. Отже, перевага підходу з трансляційним зіркоподібним вузлом повинна бути зрозумілою. Слід зазначити, що сама ненажерлива стратегія майже гарантовано дає в результаті топологію одиночної області (і, таким чином, ефективне поширення інформації). Наші міркування прості. Поперше Центри, що існують, не можуть усі залиша 17 тися Центрами після того, як усі вони з'єднані між собою, оскільки два сусідніх вузли не можуть обоє бути локальними максимумами ЦВВ (чи чогонебудь ще). Тому або нові Центри виявляються в числі інших вузлів у результаті зміни топології, або лише один Центр переживає зміну. В останньому випадку ми маємо одну область. Ми доводимо, що перший випадок малоймовірний: відзначаємо, що ЦВВ існуючих Центрів цією зміною (правдоподібно) підсилюється (підвищується) більше, ніж ЦВВ інших вузлів. Тобто, ми вважаємо, що з'єднання існуючих центрів у повний підграф "підніме їх" відносно інших вузлів, а також зведе їх ближче. Якщо ця концепція 'підйому' правильна, то ми прийдемо до одиночного Центра й одиночної області. 4.2 Заходи для перешкоджання поширення Тепер звернемося до проблеми проектування чи перепроектування топології мережі для того, щоб перешкодити поширенню. У цьому випадку проблема складніше, ніж у випадку допомоги. Причиною цьому є те, що ми будуємо мережі саме для того, щоб підтримувати зв'язок і сприяти йому. Тому ми не можемо просто шукати крайнє, "повне" рішення, оскільки ідеальним рішенням для перешкоджання поширення є одна область на вузол, тобто, відключити усі вузли від всіх інших! Замість цього ми повинні розглянути інкрементні зміни даної мережі. Ми розглядаємо два типи стратегій "щеплень": щеплення вузлів (що є рівносильним їхньому видаленню, що стосується поширення) чи щеплення зв'язків (що також є рівносильним їхньому видаленню). Знову включаємо в даний винахід перелік концепцій, цього разу застосовуваних для перешкоджання поширенню: 1. Можна прищепити Центри (див. Фіг.6), можливо, разом з невеликою околицею навколо них. 2. Можна замість цього знайти кільце вузлів, що оточують кожен Центр (з радіусом, можливо, два чи три мережних сегменти) і прищепити це кільце. На Фіг.7 зроблене щеплення кільцю вузлів на один мережний сегмент від кожного Центра. 3. Можна зробити щеплення мостовим зв'язкам. Див. Фіг.9. 4. Можна зробити щеплення вузлам на кінцях мостових зв'язків. Див. Фіг.8. Слід зазначити, що концепції 1 і 2 застосовні навіть у випадку, якщо існує лише одна область. Концепції 3 і 4 можна використовувати, коли знайдені кілька областей. Зверніть увагу, що щеплення мостового зв'язку (концепція 3) - це не те ж саме, що щеплення двох вузлів, з якими цей зв'язок з'єднується (концепція 4): щеплення вузла ефективно видаляє цей вузол і всі зв'язки, з'єднані з ним, у той час як щеплення будь-якого зв'язку видаляє лише цей зв'язок. На Фіг.8 щеплені два вузли на кінцях мостового зв'язку, а на Фіг.9 щеплений лише сам мостовий зв'язок. Крім того, у випадку щеплення зв'язків справедливими є ті ж міркування, що й у випадку додавання зв'язків, а саме: важливою є висота зв'язку. Відповідно до нашого визначення, "ЦВВ зв'язку" це середньоарифметичне значень ЦВВ вузлів на кінцях зв'язку. Тоді концепції 3 і 4 майже напевно найбільш ефективні, якщо мостові зв'язки, обрані для щеплення, мають відносно високі ЦВВ. 88963 18 Прищепити зв'язок означає видалити зв'язок. А "видалення" означає блокування будь-якої і всієї передачі по цьому зв'язку. Тепер, відповідно до цього визначення, можемо сказати, що щеплення вузла означає щеплення ВСІХ зв'язків, з'єднаних з цим вузлом. Таким чином, неможлива передача ні в щеплений вузол, ні з нього. Це рівносильно "видаленню вершини з графа". Для наших цілей закривати вузол, щоб прищепити його, немає необхідності. Потрібно просто блокувати всю передачу в цей вузол і з нього. Можливо ще одне визначення щеплення. Якщо яким-небудь чином можна виявляти і блокувати небажану інформацію і тим самим фільтрувати передачу по зв'язках, то нам не потрібно блокувати ВСЮ передачу по зв'язку, щоб прищепити цей зв'язок. Тобто, якщо ми можемо виявляти небажану, шкідливу інформацію (наприклад, вірус), те досить блокувати лише ЦЮ форму для передачі, а інші повідомлення можна пропускати. Визначення щеплення зв'язку тоді буде виглядати в такий спосіб: блокування будь-якої передачі "небажаної" інформації зі зв'язку. Тоді щеплення вузла можна визначити як щеплення всіх зв'язків, з'єднаних з цим вузлом (як і раніше). Посилання [1] Geoffrey Canright and Kenth Engø-Monsen, "Roles in Networks". Science of Computer Programming, 53 (2004) 195-214. [2] Geoffrey Canright and Kenth Engø-Monsen, "Spreading on networks: а topographic view", submitted to European Conference on Complex Systems (ECCS05). [3] Geoffrey Canright, Kenth Engø-Monsen, Åsmund 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), 167256. [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. E63, 066117 (2001). [7] M.E.J. Newman, "Spread of epidemic disease on networks". Phys. Rev. E66, 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, 22nd Symposium on Reliable Distributed Systems (SRDS 2003), 25-34. [10] A good introduction to many of these definitions may be found in: http://www.analytictech.com/networks/centrali.htm [11] P. Bonacich, "Factoring and weighting approaches to status scores and clique identification". Journal of Mathematical Sociology, 2 (1972), 113120. 19 [12] The star illustrates this difference to some extent. Suppose the graph is a star with n 'leaves' that is, a graph with one node in the center, linked to each of n other nodes, each of which have no neighbour other than the center node. The degree centrality of the center is of course n, and that of the leaves is 1. The EVC of the center is| however only n larger than the EVC of the leaves. Hence using EVC - which makes the centrality of the center dependent on that of its neighbors - gives a reduction 88963 20 (by a factor 1 n ) in the (potentially large) difference in degree centrality between leaves and center. [13] E. M. Rogers, Diffusion of Innovations, 3rd ed. Free Press, New York (1983). [14] For a discussion of closely related ideas, see: M. Burgess, G. Canright, and K. Engø. "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. 21 Комп’ютерна верстка Л. Ціхановська 88963 Підписне 22 Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601