stringtranslate.com

Теория сетей

Небольшой пример сети с восемью вершинами (узлами) и десятью ребрами (связями).

В математике , информатике и сетевых науках теория сетей является частью теории графов . Он определяет сети как графы , узлы или ребра которых обладают атрибутами. Теория сетей анализирует эти сети с точки зрения симметричных или асимметричных отношений между их (дискретными) компонентами.

Теория сетей имеет приложения во многих дисциплинах, включая статистическую физику , физику элементарных частиц , информатику, электротехнику , [1] [2] биологию , [3] археологию , [4] лингвистику , [5] [6] [7] экономику , финансы , исследования операций , климатология , экология , общественное здравоохранение , [8] [9] [10] социология , [11] психология , [12] и нейробиология . [13] [14] [15] Приложения теории сетей включают логистические сети, Всемирную паутину , Интернет , сети регулирования генов , метаболические сети, социальные сети , эпистемологические сети и т. д.; дополнительные примеры см. в списке тем по теории сетей .

Решение Эйлером задачи о семи мостах Кенигсберга считается первым истинным доказательством в теории сетей.

Оптимизация сети

Сетевые задачи, требующие поиска оптимального способа выполнения чего-либо, изучаются как комбинаторная оптимизация . Примеры включают сетевой поток , задачу кратчайшего пути , проблему транспортировки , проблему перегрузки , проблему местоположения , проблему сопоставления , проблему назначения , проблему упаковки , проблему маршрутизации , анализ критического пути , а также технику оценки и анализа программ .

Сетевой анализ

Анализ электрических сетей

Анализ электроэнергетических систем можно проводить с использованием теории сетей с двух основных точек зрения:

  1. Абстрактная перспектива (т. е. граф состоит из узлов и ребер), независимо от аспектов электроэнергетики (например, импеданса линии передачи). Большинство этих исследований сосредоточено только на абстрактной структуре энергосистемы с использованием распределения степеней узлов и распределения посредничества, что дает существенное представление об оценке уязвимости сети. Посредством этих типов исследований можно определить категорию структуры сетки с точки зрения сложной сети (например, одномасштабная, безмасштабная). Эта классификация может помочь инженерам электроэнергетической системы на этапе планирования или при модернизации инфраструктуры (например, при добавлении новой линии электропередачи) поддерживать надлежащий уровень резервирования в системе передачи. [1]
  2. Взвешенные графики, сочетающие в себе абстрактное понимание сложных теорий сетей и свойств электроэнергетических систем. [2]

Анализ социальных сетей

Визуализация анализа социальных сетей [16]

Анализ социальных сетей исследует структуру взаимоотношений между социальными субъектами. [17] Этими субъектами часто являются отдельные лица, но также могут быть группы , организации , национальные государства , веб-сайты или научные публикации .

С 1970-х годов эмпирическое исследование сетей играет центральную роль в социальных науках, и многие математические и статистические инструменты, используемые для изучения сетей, были впервые разработаны в социологии . [18] Среди многих других приложений анализ социальных сетей использовался для понимания распространения инноваций , новостей и слухов. [19] Точно так же его использовали для изучения распространения как болезней , так и поведения, связанного со здоровьем . [20] Он также применялся к изучению рынков , где он использовался для изучения роли доверия в отношениях обмена и социальных механизмов в установлении цен. [21] Его использовали для изучения вербовки в политические движения , вооруженные группы и другие общественные организации. [22] Его также использовали для концептуализации научных разногласий [23] , а также академического престижа. [24] Совсем недавно сетевой анализ (и его близкий родственник анализ трафика ) получил широкое применение в военной разведке, [25] для раскрытия повстанческих сетей как иерархической, так и безлидерной природы. [ нужна цитата ]

Анализ биологических сетей

С недавним взрывным ростом общедоступных биологических данных с высокой пропускной способностью анализ молекулярных сетей приобрел значительный интерес. [26] Тип анализа в этом контексте тесно связан с анализом социальных сетей, но часто фокусируется на локальных закономерностях в сети. Например, сетевые мотивы — это небольшие подграфы, которые чрезмерно представлены в сети. Точно так же мотивы деятельности — это закономерности в атрибутах узлов и ребер сети, которые чрезмерно представлены в структуре сети. Использование сетей для анализа закономерностей в биологических системах, таких как пищевые сети, позволяет нам визуализировать природу и силу взаимодействий между видами. Анализ биологических сетей в отношении болезней привел к развитию области сетевой медицины . [27] Недавние примеры применения сетевой теории в биологии включают приложения для понимания клеточного цикла [28], а также количественную основу для процессов развития. [29]

