128 |
Глава 5. Графовые алгоритмы |
SNA — благодаря распределенной и взаимосвязанной архитектуре социальных сетей — является одним из наиболее мощных примеров использования теории графов. Другой способ работы с графом — рассматривать его как сеть и при менять алгоритмы, разработанные для сетей. Это целая область‚ называемая
теорией сетевого анализа, и ее мы обсудим далее.
ВВЕДЕНИЕ В ТЕОРИЮ СЕТЕВОГО АНАЛИЗА
Мы знаем, что взаимосвязанные данные могут быть представлены в виде сети. В теории сетевого анализа подробно изучают методологии, разработанные для исследования и анализа таких данных. В этом разделе мы рассмотрим некоторые важные аспекты теории сетевого анализа.
Обратите внимание, что вершина — базовая единица сети. Сеть — это совокуп ность взаимосвязанных вершин (различных исследуемых объектов), а каждая линия соединения отображает отношения между ними. Чтобы решить задачу, нужно количественно оценить полезность и важность вершины в сети. Для этого существует несколько методов.
Рассмотрим ряд важных концепций, используемых в теории сетевого анализа.
Кратчайший путь
Путь представляет собой маршрут между выбранной начальной и конечной вершинами; это набор вершин, p, соединяющих начальную вершину с конечной. Ни одна вершина в p не повторяется.
Длина пути равна количеству входящих в его состав ребер. Из всех вариантов путь с наименьшей длиной называется кратчайшим. Расчет такого пути широ ко используется в алгоритмах теории графов, но не всегда прост для вычисления. Существуют различные алгоритмы поиска кратчайшего пути между начальным и конечным узлами. Один из самых популярных — алгоритм Дейкстры, опу бликованный в конце 1950-х годов. Его можно использовать в системе глобального позиционирования, GPS (Global Positioning System), для расчета минималь ного расстояния между источником и пунктом назначения. Алгоритм Дейкстры также применяется в алгоритмах сетевой маршрутизации.
Между Google и Apple не прекращается битва за разработку наи лучшего алгоритма поиска кратчайшего расстояния в картах Google и Apple Maps. Задача состоит в том, чтобы сделать алгоритм настолько быстрым, чтобы кратчайший путь вычислялся за считанные секунды.
Введение в теорию сетевого анализа |
129 |
Позже в этой главе мы обсудим алгоритм поиска в ширину, BFS (breadth-first search algorithm), который может быть преобразован в алгоритм Дейкстры. BFS предполагает одинаковые затраты на каждый вариант обхода графа. Для алго ритма Дейкстры затраты могут быть разными, и это необходимо учесть, чтобы превратить BFS в алгоритм Дейкстры.
Алгоритм Дейкстры вычисляет кратчайший путь от одной из вершин. Если мы хотим найти все пары кратчайших путей, нужно использовать алгоритм Флойда — Уоршелла (Floyd-Warshall algorithm).
Создание окрестностей
Поиск стратегий для создания окрестностей вокруг выбранных вершин имеет решающее значение для графовых алгоритмов. Методологии создания окрест ностей основаны на выборе прямых связей с интересующей вершиной. Одной из таких методологий является стратегия k-го порядка, которая выбирает вер шины, находящиеся на расстоянии k переходов от интересующей вершины.
Давайте рассмотрим различные критерии создания окрестностей.
Треугольники (triangles)
В теории графов поиск вершин, которые тесно связаны друг с другом, крайне важен для анализа. Один из методов состоит в том, чтобы попытаться иденти фицировать в сети треугольники, представляющие собой подграф, состоящий из трех непосредственно соединенных между собой вершин.
Давайте обсудим практический пример: выявление мошенничества (он будет подробнее рассмотрен в конце этой главы). Если эго-сеть узла m состоит из трех вершин, включая вершину m, то эта эго-сеть является треугольником. Вершина m будет эго, а две связанные вершины будут альтерами, скажем, вершина A и вершина B. Если оба альтера являются известными мошенниками, то мы мо жем с уверенностью объявить вершину m мошенником. Если только один из альтеров замешан в мошенничестве, мы не сможем представить убедительные доказательства, но нам следует продолжить поиски.
Плотность (density)
Начнем с определения полносвязной сети. Полносвязной сетью (fully connected network) мы называем граф, где каждая вершина напрямую связана с каждой другой вершиной.
130 |
Глава 5. Графовые алгоритмы |
Если у нас имеется полносвязная сеть N, то количество ребер в сети может быть представлено следующим образом:
Здесь в дело вступает плотность (density). Плотность измеряет отношение на
блюдаемых ребер к максимальному количеству ребер, если EdgesObserved — это количество ребер, которые мы хотим рассмотреть. Ее можно сформулировать
так:
Обратите внимание, что для треугольника плотность сети равна 1 и она пред ставляет собой максимально возможную связную сеть.
Показатели центральности
Существуют различные показатели центральности (сentrality measures) кон кретной вершины в графе или подграфе. С их помощью можно, например, ко личественно оценивать важность человека в социальной сети или важность здания для города.
В анализе графов широко используются следующие показатели центральности:
zz cтепень (degree);
zz посредничество (betweenness); zz близость (closeness); zzвлиятельность (Eigenvector).
Давайте разберем их подробно.
Степень
Количество ребер, соединенных с определенной вершиной, называется ее степенью (degree). Степень может указывать на то, насколько хорошо подключена конкретная вершина и какова ее способность быстро распространять сообщение по сети.
Введение в теорию сетевого анализа |
131 |
Давайте рассмотрим aGraph = ( , ), где представляет собой набор вершин‚ а — набор ребер. Напомним, что aGraph содержит | | вершин и | | ребер. Если мы разделим степень узла на (| | –1), то получим степень центральности (degree centrality):
Разберем конкретный пример. Взгляните на следующий граф (рис. 5.9).
Рис. 5.9
На этом графе вершина C имеет степень 4. Ее степень центральности может быть рассчитана следующим образом:
Посредничество
Посредничество, или промежуточность (betweenness),— это показатель цент ральности в графе. В контексте социальных сетей она позволяет количественно оценить вероятность того, что человек является частью взаимодействия в под группе. Для компьютерной сети посредничество количественно определяет негативное влияние отказа ребра на связь между вершинами графа.