Область наук:
  • Математика
  • Рік видавництва: 2007
    Журнал: Известия Південного федерального університету. Технічні науки
    Наукова стаття на тему 'Математичне моделювання інтернет-систем'

    Текст наукової роботи на тему «Математичне моделювання інтернет-систем»

    ?Мал. 6. Фрагмент дорожньої мережі 3

    А

    В даному випадку, з огляду на аналогію прецеденту c3, існує кілька варіантів планування: або зниження швидкості транспортного засобу на вказаній ділянці, або побудова нової траєкторії маршруту (пунктирна лінія на рис. 5). Новий маршрут виявився на 50 км довше попереднього, проте дозволяє скоротити ризик виникнення аналогічного прецеденту.

    У даній роботі застосовано логічний підхід до відбору прецедентів при плануванні перевезення. Прецеденти повинні нести корисну інформацію. Спільне застосування ГІС з механізмом прецедентів дозволяють підвищити ефективність планування і управління логістичним процесом. Підхід на основі відбору прецедентів за методом аналогій допомагає враховувати ризики на етапі планування транспортування.

    1. Логістика автомобільного транспорту: Учеб. посібник / В.С. Лукинський, В.І. Бережний, Е.В. Бережна та ін. - М .: Фінанси і статистика, 2004.

    2. Транспортна логістика: Підручник для транспортних вузів / Під загальною редакцією Л.Б. Миротин. - М .: Изд-во «Іспит», 2002..

    3. Курганов В.М. Логістика. Транспорт і склад в ланцюзі постачань товарів. Навчально-практичний посібник. - М .: Книжковий світ. - 2006.

    4. Шелобаев. Економіко-математичні методи і моделі: Учеб. посібник для вузів. 2-е изд. перераб. і доп. - М .: ЮНИТИ-ДАНА, 2005.

    5. Просветов Г.І. Математичні методи в логістиці: Навчально-методичний посібник. -М .: Вид-во РДЛ, 2006.

    6. Сток Джеймс Р., Ламберт Дуглас М. Стратегічне управління логістикою. - М .: ИНФРА-му, 2005.

    7. Логістика: навч. посібник / Б.А. Анікін [и др.]; під ред. Б.А. Анікіна, Т.А. Родкіна. -М .: ТК Велбі, Вид-во Проспект, 2006. - 408 с.

    8. Губін П. «Роздуми на розвилці у трьох доріг». - «Логістик & система ». 7/05.

    9. Геоинформатика: Учеб. для студ. вузів / О.Г. Капралов, А.В. Кошкарев, В.С. Тикунов і ін .; Під ред. В.С. Тикунова. - М .: Видавничий центр «Академія», 2005. - 480 с.

    10. Берштейн Л.С., Боженюк А.В. Нечіткі моделі прийняття рішень: дедукція, індукція, аналогія. Монографія. - Таганрог. Вид-во ТРТУ, 2001..

    А.А. цілих

    МАТЕМАТИЧНЕ МОДЕЛЮВАННЯ ІНТЕРНЕТ-СИСТЕМ

    Вступ. Розподілені системи, в тому числі мережі стільникового зв'язку, комп'ютерні мережі та інтернет, володіють складною топологією і мають в своїй осно-

    СПИСОК

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

    Розробка адекватного математичного апарату для пояснення цих явищ ведеться в рамках сучасної теорії соціальних мереж. Одним з підходів до аналізу такого роду систем є теорія «малого світу», мешканців якого відділяють один від одного кілька «рукостискань».

    Висновок про те, що більшість членів спільноти малого світу мають приблизно однакову кількість контактів, був вперше зроблений в роботах вчених Ердос і Рен `ї [1].

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

    За результатами «поштового» дослідження вченого Мілграма в 1967 р, середня довжина такого ланцюжка склала 5,5 ланок. З матеріалів, опублікованих журналом Science в 2003 р, слід, що гіпотеза про «шести ступенях» справедлива і для комунікацій по електронній пошті. Предметом іншого дослідження в 2000 р стали властивості мережі гіперпосилань між документами в Інтернеті. Усереднена довжина такого ланцюжка склала 19 проміжних переходів для N ~ 8 ^ 108 документів. Надалі діє логарифмічна залежність - при збільшенні числа документів на порядок число переходів збільшиться на два.

    Моделі випадкових мереж. Сучасна теорія випадкових мереж постулює випадковість зв'язків між вершинами мережі.

    Під випадковим графом [2] будемо розуміти граф із заданим числом вершин, суміжність яких визначається деяким випадковим чином.

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

    Припустимо, що є мережа з N документів. В середньому, кожен з них містить z посилань на інші документи в мережі. Таким чином, у всій мережі є Nz / 2 зв'язків між документами. Модель випадкових мереж передбачає, що зв'язки встановлюються між випадково вибраними парами документів, вершини в яких з'єднані з ймовірністю p.

    При цьому модель демонструє ефект малого світу. Усереднена відстань між двома вершинами у випадковому графі зростає як логарифм від числа вершин. Таким чином, середня довжина D ланцюжка, що з'єднує два випадкових документа, дорівнює D = ln N / ln z. Оскільки ln N повільно збільшується з ростом N, то D також мало навіть для дуже великих систем.

    Згідно з моделлю Ердос-Рен `ї, випадковий граф складається з N помічених вершин, з'єднаних n ребрами, які вибираються випадковим чином з N (N-1) / 2 можливих. Існує всього CN (N-i) / 2 графів з N вершинами і n ребрами, які утворюють імовірнісний простір з однаковою ймовірністю для кожної реалізації.

    Теорія випадкових графів вивчає імовірнісний простір графів з N вершинами при N ^ да, використовуючи методи випадкового аналізу.

    В процесі еволюції випадкового графа, починаючи з N ізольованих вершин, послідовно додаються випадкові ребра. Графи, отримані на кожній наступній стадії еволюції, відповідають все більшим можливостям р. В результаті еволюції при р = 1 приходимо до повного графу з числом ребер п = N (N-1X2.

    Характерно, що багато важливих властивості випадкових графів виявляються несподівано при досягненні деякої критичної ймовірності рс (№) [3]. До цього або майже кожен граф має деяким властивістю Q, або майже жоден граф їм не володіє. Якщо р (№) зростає повільніше, ніж рс (№) при N ^ так, то майже жоден граф не володітиме властивістю Q. Якщо р (№) зростає швидше, ніж рс (№), майже будь-який граф буде мати властивість Q.

    Імовірність того, що граф з N вершинами і функцією розподілу ребер р = р (№) має властивість Q, визначається виразом

    Іт PNp _

    N ^ х

    0, якщо ^ 0

    pc (n)

    Л p (n)

    1, якщо--> х

    pc (n)

    Прояв деяких властивостей пов'язано з кількістю вершин в графі. Так, властивість появи циклів при незмінному p швидше проявиться в графах більшого розміру. Критична ймовірність наявності циклу порядку до становить pc (N) = cN "1. З іншого боку, середня ступінь графа в принципі має критичне значення, яке залежить від розміру системи.

    Діаметр графа. Визначимо діаметр графа як найбільша відстань між будь-якими двома його вершинами. При цьому діаметр незв'язною графа з ізольованими кластерами або нескінченний, або визначається як максимальний з діаметрів його кластерів.

    При малому p випадкові графи мають малий діаметр, оскільки кількість вершин з відстанню 1 від обраної вершини залежить логарифмически тільки від кількості вершин, тобто пропорційно 1п (И) / 1п (<до>).

    Для більшості значень р практично всі графи мають подібний діаметр [3], який визначається виразом:

    1п ^) _ 1п (^ _ 1п (pN) _ 1п (< k >).

    Кластерні. Однак модель випадкового графа не відображає повною мірою всіх властивостей реальних мереж. У багатьох соціальних мережах простежується тенденція до кластерного - існуванню груп тісно пов'язаних між собою елементів.

    Можна ввести коефіцієнт кластерного C [4], що представляє собою середню частку таких пар сусідніх вершин вузла, які також є сусідами один одного.

    Виберемо деяку вершину ^ має До ребер, що з'єднують її з До вершинами. У разі, коли перші ближні сусіди вершини є частиною кліки, між ними існує К / '(К /' - 1) / 2 ребер.

    Коефіцієнт кластерного вершини визначається як Ci = 2Ei / (Ki (Ki-1)), де Ei - число ребер між Ю вершинами. Коефіцієнт кластерного мережі знаходиться як сума коефіцієнтів окремих вершин.

    У повністю пов'язаної мережі С = 1. У випадковому графі коефіцієнт кластерного дорівнює ймовірності С = р. У реальних мережах коефіцієнт кластерного зви-

    але значно більше, ніж в випадкових мережах з тією ж кількістю ребер і вершин - значення C хоча і багато менше одиниці, проте істотно перевершує 1 / N.

    Протилежністю випадковим графам є регулярні решітки з повністю упорядкованими зв'язками кожного елемента з деяким числом сусідів. Легко бачити, що частина безпосередніх сусідів кожного елемента завжди пов'язана один з одним, завдяки чому забезпечуються кластерні властивості мережі. Однак через відсутність «далеких» зв'язків така мережа не має ефект малого світу.

    Модель, вузли якої мають одночасно кілька локальних і випадкових «далеких» зв'язків [5], демонструє як ефект малого світу, так і кластеризації.

    Розподіл ступенів. Легко помітити, що не всі вершини мережі мають однакову кількість ребер. Ступінь вершини характеризується функцією P (k), яка визначає ймовірність того, що випадково обрана вершина буде мати рівно k ребер. У випадковому графі велика частина вершин має приблизно рівний ступінь, близьку до середнього ступеня <k> мережі.

    Вважається, що розподіл ступенів вершин випадкового графа є розподілом Пуассона з піком в P (<k>). Однак, згідно з емпіричним результатами [6], для більшості реальних мереж розподіл ступенів значно відрізняється від розподілу Пуассона і є поважним:

    P (k) ~ k-n.

    Для моделі «голлівудовского графа» характерна розрідженість, високий коефіцієнт кластеризації і малий діаметр. Імовірність того, що сторінка

    має гіперпосилання до k сторінкам, становить k ~ 2 '5, а ймовірність того, що m

    -2 1

    сторінок мають посилання до даної сторінки, дорівнює m .

    Теорія «краватки-метелики» передбачає, що Інтернет - сильно спрямована мережу, розділена на великі області, приблизно рівні за кількістю сторінок.

    З будь-якої сторінки Сільносвязанная ядра, вузла краватки-метелики, можна потрапити на будь-яку іншу сторінку ядра. Таким чином, за допомогою гіперпосилань користувачі можуть легко переміщатися між такими сайтами в будь-якому напрямку. Одна сторона «метелики» містить «стартові» сторінки, з яких доступні всі сторінки ядра, але не навпаки - це база графа. Інша сторона містить «кінцеві» сторінки, які можуть бути досягнуті з сторінок ядра, але не мають зворотних посилань на нього - антібаза графа.

    Висновок. Таким чином, на сьогодні існують три основні підходи до математичного моделювання соціальних мереж. Випадкові графи широко застосовуються для моделювання і емпіричних досліджень. Клас моделей малого світу спирається на базове поняття кластерного. Моделі без масштабування пояснюють походження статечного розподілу ступенів вершин і інших відхилень від розподілу Пуассона високою інтерактивністю і динамікою інтернет-систем і дозволяють досить вірогідно описати майже всі особливості структури Інтернету.

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Erdos, P., Renyi, A. On Random Graphs // Publ. Math. Debrecen, Vol. 6, 1959. Pp. 290-297.

    2. Gross, J., Yellen, J. Graph Theory and Its Applications. Chapman & Hall / CRC, 2005.

    3. Колчин В.Ф. Випадкові графи. - М .: Физматлит, 2004.

    4. Watts, D., Strogatz, S. Collective Dynamics of Small-World Networks // Nature, Vol. 393, 1998. Pp. 440-442.

    5. Kleinberg, J. The small-world phenomenon: An algorithmic perspective // ​​Proc 32nd Symposium on Theory of Computing, 2000..

    6. Reka, A., Jeong, H., and Barabsi, A. Diameter of the World Wide Web // Nature, Vol. 401, 1999. Pp. 130-131.

    Е.Е. Краснощеков

    ПОШУК релевантних документів В ЕКОНОМІЧНИХ СИСТЕМАХ За запитом, розширенням парадигматичні відношення

    У статті розглянуті технологія адаптивного розпізнавання образів APRP і загальні підходи до організації оптимального пошуку з використанням нечіткого порівняння. Проаналізовано існуючі підходи до вирішення завдань пошуку і запропоновано їх поліпшення. Розглянуто застосування при пошуку автоматично побудованих асоціативних відносин замість парадигматических відносин, побудованих вручну. Проведена експериментальна оцінка методу пошуку по розширеному запитом.

    Вступ

    Обсяг електронних документальних баз даних в економічних системах за останні роки значно зріс. В даний час значна частина економічних документів доступна в глобальній мережі Інтернет, яка надає не тільки майже необмежені можливості для розміщення даних, але і можливості для доступу до документів з будь-якої точки земної кулі за умови наявності комп'ютера, підключеного до «всесвітньої павутини».

    Кількість електронних документів в мережі Інтернет настільки велике, що виявити необхідний ресурс без «путівника» майже неможливо. Сьогодні роль путівника і довідника в Інтернеті грають пошукові системи.

    У подібній ситуації різко зросла потреба в системах пошуку і аналізу даних. Саме пошукова система визначає, чи перетворяться в знання численні розрізнені дані, що надходять по різних каналах зв'язку і накопичуються в різноманітних державних, відомчих, приватних та інших електронних архівах.

    Пошук документів можна віднести до найбільш важливим завданням змістовної обробки текстової інформації, що, зокрема, зумовлено потребою пошуку інформації в мережі Інтернет.

    Розробка методів текстового пошуку має давню історію, яка налічує понад сорок років [1]. За цей час інформаційно-пошукові системи еволюціонували від систем формально-логічного типу [2] до систем нечіткого пошуку, основними рисами яких є наступні [3]:

    • запит задається на природній мові, а не у вигляді формального вираження булево-контекстного типу;

    • деякі або навіть всі знайдені документи містять лише частину інформативних слів запиту;

    • знайдені документи видаються в ранжированном вигляді, т. Е. В порядку убування їх відповідності запиту.


    Завантажити оригінал статті:

    Завантажити