Мир тесен (граф)

Графы «Мир тесен» имеют тенденцию содержать в себе клики и почти-клики, под которыми понимают подсети, имеющие связи почти между всеми вершинами в них. Это следует из определения такого свойства графа, как высокий коэффициент кластеризации. Во-вторых, большинство пар вершин будут соединены хотя бы одним коротким путём. Более строго: расстояние от одной вершины до другой в среднем (также известное как длина кратчайшего пути в среднем) относительно мало. Длина кратчайшего пути в среднем высчитывается по следующей формуле[2]:

${\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}$ — количество вершин в графе

Некоторые другие особенности, которые будут описаны далее, часто присутствуют в графах «Мир тесен». Обычно в таких графах есть изобилие хабов — вершин, у которых большая степень вершины. Эти хабы играют роль общего соединения, являются связующим звеном в кратчайшем пути между другими рёбрами. По аналогии, граф «Мир тесен» авиарейсов имеет малую длину кратчайшего пути в среднем (то есть между любыми двумя городами в мире потребуется, вероятно, не больше трёх перелётов) из-за того, что большинство авиарейсов проходят через узловые аэропорты.

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

Принадлежность к классу графов «Мир тесен» оценивается сравнением кластеризации и длины путей данной сети с соответствующими параметрами эквивалентной случайной сети с такой же степенью распределения[3]. Другой метод оценивания принадлежности сети к классу графов «Мир тесен» использует исходное определение графа «Мир тесен», сравнивая степень кластеризации данной сети со степенью кластеризации эквивалентного графа-решётки и длину среднего пути с длиной среднего пути в произвольном графе[4]. Мера принадлежности графа к классу «Мир тесен» (${\displaystyle \omega }$) определяется, как

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

${\displaystyle L}$ — средняя длина кратчайшего пути в рассматриваемом графе

${\displaystyle C}$ — степень кластеризации рассматриваемого графа

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

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

Р. Коуэн и Шломо Хавлин[5][6] показали аналитически, что безмасштабные сети — ультра-малые миры. В этом случае, из-за хабов, кратчайшие пути становятся существенно короче и масштабируются как

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

Свойства графа «мир тесен» были обнаружены во многих объектах реального мира, включая карты дорог, пищевые цепочки, электрические сети, сети протекания метаболизма (metabolite processing networks), нейронные сети, сети избирателей, граф телефонных звонков и сети социального влияния.

Белок-белковые взаимодействия имеют такое свойство графа «Мир тесен», как соответствие степенному закону распределения[7].

Аналогично, свойствами графа «Мир тесен» обладает регуляция транскрипции, в которой вершинам соответствуют гены, причём они связаны, если один ген имеет вверх- или вниз-регулирующее генетическое влияние на другой[8].

Некоторыми исследователями (например, Barabási ) было высказано предположение, что распространённость графов «Мир тесен» в биологических системах может отражать эволюционное преимущество такой топологии. Поводом к такому предположению стала гипотеза, что графы «Мир тесен» более устойчивы при различных внешних воздействиях по сравнению с другими топологиями сети. Если бы эта гипотеза была верна, то это обеспечило бы преимущество биологическим системам, которые являются субъектами мутаций и вирусных инфекций[9].

В графах «Мир тесен» со степенным законом распределения степеней вершин удаление случайной вершины редко служит причиной существенного увеличения кратчайшего пути в среднем (или существенного уменьшения коэффициента кластеризации). Это следует из того факта, что большинство кратчайших путей проходят через хабы, и если периферическая вершина удаляется, маловероятно, что она вмешается в прохождение между другими периферийными вершинами. Поскольку доля периферийных вершин в графе «Мир тесен» существенно выше, чем доля хабов, вероятность удаления важной вершины крайне мала[10]. Например, если маленький аэропорт в Петрозаводске перестанет функционировать, то это не увеличит среднее количество полётов, которые требуются пассажирам, чтобы добраться до точки назначения. Тем не менее, если случайное удаление попадает в хаб, длина кратчайшего пути в среднем может вырасти весьма существенно. Это можно увидеть ежегодно, когда северный аэропорт в США, такой, как Чикагский аэропорт О’Хара заносит снегом, и многие люди вынуждены лететь с пересадками и добираться до пункта назначения окольными путями.