Нарративный сетевой анализ

Нарративная сеть выборов в США 2012 г. [30]

Автоматический анализ текстовых корпусов позволил извлекать акторов и их реляционные сети в огромных масштабах. Полученные в результате повествовательные сети , которые могут содержать тысячи узлов, затем анализируются с использованием инструментов теории сетей для выявления ключевых действующих лиц, ключевых сообществ или партий, а также общих свойств, таких как надежность или структурная стабильность всей сети или центральность определенные узлы. [31] Это автоматизирует подход, представленный количественным нарративным анализом, [32] при котором тройки субъект-глагол-объект идентифицируются с парами актеров, связанных действием, или парами, образованными актером-объектом. [30]

Анализ ссылок

Анализ связей — это разновидность сетевого анализа, изучающая связи между объектами. Примером может служить изучение адресов подозреваемых и потерпевших, номеров телефонов, которые они набирали, финансовых операций, в которых они участвовали в течение определенного периода времени, а также семейных отношений между этими субъектами в рамках полицейского расследования. Анализ связей здесь обеспечивает важные отношения и ассоциации между очень многими объектами разных типов, которые не очевидны из изолированных фрагментов информации. Компьютерный или полностью автоматический компьютерный анализ каналов все чаще используется банками и страховыми агентствами для обнаружения мошенничества , операторами связи для анализа телекоммуникационных сетей, медицинским сектором в эпидемиологии и фармакологии , в правоохранительных расследованиях , поисковыми системами для оценки релевантности . (и наоборот, спамерами для спамдексинга и владельцами бизнеса для поисковой оптимизации ), и везде, где необходимо анализировать отношения между многими объектами. Ссылки также возникают из-за сходства временного поведения в обоих узлах. Примеры включают климатические сети, в которых связи между двумя местами (узлами) определяются, например, сходством осадков или колебаний температуры в обоих местах. [33] [34]

Анализ веб-ссылок

Некоторые алгоритмы ранжирования веб-поиска используют метрики централизации на основе ссылок, включая PageRank Google , алгоритм HITS Кляйнберга , алгоритмы CheiRank и TrustRank . Анализ ссылок также проводится в информатике и коммуникативных науках, чтобы понять и извлечь информацию из структуры коллекций веб-страниц. Например, анализ может касаться взаимосвязей между веб-сайтами или блогами политиков. Другое использование — классификация страниц в соответствии с их упоминанием на других страницах. [35]

Меры центральности

Информацию об относительной важности узлов и ребер в графе можно получить с помощью показателей центральности , широко используемых в таких дисциплинах, как социология . Например, центральность собственных векторов использует собственные векторы матрицы смежности, соответствующей сети, для определения узлов, которые имеют тенденцию часто посещаться. Формально установленными мерами центральности являются центральность по степени , центральность по близости , центральность по промежуточности , центральность по собственному вектору , центральность по подграфу и центральность по Кацу . Цель или задача анализа обычно определяет тип используемой меры центральности. Например, если кого-то интересует динамика сетей или устойчивость сети к удалению узлов/ссылок, часто динамическая важность [36] узла является наиболее подходящей мерой центральности.

Ассортативное и дисассортативное смешение.

Эти концепции используются для характеристики предпочтений соединения концентраторов в сети. Хабы — это узлы, которые имеют большое количество ссылок. Некоторые концентраторы имеют тенденцию подключаться к другим концентраторам, в то время как другие избегают подключения к концентраторам и предпочитают подключаться к узлам с низким уровнем подключения. Мы говорим, что хаб является ассортативным, когда он имеет тенденцию соединяться с другими хабами. Дисассортативный хаб избегает подключения к другим хабам. Если хабы имеют связи с ожидаемыми случайными вероятностями, их называют нейтральными. Существует три метода количественной оценки степени корреляции. [37]

