5

Графовые алгоритмы

Существует класс вычислительных задач, решить которые проще всего, пред­ ставив их в виде графов и применив алгоритмы, называемые графовыми (graph algorithms). Например, графовые алгоритмы используются для эффективного поиска значения в графическом представлении данных. Прежде всего алгоритм определяет структуру графа, затем ищет правильную стратегию прохода по его ребрам с целью получить данные, хранящиеся в вершинах. Поскольку графовым алгоритмам для работы необходимо искать значения, в основе их разработки лежат эффективные стратегии поиска. Использование графовых алгоритмов — один из наилучших способов поиска информации в сложных структурах данных, связанных между собой значимыми отношениями. Сегодня‚ в эпоху больших данных, социальных сетей и распределенных данных, такие методы становятся все более важными и нужными.

Эту главу мы начнем с базовых концепций графовых алгоритмов. Затем по­ знакомимся с основами сетевого анализа, а также с различными методами, ко­ торые можно использовать для обхода графов. Наконец, рассмотрим пример использования графовых алгоритмов для обнаружения мошенничества.

Итак, мы обсудим:

zz Различные способы представления графов. zz Введение в теорию сетевого анализа.

zz Понятие обхода графа.

zz Практический пример — анализ мошенничества. zzМетоды создания окрестностей в пространстве задачи.