Что такое граф? и для чего применяется?

Графы - что это и для чего применяются?Формально граф - это набор вершин и ребер, или, говоря более простым языком, набор узлов и взаимосвязей между ними. В графах объекты представлены узлами, а способы, которыми эти объекты соединены между собой, - взаимосвязями. Эта универсальная и вы­разительная структура позволяет моделировать всевозможные сце­нарии, от постройки космической ракеты до строительства системы дорог, от поставок продуктов питания до историй болезни населения, и многое другое.

 

Графы повсюду

Графы чрезвычайно полезны при анализе самых разных наборов дан­ных в таких областях, как наука, государственное управление и бизнес. Реальный мир, в отличие от основанной на шаблонах устаревшей модели реляционных баз данных, разнообразен и взаимосвязан: в одних мес­тах равномерно и упорядочено, в других случайно и нерегулярно. После освоения графов вы начнете замечать их присутствие повсюду. Гартнер (Gartner), например, выделяет в мире бизнеса пять видов графов: социальный, целевой, потребления, инте­ресов и мобильности - и утверждает, что способность использовать эти графы обеспечивает «устойчивое преимущество в конкурентной среде».

Например, данные в Twitter легко представить в виде графа. На рис. 1 изображена небольшая сеть пользователей Twitter. Каждый узел поме­чен как «пользователь», с указанием его роли в сети. Узлы соединены взаимосвязями, определяющими дополнительный семантический кон­текст, а именно: Билли следует за Гарри, а Гарри, в свою очередь, следует за Билли. Рут и Гарри так же следуют друг за другом, но, к сожалению, хотя Рут следует с Билли, Билли (пока) не ответил взаимностью.

 Малый социальный граф

 Рис. 1 ❖ Малый социальный граф

 

Конечно же, реальный граф Twitter в сотни миллионов раз больше, чем изображенный на рис. 1, но работает по тому же принципу. На рис. 2 мы расширили граф, включив в него сообщения, опублико­ванные Рут.

Несмотря на свою простоту, рис. 2 демонстрирует выразитель­ную мощь графового моделирования. Из него легко понять, что Рут опубликовала последовательность сообщений. Ее самое последнее сообщение можно найти по взаимосвязи, помеченной как ТЕКУЩЕЕ. Да­лее следуют сообщения Рут, помеченные как ПРЕДЫДУЩЕЕ.

 

Модель графов с метками и свойствами

При обсуждении рис. 2 мы неформально представили самую популяр­ную графовую модель - графовую модель с метками и свойствами . Графовая модель с метками имеет следующие характеристики:

  • содержит узлы и взаимосвязи;
  • у узлов есть свойства (пары ключ-значение);
  • узлы должны быть помечены одной или более метками;
  • взаимосвязи имеют имя и направление, для них всегда определен на­чальный и конечный узлы;
  • у взаимосвязей также имеются свойства.

Большинство считает, что графовая модель со свойствами является простой и интуитивно понятной. Но, несмотря на свою простоту, именно она используется в подавляющем большинстве случаев при применении графов для отображения данных.

Опубликованные сообщения в графовой модели

Рис. 1.2  Опубликованные сообщения

 

 

Обзор областей применения графов

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

С высоты птичьего полета области применения графов можно раз­делить на две части:

  • технологии организации транзакционных графовых хранилищ, как правило, используемых в режиме реального времени непо­средственно из приложения. Эти технологии называются графо­выми базами данных, и им в этой книге будет уделено основное
    внимание. Они являются аналогом «нормальной» обработки транзакций в масштабе реального времени (On-Line Transac­tion Processing, OLTP) реляционных баз данных.
  • технологии автономного анализа графов, обычно реализующие серии пакетных шагов. Эти технологии часто называют меха­низмами вычисления графов (graphcomputeengine).Их можно отнести к той же категории, что и другие приемы анализа объ­емных данных, например интеллектуальный анализ данных и аналитическая обработка данных в реальном времени (On­Line Analytical Processing, OLAP).

Существует и еще один способ классификации применения гра­фов, основанный на видах графовых моделей. Имеются три до­минирующие графовые модели: графы со свойствами, триплексы схем описания ресурсов (Resource Description Framework, RDF) и гиперграфы. Они подробно рассмотрены в приложении А. Боль­шая часть популярных графовых баз данных, представленных на рынке, использует графовые модели со свойствами, поэтому именно эта модель и будет использована в моем блоге.

Вас заинтересует / Intresting for you:

Citizen Integrator  - что это ...
Citizen Integrator  - что это ... 887 просмотров Дэн Sun, 07 Oct 2018, 08:29:12
Фриц Хугланд - профессионал Or...
Фриц Хугланд - профессионал Or... 850 просмотров Дэн Sun, 05 Aug 2018, 16:21:01
Рене Ковингтон (Renee Covingto...
Рене Ковингтон (Renee Covingto... 3431 просмотров Antoni Sun, 05 Aug 2018, 16:21:01
Дэн Хотка (Dan Hotka) - специа...
Дэн Хотка (Dan Hotka) - специа... 4879 просмотров Дэн Sun, 05 Aug 2018, 16:21:01

Comments on Что такое граф? и для чего применяется?

Будьте первым прокомментировавшим
Пожалуйста, авторизуйтесь, для комментирования