Світ тісний (граф)

Графи «Світ тісний» мають тенденцію містити в собі кліки і майже-кліки, під якими розуміють підмережі, які мають зв'язки майже між усіма вершинами в них. Це випливає з визначення такої властивості графа, як високий коефіцієнт кластеризації. По-друге, більшість пар вершин будуть з'єднані хоча б одним коротким шляхом. Більш строго: відстань від однієї вершини до іншої в середньому (також відоме як довжина найкоротшого шляху в середньому) відносно мало. Довжина найкоротшого шляху в середньому вираховується за такою формулою[6]:

${\displaystyle L={\frac {1}{N(N-1)}}\sum _{i,j\in N,i\neq j}d_{ij}}$

${\displaystyle d_{ij}}$ — відстань від вершини ${\displaystyle i}$ до вершини ${\displaystyle j}$

${\displaystyle N}$ — кількість вершин у графі

Деякі інші особливості, які будуть описані далі, часто присутні в графах «Світ тісний». Зазвичай в таких графах є достаток хабів — вершин, у яких велика ступінь вершини. Ці хаби грають роль загального з'єднання, є сполучною ланкою в найкоротшому шляху між іншими ребрами. За аналогією, граф «Світ тісний» авіарейсів має малу довжину найкоротшого шляху в середньому (тобто між будь-якими двома містами у світі буде потрібно, ймовірно, не більше трьох перельотів) через те, що більшість авіарейсів проходять через вузлові аеропорти.

Для аналізу цієї властивості (а саме, наявності хабів) враховують частку вершин в мережі, які мають специфічне кількість вхідних з'єднань (ступінь розподілу мережі). Мережі з великою кількістю хабів, ніж очікується, будуть мати велику частку вершин з високим ступенем, отже, ступінь розподілу буде збільшуватися до високих значень. У розмовній мові це називається «розподіл важкого хвоста». Наявність у мережі високого ступеня розподілу, відповідної критерієм узгодженості з степеневим законом розподілу, є ознакою того, що мережа є графом «Світ тісний». Мережі зі степеневим законом розподілу також відомі як «безмасштабні мережі». Графи дуже різною топології класифікуються як графи «Світ тісний» до тих пір, поки виконуються зазначені вище дві умови (висока ступінь розподілу та відповідність степеневому закону).

Належність до класу графів «Світ тісний» оцінюється порівнянням кластеризації та довжини шляхів даної мережі з відповідними параметрами еквівалентної випадкової мережі з такою ж мірою розподілу[7]. Інший метод оцінювання приналежності мережі до класу графів «Світ тісний» використовує початкове визначення графа «Світ тісний», порівнюючи ступінь кластеризації даної мережі зі ступенем кластеризації еквівалентного графа-решітки і довжину середнього шляху з довжиною середнього шляху в довільному графі[8]. Міра приналежності графа до класу «Світ тісний» (${\displaystyle \omega }$) визначається, як

${\displaystyle \omega ={\tfrac {L_{r}}{L}}-{\tfrac {C}{C_{l}}}}$

${\displaystyle L}$ — довжина найкоротшого шляху в середньому в розглянутому графі

${\displaystyle C}$ — ступінь кластеризації розглянутого графа

${\displaystyle L_{r}}$ — довжина найкоротшого шляху в середньому у випадковому графі

${\displaystyle C_{l}}$ — ступінь кластеризації графа-решітки

Р. Коуен і Шломо Хавлін [9][10] показали аналітично, що безмасштабні мережі — ультра-малі світи. У цьому випадку, завдяки хабам, найкоротші шляхи стають істотно коротше і масштабуються, як

${\displaystyle L\propto \log \log N}$

Властивості графа «світ тісний» були виявлені в багатьох об'єктах реального світу, включаючи карти доріг, харчові ланцюжки, електричні мережі, мережі протікання метаболізму (metabolite processing networks), нейронні мережі, мережі виборців, граф телефонних дзвінків та мережі соціального впливу. Білок-білкові взаємодії мають таку властивість графа «Світ тісний», як відповідність степеневому закону розподілу[11]. Аналогічно, властивостями графа «Світ тісний» володіє регуляція транскрипції, в якій вершинам відповідають гени, причому вони пов'язані, якщо один ген має вгору або вниз регулювальний генетичний вплив на інший[12].

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

