Всеукраїнська науково-практична конференція



Сторінка4/60
Дата конвертації11.05.2018
Розмір3.74 Mb.
1   2   3   4   5   6   7   8   9   ...   60

КИРИЧЕНКО О.Л., KANOVSKY І. *, ОСТАПОВ С.Е.


ЧЕРНІВЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ІМЕНІ ЮРІЯ ФЕДЬКОВИЧА

(УКРАЇНА)

*MAX STERN ACADEMIC COLLEGE OF EMEK YEZREEL, ISRAEL

СКЛАДНІ МЕРЕЖІ ТА ЇХ СТАТИСТИЧНІ ХАРАКТЕРИСТИКИ: АНАЛІЗ ДЕЯКИХ

СЕГМЕНТІВ WEB-ПРОСТОРУ



У даній роботі зроблено огляд робіт, присвячених дослідженню статистичних характеристик складних мереж, на прикладі WWW-простору. Розроблено кроулер для збирання статистичної інформації веб-сторінок та методику дослідження мереж, суть якої полягає у зондуванні мережі з багатьох точок входу. Досліджено сегменти net.ua, edu.ua українського web - простору та сегмент ac.il ізраїльського. Доведено адекватність методики та отриманих результатів. Порівняння отриманих результатів з літературними даними свідчить, що досліджені сегменти українського веб-простору за своїми статистичними характеристиками належать до безмасштабних мереж, що повністю відповідає сучасним тенденціям розвитку глобальних мереж.
Дослідження складних мереж останнім часом набуває все більшої популярності серед науковців. Вивчаються статистичні характеристики зв’язків між людьми в соціальних структурах; розподіл посилань в наукових публікаціях; статистика розповсюдження інфекційних захворювань; зв’язок між словами в літературних творах, між абонентами в телекомунікаційних мережах; розподіл посилань на веб-сторінках всесвітньої мережі Інтернет тощо [1-3].

Наприклад, на рис. 1 подано залежність частоти появи слова у творі Івана Франка «Лис Микита» в залежності від його рангу, тобто місця у списку, впорядкованому за спаданням частот усіх слів тексту [2]. Суцільною лінією подано апроксимацію степеневою функцією f(r) ~r-α (α=1).



Рис.1. Залежність частоти появи слова від його рангу для твору І.Франка «Лис Микита»


Як бачимо з рисунку, наведені дані підкоряються закону Зіпфа з показником α=1. Мовою теорії складних мереж це значить, що статистичні властивості графу слів літературного твору відповідають безмасштабним мережам.

На рис. 2 подано дослідження транспортних мереж для чотирьох міст Західної України [4].



Рис.2. Розподіл ступенів вузлів транспортних мереж міст Західної України


Дослідження виконано для Львова, Івано-Франківська, Тернополя та Чернівців. Бачимо, що в усіх випадках статистичні властивості отриманих графів підкоряються степеневому закону f(r)~r-α, причому показник степеня для Львова – α=2.33±0.23; для Івано-Франківська - α=1.67±0.2; для Тернополя - α=2.1±0.3; Чернівців - α=2.05±0.17. Аналогічні дослідження було проведено у [3] для цілої низки міст світу. Отже, ми можемо зробити висновок, що транспортні мережі досліджених міст також виявляють статистичні закономірності, характерні для безмасштабних мереж.

Багато робіт присвячено вивченню WWW-простору, статистичні характеристики якого вивчають як граф, вузлами якого є web-сторінки, а ребрами – зв’язки між ними. Досліджуються як орієнтовані, так і неорієнтовані графи. У роботі [5] досліджувалися статистичні характеристики національних веб-доменів. Результати подано на рис. 3-4.



Рис. 3. Розподіл ймовірності веб-сторінок в залежності від їх степеня для національних web-доменів по вхідних зв’язках



Рис. 4. Розподіл ймовірності веб-сторінок в залежності від їх степеня для національних web-доменів по вихідних зв’язках