Рекуррентные сети

Матрицу рекуррентности рекуррентного графика можно рассматривать как матрицу смежности неориентированной и невзвешенной сети. Это позволяет анализировать временные ряды по сетевым показателям. Область применения варьируется от обнаружения изменений режима, определения характеристик динамики до анализа синхронизации. [38] [39] [40]

Пространственные сети

Многие реальные сети встроены в космос. Примеры включают транспортные и другие инфраструктурные сети, нейронные сети мозга. Было разработано несколько моделей пространственных сетей. [41]

Распространение

Контент в сложной сети может распространяться двумя основными способами: консервативным и несохраняемым распространением. [42] При консервативном распространении общий объем контента, поступающего в сложную сеть, остается постоянным при прохождении через нее. Модель сохраненного распространения лучше всего можно представить в виде кувшина с фиксированным количеством воды, наливаемой в ряд воронок, соединенных трубками. Здесь кувшин представляет собой первоначальный источник, а вода — это распространяемое содержимое. Воронки и соединительные трубки представляют собой узлы и соединения между узлами соответственно. Когда вода переходит из одной воронки в другую, вода мгновенно исчезает из воронки, которая ранее подвергалась воздействию воды. При несохраняемом распространении количество контента меняется по мере его поступления и прохождения через сложную сеть. Модель несохраняющегося распространения лучше всего можно представить в виде непрерывно работающего крана, проходящего через ряд воронок, соединенных трубками. Здесь количество воды из первоисточника бесконечно. Кроме того, любые воронки, подвергшиеся воздействию воды, продолжают подвергаться воздействию воды, даже когда она проходит через последующие воронки. Неконсервативная модель наиболее подходит для объяснения передачи большинства инфекционных заболеваний , нервного возбуждения, информации и слухов и т. д.

Сетевая иммунизация

Вопрос о том, как иммунизировать эффективно масштабируемые свободные сети, которые представляют собой реалистичные сети, такие как Интернет и социальные сети, широко изучен. Одной из таких стратегий является иммунизация узлов наибольшей степени, т. е. целевые (намеренные) атаки [43] , поскольку в этом случае она относительно высока и требуется иммунизация меньшего количества узлов. Однако в большинстве реалистичных сетей глобальная структура недоступна, а узлы наибольшей степени неизвестны.

Смотрите также