У теорії шести рукостискань розглядаються люди, що живуть в один час. Якщо розглядати всіх людей, коли-небудь жили на Землі, то теорія шести рукостискань перестане працювати. Наприклад, кількість ступенів поділу між Альбертом Ейнштейном і Олександром Македонським більше 30, і ця мережа не має властивостей графа «Світ тісний». Аналогічні властивості є у мережі «піти до школи з»: якщо одна людина навчається в певному коледжі через 10 років після іншого, то малоймовірно, що вони познайомилися в цьому коледжі.

Точно так само, кількість станцій, через які повідомлення повинно пройти, не завжди було маленьким. У ті дні, коли пошта доставлялася з рук в руки або кінної поштою, кількість разів, яке лист передається з рук в руки між відправником та одержувачем було набагато більше, ніж сьогодні. Кількість разів, яке повідомлення передається з рук в руки між відправником та одержувачем в роки візуального телеграфу (близько 1800—1850) було визначено вимогою, що дві станції з'єднані лінією візуального контакту.

Неявні припущення, якщо не перевірені, можуть стати причиною необ'єктивності в літературі про графах на користь помилкової ідентифікації графів «Світ тісний» (наприклад картотека, що виникла через необ'єктивності публікації).

Деякими дослідниками (наприклад, Barabási) було висловлено припущення, що поширеність графів «Світ тісний» в біологічних системах може відображати еволюційна перевага такої топології. Приводом до такого припущення стала гіпотеза, що графи «Світ тісний» стійкіші при різних зовнішніх впливах в порівнянні з іншими топологіями мережі. Якби ця гіпотеза була вірна, то це забезпечило б перевагу біологічним системам, які є суб'єктами мутацій і вірусних інфекцій[13].

У графах «Світ тісний» зі степеневим законом розподілу ступенів вершин видалення випадкової вершини рідко служить причиною істотного збільшення найкоротшого шляху в середньому (або істотного зменшення коефіцієнта кластеризації). Це випливає з того факту, що більшість найкоротших шляхів проходять через хаби, і якщо периферична вершина видаляється, малоймовірно, що вона втрутиться в проходження між іншими периферійними вершинами. Оскільки частка периферійних вершин у графі «Світ тісний» істотно вище, ніж частка хабів, ймовірність видалення важливої вершини вкрай мала[14]. Наприклад, якщо маленький аеропорт в Петрозаводську перестане працювати, то це не збільшить середню кількість польотів, які потрібні пасажирам, щоб дістатися до точки призначення. Проте, якщо випадкове видалення потрапляє в хаб, довжина найкоротшого шляху в середньому може вирости досить істотно. Це можна побачити щорічно, коли північний аеропорт в США, такий, як Чиказький аеропорт О'Хара заносить снігом, і багато людей змушені летіти з пересадками і добиратися до пункту призначення обхідними шляхами.

На відміну від графа «Світ тісний», у випадковій мережі, в якій всі вершини мають приблизно однакову кількість з'єднань, видалення випадкової вершини збільшує довжину найкоротшого шляху в середньому незначно, але однаково для будь-якої віддаленої вершини. У цьому сенсі випадкові мережі уразливі до випадкових збурень в той час як графи «Світ тісний» стійкі[15]. Однак графи «Світ тісний» уразливі до спрямованих атак на хаби в той час як у випадкових мережах не можна вибрати цілі, знищення яких призведе до катастрофічних наслідків[16][17].

Відповідно, віруси еволюціонували таким чином, щоб взаємодіяти з протеїнами — хабами, такими як p53, тим самим вносячи суттєві зміни в поведінку клітин, сприятливі для відтворення вірусів[18].

Основний механізм конструювання графів «Світ тісний» — Модель Ватца — Строгаца.

