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. ^ ab Borchers A, Pieler T (ноябрь 2010 г.). «Программирование плюрипотентных клеток-предшественников, полученных из эмбрионов Xenopus, для создания определенных тканей и органов». Genes . 1 (3): 413–426. doi : 10.3390/en11061381 . PMC  3966229 . PMID  24710095.
  2. ^ ab Салех, Махмуд; Эса, Юсеф; Онуора, Нвабуезе; Мохамед, Ахмед А. (2017). "Оптимальное размещение микросетей в электрических распределительных системах с использованием сложной сетевой структуры". Оптимальное размещение микросетей в электрических распределительных системах с использованием сложной сетевой структуры - Публикация конференции IEEE. IEEE . стр. 1036–1040. doi :10.1109/ICRERA.2017.8191215. ISBN 978-1-5386-2095-3. S2CID  44685630 . Получено 2018-06-07 .
  3. ^ Хабиби И, Эмамиан ЭС, Абди А (август 2014 г.). «Количественный анализ внутриклеточной коммуникации и ошибок сигнализации в сигнальных сетях». BMC Systems Biology . 8 : 89. doi : 10.1186/s12918-014-0089-z . PMC 4255782. PMID  25115405 . 
  4. ^ Sindbæk S (2007). Сети и узловые точки: возникновение городов в Скандинавии ранней эпохи викингов - Antiquity 81(311) . Cambridge University Press. С. 119–132.
  5. ^ Парадовски, МБ; Яриновски, А.; Елинска, М.; Чопек, К. (2021). «Избранные постерные доклады с конференции Американской ассоциации прикладной лингвистики, Денвер, США, март 2020 г.: Внеклассное взаимодействие со сверстниками имеет значение для усвоения второго языка во время краткосрочных зарубежных поездок: вклад анализа социальных сетей». Language Teaching . 54 (1): 139–143. doi : 10.1017/S0261444820000580 .
  6. ^ Парадовски, МБ; Яриновски, А.; Чопек, К.; Елинска, М.; и др. (2021). «Взаимодействие со сверстниками и изучение второго языка: вклад анализа социальных сетей в обучение за рубежом и дома». В Митчелл, Розамонд; Тайн, Генри (ред.). Язык, мобильность и обучение за рубежом в современном европейском контексте . Нью-Йорк: Routledge. стр. 99–116. doi :10.1017/S0261444820000580. ISBN 978-10-03087-95-3. S2CID  228863564.
  7. ^ Paradowski, MB; Cierpich-Kozieł, A.; Chen, C.-C.; Ochab, JK (2022). «Как выходные данные перевешивают входные данные, а собеседники имеют значение для SLA обучения за рубежом: вычислительный анализ социальных сетей взаимодействия учащихся». The Modern Language Journal . 106 (4): 694–725. doi :10.1111/modl.12811. S2CID  255247273.
  8. ^ Harris JK, Luke DA, Zuckerman RB, Shelton SC (июнь 2009 г.). «Сорок лет исследований пассивного курения: разрыв между открытием и поставкой». American Journal of Preventive Medicine . 36 (6): 538–548. doi :10.1016/j.amepre.2009.01.039. OCLC  5899755895. PMID  19372026.
  9. ^ Varda DM, Forgette R, Banks D, Contractor N (2009). «Методология социальных сетей в изучении катастроф: проблемы и идеи, высказанные в ходе исследований после урагана «Катрина»». Population Research and Policy Review . 28 (1): 11–29. doi :10.1007/s11113-008-9110-9. ISSN  0167-5923. OCLC  5659930640. S2CID  144130904.
  10. ^ Санкерсинг Д., Мартин ФК, Салливан П., Белл Д. (декабрь 2022 г.). «Сети ухода и поддержки немощных лиц, проживающих в сообществе на северо-западе Лондона: сравнение мнений пациентов и работников здравоохранения». BMC Geriatrics . 22 (1): 953. doi : 10.1186/s12877-022-03561-y . PMC 9737751. PMID  36494627 . 
  11. ^ делла Порта Д, Диани М (2010). Социальные движения 2e: Введение (2-е изд.). Уайли-Блэквелл. ISBN 978-1-4051-0282-7.
  12. ^ Парадовски, МБ; Елинска, М. (2023). «Предикторы упорства L2 и их сложные взаимодействия в онлайн-обучении иностранным языкам: мотивация, самостоятельное обучение, автономия, любопытство и языковые установки». Computer Assisted Language Learning : 1–38. doi : 10.1080/09588221.2023.2192762 .
  13. ^ Bassett DS, Sporns O (февраль 2017 г.). «Сетевая нейронаука». Nature Neuroscience . 20 (3): 353–364. doi : 10.1038/nn.4502. PMC 5485642. PMID  28230844. 
  14. ^ Алекс Форнито. «Введение в сетевую нейронауку: как строить, моделировать и анализировать коннектомы - 0800-10:00 | OHBM». pathlms.com . Получено 11.03.2020 .
  15. ^ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность мозговой сети в состоянии покоя». Scientific Reports . 11 (1): 2176. Bibcode :2021NatSR..11.2176S. doi :10.1038/s41598-021-81767-7. PMC 7838299 . PMID  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. Анализ социальных сетей: методы и приложения. Кембридж: Cambridge University Press. Рейни, Ли и Барри Уэллман , Сетевые: новая социальная операционная система. Кембридж, Массачусетс: MIT Press, 2012.
  18. ^ Ньюман, MEJ Networks: Введение. Oxford University Press. 2010
  19. ^ Аль-Тайе МЗ, Кадри С (2017). «Распространение информации в социальных сетях». Python для анализа графов и сетей . Расширенная обработка информации и знаний. стр. 165–184. doi :10.1007/978-3-319-53004-8_8. ISBN 978-3-319-53003-1. ЧМЦ  7123536 .
  20. ^ Luke DA, Harris JK (апрель 2007 г.). «Анализ сетей в здравоохранении: история, методы и применение». Annual Review of Public Health . 28 (1): 69–93. doi : 10.1146/annurev.publhealth.28.021406.144132 . PMID  17222078.
  21. ^ Одабаш М., Холт Т.Дж., Брейгер Р.Л. (октябрь 2017 г.). «Рынки как среда управления для организаций на грани противозаконности: выводы из анализа социальных сетей». American Behavioral Scientist . 61 (11): 1267–1288. doi : 10.1177/0002764217734266. hdl : 10150/631238 . S2CID  158776581.
  22. ^ Larson JM (11 мая 2021 г.). «Сети конфликта и сотрудничества». Annual Review of Political Science . 24 (1): 89–107. doi : 10.1146/annurev-polisci-041719-102523 .
  23. ^ Leng RI (24 мая 2018 г.). «Сетевой анализ распространения доказательств относительно эффективности диет с контролируемым содержанием жиров во вторичной профилактике ишемической болезни сердца (ИБС): выборочное цитирование в обзорах». PLOS ONE . ​​13 (5): e0197716. Bibcode :2018PLoSO..1397716L. doi : 10.1371/journal.pone.0197716 . PMC 5968408 . PMID  29795624. 
  24. ^ Burris V (апрель 2004 г.). «Академическая кастовая система: иерархии престижа в сетях обмена докторскими диссертациями». American Sociological Review . 69 (2): 239–264. doi : 10.1177/000312240406900205. S2CID  143724478. Получено 22 сентября 2021 г.
  25. ^ Робертс Н., Эвертон СФ. "Стратегии борьбы с темными сетями" (PDF) . Журнал социальной структуры . 12 . Получено 22 сентября 2021 г. .
  26. ^ Хабиби И, Эмамян Э.С., Абди А. (2014-10-07). "Расширенные методы диагностики неисправностей в молекулярных сетях". PLOS ONE . 9 (10): e108830. Bibcode : 2014PLoSO...9j8830H. doi : 10.1371/journal.pone.0108830 . PMC 4188586. PMID  25290670 . 
  27. ^ Barabási AL, Gulbahce N, Loscalzo J (январь 2011 г.). «Сетевая медицина: сетевой подход к человеческим болезням». Nature Reviews. Genetics . 12 (1): 56–68. doi :10.1038/nrg2918. PMC 3140052. PMID  21164525 . 
  28. ^ Jailkhani N, Ravichandran S, Hegde SR, Siddiqui Z, Mande SC, Rao KV (декабрь 2011 г.). «Определение ключевых регуляторных элементов выявляет точки уязвимости в сети сигнализации, активируемой митогеном». Genome Research . 21 (12): 2067–2081. doi :10.1101/gr.116145.110. PMC 3227097 . PMID  21865350. 
  29. ^ Джексон МД, Дюран-Небреда С, Бассель ГВ (октябрь 2017 г.). «Сетевые подходы к количественной оценке многоклеточного развития». Журнал Королевского общества, Интерфейс . 14 (135): 20170484. doi :10.1098/rsif.2017.0484. PMC 5665831. PMID  29021161 . 
  30. ^ ab Судхахар, Саатвига; Велтри, Джузеппе А; Кристианини, Нелло (2015). «Автоматизированный анализ президентских выборов в США с использованием больших данных и сетевого анализа». Большие данные и общество . 2 (1): 205395171557291. doi :10.1177/2053951715572916. hdl : 2381/31767 .
  31. ^ Сетевой анализ повествовательного контента в больших корпусах; S Sudhahar, G De Fazio, R Franzosi, N Cristianini; Natural Language Engineering, 1–32, 2013
  32. ^ Количественный повествовательный анализ; Роберто Францоси; Университет Эмори © 2010
  33. ^ Tsonis AA, Swanson KL, Roebber PJ (2006). «Что делают сети с климатом?». Бюллетень Американского метеорологического общества . 87 (5): 585–595. Bibcode :2006BAMS...87..585T. doi : 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. ^ Restrepo JG, Ott E, Hunt BR (сентябрь 2006 г.). "Характеристика динамической важности сетевых узлов и связей". Physical Review Letters . 97 (9): 094102. arXiv : cond-mat/0606122 . Bibcode :2006PhRvL..97i4102R. doi :10.1103/PhysRevLett.97.094102. PMID  17026366. S2CID  18365246.
  37. ^ MEJ Newman (2003). "Смешивание шаблонов в сетях". Physical Review E. 67 ( 2): 026126. arXiv :cond-mat/0209450. Bibcode :2003PhRvE..67b6126N. doi :10.1103/PhysRevE.67.026126. PMID 12636767. S2CID 15186389.
  38. ^ Marwan N, Donges JF, Zou Y, Donner RV, Kurths J (2009). «Комплексный сетевой подход к рекуррентному анализу временных рядов». Physics Letters A. 373 ( 46): 4246–4254. arXiv : 0907.3368 . Bibcode : 2009PhLA..373.4246M. doi : 10.1016/j.physleta.2009.09.042. ISSN  0375-9601. S2CID  7761398.
  39. ^ Donner RV, Heitzig J, Donges JF, Zou Y, Marwan N, Kurths J (2011). «Геометрия хаотической динамики – сложная сетевая перспектива». European Physical Journal B. 84 ( 4): 653–672. arXiv : 1102.1853 . Bibcode : 2011EPJB...84..653D. doi : 10.1140/epjb/e2011-10899-1. ISSN  1434-6036. S2CID  18979395.
  40. ^ Feldhoff JH, Donner RV, Donges JF, Marwan N, Kurths J (2013). "Геометрическая сигнатура сложных сценариев синхронизации". Europhysics Letters . 102 (3): 30007. arXiv : 1301.0806 . Bibcode : 2013EL....10230007F. doi : 10.1209/0295-5075/102/30007. ISSN  1286-4854. S2CID  119118006.
  41. ^ Waxman BM (1988). «Маршрутизация многоточечных соединений». Журнал IEEE по избранным областям в коммуникациях . 6 (9): 1617–1622. doi :10.1109/49.12889.
  42. ^ Newman M, Barabási AL, Watts DJ, ред. (2006). Структура и динамика сетей . Принстон, Нью-Джерси: Princeton University Press.
  43. ^ Callaway DS, Newman ME, Strogatz SH, Watts DJ (декабрь 2000 г.). «Надежность и хрупкость сети: просачивание на случайных графах». Physical Review Letters . 85 (25): 5468–5471. arXiv : cond-mat/0007300 . Bibcode : 2000PhRvL..85.5468C. doi : 10.1103/PhysRevLett.85.5468. PMID  11136023. S2CID  2325768.

Книги

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

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