Рекомендации

  1. ^ аб Борчерс А, Пилер Т (ноябрь 2010 г.). «Программирование плюрипотентных клеток-предшественников, полученных из эмбрионов Xenopus, для создания специфических тканей и органов». Гены . 1 (3): 413–426. дои : 10.3390/en11061381 . ПМЦ  3966229 . ПМИД  24710095.
  2. ^ Аб Салех, Махмуд; Эса, Юсеф; Онуора, Нвабуез; Мохамед, Ахмед А. (2017). «Оптимальное размещение микросетей в системах распределения электроэнергии с использованием сложной сетевой структуры». Оптимальное размещение микросетей в системах распределения электроэнергии с использованием сложной сетевой структуры - Публикация конференции IEEE. ieeexplore.ieee.org. стр. 1036–1040. doi : 10.1109/ICRERA.2017.8191215. ISBN 978-1-5386-2095-3. S2CID  44685630 . Проверено 7 июня 2018 г.
  3. ^ Хабиби I, Эмамян Э.С., Абди А. (август 2014 г.). «Количественный анализ внутриклеточной связи и ошибок сигнализации в сигнальных сетях». Системная биология BMC . 8 : 89. doi : 10.1186/s12918-014-0089-z . ПМЦ 4255782 . ПМИД  25115405. 
  4. ^ Синдбек С (2007). Сети и узловые точки: возникновение городов в Скандинавии раннего периода викингов - Античность 81(311) . Издательство Кембриджского университета. стр. 119–132.
  5. ^ Парадовски, МБ; Яриновский, А.; Елинска, М.; Чопек, К. (2021). «Избранные стендовые доклады с конференции Американской ассоциации прикладной лингвистики, Денвер, США, март 2020 г.: Внеклассное взаимодействие со сверстниками имеет значение для овладения вторым языком во время краткосрочного пребывания за границей: вклад анализа социальных сетей». Обучение языку . 54 (1): 139–143. дои : 10.1017/S0261444820000580 .
  6. ^ Парадовски, МБ; Яриновский, А.; Чопек, К.; Елинска, М.; и другие. (2021). «Взаимодействие со сверстниками и изучение второго языка: вклад анализа социальных сетей в обучение за рубежом по сравнению с домашней средой». В Митчелле, Розамонд; Тайн, Генри (ред.). Язык, мобильность и обучение за рубежом в современном европейском контексте . Нью-Йорк: Рутледж. стр. 99–116. дои : 10.1017/S0261444820000580. ISBN 978-10-03087-95-3. S2CID  228863564.
  7. ^ Парадовски, МБ; Церпих-Козел, А.; Чен, К.-К.; Охаб, Дж. К. (2022). «Как результаты перевешивают входные данные, а собеседники имеют значение для SLA обучения за рубежом: вычислительный анализ взаимодействия учащихся в социальных сетях». Журнал современного языка . 106 (4): 694–725. дои : 10.1111/модл.12811. S2CID  255247273.
  8. ^ Харрис Дж.К., Люк Д.А., Цукерман Р.Б., Шелтон СК (июнь 2009 г.). «Сорок лет исследований пассивного курения: разрыв между открытием и доставкой». Американский журнал профилактической медицины . 36 (6): 538–548. дои : 10.1016/j.amepre.2009.01.039. OCLC  5899755895. PMID  19372026.
  9. ^ Варда Д.М., Форджетт Р., Бэнкс Д., Подрядчик Н. (2009). «Методология социальных сетей в изучении катастроф: проблемы и идеи, полученные в результате исследований после Катрины». Демографические исследования и обзор политики . 28 (1): 11–29. дои : 10.1007/s11113-008-9110-9. ISSN  0167-5923. OCLC  5659930640. S2CID  144130904.
  10. ^ Санкерсинг Д., Мартин ФК, Салливан П., Белл Д. (декабрь 2022 г.). «Сети ухода и поддержки слабых людей, живущих в местных сообществах на северо-западе Лондона: сравнение восприятия пациентов и медицинских работников». BMC Гериатрия . 22 (1): 953. doi : 10.1186/s12877-022-03561-y . ПМЦ 9737751 . ПМИД  36494627. 
  11. ^ делла Порта Д, Диани М (2010). Социальные движения 2e: Введение (2-е изд.). Уайли-Блэквелл. ISBN 978-1-4051-0282-7.
  12. ^ Парадовски, МБ; Елинска, М. (2023). «Предикторы выдержки L2 и их сложное взаимодействие при онлайн-обучении иностранным языкам: мотивация, самостоятельное обучение, автономия, любопытство и языковое мышление». Изучение языка с помощью компьютера : 1–38. дои : 10.1080/09588221.2023.2192762 .
  13. ^ Bassett DS, Sporns O (февраль 2017 г.). «Сетевая нейробиология». Природная неврология . 20 (3): 353–364. дои : 10.1038/nn.4502. ПМЦ 5485642 . ПМИД  28230844. 
  14. ^ Алекс Форнито. «Введение в сетевую нейронауку: как строить, моделировать и анализировать коннектомы - 08:00-10:00 | OHBM». pathlms.com . Проверено 11 марта 2020 г.
  15. ↑ Сабери М., Хосровабади Р., Хатиби А., Мисич Б., Джафари Г. (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность мозговой сети в состоянии покоя». Научные отчеты . 11 (1): 2176. Бибкод : 2021НатСР..11.2176С. дои : 10.1038/s41598-021-81767-7. ПМЦ 7838299 . ПМИД  33500525. 
  16. ^ Гранжан М (2014). «La connaissance est un reseau». Les Cahiers du Numérique . 10 (3): 37–54. дои : 10.3166/lcn.10.3.37-54 . Проверено 15 октября 2014 г.
  17. ^ Вассерман, Стэнли и Кэтрин Фауст. 1994. Анализ социальных сетей: методы и приложения. Кембридж: Издательство Кембриджского университета. Рэйни, Ли и Барри Веллман , Сеть: новая социальная операционная система. Кембридж, Массачусетс: MIT Press, 2012.
  18. ^ Ньюман, MEJ Networks: Введение. Издательство Оксфордского университета. 2010 год
  19. ^ Аль-Тайе МЗ, Кадри С (2017). «Распространение информации в социальных сетях». Python для графического и сетевого анализа . Расширенная обработка информации и знаний. стр. 165–184. дои : 10.1007/978-3-319-53004-8_8. ISBN 978-3-319-53003-1. ПМЦ  7123536 .
  20. ^ Люк Д.А., Харрис Дж.К. (апрель 2007 г.). «Сетевой анализ в общественном здравоохранении: история, методы и приложения». Ежегодный обзор общественного здравоохранения . 28 (1): 69–93. doi : 10.1146/annurev.publhealth.28.021406.144132 . ПМИД  17222078.
  21. ^ Одабаш М., Холт Т.Дж., Брейгер Р.Л. (октябрь 2017 г.). «Рынки как среда управления для организаций, находящихся на грани нелегальности: выводы анализа социальных сетей». Американский учёный-бихевиорист . 61 (11): 1267–1288. дои : 10.1177/0002764217734266. hdl : 10150/631238 . S2CID  158776581.
  22. ^ Ларсон Дж. М. (11 мая 2021 г.). «Сети конфликта и сотрудничества». Ежегодный обзор политической науки . 24 (1): 89–107. doi : 10.1146/annurev-polisci-041719-102523 .
  23. ^ Ленг Р.И. (24 мая 2018 г.). «Сетевой анализ распространения данных об эффективности диет с контролируемым содержанием жиров во вторичной профилактике ишемической болезни сердца (ИБС): выборочное цитирование в обзорах». ПЛОС ОДИН . 13 (5): e0197716. Бибкод : 2018PLoSO..1397716L. дои : 10.1371/journal.pone.0197716 . ПМК 5968408 . ПМИД  29795624. 
  24. ^ Беррис V (апрель 2004 г.). «Академическая кастовая система: иерархия престижа в сетях обмена докторами наук». Американское социологическое обозрение . 69 (2): 239–264. дои : 10.1177/000312240406900205. S2CID  143724478 . Проверено 22 сентября 2021 г.
  25. ^ Робертс Н, Эвертон СФ. «Стратегии борьбы с темными сетями» (PDF) . Журнал социальной структуры . 12 . Проверено 22 сентября 2021 г.
  26. ^ Хабиби I, Эмамян Э.С., Абди А. (07.10.2014). «Расширенные методы диагностики неисправностей в молекулярных сетях». ПЛОС ОДИН . 9 (10): е108830. Бибкод : 2014PLoSO...9j8830H. дои : 10.1371/journal.pone.0108830 . ПМЦ 4188586 . ПМИД  25290670. 
  27. ^ Барабаси А.Л., Гулбахче Н., Лоскальцо Дж. (январь 2011 г.). «Сетевая медицина: сетевой подход к болезням человека». Обзоры природы. Генетика . 12 (1): 56–68. дои : 10.1038/nrg2918. ПМК 3140052 . ПМИД  21164525. 
  28. ^ Джаилхани Н., Равичандран С., Хегде С.Р., Сиддики З., Манде СК, Рао К.В. (декабрь 2011 г.). «Определение ключевых регуляторных элементов определяет точки уязвимости в сигнальной сети, активируемой митогеном». Геномные исследования . 21 (12): 2067–2081. дои : 10.1101/гр.116145.110. ПМК 3227097 . ПМИД  21865350. 
  29. ^ Джексон, доктор медицинских наук, Дюран-Небреда С., Бассель Г.В. (октябрь 2017 г.). «Сетевые подходы к количественной оценке многоклеточного развития». Журнал Королевского общества, Интерфейс . 14 (135): 20170484. doi :10.1098/rsif.2017.0484. ПМЦ 5665831 . ПМИД  29021161. 
  30. ^ ab Автоматизированный анализ президентских выборов в США с использованием больших данных и сетевого анализа; С. Судхахар, Г. А. Велтри, Н. Кристианини; Большие данные и общество 2 (1), 1–28, 2015 г.
  31. ^ Сетевой анализ повествовательного контента в крупных корпусах; С. Судхахар, Г. Де Фацио, Р. Францози, Н. Кристианини; Инженерия естественного языка, 1–32, 2013 г.
  32. ^ Количественный описательный анализ; Роберто Францози; Университет Эмори © 2010
  33. ^ Цонис А.А., Суонсон К.Л., Роббер П.Дж. (2006). «Какое отношение сети имеют к климату?». Бюллетень Американского метеорологического общества . 87 (5): 585–595. Бибкод : 2006BAMS...87..585T. дои : 10.1175/BAMS-87-5-585 . ISSN  0003-0007.
  34. ^ Бурс Н., Букхаген Б., Барбоза Х.М., Марван Н., Куртс Дж ., Маренго Дж.А. (октябрь 2014 г.). «Прогнозирование экстремальных наводнений в восточной части Центральных Анд на основе комплексного сетевого подхода». Природные коммуникации . 5 : 5199. Бибкод : 2014NatCo...5.5199B. дои : 10.1038/ncomms6199 . PMID  25310906. S2CID  3032237.
  35. ^ Аттарди Г., Ди Марко С., Сальви Д. (1998). «Категоризация по контексту» (PDF) . Журнал универсальной информатики . 4 (9): 719–736.
  36. ^ Рестрепо Дж.Г., Отт Э., Хант БР (сентябрь 2006 г.). «Характеристика динамической важности сетевых узлов и связей». Письма о физических отзывах . 97 (9): 094102. arXiv : cond-mat/0606122 . Бибкод : 2006PhRvL..97i4102R. doi : 10.1103/PhysRevLett.97.094102. PMID  17026366. S2CID  18365246.
  37. ^ МЭД Ньюман (2003). «Смешение узоров в сетях». Физический обзор E . 67 (2): 026126. arXiv :cond-mat/0209450. Бибкод : 2003PhRvE..67b6126N. doi : 10.1103/PhysRevE.67.026126. PMID 12636767. S2CID 15186389.
  38. ^ Марван Н., Донгес Дж. Ф., Зоу Ю., Доннер Р. В., Куртс Дж. (2009). «Комплексный сетевой подход для повторяющегося анализа временных рядов». Буквы по физике А. 373 (46): 4246–4254. arXiv : 0907.3368 . Бибкод : 2009PhLA..373.4246M. doi :10.1016/j.physleta.2009.09.042. ISSN  0375-9601. S2CID  7761398.
  39. ^ Доннер Р.В., Хейциг Дж., Донгес Дж.Ф., Зоу Ю., Марван Н., Куртс Дж. (2011). «Геометрия хаотической динамики - сложная сетевая перспектива». Европейский физический журнал Б. 84 (4): 653–672. arXiv : 1102.1853 . Бибкод : 2011EPJB...84..653D. дои : 10.1140/epjb/e2011-10899-1. ISSN  1434-6036. S2CID  18979395.
  40. ^ Фельдхофф Дж. Х., Доннер Р. В., Донгес Дж. Ф., Марван Н., Куртс Дж. (2013). «Геометрическая подпись сложных сценариев синхронизации». Письма по еврофизике . 102 (3): 30007. arXiv : 1301.0806 . Бибкод : 2013EL....10230007F. дои : 10.1209/0295-5075/102/30007. ISSN  1286-4854. S2CID  119118006.
  41. ^ Ваксман Б.М. (1988). «Маршрутизация многоточечных соединений». Журнал IEEE по избранным областям коммуникаций . 6 (9): 1617–1622. дои : 10.1109/49.12889.
  42. ^ Ньюман М., Барабаси А.Л., Уоттс DJ, ред. (2006). Структура и динамика сетей . Принстон, Нью-Джерси: Издательство Принстонского университета.
  43. ^ Каллауэй Д.С., Ньюман М.Э., Строгац Ш., Уоттс DJ (декабрь 2000 г.). «Надежность и хрупкость сети: просачивание на случайных графах». Письма о физических отзывах . 85 (25): 5468–5471. arXiv : cond-mat/0007300 . Бибкод : 2000PhRvL..85.5468C. doi : 10.1103/PhysRevLett.85.5468. PMID  11136023. S2CID  2325768.

Книги

Внешние ссылки

В Wikiquote есть цитаты, связанные с теорией сетей .