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

Теория графов находит применение, например, в геоинформационных системах. Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра.

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

Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.

История возникновения теории графов

Родоначальником теории графов считается выдающийся математик, член Петербургской академии наук Леонард Эйлер.

В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

• Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
• Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
• Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

Изображение графов на плоскости

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

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

Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление.

Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет. Часто на практике бывает трудно ответить на вопрос, являются ли два изображения моделями одного и того же графа или нет (другими словами, изоморфны ли соответствующие изображениям графы). В зависимости от задачи, одни изображения могут давать более наглядную картину, чем другие.

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

Социальный граф (англ. Social graph) — это граф, узлы которого представлены социальными объектами, такими как пользовательские профили с различными атрибутами (например: имя, день рождения, родной город и т. д.), сообщества, медиа-контент и т. д., а ребра — социальными связями между ними.

Неявный социальный граф (англ. Implicit social graph) — это такой граф, который можно сформировать на основе взаимодействий пользователя со своими «друзьями» и группами «друзей» в социальной сети. В этом графе в отличие от обычного социального графа нет явного указания «друзей», то есть нет явных социальных связей.

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

Обработка данных социальных графов связана с рядом проблем, как например различия социальных сетей, закрытость социальных данных.

Задачи

Идентификация пользователей

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

Социальный поиск
Поиск социальных объектов (пользователей, их данных, их записей и т. д.), основанный на анализе набора связей, в которых находятся искомые объекты.

Генерация рекомендаций
Важной задачей является поиск точных алгоритмов генерации рекомендаций и предложений пользователям, который так же используется при создании графа интересов на основе социального графа.

• Рекомендация друзей — пользователи редко делят свои контакты на социальные группы, но, тем не менее, они неявно делят эти контакты на кластеры, через их взаимодействия в рамках социальной сети.
• Рекомендации контента — рекомендации медиа-контента, сообществ, новостей и т. п.

Существуют традиционные подходы в области рекомендательных систем:

• Коллаборативная фильтрация — заключается в формировании списка рекомендованных объектов на основе мнений пользователей, ведущих себя похожим образом.
• Фильтрация содержимого — основывается на характеристиках предмета и известной о нем информации.
• Социальные подходы — отталкиваются от социальных связей пользователей.

Выявление «настоящих» связей

Применение подхода «разведки на основе открытых источников» для выявления истинных связей между пользователями, то есть настоящих друзей, родственников и т. п.

Граф интересов

Граф интересов — это онлайн представление интересов конкретного человека, полученное на основе его активности в социальных сетях.

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

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

Cвязи в графе интересов

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

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

Граф интересов также может быть представлен в виде взвешенного графа, в этом случае вес ребра означает силу взаимосвязи между вершинами.

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

Отношения между графом интересов и социальным графом

Граф интересов и социальный граф тесно взаимосвязаны, но это не одно и то же.

Граф интересов используется для создания сети интересов людей. В то время как Facebook и другие социальные сети организованы вокруг друзей человека, то есть вокруг социального графа, сети увлечений созданы вокруг интересов личностей, их графа интересов.

Подобно тому как социальный граф — это карта взаимосвязей личности с теми, кто «следует» за ней в сети, граф интересов — это так же взаимосвязь с интересами личности в сети.

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

Граф интересов должен быть точным и выразительным, он должен принимать во внимание явно объявленные интересы, например, «Like» на Facebook или «интересы» в профиле на LinkedIn, а также неявные интересы, выведенные на основе активности пользователя, например, такие как щелчки мышью, комментарии, теги к фото и чек-ины. Социальные сети часто являются источником этой информации.

Использование графа интересов

Существует несколько способов использования графа интересов, как с точки зрения потребителя, так и с точки зрения бизнесмена. В сочетании с социальным графом, граф интересов может быть применён для установления связей между пользователями в социальных сетях или в реальном мире. В таких сетях пользователи могут указывать и делиться своими увлечениями, но при этом им не обязательно знать друг друга.

Граф интересов так же может быть применён в маркетинге, в целях анализа аудитории проекта и дальнейших продаж на основе этой информации, для анализа тональности текста и для таргетированной рекламы, основанной на интересах.

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

Также граф интересов может использоваться при создании продукции с учётом пожеланий потребителя, он помогает определить какие особенности и возможности следует предоставить в следующих версиях. Граф интересов имеет множество других применений включая задачи обнаружения содержимого и фильтрации для предоставления рекомендаций по фильмам, книгам, музыке и так далее.

материал с medium.com