Ориентированные мультиграфы

Если в мультиграфе существует направленная связь между узлами, мы называ­ ем его ориентированным мультиграфом (directed multigraphs) (рис. 5.6).

Рис. 5.6

Пример ориентированного мультиграфа: Майк отчитывается перед Джоном в офисе, а Джон учит Майка языку программирования Python.

Особые типы ребер

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

zz Петля (self-edge). Иногда вершина имеет отношение к самой себе. Например, Джон переводит деньги со своего рабочего счета на личный. Подобные осо­ бые отношения могут быть представлены ребром‚ ориентированным само на себя.

zz Гиперребро (hyperedge). Иногда ребро объединяет более одной вершины. Ребро, соединяющее более одной вершины для представления соответству­ ющих отношений, называется гиперребром. Например, предположим, что все трое — Майк, Джон и Сара — работают над одним проектом.

Граф, имеющий одно или несколько гиперребер, называется гиперграфом (hypergraph).

На рис. 5.7 представлены графы с петлей и гиперребром.

Рис. 5.7

Обратите внимание, что граф может содержать как петли‚ так и гиперребра одновременно.

Эгоцентрические сети

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

Эго-сеть конкретной вершины, 3, показана на рис 5.8.

Обратите внимание, что данная эго-сеть представляет собой окрестность первой степени. Эта концепция может быть распространена на окрестности n-степени, включающие в себя все вершины, удаленные от конкретной вершины на n шагов.

Анализ социальных сетей

Анализ социальных сетей (social network analysis, SNA) — одно из важных при­ менений теории графов. Анализ сетевого графа считается анализом социальной сети, если применимо следующее:

zz Вершины графа представляют людей.

zz Ребра между ними представляют социальные отношения, такие как дружба, общее хобби, родство, сексуальные отношения, антипатии и т. д.

zzБизнес-вопрос, на который мы пытаемся ответить с помощью анализа графов, имеет некоторый выраженный социальный аспект.

Рис. 5.8

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

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

SNA можно использовать для следующих целей:

zz понимание действий пользователей на платформах социальных сетей, таких как Facebook, Twitter или LinkedIn;

zz изучение природы мошенничества;

zz исследование преступного поведения в обществе.

Компания LinkedIn внесла большой вклад в исследования и разработку новых методов, связанных с SNA. Фактически LinkedIn можно считать пионером многих алгоритмов в этой области.