В отличие от графа «Мир тесен», в случайной сети, в которой все вершины имеют приблизительно одинаковое количество соединений, удаление случайной вершины увеличивает длину кратчайшего пути в среднем незначительно, но одинаково для любой удаляемой вершины. В этом смысле случайные сети уязвимы для случайных возмущений, в то время как графы «Мир тесен» устойчивы[11]. Однако графы «Мир тесен» уязвимы для направленных атак на хабы, в то время как в случайных сетях нельзя выбрать цели, уничтожение которых приведёт к катастрофическим последствиям[12][13].

Соответственно, вирусы эволюционировали таким образом, чтобы взаимодействовать с протеинами-хабами, такими как p53, тем самым внося существенные изменения в поведение клеток, благоприятствующие воспроизведению вирусов[14].

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

Построение графов «Мир тесен» с временным запаздыванием[15], позволяет создавать не только фракталы, но и хаос при правильных условиях[16] или переход к хаосу в динамических сетях[17].

При решении задачи о степени диаметра конструируется граф, в котором количество соседей каждой вершины ограничено, в то время как расстояние между любой парой вершин (диаметр сети) минимизируется. Конструирование таких графов «Мир тесен» осуществляется в рамках усилий нахождения графов порядка, близкого к пределу Мура.

Другой путь конструирования графов «Мир тесен» с нуля показан у Бармпутиса и Мюррея[18], где строится сеть с очень маленьким средним расстоянием и очень большой средней кластеризацией. Быстрый алгоритм константной сложности дан вместе с измерениями надёжности полученных графов. В зависимости от области, можно начать с одного такого «ultra small-world» графа, и затем заново включить некоторые рёбра, или использовать некоторые маленькие такие сети как подграф большего графа.

Граф «Мир тесен» используют для моделирования в различных областях.

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

Если в эксперименте Стэнли Милгрэма исследователю требуется найти именно кратчайший путь, то ему надо отправить письма всем своим знакомым и заставить их сделать то же самое. Такой «флуд» в сети достигнет цели так быстро, как только возможно, но такая массовая рассылка практически невозможна. Другой вариант эксперимента — отправлять письмо только одному человеку за раз. В результате проведения эксперимента Мир тесен было совершено поразительное алгоритмическое открытие: в графе «Мир тесен» людям, не знающим всю структуру графа, а имеющим только локальную информацию (о своих знакомых), удаётся коллективно найти относительно короткий путь к цели (наличие относительно короткого пути является известным свойством графов типа «Мир тесен»)[38].

Возникает вопрос: почему социальная сеть структурирована таким образом, что такой децентрализованный алгоритм поиска даёт оптимальные результаты? Подобные децентрализованные алгоритмы поиска работают также во Всемирной паутине, в нейронных сетях и во множестве других областей. Следовательно, понимание алгоритмов работы децентрализованных поисковых алгоритмов обеспечит их широкое применение[39].

Для дальнейших рассуждений необходимо сформулировать более строгое определение децентрализованного алгоритма поиска. Алгоритм рекурсивный: мы стоим в вершине ${\displaystyle v}$, нам нужно достичь вершины ${\displaystyle t}$, мы знаем лишь соседей вершины ${\displaystyle v}$, среди них нужно выбрать вершину ${\displaystyle w}$ и запустить алгоритм от неё. Децентрализованный алгоритм оценивается временем доставки — ожидаемым количеством шагов, необходимых для достижения цели, при этом граф «Мир тесен», стартовая и целевая вершины генерируются случайным образом. Цель исследований — найти полилогарифмические относительно ${\displaystyle n}$ алгоритмы децентрализованного поиска. Эти исследования проводил Джон Клейнберг в работе «Complex networks and decentralized search algorithms»[39].

• Модель Эрдёша — Реньи
• Модель Барабаши — Альберт
• Число Эрдёша
• Безмасштабная сеть
• Шесть шагов до Кевина Бэйкона
• Мир тесен
• Социальная сеть (социология)
• Число Данбара

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

