Теория графов на практике: Часть 1
Автор: Brian Hayes
Перевод: Шумилина М.С.
Источник: American Scientist
Автор: Brian Hayes
Перевод: Шумилина М.С.
Источник: American Scientist
Статья посвящена практической значимости теории графов и исследование структуры сети с помощью графов
Какой диаметр Всемирной паутины? Ответ не 7927 км, хотя сеть действительно всемирная. По словам Альберта-Ласло Барабаси, диаметр Веб 19. Диаметр рассматривается не как геометрическое расстояние; концепция исходит из области математики, которая называется теория графов. В Интернете вы перемещаетесь с места на место, нажав на гипертекстовые ссылки, и поэтому имеет смысл определить расстояние, считая свои шаги с помощью таких ссылок. Вопрос: Если выбрать две веб-страницы наугад, сколько ссылок будет разделять их, в среднем? Среди 800 миллионов страниц в Интернете, есть место, чтобы прогуляться очень длинный путь, но Барабаси обнаружил, что, если вы знаете, куда вы идете, вы можете оказаться практически в любом месте в 19 щелчков мыши. Расчет Барабаси отражает интересный сдвиг в стиль и технологии теории графов. Еще несколько лет назад это было бы необычно применять графо-теоретические методы в такой огромной структуре, как Всемирной паутине. Конечно, всего несколько лет назад интернета не существовало. Сейчас очень много объектов сети, кажется, всюду, и многие из них привлекают графотеоретический анализ. Возможно, настало время говорить не только о теоретических аспектах графов, но и о практических, или даже технических.
Так для определения, большинство из нас предпочитают думать о наших графах наглядно. А на самом деле все знают, что то, что теория графов действительно о соединение точек. Множество V состоит из вершин (также известный как узлы), которые изображаются в виде точек. Множество Е состоит из ребер (также называемые дуги или ссылки), и каждое ребро рисуется как линия, соединяющая две вершины, ее конечные точки.
Большую часть времени, картина состоит из не менее тысячи наборов, и все же есть причины для сохранения более формального определения. Когда вы смотрите на рисунок графа, трудно не фокусироваться на расположение точек и линий, но в теории графов все дело в структуре соединений: топологии, не геометрии.
Теория графов получила свое начало в 18 веке, когда великий математик швейцарского происхождения Леонард Эйлер решил загадку о Кенигсбергских мостах. В то время, Кенигсберг (ныне Калининград) имела семь участков, соединненых мостами через реку Прегель. Вопрос головоломки о прогулки по городу, можно ли пересекать каждый мост ровно один раз. Проблема может быть представлена в виде графа (на самом деле мультиграфа), представляя земельные участки в качестве вершин и мосты в качестве ребер.
Эйлер показал, что вы можете ответить на вопрос подведения степенью, или валентностью, каждой вершины, число ребер. Если граф имеет не более двух нечетных вершин, то некоторый путь проходит через каждое ребро один раз. В Кенигсбергском графе все четыре вершины нечетные.
Методы теории графов вскоре оказались полезными не только для планирования прогулки вдоль Преголи. Немецкий физик Густав Кирхгоф проанализировав электрические цепи в терминах графов, с проводами края и точками соединения в качестве вершин. Химики нашли естественное соответствие между графиками и структурными схемами молекул: атом является вершиной, а ребро связи между атомами. Графами также описывают связи и транспортные сети, и даже нейронные сети мозга. Другие применение менее очевидны. Например, шахматный турнир представляет собой граф: игроки узлы, а матчи ребра. В экономике также графы: компании или отрасли промышленности являются узлами, а ребра представляют собой операции.
В 20-м веке теория графов стала более статистической и алгоритмической. Одним богатым источником идей стало изучение случайных графов, которые обычно формируются, начиная с изолированной вершины и добавлением ребер по одному за раз.
В недавней работающей всемирной паутине и других очень больших графах также статистических и алгоритмических по природе, и они имеют тесные связи с Эрдеша-Реньи теории случайных графов. Но есть новый поворот. Многие из этих огромных графов не намеренной конструкции, но природные артефакты, которые выросли через некоторый аккреционный или эволюционный процесс. Интернет, в частности, является объектом никем не разработанным. При близком рассмотрении, структура таких графиков кажется ни полностью, ни частично регулярными. Понимание баланса порядка и хаоса в этих графиков является одной из целей текущей предприятий. Более основная цель просто найти вычислительные методы, которые не будут в шоке от графа с 10 8 узлов.
Хорошим примером действительно большого графа приходит из записей телефонных счетов. Джоан Фейгенбаум лаборатории в Floral Park, Нью-Джерси, возглавляющий группу, работающую с графом известным как граф вызовов. Вершины - телефонные номера, а ребра - звонки с одного номера на другой. Конкретный граф вызовов недавно проанализировал Джеймс М. Абелло, граф имеет 53767087 вершин и более 170 млн. ребер.
Граф вызовов на самом деле направленый мультиграф потому, что два конца вызова можно выделить как инициатор и получатель, мультиграф, потому что пару телефонов может связывать несколько вызовов в день. Для удобства анализа этих аспектов графа нередко игнорируются: наборы кратных ребер свернуты в единый край, и граф рассматривается как если бы оно было ненаправленным. (На графике также имеет около 255 самостоятельных петель, которые я нахожу довольно загадочным. Я редко звоню себе, и это никогда не междугородние).
Первая задача в изучении графа вызовов является то, что вы не можете проглотить ее целиком. Даже если анализ был проведен на компьютере с шестью гигабайтами оперативной памяти, полный граф не подходит. В этих условиях большинство алгоритмов разорительно неэффективно, потому что куски графа должно быть неоднократно курсировали между оператичной памятью и дисковой памяти. Граф вызовов, таким образом, становится испытательным стендом для алгоритмов, предназначенных быстро бегать по данным, хранящихся во внешней памяти.
Что Абелло узнал о граф вызовов? Это не связный граф, но имеет 3700 тысяч отдельных компонентов, большинство из них крошечные, три четверти из компонентов пары телефонов, которые вызываются только друг с другом. Тем не менее, граф вызовов также имеет одну гигантскую компоненту связности, с 44989297 вершины, или более 80 процентов от общего числа. Возникновение гигантской компоненты характерно Эрдеша-Реньи случайным графам, но структура соединений в графе вызовов, конечно, не случайна.
Абелло и его коллеги отправились на охоту в графе вызовов на структуры, называемые клики, или полные графы. Они являются графами, в которых каждая вершина соединена ребром с любой другой вершиной. Выявление крупнейших таких структур-максимальные клики -вычислить трудно даже в графе среднего размера. В графе вызовов, единственно возможной стратегией является вероятностный поиск, который находит большую клику без доказательства их максимальности. Абеллом найдены клики размер 30, которые почти наверняка самые большие. Примечательно, что существуют более 14.000 из этих 30-членнные клики. Каждый клик представляет собой отдельную группу 30 человек, в котором все говорили со всеми по крайней мере один раз в течение дня.
В качестве объекта исследования для теории графов, всемирная сеть имеет то преимущество, что она поставляется уже кодировкой для компьютерного анализа. Вершины и ребра не должны быть каталогизированы, любой компьютер, подключенный к Интернету, может перемещаться по графу просто переходя по ссылкам от узла к узлу. Как граф вызовов, веб-это направленный мультиграф с самостоятельной петли, но многие анализы игнорируют эти осложнения сети, как если бы она была простым неориентированным графом.
Чтобы оценить диаметр сети, Барабаси и его коллеги из Нотр-Дама не посещали каждый узел и проходили все ссылки, они изучили небольшой уголок в Интернете и экстраполировали на остальную часть графа. Группа Барабаси использовала программное обеспечение "робот", направляя все ссылки на стартовую страницу, все ссылки на каждой странице достигли эту страницу, и так далее. Это тот же метод, используемый на индекс поисковых систем в Интернете, но поисковые системы никогда не бывают исчерпывающими, они настроены на каталог документов, представляющих интерес для людей, а не для оценки связности графа.
Первоначально, Нотр-Дам робот смотрел только на интернет-домена nd.edu и собрал информацию о 325 729 документах и ссылок 1469680 (около 0,3 процента сети). Ключевым шагом в анализе этих данных было вычислить вероятность того, что страница имеет заданное количество внутренних и внешних ссылок. Барабаси и его коллеги обнаружили, что обе вероятности подчиняются степенному закону. В частности, вероятность того, что страница имеет к внешним ссылкам пропорционально к -2,45, и вероятность к внутренним ссылкам дается к -2,1. . Из степенного закона следует, что страницы с помощью нескольких ссылок являются наиболее многочисленными, но вероятность большего числа связей постепенно падает настолько, можно ожидать страницы с нескольких сотен или несколько тысяч ссылок. Хотя узлы очень высокой степени редки, они оказывают существенное влияние на связность сети. Такие узлы уменьшают граф путем предоставления ярлыков между противном случае далекими вершинами. Для nd.edu области Барабаси и др. измеряют средний диаметр 11,2 ребра; степенная модель предсказывала 11,6. Экстраполируя на веб в целом дали диаметром около 19 ссылок.
Диаметр графа является важной статистикой, когда вы пытаетесь найти что-то в Интернете. В случае слепого, случайного поиска, как правило, должны изучить половину 800 миллионов документов, спотыкаясь. Но результат Нотр-Дама предполагает, что из любой разумной отправной точки, должен быть путь к целевой странице, пересекая лишь около 19 звеньев. Барабаси и др. заметили: "Относительно небольшое значение [диаметр] указывает, что интеллектуальный агент, который может интерпретировать связи и следовать только соответствующей одной, можно найти нужную информацию быстро передвигаясь в Интернете." (Но найти соответствующие ссылки не всегда легко! Когда я попытался найти пути между случайно выбранными страницами, я уходил сомневаясь, что я квалифицирован как интеллектуальный агент).
Редкие узлы высокой степени также играют роль в другом графотеоретическом анализе сети. Одна группа, которая делает такую работу называет себя Clever Group группа. Умная группа обращает внимание на два специальных видов узла в Интернете. «Хабы» являются узлами высокой степени из страниц, которые указывают на многие другие страницах. «Власть» имеют высокую степень, они указаны на многих других страницах, и особенно хабах. Типичные центры списков - личные закладки или отдельные страницы из каталога услуг, таких как Yahoo. Власть - веб-страницы, что многие люди находят достаточно интересным, чтобы создать ссылку на него.
Умный алгоритм определяет узлы и власти, итерационный процесс обратной связи. Первоначальное сканирование веб-страниц определяется высокой степенью, которая составляют начальный набор кандидатов центров и органов власти. Затем эти наборы уточнены рекурсивной процедурой, которая отбрасывает центра кандидата, если многие из его внешние ссылки указывают на страницы, которые являются членами множества; также власти-сорняки, если они не указали на многие из хабов. Повторное применение этого алгоритма позволяет сосредоточить внимание на тех, узлов и органов, которые наиболее плотно связаны друг с другом.
В одном из проектов, входящих в группу Clever использовали связей между центрами и органами власти для выявления более чем 100.000 «новых общин»-коллекции веб-сайтов, которые разделяют некоторые общие темы. Например, в ходе исследования выяснилось , страницы австралийских пожарных связанны с турецкой студенческой организацией в США .Примечательно, что общины были определены методом, который не полагается в любом случае на содержание веб-страниц; алгоритм смотрел только на картину соединения.
Аналогичные принципы при работе в двигателе веб-поиска Google, разработанной Сергеем Брином и Лоренсом Страница из Стэнфордского университета. Google использует обычные сканирования текста для создания индекса содержимого Web, но рекомендуванные страницы в ответ на запрос ранжируются в соответствии с информацией по анализу ссылок. Страница высоко оценивается, если много страниц указывают на нее, и если многие другие страницы указывают на эту страницу, и так далее.
Измерение свойств графа, такие как диаметр или распределения степеней вершин является первым шагом на пути к пониманию его структуры. Следующим шагом является разработка математической модели структуры, которая обычно принимает форму алгоритма для генерации графов с теми же статистическими свойствами. Т