З рисунків видно, що південнокорейський домен має певні особливості порівняно з іншими: нестандартний хід кривої при середніх та великих степенях вузлів, а також велике значення середнього степеня вузла як по вхідних, так і по вихідних зв’язках. Автори [5] ці особливості пов’язують з наявністю у цьому домені спамерських сайтів, які, якраз, і характеризуються сильними перехресними зв’язками.

Український домен в цілому досліджувався в роботі [6], де також отримано аналогічні результати (див. рис. 5).


Рис. 5. Статистичні характеристики українського сегменту Інтернет за даними роботи [6]: ліворуч – розподіл ймовірності вузлів опорної частини по їх степенях; праворуч – розподіл коефіцієнтів кластерності вузлів по їх степенях
Що стосується веб-простору в цілому, то показовою роботою з дослідження його статистичних характеристик вважається стаття A.Broder (компанія AltaVista) зі співробітниками [7], де показано, що WWW-простір являє собою безмасштабну мережу, яка підкоряється степеневому закону розподілу з показниками степеня 2.1 за вхідними зв’язками та 2.7 – за вихідними (див. рис. 6).







http://www9.org/w9cdrom/160/fig3.gif

http://www9.org/w9cdrom/160/fig4.gif

Рис. 6. Розподіл кількості веб-сторінок по вхідних (ліворуч) та вихідних (праворуч) зв’язках за даними роботи [7]

Як видно з наведених результатів, статистичні характеристики веб-простору як усієї мережі Інтернет, так і національних веб-доменів можна описати за допомогою безмасштабних мереж, які підкоряються степеневому закону розподілу з показниками 1.8÷2.2 для вхідних зв’язків та 1.3÷2.7 – для вихідних.

Усе це дозволяє зобразити структуру веб-простору таким чином [5-7] (рис. 7):

Рис. 7. Графічна структура веб-простору


Як бачимо, веб-простір складається з деякого ядра (MAIN) або, як його називають в роботі [6], опорної мережі (сукупності веб-сторінок зі степенем не менше двох), та периферійних сторінок, які посилаються на сторінки ядра (IN) або на які є посилання з нього (OUT). Периферійні сторінки пов’язані між собою так званими тунелями (TUNNEL) та мають «вуса» (TENDRILS) зі сторінок, що не входять до структури ядра.

Залишається, однак, нез’ясованим питання про те, які статистичні характеристики мають окремі зони національних доменів. Цікаво також було б дослідити сегменти українського веб-простору та порівняти їх характеристики з аналогічними сегментами інших країн.

Такі задачі виконуються, як правило, за допомогою спеціального програмного забезпечення, кроулера, який «блукає» сторінками, збирає та обробляє статистичну інформацію.

На жаль, такі програми недоступні для широкого загалу, тому для цих досліджень доводиться розробляти та тестувати їх самостійно.

Розроблений нами кроулер написаний з використанням мови програмування Java. Він складається з декількох модулів: Downloader, Content parser, Url extractor, Url resolver, Bussines module, Url manager. Кроулеру доводиться завантажувати та обробляти значні обсяги даних з різноманітних веб-сторінок. Це пов’язано насамперед з високою динамічністю контенту (випливаючі підказки, автодоповнення, «розумний пошук»), з новими можливостями сторінок щодо індивідуальних налаштувань і створення персональної зони (особисті файли, зображення, відео, блоги) для користувача. Модульна структура забезпечує гнучку конфігурацію та стабільну роботу програми під навантаженням. Головними перевагами такої архітектури є завантаження сторінок настільки швидко, наскільки можливо, у декілька потоків, відслідковування посилань, з метою уникнення завантаження одних і тих самих сторінок декілька разів, коректна обробка ситуацій у разі тимчасової недоступності конкретного ресурсу.