• P.Bork, LJ Jensen, C. von Mering, A.Ramani, I.Lee, EM.Marcotte. Protein interaction networks from yeast to human (англ.) // Current Opinion in Structural Biology. — Elsevier, 2004. — Vol. 14, no. 3. — P. 292—299. — doi:10.1016/j.sbi.2004.05.003. — PMID 15193308.
• V.Van Noort, B.Snel, MA.Huynen. The yeast coexpression network has a small-world, scale-free architecture and can be explained by a simple model (англ.) // EMBO Rep. : journal. — 2004. — March (vol. 5, no. 3). — P. 280—284. — doi:10.1038/sj.embor.7400090. — PMID 14968131.
• X. S. Yang. Fractals in small-world networks with time-delay (неопр.) // Chaos, Solitons & Fractals. — 2002. — Т. 13. — С. 215—219.
• X. S. Yang. Chaos in small-world networks (неопр.) // Phys. Rev. E 63, 046206. — 2001.
• W. Yuan, X. S. Luo, P. Jiang, B. Wang, J. Fang. Transition to chaos in small-world dynamical network (англ.) : journal. Архивировано 3 января 2014 года.
• D.Barmpoutis and R.M. Murray. Networks with the Smallest Average Distance and the Largest Average Clustering (англ.) : journal. — 2010.
• D. Li, K. Kosmidis, A. Bunde, S. Havlin. Dimension of spatially embedded networks (англ.) // Nature Physics : journal. — 2011. — doi:10.1038/nphys1932. — .

• Патент US8495206 - Method and system for job scheduling in distributed data processing system ... - Google Патенты (англ.).
• Duncan J. Watts & Steven H. Strogatz. Collective dynamics of ‘small-world’ networks (англ.). Nature Publishing Group, a division of Macmillan Publishers Limited. (1999).
• A.Barrat and M.Weigt. On the properties of small-world network models (англ.). Europ. Phys. J. B 13, 547 (2000) (1999).
• S.N. Dorogovtsev, J.F.F. Mendes. Evolution of networks (англ.). Adv. Phys. 51, 1079 (2002) (2002).
• Dionysios Barmpoutis, Richard M. Murray. Noise Propagation in Biological and Chemical Reaction Networks (англ.). California Institute of Technology.
• S. Boccaletti, V. Latora, Y. Moreno, M. Chavez., D.-U. Hwang. Complex networks: Structure and dynamics (англ.). Elsevier.
• Mariano Sigman, Guillermo A. Cecchi. Global organization of the Wordnet lexicon (неопр.) (2001).
• Information Theory & Business Intelligence Strategy — Small Worlds Data Transformation Measure — MIKE2.0, the open source methodology for Information Development (неопр.).
• Sandberg, Oskar Searching in a Small World (неопр.).
• Cohen, Philip. Small world networks key to memory (неопр.) (26 мая 2004).
• Sara Solla. Lecture & Slides: Self-Sustained Activity in a Small-World Network of Excitable Neurons (неопр.).
• Lucas Antiqueira, Thiago Alexandre Salgueiro Pardo, Maria das Gra ̧cas Volpe Nunes, Osvaldo Novais de Oliveira Jr., Luciano da Fontoura Costa. Some issues on complex networks for author characterization (неопр.) (2006). doi:10.1.1.94.3070.
• Adolfo Paolo Masucci, Alkiviadis Kalampokis, Victor Martínez Eguíluz, Emilio Hernández-García. Wikipedia Information Flow Analysis Reveals the Scale-Free Architecture of the Semantic Space (англ.) (28 февраля 2011). doi:10.1371/journal.pone.001733.
• Ricard V. Sole, Bernat Corominas Murtra, Sergi Valverde, Luc Steels. Language Networks: their structure, function and evolution (неопр.) (9 января 2007).
• Dynamic Proximity Networks by Seth J. Chandler, The Wolfram Demonstrations Project.
• Small-World Networks entry on Scholarpedia (by Mason A. Porter)