Побудова графів «Світ тісний» з тимчасовим запізненням[19], дозволяє створювати не тільки фрактали, а й хаос при правильних умовах[20] або перехід до хаосу в динамічних мережах[21]. При розв'язанні задачі про ступінь діаметра конструюється граф, в якому кількість сусідів кожної вершини обмежена, в той час як відстань між будь-якою парою вершин (діаметр мережі) мінімізується. Конструювання таких графів «Світ тісний» здійснюється в рамках зусиль знаходження графів порядку, близького до межі Мура.

Інший шлях конструювання графів «Світ тісний» з нуля показаний у Бармпутіса і Мюррея[22], де будується мережа з дуже маленьким середньою відстанню і дуже великий середньої кластеризацією. Швидкий алгоритм константної складності даний разом з вимірами надійності отриманих графів. Залежно від галузі, можна почати з одного такого «ultra small — world» графа, і потім заново включити деякі ребра, або використовувати деякі маленькі такі мережі як підграф більшого графа.

Див. також: агрегація обмежена дифузією, утворення шаблонів

Граф «Світ тісний» використовують для моделювання в різних галузях.

Модель графа «Світ тісний» включає рівномірний розподіл довжин посилань, що підкоряється степеневому закону розподілу, середня відстань між двома вершинами змінюється залежно від сили розподілу[41].

Якщо в експерименті Стенлі Мілґрема досліднику потрібно знайти саме найкоротший шлях, то йому треба відправити листи всім своїм знайомим і змусити їх зробити те ж саме. Такий «флуд» у мережі досягне мети так швидко, як тільки можливо, але така масова розсилка практично неможлива. Інший варіант експерименту — відправляти лист тільки одній людині за раз. У результаті проведення експерименту Світ тісний було скроєно разючу алгоритмічне відкриття: в графі «Світ тісний» людям, які не знають всю структуру графа, а мають тільки локальну інформацію (про своїх знайомих), вдається колективно знайти відносно короткий шлях до мети (наявність відносно короткого шляху є відомим властивістю графів типу «Світ тісний»)[42].

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

Для подальших міркувань необхідно сформулювати більш суворе визначення децентралізованого алгоритму пошуку. Алгоритм рекурсивний: ми стоїмо в вершині ${\displaystyle v}$, нам потрібно досягти вершини ${\displaystyle t}$, ми знаємо лише сусідів вершини ${\displaystyle v}$, серед них потрібно вибрати вершину ${\displaystyle w}$ і запустити алгоритм від неї. Децентралізований алгоритм оцінюється часом доставки — очікуваним кількістю кроків, необхідних для досягнення мети, при цьому граф «Світ тісний», стартова і цільова вершини генеруються випадковим чином. Мета досліджень — знайти полілогаріфмічні щодо ${\displaystyle n}$ алгоритми децентралізованого пошуку. Ці дослідження проводив Джон Клейнберг у роботі «Комплексні мережі та децентралізовані алгоритми пошуку».

• [[:w::en:Erdős–Rényi model|Erdős-Rényi (ER) model]]
• [[:w::en:Watts and Strogatz Model|Watts and Strogatz Model]]
• [[:w::en:Barabási–Albert model|Barabási–Albert model]]
• Число Ердеша
• Безмасштабна мережа
• Світ тісний
• Складні мережі
• Соціальна мережа
• Число Данбара

