Шаг 1.2. Итеративное сокращение фанов и центров S
. Пока S
i
6= Удалить из все вершины s со степенью исхода d
o
(s) < Удалить из все вершины s со степенью захода d
i
(s) < Шаг 2. Порождение двудольного ядра i = 1 . . . k do:
109
* z s w ^ > : q w 7 3 : R * - s s f1 f2 f3 f4 c1 c2 c3 c4 c5 F (фаны) C (центры) Рис. 46: (двудольное ядро. • Получить (i, j) двудольные сообщества. Базис: (1, j) сообщество состоит из одной вершины s со степенью исхода d o (s) = Индукционный шаг Для каждого центра (i ? 1, j) сообщества, найти ссылающуюся на него вершину f 0 , не входящую в сообщество. Если связана со всеми j центрами сообщества, то добавить в двудольное ядро в качестве нового фана. Комментарий. Вообще говоря, двудольные ядра не определяют полностью сообщества. Скорее они выявляют их "центральную"часть и дают некоторое направление для поиска темы Сообщества максимального потока Сообщества максимального потока. Пусть G S = hS, E S i граф связей надмножеством объектов S. Одно из определений сообщества можно сформулировать следующим образом: Сообщество это подмножество объектов C ? S такое, что • каждый объект u ? C имеет больше ребер (входящих и исходящих, связывающих его с другими членами C, чем ребер, связывающих его с объектами из S \ В общем случае, задача выделения таких сообществ является полной. Поэтому в работе было предложено приближенное решение этой задачи, основанное на нахождении максимальных потоков. Обнаруженные таким образом сообщества называются сообществами максимальных потоков. Напомним (см. раздел 7), что транспортная сеть N =< G = (V, E), c, s, t >, состоит из ориентированного графа G, ребра которого имеют пропускные способности c(e) ? 0, источника s ? V , в который не входят ребра, истока, из которого не выходят ребра. Поток f в сети N - это функция f : E ? R такая, что) 0 ? f(e) ? c(e) для каждого ребра e ? E; 2) для каждой вершины v ? V \ {s, t} P{f (e)| e входит в v} = P{f(e)| e выходит из Величина потока f в сети N val(f) = P u?V f (s, Поток с наибольшим значением величины называется максимальным. В разделе 7 мы рассмотрели задачу определения максимального потока и описали алгоритм МАХП, решающий эту задачу за время O(|V | 3 ) (). Применение этих алгоритмов для обнаружения сообществ в социальных сетях основано наследующей теореме Форда-Фалкерсона теорема величина максимального потока в сети равна величине минимального разрезав ней. Здесь разрез A в сети N - это подмножество вершин A ? V такое, что источника сток t ? V \A. Разрез A однозначно задает множество ребер P (A) = {(u, v) | u ? A, v ? V выходящих из Если пропускные способности ребер равны 1, то для максимального потока fmax его величина) равна минимальному числу ребер |P (A)|, соединяющих некоторый (минимальный) разрез A с остальной частью сети. Рис. 47 иллюстрирует такие разрезы u1 u2 u3 u4 u5 u6 w t e e e e e e e e e e e e e e e e e Рис. 47: Максимальный поток в сети. Сечения разделяют обнаруженные сообщества Поток между вершинами s и t ограничен двумя ребрами бутылочного горлышка (u3, u4) и, u5) . Аналогично, поток между вершинами s и w ограничен ребрами (u1, u6) (u2, u6). Если эти ребра отсечь (удалить из сети, то мы получим три различных сообщества. Алгоритм Find-Community(S ? , K число итераций := S ? ; for it = 1 to K do { G := crawlGraph(C); n := ранжировать все v ? по числу ребер внутри C ? ; C := C ? {v ? C ? |v имеет высокий ранг в C ? } }; return C; end Function Max-Flow-Community(G= (V,E), C, k) begin V := V ? {s, t} ; for all v ? V do {E := E ? {(s, v)}; c(s, v) := ?}; for all (u, v) ? E, u 6= s do; { c(u, v) = k; if (v, u) 6? E then {E := E ? {(v, u)}; c(v, u) := k} }; for all v ? V , v 6? C ? {s, t} do {E := E ? {(v, t); c(v, t) = 1}; МАХП 0 (G, s, t) ; return {v ? V | v достижима из Рис. 48: Алгоритм поиска сообщества максимального потока Алгоритм Find-Community представлен на рис. 48. Он работает следующим образом. • Вход. Социальная сеть и множество исходных объектов (страниц) S ? . Предполагается, что пользователю известно, что исходные объекты принадлежат одному сообществу. Алгоритм будет определять границы этого сообщества. • Выход. C ? S ? список объектов сообщества. • Процесс. Алгоритм работает в два этапа Этап 1. Расширение исходных страниц. Алгоритм обходит социальную сеть, начиная с исходных страниц, и собирает некоторую окрестность множества C = S ? . Для этого используется процедура crawlGraph(C), которая добавляет к C все вершины, находящиеся на ограниченном расстоянии от вершин C (при этом обход в ширину происходит без учета направления ребер Этап 2. Максимальный поток. Для отделения сообщества C ? от остальной сети применяется алгоритм поиска максимального потока МАХП 0 (G, s, t) . Предполагается, что этот алгоритм определения максимального потока алгоритмом МАХП удалит ребра, соединяющие минимальный разрез с остальным графом. Для нахождения требуемого сообщества эти этапы могут повторяться несколько раз. Значения параметров K и k выбираются эмпирически. Часто выбирается значение k = |S|. 10.7 Задачи Задача 10.1. Докажите лемму Задача 10.2. Пусть G = (I, E) ориентированный граф. Предложите алгоритм для вычисления для вершины i ? I значения ее близкой центральности (Closeness Centrality) по формуле) = n ? 1 P j?I ?(i, Оцените сложность предложенного алгоритма. Задача 10.3. Пусть G = (I, E) нагруженный ориентированный граф c неотрицательными длинами ребер c : E ? R + . Предложите реализацию алгоритма из теоремы 10.2, для вычисления значений срединной центральности всех вершин i ? V. Оцените сложность предложенного алгоритма. Задача 10.4. Графовая центральность (graph centrality (Hage, Harary, 1995)) вершины i графа = (I, определяется как) = 1 max k?I ?(i, Предложите алгоритмы для вычисления графовой центральности всех вершин для ненагру- женных и нагруженных графов и оцените сложность этих алгоритмов. Задача 10.5. Центральность нагрузки (stress centrality (Shimbel, 1953)) определяется для вершины графа G = (I, E) как) = X j6=i6=k Предложите алгоритмы для вычисления центральности нагрузки всех вершин для ненагру- женных и нагруженных графов и оцените сложность этих алгоритмов. Задача 10.6. Напомним, что диаметром (неориентированного графа G = (V, E) с весами ребер c : E ? R + назывется максимальное расстояние между вершинами графа d G = max{?(u, v)|u, v ? V см. задачу 6.5). Радиальность (radiality (Valente, Foreman, 1998)) определяется для вершины i графа G = (I, E) как) = P k?V (d g + 1 ? ?(i, k)) (n ? Предложите алгоритм для вычисления радиальности всех вершин для ненагруженных и нагруженных графов и оцените сложность этих алгоритмов Задача 10.7. Пусть G = (V, E) ненагруженный ориентированный граф. Предложите алгоритм для вычисления для вершины i ? V значения ее средней престижности (Proximity
Prestige) определяемой по формуле) =
|I
i
|
2
(n ? 1)
P
j?I
i
?(j, где I
i это множество вершин, из которых можно достичь i в G, n = |V | . Оцените сложность предложенного алгоритма.
Задача 10.8. Определите какие ранги присвоит алгоритм PageRank вершинам следующих графов.
а) G
1
= (V, E)
:
V = {a, b, c, d, e}
E = {(a, b)(b, a), (b, c), (c, a), (c, d), (d, a), (d, e), (e, a), (e, б) G
2
= (V, E)
:
V = {a, b, c, d, e}
E = {(a, b)(b, a), (c, a), (c, b), (d, a), (d, b), (e, a), (e, в) G
3
= (V, E)
:
V = {a, b, c, d}
E = {(a, b), (b, a), (b, c), (c, a), (c, d), (d, a), (d, Поскольку в этих графов из каждой вершины выходят ребра, положим параметр d = 1.
114
Список литературы А. Ахо, Дж. Хопкрофт, Дж. Ульман Структуры данных и алгоритмы. М Вильямс, 2000.
[2] Гэри М, Джонсон Д. Вычислительные машины и труднорешаемые задачи. М Мир, с Евстигнеев В.А. Применение теории графов в программировании. М.:Наука, Физмат лит, с Кормен Т, Лейзерсон Ч, Ривест Р, Штайн К. Алгоритмы (построение и анализ. СПб.:
Вильямс, 2005.
[5] Кристофидес Н. Теория графов. Алгоритмический подход. М. : Мир, 1978.
[6] Левин Л.А., Универсальные задачи перебора // Проблемы передачи информации, 9, С Липский В. Комбинаторика для программистов.-М.:Мир,1988.
[8] Ловас Л, Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М Мир, 1988, с Майника Э. Алгоритмы оптимизации на сетях и графах. -М.:Мир,1981.
[10] Пападимитриу Х, Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.-
М.:Мир, 1985.
[11] Плесневич ГС, Сапаров МС. Алгоритмы в теории графов. Ашхабад:Ылым, 1981, 312 с У. Татт. Теория графов. М Мир, 1988.
[13] Р. Уилсон. Введение в теорию графов. М Мир, 1977.
[14] D. Applegate, R. Bixby, V. Chvatal, and W. Cook. The Traveling Salesman Problem: A
computational study. Princeton University Press, 2007.
[15] Brandes U. A faster algorithm for betweeness centrality// Journal of Mathematical Sociology
25(2), 2001, 163-177.
[16] Cherkassky B.V., Goldberg A.V., Radzik T. Shortest paths algorithms: theory and experimental evaluation. Mathematical programming, 1996
[17] Cook S.A., The complexity of theorem-proving procedures // Proc. 3-th Ann ACM Symp. on
Theory of Computing, 1971. P.151158.
(Русск. перевод Кук С.А., Сложность процедур вывода теорем. Киб. сб., нов.сер., вып М.:Мир, 1975, 5-15).
[18] FlakeG. W., Lawrence S., Giles C. L., Coetzee F. Self-Organization of the Web and Identi cation of Communities. IEEE Computer 35(3),2002, 6671.
[19] G. Gutin and A. Punnen. The Traveling Salesman Problem and Its Variations. Springer, 2007.
[20] Karp R.M., Reducibility among combinatorial problems, in R.E.Miller and J.W.Thatcher
(eds),Complexity of Comuter Computations, Plenum Press, NY, 1972, 85-103.
(Русск. перевод Карп Р.М. Сводимость комбинаторных задач.Киб. сб., нов.сер., вып. 12.
М.:Мир, 1975, 16-38).
115
[21] Kleinberg J. M. Authoritative sources in a hyperlinked environment. In Proc. of ACM-SIAM
Symposium on Discrete Algorithms, 1998.
[22] E. Lawler, J. Lenstra, A. Rinnooy Kan, and D. Shmoys. The Traveling Salesman Problem. John
Wiley, 1985.
[23] Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry (1998). The PageRank citation ranking: Bringing order to the Web. Technical Report, Department of Computer Science,
Stanford University.
[24] Rosenkrantz D.J., Stearns R.E., Lewis P.M. An analysis of several heuristics for the traveling salesman problem. // SIAM J. Comput. 6, 563-581.
[25] Scott, J. Social network analysis: A handbook (2nd ed.). SAGE publications, 2000.
[26] Social Network Data Analytics. Ed. C.C.Aggarwal. Springer, 2011.
[27] Xu G., Zhang Y., Li L. Web Mining and Social Networking. Techniques and Applications/
Springer Science+Business Media, 2011.
116
Предметный указательNP-полная проблема, база графа, близкая центральность актора (вершины) , брат (сестра) вершины дерева, вершина графа, вершинное покрытие ребер , ветвь дерева, высота вершины дерева, дерева, 15 Гамильтонов цикл , глубина вершины дерева, глубинный остов графа, граф двудольный (бихроматический), 11, двусвязный, достижимости (транзитивного замыкания), 41 неориентированный, ориентированный, размеченный, связный, сильно связный, сильно связных компонент, упорядоченный, двусвязная компонента (блок) графа, дерево неориентированное, ориентированное, бинарное (двоичное) , диаметр графа , изоморфизм графов, клика , конденсация графа, корень дерева, кратчайший путь, лес, лист дерева, матрица инцидентности графа, матрица смежности графа, минимальная компонента сильной связности, 38 мультиграф ориентированный, максимальный поток в сети, минимальная компонента, минимальный разрез в сети, мост графа , независимое множество вершин , обратное ребро, обход дерева внутренний (инфиксный) , обратный (суффиксный) , прямой (префиксный, остов (остовное дерево) графа , отец (родитель) вершины, 15 паросочетание в графе, 65 подграф, поиск в глубину , поиск в ширину, 31 полустепень захода для вершины ориентированного графа, исхода для вершины ориентированного графа, порождающее подмножество вершин, потенциал вершины в сети , поток в сети, потомок вершины дерева, предок вершины дерева, пропускная способность дуги, прямое ребро, путь в графе, ребро графа, радиус графа внешний , внутренний , разрез в сети, раскраска вершин графа, списки смежности графа, степень вершины графа, 4 117 сводимость за полиномиальное время, сеть вспомогательная, простая, транспортная, сильно связная компонента, 36 cовершенное паросочетание , социальная сеть , срединная центральность актора (вершины) степень престижности актора (вершины) , степень центральности актора (вершины) , сын (ребјнок) вершины, топологическая сортировка, точка сочленения , тупиковый поток , увеличивающий путь в сети, формула, хроматическое число графа, цикл (в графе, центр графа внешний , внутренний , 53 Эйлеров цикл, 11 118
УДК 681.3.06 + 519.6
ББК Учебное издание
Дехтярь Михаил Иосифович
Алгоритмические задачи на графах
Учебное пособие
Подписано в печать 01.10.2012. Уч.-изд.л.7,37. Электронное изд. Заказ Тверской государственный университет
Факультет прикладной математики и кибернетики
Адрес: 170000, г.Тверь, пер.Садовый, 35.
|
Скачать 1.07 Mb.