Кроулер використовувався для аналізу веб-сторінок українського та ізраїльського сегментів WWW-простору. З його допомогою було досліджено три сегменти вказаних мереж: net.ua; edu.ua та відповідний йому сегмент ac.il. В усіх випадках було про скановано більше 400 тисяч веб-сторінок, встановлено ступінь кожного вузла, визначено коефіцієнт кластерності, побудовано розподіл ймовірностей вузлів за вхідними та вихідними зв’язками.

Методика дослідження мереж була наступною. Для кожної мережі вибиралася певна кількість точок входу, які використовувалися кроулером для зондування. Таких точок входу було 100 для edu.ua, 384 – для net.ua та 27 – для ac.il. Зібрані дані оброблялися та аналізувалися за допомогою додатково розробленого програмного забезпечення, що дало змогу одержати статистичні характеристики досліджених сегментів цих мереж.

Результати статистичної обробки отриманих результатів по всіх точках входження для трьох досліджених зон по вихідних зв’язках подано на рисунку 8.





Рис. 8. Розподіл ймовірностей вузлів по вихідних зв’язках для досліджених сегментів edu.ua (вгорі ліворуч), ac.il (вгорі праворуч) та net.ua (внизу ліворуч) в порівнянні з даними для Оксфордського університету (внизу праворуч)


З наведених результатів видно, що досліджені нами сегменти веб-простору не можуть бути описаними однією лінійною залежністю. На графіках подано апроксимуючі прямі для малих значень степеня вузлів і для великих його значень так, як це робиться в роботі [5]. На наш погляд, однак, природніше розподіл по вихідних зв’язках апроксимувати експоненціальною функцією. Така апроксимація, як це видно з рисунку, і для українських, і для ізраїльського сегментів описується коефіцієнтами одного порядку. Більше того, для сегментів edu.ua та його ізраїльського аналогу ac.il, розподіли взагалі апроксимуються однією експоненціальною функцією. Для порівняння на рисунку 8 подано аналогічні дані по вихідних зв’язках для Оксфордського університету, хід залежності яких аналогічний дослідженим нами.

Як видно з рисунків, досліджені мережі складаються, в основному, з вузлів, які мають значну кількість вихідних зв’язків, тобто середній ступінь вузла зміщений в бік великих значень. Оцінка середніх ступенів для цих мереж дає результати в діапазоні <k>=55÷120, що й підтверджує наш висновок. Ці значення корелюють із ділянкою зміни апроксимуючих прямих, що відбувається приблизно при k~100.

Таким чином, судячи з наведених даних, розподіл ймовірностей вузлів веб-простору по вихідних зв’язках підкоряється експоненціальному закону.

На рисунку 9 подано аналогічні дослідження для вхідних зв’язків.





Рис. 9. Розподіл ймовірностей вузлів по вхідних зв’язках для досліджених сегментів edu.ua (вгорі ліворуч),

ac.il (вгорі праворуч) та net.ua (внизу ліворуч) в порівнянні з даними для Оксфордського університету (внизу праворуч)

Видно, що розподіл ймовірностей усіх досліджених мереж по вхідних зв’язках добре апроксимуються степеневим законом з практично однаковими показниками степеня (2.0-2.2), що говорить про безмасштабність мереж по вхідних зв’язках. Також ми бачимо, що характер отриманих нами залежностей повністю відповідає отриманим раніше результатам сканування веб-сторінок Оксфордського університету. Якщо формально розрахувати середнє значення степеня вузла <k>, то воно, як і слід було чекати, зсунуте в бік малих значень: для мережі edu.ua <k>=9.6; для net.ua - <k> = 5.8, що в кілька разів менше за відповідні мережі вихідних зв’язків.

Об’єднуючи розраховані залежності для вхідних та вихідних підмереж, можна отримати статистичні характеристики неорієнтованих графів веб-сторінок досліджених зон українського домену Інтернет. Побудовані залежності подані на рисунку 10.