• Jin Chen. Systematic Assessment of Protein Interaction Data using Graph Topology Approaches. — 2006.^{[недоступне посилання з травня 2019]}
• Maaike Snelder. Designing Robust Road Networks A general design method applied to the Netherlands. — ISBN 978-90-5584-135-6. Архівовано 27 травня 2014 у Wayback Machine.
• Stefano Boccaletti, Vito Latora, Yamir Moreno. Handbook on Biological Networks. — ISBN 978-981-283-979-7.
• F. Lamanna and G. Longo. Connectivity and stability of the air network in the Southeastern Europe: A Small World approach // JOURNAL OF TRANSPORT AND SHIPPING. — 2007. — № 4. — ISSN 1109–9437.
• Robert Hillard (2010). Information-Driven Business. Wiley. ISBN 978-0-470-62577-4.
• Клей Ширки (2008). Here Comes Everybody. Penguin Group. с. 327. ISBN 978-1-59420-153-0.
• M. D. Humphries, K. Gurney and T. J. Prescott, Phil. Trans (2007). Is there a brainstem substrate for action selection?. R. Soc. B. doi:10.1098/rstb.2007.2057.
• K.E. Joyce, S. Hayasaka, J.H. Burdette, P.J. Laurienti (2011). The ubiquity of small-world networks Q.K. Telesford,. Brain Connect: 367–75. doi:10.1089/brain.2011.0038.
• Finnegan, William (2003). Affinity Groups and the Movement Against Corporate Globalization (англ.) 1. Wiley-Blackwell. с. 210–218. ISBN 978-0631221968. Проігноровано невідомий параметр |издание= (довідка); Проігноровано невідомий параметр |автор издания= (довідка)
• X. S. Yang (2001). Small-world networks in geophysics. Geophys. Res. Lett., 28(13): 2549—2552.
• A. Jimenez, K. F. Tiampo, A. M. Posadas (2008). Small-world in a seismic network: the California case. Nonlin. Processes Geophys., 15: 389—395.
• Jon Kleinberg. Complex networks and decentralized search algorithms. — 2006.^{[недоступне посилання з травня 2019]}
• Xiangdong Che, M. Ali, R.G. Reynolds. Robust evolution optimization at the edge of chaos: Commercialization of culture algorithms. — 2010. — ISBN 978-1-4244-6909-3.
• Sporns, Olaf; Tononi G, Edelman GM (2004.). Organization, development and function of complex brain networks. Trends Cogn Sci. 8 (9): 418–425. PMID 15350243. doi:10.1016/j.tics.2004.07.008.
• Yu, Shan; D. Huang, W. Singer and D. Nikolić (2008). A Small World of Neuronal Synchrony. Cerebral Cortex 18 (12): 2891–2901. PMC 2583154. PMID 18400792. doi:10.1093/cercor/bhn047.
• M.Barthelemy, L.Amaral (1999). Small-world networks: Evidence for a crossover picture. Phys. Rev. Lett. 82 (15): 3180. Bibcode:1999PhRvL..82.3180B. arXiv:cond-mat/9903108. doi:10.1103/PhysRevLett.82.3180.
• R.Cohen, S.Havlin, and D.ben-Avraham (2002). Structural properties of scale free networks. Handbook of graphs and networks (Wiley-VCH, 2002) (Chap. 4).
• R. Cohen, S.Havlin (2003). Scale-free networks are ultrasmall. Phys. Rev. Lett. 90 (5): 058701. Bibcode:2003PhRvL..90e8701C. PMID 12633404. arXiv:cond-mat/0205476. doi:10.1103/PhysRevLett.90.058701.

• P.Bork, LJ Jensen, C. von Mering, A.Ramani, I.Lee, EM.Marcotte (2004). Protein interaction networks from yeast to human (PDF). Current Opinion in Structural Biology 14 (3): 292–299. PMID 15193308. doi:10.1016/j.sbi.2004.05.003.

• V.Van Noort, B.Snel, MA.Huynen (Mar 2004). The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model. EMBO Rep. 5 (3): 280–284. PMC 1299002. PMID 14968131. doi:10.1038/sj.embor.7400090.

• X. S. Yang (2002). Fractals in small-world networks with time-delay. Chaos, Solitons & Fractals 13: 215—219.

• X. S. Yang (2001). Chaos in small-world networks. Phys. Rev. E 63, 046206.

• W. Yuan, X. S. Luo, P. Jiang, B. Wang, J. Fang. Transition to chaos in small-world dynamical network. Архів оригіналу за 3 січня 2014. Процитовано 28 травня 2014.

• D.Barmpoutis and R.M. Murray (2010). Networks with the Smallest Average Distance and the Largest Average Clustering. Проігноровано невідомий параметр |class= (довідка); Проігноровано невідомий параметр |eprint= (довідка)

• D. Li, K. Kosmidis, A. Bunde, S. Havlin (2011). Dimension of spatially embedded networks. Nature Physics. Bibcode:2011NatPh...7..481D. doi:10.1038/nphys1932.