Спосіб керування мережами через аналізування зв’язності

1. Спосіб визначення здатності мережі розповсюджувати інформацію або фізичний трафік, причому зазначена мережа включає низку вузлів мережі, з'єднаних між собою зв'язками, причому зазначений спосіб включає наступні стадії: • стадія, на якій складають карту топології мережі; • стадія, на якій обчислюють значення для міцності зв'язків між вузлами; • стадія, на якій за зазначеними значеннями міцності зв'язків обчислюють індекс власновекторної централізованості для усіх вузлів; • стадія, на якій ідентифікують вузли, що є локальними максимумами індексу власновекторної централізованості, як центральні вузли; • стадія, на якій вузли групують в області, що оточують кожний ідентифікований центральний вузол; • стадія, на якій кожному вузлу присвоюють роль відповідно до його положення в області як центральні вузли, вузли-члени області, межові вузли, мостові вузли, вузли-данглери; • стадія, на якій оцінюють чутливість мережі до розповсюдження, базуючись при цьому на кількості областей, їх розміру і як вони з'єднані, який відрізняється тим, що • включає стадію, на якій присвоюють роль вузлачлена області у даній області усім вузлам, для яких шлях зв'язку найкрутішого підйому на топологічній карті однозначно закінчується у центральному вузлі цієї області. 2. Спосіб за п. 1, який відрізняється тим, що включає стадію, на якій обчислюють значення зазначеної міцності зв'язків, і для цього підраховують кількість різних типів зв'язків, яку будь-яка пара 2 (19) 1 3 88459 4 ність та (або) безпеку та (або) ефективність зв'язку 13. Спосіб за одним з пп. 1-8, який відрізняється у зазначеній мережі. тим, що його застосовують для проектування архі12. Спосіб за одним з пп. 1-8, який відрізняється тектури розподільної мережі для товарів. тим, що його застосовують для проектування архі14. Спосіб за одним з пп. 1-8, який відрізняється тектури енергетичної мережі, для того щоб пократим, що його застосовують для проектування щити надійність зазначеної мережі. транспортної мережі. Даний винахід відноситься до низки способів керування мережами (як логічними, так і фізичними) в межах кількох регіонів. Зокрема, цей винахід розкриває спосіб аналізування мережі, що складається з будь-якої низки вузлів мережі, з'єднаних зв'язками. Майже будь-яку громадську або фізичну структуру, у якій індивідуальні суб'єкти зв'язані разом певними відносинами, можна аналізувати з точки зору мережі незалежно від того, чи є вони соціальними групами, авіатрасами або групами комп'ютерів. Мережі являють собою цікаві об'єкти. Вони мають різноманітну структуру і водночас є простими: вони складаються, у найпростішій формі, лише з вузлів, з'єднаних зв'язками. Абстрактна ідея мережі або графа (термін, що вживається взаємозамінним) дуже корисна й при моделюванні структур, що спостерігаються у реальному світі. Приклади включають: громадські мережі, комунікаційні мережі, „всесвітня павутина", метаболічні й генетичні мережі в біологічних системах, харчові мережі, хворобливі й енергетичні мережі. Коротше, мережа - це проста, нетривіальна абстрактна структура, цікава сама по собі, а також дуже відповідна для багатьох галузей науки й техніки. В галузі телекомунікації теорії щодо керування мережами й структур мереж встановлені вже тривалий час. Розуміти мережу вкрай важливо. Ефективність експлуатації й обслуговування такої телекомунікаційної мережі здебільшого залежатимуть від знання даної мережі. Це важливо стосовно середнього час безвідмовної роботи, а також стосовно поширення пошкодження, наприклад, вірусів, самопоширюваних програм тощо. Щодо мереж передачі даних, ситуація здебільшого така сама. Схожі міркування доречні й для експлуатації мереж електропостачання, особливо що стосується безпеки. При проектуванні й експлуатації електричної мережі важливо мати стійку мережу, щоб, наприклад, запобігти ситуацій, коли велика частина населення залишається без електроенергії через припинення її подачі. З міркувань надійності важливим є аналіз зв'язності мережі. Системне адміністрування неминуче включає керування мережею, котра складається з кількох видів зв'язків. Наприклад: фізичні зв'язки між машинами, логічні зв'язки між користувачами й файлами і громадські зв'язки між користувачами. Важливий аспект системного адміністрування полягає у забезпеченні вільного потоку необхідної інформації через мережу, водночас подавляючи потік шкідливої або дискредитируючої інформації через цю саму мережу. Структура мережі грає вкрай важливу роль у втіленні цих двох важливих і частково суперечних цілей системного адміністрування. Обидві цілі включають розповсюдження інформації через зв'язки мережі; відтак, обидві проблеми дуже чутливі до структури мережі. Через цю залежність розуміння структури мережі може перетворитися на цінну складову системного адміністрування. Крім того, існують, природно, такі мережі, що є водночас громадськими й технологічними. Прикладами служать телефонні мережі, однорангові мережі [10], оверлайнові щодо Інтернет, і комбіновані мережі комп'ютерів, файлів і користувачів, що є повсякденною турботою кожного системного адміністратора. І знов-таки, у цьому випадку безпека здається очевидним застосуванням для цих ідей: наприклад, хтось бажає ідентифікувати вузли, котрим має надатися найвищий пріоритет у захисті проти вірусів. Дослідженням мереж протягом останніх приблизно десяти років приділяється велика увага. Більшість мір структури мереж, що досліджені дотепер [8], мають вигляд властивостей „повного графа", тобто скалярні міри або розподіли, що застосовуються до графа у цілому і вираховуються з використанням усереднення. Прикладами таких властивостей „повного графа" служать розподіл ступенів вершини, діаметр або середня довжина шляху, коефіцієнти кластеризації і поняття „малих світів", що ґрунтується на попередніх двох. Властивості повного графа важливі й корисні; однак вони не спроможні дати повну відповідь на питання: „Як ми можемо зрозуміти структуру мережі?" Є багато прикладів, коли важливим є знання мереж, котрі набувають абстрактнішу форму, аніж телекомунікаційні мережі, мережі передачі даних або електричні мережі. Наприклад, у галузі епідеміології важливим є розуміння громадських мереж і як ці мережі сприяють розповсюдженню хвороб. У галузі розподілу інформації важливо знати механізми, що регулюють розповсюдження інформації серед населення - чи то на місцевому, чи то на глобальному рівні. Дивлячись на відносини між людьми або громадські мережі, увагу приділяють зв'язкам між фізичними особами, а не їх категоріям або тому, що їх характеризує. Отже, громадська мережа - це будь-яка група осіб, у якій фізичні особи мають певне відношення одна до одної. Осіб з високим ступенем громадського впливу у громадських мережах часто відносять до категорії неформальних лідерів. Вони є впливовими в силу свого досвіду або в силу свого соціального стану. У будь-якому разі цей вплив часто проявляється у наданні неформальним лідерам великої кількості громадсь 5 88459 6 ких контактів; вони зв'язані з великою кількістю "авторитетні джерела" вказують інші. Ці ідеї молюдей. Це, природно, є логічним: мати громадсьжуть бути дуже корисними при аналізуванні всекий вплив означає, що ви маєте здатність керувасвітньої павутини (WWW): "авторитетні джерела" є ти великою кількістю людей. вірогідними гарними кінцевими точками інформаКорисність цієї ідеї для громадських мереж виційного пошуку, а "концентратори" корисні у спряглядає очевидною [4]. Очевидно, що цікаво іденмовуванні пошуку на "авторитетні джерела". Здатифікувати спільноти у мірній громадській мережі. ється очевидним, що схожі ролі виникають й у Прикладом із дещо відрізним забарвленням є мегромадських мережах: іноді дехто знає, хто саме режа статевих контактів. Тут також ці ідеї можуть має необхідну інформацію ("авторитетне джеребути вельми корисними у діяльності, спрямованій ло"); іншим разом комусь треба спитати про це у на обмеження розповсюдження хвороб, що перегарного "концентратору". даються статевим шляхом: можливо хтось зосеПраця Клайнберга дає нам індекси для кожноредиться на двох цілях, що доповнюють одна одго вузла у мережі. Ці індекси розповідають нам ну, а саме: (1) запобігання інфекції центральних корисну інформацію про роль (ролі), яку вузол грає вузлів кожної спільноти і (2) запобігання передачі у мережі. Ця інформація вельми відрізняється від хвороби через мостові вузли. інформації повного графа; і однак вона ще й досі З огляду на вищезазначене, мережі заслугодобувається, принаймні, як первісно представлевують на серйозні дослідження. Мережа - це одна на, виключно з топологічної структури графа. з найпростіших абстракцій структури, яку можна Іншим аспектом графа, котрий знов-таки відрівивчати; втім досягнення розуміння структури мезняється від властивостей повного графа, є спільрежі є нетривіальною справою. нотна структура графа. У тій самій статті КлайнУ науковій галузі мережевого аналізу є кілька берг пропонує, як знаходити такі спільноти у шляхів оцінити централізованість мережевихвузграфах, наприклад, у Web. Використовувані мателів. Одна з цих мір називається власновекторною матичні інструменти є в основному такими самицентралізованістю. Власновекторна централізовами, що й використовуються для знаходження оціність (ВВЦ) була визначена на початку сімдесятих нок концентратора/авторитетного джерела - що років Боначичем [2]. Ідея, на якій ґрунтується ВВЦ, означає, серед іншого, що розкладення графа на - важливо не лише те, наскільки багато людей ви спільноти також ґрунтувалося виключно на струкзнаєте, а також наскільки важливими (центральтурі графа без залучення будь-якого знання або ними) вони є, що визначає, наскільки важливими властивостей вузлів або зв'язків. Крім того, можна (центральними) є ви. Отже, фактично це є рекурвідзначити, що розкладення графа на підспільноти сивне визначення: моя важливість (централізовадає нову інформацію про ролі, що грають вузли: ність) залежить від важливості (централізованості) вони можуть бути „лідерами" у деякому сенсі; момоїх сусідів, яка в свою чергу залежить від моєї же так трапитися, що вони лежать ні у якій спільважливості (централізованості). Це рекурсивне ноті, або можуть лежати на „краю"; і вони можуть визначення має на меті дозволити нам ідентифікуграти важливу роль у з'єднуванні кількох спільнот. вати ті концентратори, що є насправді впливовими Багато інших праць присвячені тій самій проз точки зору всієї мережі. В противному випадку блемі: як знаходити „природні" спільноти у орієнвизначення, що враховувало важливість лише тованому графі такому як Web. Гірван і Ньюмен того, наскільки багато сусідів ви маєте, напевне [5], напроти, розглянули це питання для неорієннаразилося б на ризик призначення центрів ізотованих графів. їх основний підхід - визначати спільованих кластерів концентраторами мережі. Стольноти спочатку через знаходження їх „меж", зоксовно громадських мереж, ці центри є впливовими рема, знаходження зв'язків з високою лише в обмеженому сенсі, оскільки їх вплив далі їх „проміжністю", видалення якої розбиває граф на безпосередніх сусідів не поширюється. підспільноти. Праця Клайнберга [7], що присвячена мереМетою цього винаходу є створення способу жам з орієнтованими зв'язками, відкриває певну мережевого аналізу, застосовного до фізичних корисну перспективу. Клайнберг розглядав орієнмереж або логічних мереж, що існують як овертований граф, визначений двома відрізними типалейні мережі зверху фізичної мережі. Важливим ми ролі для вузлів на графі, і вказав, як розрахувазагальним аспектом є ідентифікація зв'язків (фізити індекси, що дають кількісну оцінку ступеню, у чних або логічних), через які може протікати інфоякому кожний вузол грає ці два типи ролі. Тобто, рмація. кожному вузлу в орієнтованому графі можна приІншою метою цього винаходу є створення своїти оцінку „авторитетне джерело" і оцінку "кон„природного" засобу, тобто засобу, що базується центратора". Важливо відзначити, що ці оцінки виключно на топології графа, розкладення неорієможуть базуватися виключно на топології графонтованого графа на спільноти. Буде визначений незалежності будь-яких питань змісту або значеннабір ролей для вузлів графа таким чином, що ня або „властивостей" вузлів. кожному вузлу буде присвоєна одна і тільки одна Назви цих двох типів ролі передають їх знароль. Тобто, на відміну від підходу Клайнберга, чення. Вузли з високою оцінкою "авторитетного для цього застосування необхідно, щоб ролі були джерела" - це вузли, що є важливими, оскільки на бінарними (Так/Ні) властивостями вузлів - а також них вказують інші важливі вузли - фактично, вузли виключними. з високими оцінками "концентратор". А останні Відомі рішення [13, 3] докладніше показали, як отримують свої високі оцінки "концентратор" через застосовувати аналіз, представлений тут, до мевказування на гарні вузли "авторитетного джерережі комп'ютерів з багатьма користувачами. Прола". Коротше: "концентратори" самі вказують, а на понується природний шлях розкладення мережі на 7 88459 8 добре з'єднані кластери й присвоєння змістовних Ідея, котру переслідує це застосування, поляролей в інформаційному потоці до кожного вузла у гає у тому, що „добра зв'язність" може розглядатимережі. ся як функція висоти у дискретному просторі (граПоставлені цілі досягаються у способі мерефі). Якщо функція висоти за цим винаходом є жевого аналізу, розкритому у п.1 доданої формули достатньо гладкою, можна використовувати ідеї, винаходу. Зокрема, пропонується спосіб аналізущо є відповідними для гладких поверхонь у безпеванняздатності мережі розповсюджувати інфоррервному просторі. Тобто, щоб визначити області мацію або фізичний рух, причому зазначена меу мережі, цей винахід використовуватиме топорежа включає низку вузлів мережі, з'єднаних між графічну картину. Області відповідатимуть „горам" собою зв'язками, причому зазначений спосіб із центром кожної області, що відповідає вершині включає наступні стадії: гори. Потім визначаться межі між областями як - стадія, на якій складають карту топології меточки, однозначно пов'язані з однією гірською обрежі; ластю. - стадія, на якій обчислюють значення для міВизначені ролі - це такі: „лідер" спільноти (обцності зв'язків між вузлами; ласті); член спільноти; і два типи ролей для вузлів - стадія, на якій за зазначеними значеннями у „межовому наборі", тобто вузли, що не належать міцності зв'язків обчислюють індекс власновектордо будь-якої спільноти. ної централізованості для усіх вузлів; Прийнятий підхід приблизно нагадує підхід Гі- стадія, на якій ідентифікують вузли, що є лорвана і Ньюмена [5]. Пропонується починати не з кальними максимумами індексу власновекторної „країв", а з „центрів" спільнот. З цієї вихідної точки централізованості, як центральні вузли; посуваються „назовні", щоб знайти членів і, напри- стадія, на якій вузли групують в області, що кінці, межові вузли. Представлений набір ролей є оточують кожний ідентифікований центральний повним і несуперечливим у тому сенсі, що ці вивузол; значення забезпечують єдину й однозначну асоці- стадія, на якій кожному вузлу присвоюють ацію однієї ролі з кожним вузлом у графі. роль відповідно до його положення в області як Люди, що спілкуються між собою, утворюють центральні вузли, вузли-члени області, межові громадську мережу, зв'язки у якій ґрунтуються на вузли, мостові вузли, вузли-данглери; їх спілкуванні. Ці зв'язки можуть відрізнятися за- стадія, на якій оцінюють чутливість мережі до лежно від типу використовуваного середовища розповсюдження, базуючись при цьому на кількостелефонія, особисте спілкування або пошта. Отже, ті областей, їх розміру і як вони з'єднані. громадську мережу можна описати як мультіплекПереважні варіанти здійснення винаходу описну: це є мережа, у якій вузли пов'язані різними сані у подальших залежних пунктах формули витипами зв'язків. Хоча громадські відносини, що находу. зв'язують різних осіб, можуть існувати незалежно Для полегшення розуміння винаходу, нижче від типу використовуваного середовища, тип севін докладно описуватиметься з посиланням на редовища відіграє важливу роль у визначенні зв'ядодані фігури. На цих фігурах: зків, оскільки кожне середовище є відрізним канаФігура 1 представляє собою схему, на якій золом для інформаційного потоку. Різні середовища бражені мостовий вузол (ліворуч) і мостовий вузол зв'язку є у цьому сенсі аналогічними мовам. Наі данглери (праворуч). приклад, особа, що бажає досягти багатьох вузлів Фігура 2 ілюструє простий граф з двома облау мережі, має бути спроможною зв'язуватися честями. рез кілька типів середовища - вона повинна розФігура 3 ілюструє той самий граф, що на Фігурі мовляти переважною „мовою" інших вузлів. Ця 2, але з областями, визначеними за іншим правиідея зв'язків, диференційованих за середовищами, лом. Показані також значення ВВЦ для вузлів. справедлива для більшості видів мереж: хвороби, Фігури 4, 5 і 6 показують результуючі графи наприклад, можуть розповсюджуватися через низпроекту ΜΑΝΑ [4] з використанням трьох різних ку різних переносників інфекції, а зв'язки у трансмір для міцності зв'язків. портних мережах можуть складатися з багатьох Фігура 7 представляє собою блок-схему, що різних транспортних засобів, наприклад, автомобіілюструє спосіб, використовуваний для вирахулі, літаки або потяги. вання індексу власновекторної централізованості. Міри міцності зв'язків і ВВЦ У цьому винаході розкриваються корисні й ціМіцність зв'язків у цьому типі мультиплексної каві застосування ідей мережевого аналізу. Єдимережі можна визначити різними шляхами. Ми ною передумовою є те, що зв'язки є неорієнтовазгадуємо чотири: ними. Під неорієнтованими зв'язками ми маємо на 1) Можна просто заявити, існує чи не існує увазі зв'язки, що не вказують у конкретному назв'язок (будь-якого типу). Чисельно присвоюють 0 прямку. У всесвітній павутині web-сторінка може для „немає зв'язку" та 1 для „деякий зв'язок". вказувати на іншу сторінку, але ця сторінка не 2) Можна підрахувати кількість різних середообов'язково повинна вказувати назад. У цьому вищ, що з'єднують будь-яку пару вузлів, тобто, прикладі сторінки напевне з'єднуватимуться орієнкількість різних середовищ, що мають будь-який тованим зв'язком. Якби обидві сторінки зв'язувапотік субстанцій або інформації між будь-якими лися між собою гіперпосиланням (кожний зв'язок, двома вузлами у мережі. що йде в кожному напрямку), такі зв'язки могли б 3) Можна оцінити загальний потік між будьстиснутися в один, неорієнтований зв'язок. За цим якими двома вузлами у мережі. Для цього необвинаходом, усі мережі розглядаються як такі, що хідно перевести наявні дані у загальну міру. Таким складаються з неорієнтованих зв'язків. чином, ця міра дає чисту кількість потоку (напри 9 88459 10 клад, хвилини або слова для середовища зв'язку) середовища і виміряний у спільній одиниці виміру) між будь-якими двома вузлами у мережі. за деякий даний інтервал часу. Тобто: 4) Четверта альтернатива - визначати міцність = V A де с - індекс, що масштабуоб' єм ij å c,ij зв'язків через суміш (2) й (3). Тобто, підраховують c кожне середовище (як у (2)), але зважене (як у (3)) ється через „кольори" (середовища), Vc,ij - загальчастиною потоку для середовища, що використоний об'єм зв'язку у середовищі с між вузлами i та j. вується даною парою. 4) Нарешті, пропонується суміш підходів 2 і 3, Традиційний шлях визначення міцності зв'язків щоб надати вагу як об'єму потоку, так і наявності вказаний під номером 1. Спосіб З також є відомий. кількох середовищ. Отже, кожному середовищу с і Способи 2 й 4 є нові й патентоздатні способи випарі вузлів ij ми даємо „оцінку", що є частиною значення міцності зв'язків. (вносимою парою ij) загального зв'язку (у сенсі Індекс власновекторної централізованості комунікації), що використовує середовище с у ме(ВВЦ) математично визначений як кореневий вларежі. Нехай VT,c означає загальний об'єм (по усій сний вектор матриці. Найпростішим і найпоширемережі) зв'язку (у сенсі комунікації) з використаннішим способом знаходження кореневого власного ням середовища с. Тоді нашу „змішану" міру міцвектору матриці є „степеневий метод" [14]. Цей ності зв'язків можна записати як метод включає повторювані перемноження на век= å Vc,ij / VT,c . A тор ваг матрицею. Перемноження на вектор ваг зміш ij c матрицею є еквівалентним тому, що називається Пропонованим способом дані потоку перетво„поширенням ваг": воно перерозподіляє набір ваг рюють на матрицю суміжності, використовуючи за певним правилом. Повторювані перемноження один з чотирьох описаних вище способів, щоб даваг (з повною нормалізацією загальної ваги) дає ти кожному елементу матриці міру міцності зв'язстійкий розподіл, що є домінуючим або кореневим ків. Потім вираховують кореневий власний вектор власним вектором. Вони є оцінками, використовурезультуючої зміненої матриці суміжності. Це дованими як індекс централізованості за цим виназволяє нам присвоювати індекс (додатне число) ходом. усім вузлам у мережі, даючи їх централізованість Для ясності на Фіг.7 ми ілюструємо застосувідповідно до однієї з наших чотирьох мір. Вузли з вання степеневого методу. На цій фігурі із викоринайвищою централізованістю розглядають як найстанням рівнянь, пояснених раніше, розпочинають більш центральні вузли у мережі. Це дозволяє процес и вибирають початковий вектор w0 (стадія способу видавати перелік мережевих добірок та їх S401). При кожній ітерації вираховують нову вагу безпосередніх сусідств. Індекс централізованості wnew (стадія S403) через перерозподіл ваг відповіуможливлює також створювати топографічну карту дно до дії матричного оператора. Цю нову вагу мережевої структури, графічну візуалізацію мерепотім нормалізують (стадія S405). Потім проводять жі, що показує найбільш центральні вузли як локатест на збіжність (стадія S407). Якщо вага збіглальні „піки". ся, процес закінчують. Якщо ні, вираховують нову Ролі у мережі вагу і процес повторюють, доки вага не збіжиться. Останньою метою цього винаходу є присвоєнДля аналізу мультиплексних громадських меня природної й однозначної ролі кожному вузлу у реж міру ВВЦ було узагальнено з включенням мережі, базуючись при цьому виключно на тополотрьох інших мір міцності зв'язків (2-4), згадуваних гії графа. Як вже відмічалося, Клайнберг знайшов вище. Зміна загальної ідеї ВВЦ, застосована до дві такі ролі для орієнтованих графів: концентранових способів 2 і 4, полягає у наступному: вузол є тори та авторитетні джерела. Концентратори є центральним, якщо він має багато сусідів з висоприродно гарними у вказуванні на гарні авторитекою централізованістю - та використовує багато тні джерела, а авторитетні джерела є природно різних типів середовищ. Далі описується, як втілигарними у тому, що на них вказують гарні концентти цю загальну ідею для кожного з чотирьох підхоратори. Вже з цих простих граматичних виразів дів до визначення міцності зв'язків, розглянутих можна побачити, що відмінність між концентратовище. рами й авторитетними джерелами зникає, якщо 1) Для мультиплексних мереж можна було б ребра графа перетворюються на неорієнтовані використовувати традиційний підхід, у якому мат(таким чином, що „вказування на іншориця суміжності A складається лише з нулів й го"=„вказування на самого іншим"). Математика одиниць; але він повністю нечутливий до кількості дає той самий результат: для неорієнтованого середовищ, використовуваних кожною парою вузвипадку матриця суміжності є симетричною: А=А Т, лів. і відтак такими самими стають матриці, що визна2) У цьому разі ми просто замінимо матрицю чають концентратори та авторитетні джерела. Коротше, в разі неорієнтованих графів ці два A , усіма елементами якої є або 0, або 1, на маттипи ролей зводяться в одну. Цією однією роллю рицю A , яка визначається наступним чином: (точніше, індексом, що дає кількісну оцінку ступеколір ня, у якому вузол грає цю роль) є власновекторна ö централізованість. елемент æ A ç колір ÷ дорівнює кількості „кольорів" è ø ij Оператор концентратора ААТ і оператор авторитетного джерела АТА просто стають А2, корене(відрізних середовищ), що з'єднують вузли і та j. вий власний вектор якого є таким самим, як для А. 3) У цьому разі одиниці у традиційній матриці Отже, встановлено, що дві з ролей, ідентифіA заміняють додатним дійсним числом, що дає кованих у праці Клайнберга з орієнтованими гразагальний об'єм потоку (підсумований через усі ( ( ) ) 11 88459 12 фами, для неорієнтованого графа стають однією чення кожної гори. При цьому слід бути обережроллю (одним типом ролі). У подальших розділах ним і розбити визначення області на дві частини: цей тип ролі називається гарною зв'язністю або власно визначення, що відноситься до правила, власновекторною централізованістю. Проводитиале не уточнює його, і правило. Це необхідно чеметься подальше дослідження відмінностей серед рез те, що для дискретного випадку можливі правузлів неорієнтованого графа, іншими словами, вила, більше одного, й у такому разі дається виміж кількома відмінними ролями, яку можна призначення області, що ідею „гори" захоплює, але своїти будь-якому даному вузлу. Визначення цих правило залишає не уточненим. ролей наведено у наступному розділі. ВласновекОбидва наведені вище правила відповідають торна централізованість (ВВЦ) буде функцією виінтуїтивно обґрунтованому критерію, що сусіди соти і, відтак, вихідною точкою. біля центру повинні (як правило) належати цій Визначення ролей області. (Врешті-решт, саме кількість і зв'язність Треба пояснити різницю між „типом ролі" та сусідів центру дають йому його високу ВВЦ). Оби„роллю". З кожним вузлом можна пов'язати індекси два правила легко втілити й простим ітеративним або „оцінки" у дійсних значеннях: оцінки концентчином - починаючи з центрів й просуваючись наратора й авторитетного джерела для орієнтованозовні від них, „забарвлюючи" вузли відповідно до го графа й оцінки ВВЦ для неорієнтованого графа. областей (центрів), до яких вони належать. Однак Це є типи ролі; фактично, справедливо зазначити, правило найкрутішого підйому є правилом, котре є що усі три оцінки представляють деякий тип найточнішим для топографічної картини. централізованості. Усі вузли мають деякий ступінь Межі - між областями централізованості; і „перебування центральним" На безперервній топографічній поверхні є точнапевно є типом ролі. Під роллю, однак, у цьому ки, що лежать між горами і не належать до будьдокументі мається на увазі бінарна (так/ні) відмінякої однозначної гори. Може трапитися так, що ність, застосована до кожного вузла, і кожний вуаналогічні точки існуватимуть і для дискретного зол отримує одне „так", й, отже, йому присвоюють випадку. єдину й однозначну роль. Централізованість (тип Вузли, котрі не можна асоціювати з будь-якою ролі) дасть гладку функцію висоти по графу, дооднією горою, відносять до Межового набору. зволяючи використовувати топографічні критерії Межові Вузли: будь-який вузол, щодо якого присвоювання ролі („Так" або „Ні") кожному вузлу. однозначне правило членства Області дає більш Центри ніж одну відповідь, є Межовим Вузлом. Для простоти й читабельності, підтримують Інтуїтивно, про межові вузли можна подумати картину гір, долин, перевалів тощо для функції як про такі, що „з'єднують області". Але, якщо повисоти. Кожну гору можна визначити її піком. Пік думати трішечки більше, з'ясовується, що не всі це локальний максимум функції висоти. Першою межові вузли рівні у цьому відношенні. Деякі мероллю є тоді пік гори. жові вузли й насправді відіграють важливу роль у Центр: будь-який вузол, що є локальним макз'єднуванні двох або більше областей: вони лесимумом власновекторної централізованості, є жать на шляху, що з'єднує відповідні центри (і, Центром. відтак, області) (див. ліворуч на Фігурі 1). Інші вузОбласті ли можна видалити без будь-якої втрати ступеня Кожна гірська вершина визначає гору. Отже, з'єднання між областями (див. праворуч на Фігурі кількість областей у графі дорівнює кількості 1). Отже, природно дати набору межових вузлів центрів. (Далі, за винятком, коли визначатимуться визначення двох різних ролей. ролі, прописні букви не використовуватимуться; Мостовий Вузол: Межовий Вузол, що лежить значення має бути ясним з контексту). Області принаймні на одному шляху, що з'єднує два зазвичай складаються з більш ніж одного вузла; Центри, який не змінює самостійно свою трасу, є відтак, роллю для вузла може бути не область, а Мостовим Вузлом. Член Області. Данглер: будь-який Межовий Вузол, що не є Член Області: кожний вузол, що можна одноМостовим Вузлом, є Данглером. значно асоціювати з єдиним Центром за однознаДанглери, звичайно, можуть вводити в мережу чним правилом, є членом Області цього Центру і, нову інформацію, але вони не грають значної ролі відтак, Членом Області. у транспортуванні інформації між областями. Залишається уточнити термін „однозначне Нарешті, необхідно виділити клас зв'язків, що правило". Пропонується надавати для „однозначграють важливу роль у з'єднуванні областей. Підного правила" два можливих вибори, а саме: става для цього полягає у тому, що межовий набір Правило 1 (відстань). Вузол є пов'язаний із для правила найкрутішого підйому є взагалі дуже Центром С, якщо він ближче (за кількістю „стрибмалим або нульовим. У цьому випадку залишаєтьків" на найкоротшому шляху) до С, ніж до будься доцільним виділити ті елементи мережі, що якого іншого Центру C0. з'єднують області. Отже, наводимо визначення: Правило 2 (найкрутіший підйом). Для кожного Мостові Зв'язки: будь-який зв'язок, кінцеві точвузла і шлях найкрутішого підйому, що починаєтьки якого лежать у двох різних областях, є Мостося в і, закінчиться в одному (або кількох) Центрах. вим Зв'язком. Якщо він закінчується в єдиному Центрі, то вузол i Мостові зв'язки з'являться для будь-якого зає пов'язаний із цим Центром. значеного вище правила області. Можна уявити Ці правила є просто версія з дискретним доправила визначення областей, що дають „жирні" меном асоціювання частини домену (базисного межі. Наприклад, вузли можна було б асоціювати простору) з вершиною кожної гори - отже, визнаіз центрами за таким правилом: 13 88459 14 Правило 1' (відстань без відсічки). Вузол є по1 fi = åfj (3) в'язаний із Центром С, якщо він ближче (за кількісki j = nn(i) тю „стрибків") до С, ніж до будь-якого іншого Центру Co, i якщо його відстань від С не більша, ніж h стрибків. де „nn" означає „близькі сусіди". Таким чином, Для цього правила виникають „жирні" межі, дискретне рівняння Лапласа пропонує для дискреоскільки могло б бути багато вузлів, що є на більтного випадку „найгладкі" функції, але воно має усі шій відстані від будь-якого центру, ніж h стрибків. проблеми, що спостерігалися для безперервних Взагалі, „жирні" межі виникають, якщо вибирають гармонічних функцій, плюс ще одну. Додаткова правило, призначене для запобігання „зростанню" проблема виникає з того вкрай важливого факту, областей від своїх відповідних центрів. Відстань, що опис межі дискретного простору не є однознана яку ріст дозволяють, можна було б оцінити у чним - фактично, жодного природного шляху вистрибках (як у правилі 1') або у декрементах в значити таку межу немає. Можна, звичайно, можВВЦ. ливо принаймні довільно, припустити, що жодна з Межі за Правилом 1 є „тонкими" - практично точок не є межовою точкою - усі мусять мати свою шириною один вузол. Межі за Правилом 2 є навіть вагу, визначену структурою графа, але тоді доветонкішими - взагалі, шириною 0 вузлів, оскільки деться відмовитися від j=константа. будь-який вузол рідко матиме два або більше Власновекторна централізованість шляхів найкрутішого підйому, що вестимуть до Продовжуємо обговорення від виразу (3). Малокальних максимумів. ла зміна картини, яка наведена виразом (3), відраМатематика зу вирішує усі її проблеми. Зазначена мала зміна Математичні задачі, вирішувані за цим винаполягає у наступному: вона вимагає функцію висоходом, вирішують, використовуючи „гладкі" функції ти, що підкоряється замість властивості, що усепо дискретному простору. реднює (3), наступному: Припустимо, що простір визначення є безперервним. Тоді гармонічні функції є рішеннями рів1 fi = åfj няння Лапласа: (4) l j =nn(i) Ñ2f=0 (1) Для даного простору отримують різні рішення рівняння (1), змінюючи межові умови для j. Відразу виявляються деякі проблеми з картиною континууму. Одна проблема полягає у тому, що якщо відійти від межі, там немає ані максимумів, ані мінімумів. Отже, пропонована топографічна картина з такими гладкими функціями не спрацьовує: кожна вершина гори лежатиме на межі. Крім того, у цьому винаході описується природний шлях визначення областей. У даному разі „природний" означає спрямований у максимально можливій мірі топологією графа. Отже, небажано бути вимушеним присвоювати значення для функції j на межі - краще буде, якщо цю проблему вирішить топологія. Можна, звичайно, рішити останню задачу, задавши на межі j=константа, наприклад, нуль. Тобто, межа дається певною номінальною опірною величиною. Це є достатньо „природним"; втім, потім може спасти на думку, що j=константа по усьому простору через властивість, що усереднює, рівняння Лапласа. Дискретний варіант рівняння Лапласа: Lf=0 (2) де L=К-А - матриця Лапласа, К=Діаг(k1, k2,...) діагональна матриця, i-м елементом якої є ступень вузла ki, де ki - кількість приєднаних сусідів вузла і, а А - матриця суміжності, причому Аij=1, якщо зв'язок від i до j є, та 0 у противному випадку. Легко побачити, властивість, що усереднює, зберігається й у цьому випадку: рішення рівняння (2): Тобто, замість жорсткої середньої по усіх сусідах, суму сусідів ділять на константу А, що є такою самою для усіх вузлів. Це рівняння можна переписати як Аf=lf (5) де А - знов-таки матриця суміжності. Тепер ми маємо рівняння для знаходження власних значень, і функція висоти φ є власним вектором матриці суміжності. Цей винахід потребує, фактично, власного вектора, котрий є стійким ітеративним рішенням рівняння (4), оскільки висота за припущенням означає „гарну зв'язність". Тобто, (4) шифрує ідею, що „гарна зв'язність" вузла і визначена (в границях константи шкали l) „гарною зв'язністю" усіх сусідів вузла i. Ітерація цієї вимоги, від вихідної точки, дасть кореневий власний вектор матриці суміжності. Цей власний вектор дає стійке, самоузгоджене рішення рівняння (4); крім того, він має таку властивість, що є додатним напіввизначеним, оскільки є А. Завдяки цій одній зміні, показані вище проблеми з рівнянням Лапласа (дискретним або іншим) вже не існують. ВВЦ може мати локальні максимуми поза межі. Фактично, оскільки вона служить мірою гарної зв'язності, локальні максимуми ВВЦ мають тенденцію лежати досить далеко від будь-яких вузлів, щодо яких може виникнути спокуса назвати їх „межовими вузлами". Крім того, немає потреби визначати межу для дискретного випадку: усі вузли можуть мати значення ВВЦ, визначене за рівнянням (4), без будь-якого вводу даних як „межові умови". Зокрема, внески цього винаходу полягають у наступному: 15 88459 16 1) Дві нові змінені форми для матриці суміжти вузли 9, 13 і 11 як такі, що найбільш нагально ності, що дає дві нові міри централізованості, котрі потребують захисту від будь-яких загроз, на які дозволяють вибирати центри мережі. може наразитися система. Вузли 9 і 13 мають бути 2) Визначення і спосіб ідентифікації областей захищеними, бо вони є центри своїх областей: мережі. якщо вони будуть інфіковані, є висока вірогідність, 3) Визначення і способи присвоювання кожнощо інфікованими буде й уся їх область. му вузлу в мережі дискретних мережевих ролей. Далі, вузлу 9 можна надати вищий пріоритет 4) Використання нових мір централізованості, щодо захисту, ніж вузлу 13, оскільки ця область областей і ролей у широкому різноманітті випадків більша. Нарешті, вузол 11 заслуговує на додаткозастосування. вий захист, оскільки якщо його можна зробити імуПриклади нним до загроз, то ці загрози не матимуть готового Далі наведені приклади варіанту здійснення каналу для поширення з однієї області в іншу. цього винаходу, а також порівняння між двома Відмітимо, що використання Правила 2 не виролями для визначення областей. діляє будь-які межові вузли для спеціального заНа Фігурах 4, 5 і 6 представлені результати хисту, навіть якщо вузол 11 безсумнівно грає важдосліджень за проектом ΜΑΝΑ [4]. Графи предливу роль у з'єднуванні двох областей. Однак ставляють малу громадську мережу - робочу групу Правило 2 ідентифікує зв'язок між 11 і 13 як мосз 11 осіб. Із використанням різних пропонованих товий зв'язок. Очевидним наслідком цього є те, що мір для міцності зв'язків було визначено індекс вузли на кожному кінці кожного мостового зв'язку централізованості, що ґрунтується на ВВЦ. Топозаслуговують на спеціальні захисні заходи. графічні візуалізації показують централізованість Цю задачу можна поставити з ніг на голову, вузлів як різниці висоти. На Фігурі 4 міцність зв'яздавши адміністратору задачу розповсюдження ків оцінена, ґрунтуючись на кількості різних серенеобхідної інформації через ту саму малу мережу. довищ, використовуваних кожним вузлом (спосіб Аналіз тоді пропонує ефективну стратегію, як це 2). На Фігурі 5 представлений граф, якщо міцність здійснити: починаємо з центрів (вузли 9 і 13) і зазв'язків ґрунтується на чистому об'єму потоку між безпечуємо передачу необхідної інформації звідвузлами (спосіб 3). Нарешті, представлений на ти. Фігурі 6 базується на суміші зазначених вище споЗвичайно, слід очікувати, що правила відстані і собів визначення міцності зв'язків, тобто, як кільправило найкрутішого підйому дадуть для деяких кості використовуваних середовищ, так і на чистовузлів суперечливі результати. З Фігур 2-7 слід му об'єму потоку (спосіб 4). почерпнути такий важливий момент: загальна якіНа Фігурі 2 представлений простий граф з сна картина є доволі нечутливою до вибору прадвома центрами. Межа складається з трьох вузлів. вила визначення областей. Можна очікувати, що Один з них (вузол 11) - це мостовий вузол, що те саме справедливо й для більшості графів. Вибір безсумнівно грає суттєву роль у з'єднуванні двох центрів не залежить від того, яке правило викориобластей; два інших є данглерами. стовується, і ці центри, у свою чергу, точно існуЗастосування Правила 2 до того самого графу ють, бо вони лежать в області графа, що має певдає Фігуру 3. На цій фігурі можна побачити, що вся ну „вагу", тобто, певну кількість вузлів, що краще межа „проковтнута" домінантним центром (вузол з'єднані між собою, аніж зі своїм „довкіллям". Ко9). Вельми периферійна роль вузлів 10 і 12 (що ротше: правила відстані, котрі ніби то визначають раніш класифікувалися данглерами) на разі відообласті, насправді принципово відрізняються забражена в їх відстані (2 стрибки) від її центрів (і, лежно від того, де вони поміщають межі між облазвичайно, в її низькій ВВЦ). стями, на той час як області самі по собі є доволі Таким чином, порівняння цих двох фігур підстійкими об'єктами. тверджує очікування щодо відмінностей між двома Стислий опис визначень ролей й областей в ролями: межовий набір, з данглерами або без них, мережах за Правилом 1 зазвичай присутній, але відсутній Засадним критерієм визначення області (і її за Правилом 2. центра) була гарна зв'язність, оцінювана „гладкою" Щоб проілюструвати застосування цих ідей, функцією графа, власновекторною централізовапропонуємо вважати, що вузли на Фігурах 2 і 3 - це ністю або ВВЦ. У додаток до визначення природкористувачі у комп'ютерній мережі, а зв'язки - це них кластерів графа, у своєму підході ми присвоюробочі з'єднання між користувачами, що забезпеємо кожному вузлу у графі однозначну роль. чують потік інформації. У даному випадку вживаДва правила, що визначають області, дають ється термін „робоче з'єднання", оскільки зв'язки якісно схожі картини для структури графа у цілому, можуть бути не прямими: вони можуть бути опосеале вельми відрізні картини з точки зору, які ролі редкованими файлами, до яких користувачі модля вузлів є присутні в аналізі. жуть мати доступ для зчитування і запису [3]. ПісТобто, за Правилом 1 (що асоціює вузли з обля аналізу можна відразу дійти висновку, що ластями, ґрунтуючись на їх відстані від центрів, користувальницька система природно складається вираженій у стрибках найкоротшим шляхом) значз двох основних груп. Далі, вузол 9 є найбільш ну кількість вузлів поміщають у межовий набір. центральний у жовтій групі, а вузол 13 є найбільш Цим вузлам, в свою чергу, можна дати дві різні центральний у синій групі. Нарешті, вузол 11 є ролі: мостові вузли і данглери (див. Фігуру 2). За мостовим вузлом, що є вкрай важливий для потоку Правилом 2 щільніше дотримуються „топографічінформації між двома групами. ного" духу підходу, як описано вище, асоціюючи Припустимо далі, що ця мала система зацікавузли з центрами, з якими вони зв'язані підйомом влена у безпеці. Тоді відразу можна ідентифікуванайкрутішим шляхом. За цим правилом нормально 17 88459 18 (за відсутності спеціальної симетрії) у межовий нововведення більшістю населення зазвичай занабір не поміщають ніякі вузли - за Правилом 2, ці лежить від прийняття неформальними лідерами дві ролі у межовому наборі (мостові вузли і данг[6]. Іншими словами, прийняття будь-якого новолери) практично виключені, й усі вузли є або введення бере свій початок з його ухвали й прийнцентрами області, або членами області. яття неформальними лідерами або концентратоМожна уявити й інші правила визначення обрами громадської мережі. ластей. Основний аспект пропонованого підходу У способі, розкритому через варіант здійсненполягає у тому, що спочатку ідентифікують центри, ня і приклади винаходу, що його супроводжують, а потім дозволяють областям „рости" назовні із використовують змінену матрицю суміжності, що цих центрів. Обидва пропоновані правила відповіґрунтується на потоці даних, щоб вираховувати дають цій картині. Підхід Гірвана/Ньюмена передміру централізованості для кожного вузла у гробачає ієрархічне розкладення графа через розбимадській мережі. Цей індекс централізованості вку кластерів на підкластери тощо. Схоже дозволяє виділити найбільш центральні вузли ієрархічне розкладення графа можна було б викогромадської мережі, котрі ця матриця суміжності нати і за цим винаходом, вилучивши межові вузли представляє. Ці вузли (концентратори мережі) є, з і зв'язки і застосувавши пропонований аналіз до точки зору громадської мережі, неформальними результуючих ізольованих областей. Ґрунтуючись лідерами. Через це вони є гарними мішенями для на існуючих методах аналізу, можна визначити поширення інформації тощо, оскільки вони потенподальші ролі. У дуже простому прикладі можна ціально можуть сприяти прискоренню розповсюприсвоїти роль „Краю області" тим вузлам, що дження цієї інформації. Отже, очевидне застосуз'єднані з межовими елементами (вузлами або вання пропонованого способу лежить у сфері зв'язками). Відрізний тип ролі можна присвоїти тим розповсюдження нововведень. вузлам, що є „найдальшими" від центра, але не У вступній частині робилися посилання на епіз'єднані з будь-якими межовими елементами. деміологію, телекомунікації, системи передачі даЗастосування них, системи електропостачання тощо. Можна Нижче наводяться застосування пропонованих додати, що результат аналізу за цим винаходом способу й системи. Очевидно, що можна виділити відкриває подальшу широку сферу застосувань. високо центральні вузли і мости (зв'язки або вузОдним прикладом є планування графіків у сфері ли) як такі, що заслуговують на додаткову увагу і транспорту або у системах передачі й розподілу. піклування у запобіганні поширенню ушкодження. Через аналіз транспортного потоку у мережі автоВисоко центральні вузли найвірогідніше є такими, мобільних шляхів або системі залізничного трансщо інфікуватимуть свої області, а мости, у свою порту можна знайти найкращий час для розподілу, чергу, повинні захищатися, щоб інфекція не пошищоб запобігти пробок дорожнього руху. Так само, рювалася з однієї області в інші. Отже, було б допланування маршрутизації трафіків у системах цільним імунізувати певні елементи й таким чином телекомунікацій і передачі даних, а також планузабезпечити, що будь-яка інфекція ізолювативання рухів на загальнішій основі, є очевидним меться в одній області. Для більших областей бузастосуванням цього винаходу, оскільки пропоноло б доцільним імунізувати найбільш центральні ваний спосіб вище дозволяє легко ідентифікувати вузли у кожній області, віддаючи, звичайно, пріомісця перевантаження або добрі маршрути. Крім ритет областям з найбільшою кількістю вузлів. З того, на мікроскопічнішому рівні ним можна корисіншого боку, деякі системи, наприклад, одноранготатися при розробці комп'ютерів для аналізування ві системи з гарною зв'язністю, захистити важко, внутрішнього трафіку і таким чином для оіггимізаоскільки вони занадто добре зв'язані. Це означає, ції його компонентів і шин. Останнє застосування є що в кожній області є багато вузлів з приблизно особливо корисне у сфері паралельної обробки, такою самою централізованістю і що між областящоб зменшити трафік між процесорами є багато мостів (для тих випадків, коли є більми/комп'ютерами. ше однієї області). Хоча наведене вище є докладний опис цього Використання пропонованих системи й спосовинаходу, слід розуміти, що винахід включає еквібу застосовне до багатьох інших типів графа - у валенти у межах обсягу винаходу відповідно до принципі, до будь-якого графа, що є неорієнтоваформули винаходу. Докладний опис має у значній ним. Спосіб легко модифікувати (як описано у мірі стосуватися теорії, на якій ґрунтується цей першому варіанті здійснення), серед іншого, з мевинахід; на разі обмежимося лише тим, що викотою надати вагу (іншу, ніж 0 або 1) зв'язкам між ристання цих теорій має широку галузь застосувузлами. Пропоновані спосіб і система будуть ковань за умови, що графи є неорієнтовані. рисними при аналізі громадських мереж, що моОтже, на загальній основі пропонований спосіб жуть (знов-таки) мати (додатну) міцність, пов'язану є застосовний у широкій сфері галузей, і його моз кожним зв'язком. жна застосовувати для вирішення проблем у цих Коли будь-яке нововведення - новий продукт сферах. Інші переважні варіанти здійснення цього або послуга - вводиться у широкий обіг, розповсювинаходу будуть очевидними з доданих залежних дження цього нововведення відбувається типовим пунктів формули винаходу. чином. Нововведення зазвичай розкривається Скорочення і література малій групі перших приймальників, і трохи згодом, 1. G. D. BATISTA, P. EADES, R. TAMASSIA, AND I. залежно від ухвали перших приймальників, нефоG. TOLLIS, Graph Drawing: Algorithms for the рмальні лідери (або ведучі приймальники) приVisualization of Graphs, Prentice Hall, Upper Saddle ймають нововведення. Це є дуже критичний моRiver, New Jersey, 1999. мент процесу розповсюдження, оскільки прийняття 19 88459 20 2. P. BONACICH, Factoring and weighting 9. A. Y. NG, A. X. ZHENG, AND M. I. JORDAN, approaches to status scores and clique identification, Stable algorithms for link analysis, in Proc. 24th Journal of Mathematical Sociology, 2 (1972), pp. 113Annual Intl. ACM SIGIR Conference, ACM, 2001. 120. 10. A. ORAM, ed., Peer-to-peer; Harnessing the 3. M. BURGESS, G. CANRIGHT, AND K. ENGO, A Power of Disruptive Technologies, O'Reilly, graph theoretical model of computer security: from file Sebastopol, California, 2001. access to social engineering, International Journal of 11. L. PAGE, S. BRIN, R. MOTWANI, AND T. Information Security, (2003). Submitted for WINOGRAD, The pageant citation ranking: Bringing publication. order to the web, tech. report, Stanford Digital Library 4. G. CANRIGHT, K. ENG0-MONSEN, AND A. Technologies Project, 1998. WELTZIEN, Multiplex structure of the 12. R. PASTOR-SATORRAS AND A. VESPIGNANI, communications network in a small working group, Epidemic spreading in scale-free networks, Phys. Social NetworL· - An International Journal of Rev. Lett., 86 (2001), pp. 3200-3203. Structural Analysis, (2003). Submitted for publication. 13. T. H. STANG, F. POURBAYAT, M. BURGESS, G. 5. M. GIRVAN AND M. NEWMAN, Community CANRIGHT, K. ENG0, AND A. WELTZIEN, structure in social and biological networL·, Proc. Natl. Archipelago: A network security analysis tool, in Acad. Sci. USA, 99 (2002), pp. 8271-8276. Proceedings of The 17th Annual Large Installation 6. Ε. Μ. ROGERS, Diffusion of Innovations. Free Systems Administration Conference (LISA 2003), San Press, Fifth Edition, 2003. Diego, California, USA, October 2003. 7. J. M. KLEINBERG, Authoritative sources in a 14. G. H. GOLUB AND С. Н. VAN LOAN, Matrix hyperlinked environment, Journal of the ACM, 46 Computations. The Johns Hopkins University Press, (1999), pp. 604-632. Second Edition, 1989. 8. M. NEWMAN, The structure and function of complex networks, SI AM Review, 45 (2003), pp. 167256. 21 88459 22 23 88459 24 25 88459 26 В описі до патенту на винахід графічні зображення та текст подаються в редакції заявника Комп’ютерна верстка О. Гапоненко Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601