З рисунку видно, що для зон edu.ua та net.ua характеристики апроксимуючих прямих не змінилися, а для ac.il вплив розподілу по вихідних зв’язках призвів до збільшення нахилу апроксимуючої прямої (показник степеня змінився з -2 до -1.8). Однак, в усіх трьох випадках зрозуміло, що при малих значеннях степеня вузлів розподіл ймовірності для неорієнтованого графа визначається залежністю по вхідних зв’язках, а для великих – по вихідних.



Рис. 10. Розподіл ймовірностей для неорієнтованих графів досліджених сегментів мереж: edu.ua (ліворуч), ac.il (у центрі) та net.ua (праворуч)


Середні значення степеня вузла для таких мереж, зрозуміло, набувають проміжних значень. Зокрема, для зони edu.ua <k>=19.8, для net.ua - <k>=11.9. Цікавим є той факт, що якраз у цій області спостерігається перехід від характеристик по вхідних зв’язках до характеристик по вихідних, що можна легко побачити на графіках.

Особливості статистичних характеристик по вихідних зв’язках, які ми спостерігаємо в наших дослідженнях, видно також на графіках, отриманих іншими авторами, наприклад, в роботі [5] для національних веб-доменів Бразилії, Греції та Іспанії. Однак, вони не спостерігаються на графіках для всього веб-простору в роботі [6], хоча залежності по вхідних зв’язках дуже подібні. З другого боку, такі ж особливості спостерігаються й на графіках для веб-сторінок Оксфордського університету, де було досліджено порядку 10 тисяч сторінок. Причиною цього може бути те, що експоненціальна залежність при малій та середній кількості вузлів переходить у степеневу при майже десятиразовому збільшенні вузлів, що відбувається при дослідженні глобального веб-простору в роботі [7].

Таким чином, порівняння статистичних характеристик досліджених мереж українського веб-простору з аналогічними сегментами розвинених країн доводить, що вони є цілком розвиненими структурами та відповідають сучасним тенденціям розвитку глобальної мережі Інтернет.
ПЕРЕЛІК ЛІТЕРАТУРИ


  1. Ю. Головач. Складні мережі / Ю.Головач, О. Олємской, К.фон Фербер, Т. Головач, О. Мриглод, І. Олємской, В. Пальчиков// Журнал фізичних досліджень.–2006.–т.10, №4, С. 247-289.

  2. В.В.Пальчиков. Ефекти безмасштабності та тісного світу в складних мережах / Пальчиков В.В.//Автореферат дисертації на здобуття наукового ступеня кандидата фізико-математичних наук. – Львів. – 2010. – 21 С.

  3. Фон Фербер К. Статистичні властивості мереж громадського транспорту / К. фон Фербер, Т. Головач, В. Пальчиков // Фізичний збірник НТШ. – 2008. – Т. 7, – С. 199-209.

  4. Пасічник В.В. Дослідження статистики мереж громадського транспорту найбільших міст західного регіону України / Пасічник В.В., Іванущак Н.М. // Восточно-Европейский журнал передових технологий. – 2011. – 6/4(54). – СС.13-17.

  5. R.Baeza-Yates, C.Castillo, E.N.Efthimiadis. Characterization of National Web Domains // Електронний ресурс: режим доступу - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.68.3101

  6. Фурашев В.Н. Параметры украинского сегмента Интернет как сложной сети / В.Н.Фурашев, В.Ю. Зубок, Д.В. Ландэ // Открытые информационные и компьютерные технологии. – 2008. – 40. – СС.235-242.

  7. Broder A. Graph structure in the web / A. Broder, R. Kumar, F.Maghoul et al. // Proceedings of the 9th World Wide Web Conference, Computer networks, 2000. - 33 (1). – P. 309-320.


УДК 004.2



Поділіться з Вашими друзьями:
1   2   3   4   5   6   7   8   9   ...   60


База даних захищена авторським правом ©wishenko.org 2017
звернутися до адміністрації

    Головна сторінка