Алгоритмические задачи на графах
 Скачать 1.07 Mb.
|
|
Пусть ? jk (i) = p jk (i) p Тогда срединная центральность определяется соотношением) Заметим, что для вычисления величин p и достаточно уметь вычислять длины кратчайших путей и величины p jk , так как p jk (i) = p ji p ik если ?(j, k) = ?(j, i) + ?(i, в противном случае Поэтому срединная центральность может быть определена следующим способом. Вычислить длины и количество кратчайших путей между всеми парами вершин. Для каждой вершины i определить и просуммировать все значения ? jk (i). 101 Для определения длин кратчайших путей можно использовать алгоритм Уоршолла-Флойда из пункта 6.1.1, а для определения числа таких путей утверждение о том, что элемент a (k) ij ой степени матрицы смежности равен числу различных путей длины l изв (см. задачу 6.2). Другой способ определения числа p jk кратчайших путей связан с использованием множества вершин P j (k) предшественников k на кратчайших путях из j: P j (k) = {i | (i, k) ? E, ?(j, k) = ?(j, i) + c(i, Так как длины всех ребер неотрицательны, то все кратчайшие пути изв заканчиваются ребрами вида (i, k) для i ? P j (k) . Отсюда следует справедливость следующего соотношения. Лемма 10.1. p jk = X i?P j (k) p Для вычисления p jk в соответствии с этой формулой можно адаптировать алгоритм поискав ширину для ненагруженных графов или алгоритм Дейкстры для нагруженных ориентированных графов. Используя известные оценки сложности этих алгоритмов, получаем Предложение 10.1. Для заданной вершины j ? I можно определить длины и число кратчайших путей из нее до остальных вершин за время: а) O(|E|) для ненагруженных графов; б) O(|E| + |I| log |I|) для нагруженных ориентированных графов. Отсюда следует, что величины p jk можно вычислить за время O(|I|·|E|) для ненагруженных графов и за время O(|I| · |E| + |I| 2 log для нагруженных ориентированных графов. Поскольку для вычисления срединной центральности i в п требуется суммировать значения, то общее время вычисления будет O(|I| 3 ) . Для этого вычисления требуется память размера O(|I| 2 ) , необходимая для хранения матрицы расстояний и величин p В работе [15] Брандес (Brandes) предложил улучшение этого алгоритма, в котором суммирование по всем парам вершин заменяется на последовательное вычисление частичных сумм. Следуя этой работе, определим зависимость вершины j от вершины i как величину) Зависимости можно вычислять, используя рекурсивные соотношения. Лемма 10.2. Если в каждую вершину k ? I ведет единственный кратчайший путь из j, то) = X i?P j (k) (1 + Доказательство этой леммы предоставляется читателю (см. задачу В общем случае рекурсия более сложная. Теорема 10.1. Для любых вершин j и i справедливо соотношение) = X i?P j (k) p ji p jk (1 + Доказательство. Уточним понятие зависимости, включив в него ребро, выходящее из Пусть ? jk (i, (i, l)) = p jk (i,(i,l)) p jk , где p jk (i, (i, l)) это число кратчайших путей изв, содержащих как вершину i, таки ребро (i, l). Тогда) = X k?I ? jk (i) = X k?I X l:i?P j (l) ? jk (i, (i, l)) = X l:i?P j (l) X k?I ? jk (i, (i, l)). 102 Как мы уже отмечали, для любых k и l p jk (l) = p jl p lk . Число кратчайших путей изв содержащих ребро (i, l), очевидно, равно произведению числа кратчайших путей изв на число кратчайших путей изв. Тогда p jk (i, (i, l)) = p ji p lk = p ji p jl · p Отсюда выводим, что, (i, l)) = ( p ji p il если k = l p ji p il · p jk (l) p jk если k 6= Подставив это в выражение для ? j• (i) , получим утверждение теоремы, (i, l)) = X l:i?P j (l) ( p ji p il + X k6=l p ji p il · p jk (l) p jk ) = X l:i?P j (l) p ji p il · (1 + Следствие 10.1.1. По заданному ациклическому графу кратчайших путей из вершины j в графе G все зависимости j от остальных вершин можно вычислить за время O(|E|) и с памятью O(|I| + Доказательство. Для вычисления требуемых зависимостей достаточно обойти вершины графа кратчайших путей в порядке неубывания их расстояний от j и суммировать зависимости в соответствии с теоремой 10.1. Для этого достаточно для каждой вершины хранить зависимость j от нее и список ее предшественников в графе кратчайших путей. Общий объем этих списков пропорционален числу ребер в графе. Теорема 10.2. Срединная центральность может быть вычислена за время O(|I| · |E| + |I| 2 log и с памятью O(|I| + |E|) для нагруженных графов. Для ненагруженных графов время вычисления сокращается до O(|I| · Доказательство. Для каждой вершины-источника j ? I построим граф кратчайших путей из нее. В конце каждой итерации зависимости вершины-источника от других вершин добавляются к значениям срединной центральности этой вершины. Ниже этот алгоритм детализирован для ненагруженных графов, заданных с помошью списков смежности L i , i ? I . Как ив алгоритме поискав ширину в нем используется очередь пройденных вершин Q. В стек S вершины помещаются по мере увеличения расстояния от исходной вершины j. Походу вычисления для каждой вершины q определяется число p[q] кратчайших путей изв и список P [q] предшественников на этих путях. Алгоритм BetweenCentrality(G) 1. FOR EACH i ? I DO C B [i] := 0 ; 2. FOR EACH j ? I создать пустой стек S; 4. FOR EACH i ? I DO P [i] := ?; 5. p[j] := 1; d[i] := 0; 6. FOR EACH k ? I, k 6= j DO 7. {p[k] := 0; d[k] := ?1; % k новая" 8. создать пустую очередь ДОБАВИТЬ, j); 10. WHILE Q 6= ? DO 11. { r НАЧАЛО УДАЛИТЬ, r); 12. ВТОЛК(S, r); 13. FOR EACH q ? L r DO 103 14. { IF d(q) < 0; % вершина v q новая" 15. THEN 16. { ДОБАВИТЬ(Q, q); 17. d(q) := d(q) + пометить v как старую кратчайшие пути в q через r 19. IF d(q) = d(r) + 1 THEN 20. { p[q] := p[q] + p[r]; 21. P [q] := P [q] ? {r} 22. } 23. } 24. }; 25. FOR EACH i ? I DO ?[i] := 0; % в S вершины упорядочены по невозрастанию расстояния от v j 26. WHILE S 6= ? DO 27. { k := ВЫТОЛК(S); 28. FOR EACH i ? P [k] DO 28. ?[i] := ?[i] + p[i] p[k] · (1 + ?[k]) ; 29. IF k 6= j THEN C B [k] := C B [k] + Схему этого алгоритма, связанную, с построением и использованием графов кратчайших путей, можно применить также для вычисления других мер центральности Престижность Содержательно, некоторый актор имеет высокий престиж, если на него направлены связи от многих других акторов. Основное отличие престижности от центральности заключается в том, что в определении центральности участвуют выходящие из вершины ребра и расстояния отданной вершины до других, а престижность зависит от входящих в вершину ребер и расстояниях от других вершин до нее. Престижность определяется только для ориентированных графов. Степень престижности P D (i) актора i в социальной сети определяется как P D (i) = d Эта величина принимает значения от 0 до 1. P D (i) = означает, что все акторы сети непосредственно связаны с i. 10.3.1 Средняя престижность (Proximity Эта мера обобщает степень престижности, т.к. учитывает не только соседей актора i, но и всех других акторов, из которых есть пути в i. Область влияния актора i, обозначаемая I i , это множество акторов, из которых можно достичь в социальной сети G. Среднее расстояние от акторов из I i до i определяется как dm(I i , i) = P j?I i d(j, Средняя престижность актора i, обозначаемая определяется как) = |I i | (n ? 1)dm(I i , i) = |I i | 2 (n ? 1) P j?I i d(j, i) 104 Здесь, |I i | n?1 это доля акторов из I, которые могут достичь находится в интервале от 0 до 1. 10.3.2 Ранжированный престиж (Rank Во всех предыдущих мерах считалось, что на престиж данного актора одинаково влияют все ссылающиеся на него акторы. В реальных сетях ссылки более авторитетных акторов должны иметь больший вес, чем менее авторитетных. Ранжированный престиж позволяет оценить престиж актора через престиж его соседей. Ранжированный престиж P R (i) актора i определяется как) = X j?I A ij · здесь A ij это элементы матрицы смежности графа G: A ij = 1 , если (i, j) ? E, и A ij = 0 иначе. Заметим, что значение определено рекурсивно. Пусть P = (P R (i 1 ), . . . , P R (i n )) вектор-столбец ранжированных престижей всех акторов. Тогда P = Решениями этой системы уравнений являются собственные векторы P матрицы Ранжированный престиж используется в алгоритме PageRank, который будет рассмотрен ниже Ранжирование интернет-страниц. Алгоритм Интернет можно рассматривать как очень большую социальную сеть. Хороший метод поискав интерненте должен соединять поиск страниц, которые содержат все или почти все термины из запроса с устойчивым ранжированием, которое передвигает важные высококачественные и надежные страницы к началу списка ответов. Выше мы определили престижность как меру важности интернет-страниц. PageRank. PageRank это процедура вычисления престижа каждой страницы в связанном множестве страниц. Она была впервые предложена основателями компании Google Л. Пейджем (L. Page) и С. Брином (S. Brin) в 1998 г. [23]. Алгоритм PageRank основан на двух содержательных соображениях) ссылка на страницу является признаком престижности этой страницы) чем более престижные страницы ссылаются на данную страницу, тем выше ее собственный престиж. Существует достаточно много определений и вариантов вычисления рейтингов страниц. Здесь мы приведем самое простое определение. Интернет как граф. Мы рассматриваем World Wide Web как граф, вершинами которого являются отдельные страницы (urls) , а гипертекстовые ссылки между страницами играют роль ребер. Более формально,рассмотрим ориентированный граф G W W W = (V, E) . множество V его вершин это список страниц (urls). Ребро (v, w) ? E означает, что в теле страницы v имеется тег , где URL это URL страницы Для страницы i ? V через I(i) обозначим множество всех входящих в нее ребер, те. таких e ? E , что e = (v, i) для некоторой v ? V , а через O(i) множество всех выходящих из i ребер, т.е. таких e ? E, что e = (i, v) для некоторой v ? V . 105 Замечание часто в I(i) и O(i) учитываются только входящие и выходящие ребра из страниц на других сайтах. Интернет-сјрфинг. PageRank моделирует поведение пользователя интернет, водном окне браузера. В частности, PageRank моделирует следующие действия: Обход PageRank: 1. Пользователь начинает обход страниц с некоторой случайно выбранной страницы из V a 2. На каждом шаге пользователь обозревает некоторую страницу i. С вероятностью d ? (0, он выбирает переход по ссылкам, расположенным на этой странице (в предположении, что хоть одна такая ссылка имеется. Любая из ссылок на странице i может быть выбрана с равной вероятностью. С вероятностью 1 ? d пользователь, устав от последовательного обхода страниц, перепрыгивает сразу на случайно выбранную страницу из V . 5. Если из текущей страницы нет ссылок на другие страницы, то пользователь просто переходит на случайно выбранную страницу из V . a на самом деле, PageRank позволяет ослабить это условие и стартовать с некоторой странцы случайно выбранной из некоторого небольшого множества страниц. Что вычисляет PageRank. Ранг, который PageRank присваивает странице i ? V это вероятность достичь в конце концов эту страницу в описанном выше процессе обхода Вывод Пусть p(i) это вероятность достичь страницу i (те, ранг PageRank для страницы Пусть I(i) = {j 1 , . . . j s } множество всех страниц, которые ссылаются на i. Пусть p(j 1 ), . . . , p(j это вероятности достижения каждой из этих страниц. Через O(j обозначим множество всех ребер, выходящих из j Предположение Из каждой страницы в V выходит хоть одно ребро. • Предположим, что мы достигли страницу j 1 . С вероятностью d мы выберем движение по ссылкам. Так как число разных ссылок с равно |O(j 1 )| , то с вероятностью следуем по ссылкам) мы можем достичь страницу i. Так как следуем по ссылкам) = d, то) = d Аналогичные рассуждения справедливы и для остальных страниц j ? I(i). Тогда для k = 1, . . . , s имеем p(i|j k ) = d · 1 |O(j k )| 106 Страницу i можно достичь одним из двух способов. следуя по некоторой ссылке на нее со страниц j 1 , . . . , j s ; 2. случайно выбирая прыжок нас любой текущей страницы. • Отсюда получаем следующую формулу для вычисления вероятности p(i): p(i) = (1 ? d) · 1 |V | + (p(i|j 1 ) · p(j 1 ) + . . . + p(i|j s ) · p(j Подставляя сюда p(i|j k ) , получаем) = (1 ? d) · 1 |V | + d · s X k=1 1 |O j k | · p(j Таким образом) = (1 ? d) · 1 |V | + d · s X k=1 1 |O j k | · pageRank(j Отметим, что это рекурсивное определение. Параметр d называется коэффициентом затухания) и может принимать значения между 0 и 1. В [23] использовалось d = Вычисление рейтинга Из формулы (1) следует, что для вычисления PageRank для некоторой страницы нам требуется знать рейтинги PageRank для всех ее "предков. Стандартный способ организовать такое вычисление состоит в последовательном итерировании. Итеративное вычисление PageRank. Традиционный итеративный алгоритм для вычисления использует следующую процедуру) = 1 |V | for alli ? V (2) pageRank r (i) = (1 ? d) · 1 |V | + d · s X k=1 1 |O j k | · pageRank r?1 (j Остановиться, когда r (i) ? pageRank r?1 (i)) ! < Доказано, что при некоторых условиях на граф (сильная связность и апериодичность эти условия обеспечиваются введением прыжков с любой страницы на любую страницу) эта процедура сходится к некоторым стационарным значениям рейтингов pageRank(i) (главному собственному вектору соответствующей стохастической матрицы. На самом деле, поскольку нас интересуют относительные рейтинги страниц, для определения их порядка сходимость не требуется и процедуру можно прерывать после небольшого числа итераций. В экспериментах авторов алгоритма ([23]) для графа с 322 миллионами ребер алгоритм PageRank сошелся за итерации ? 6 @ @ @ R H H H H H H H H H j H H H H H H j + ) 1 2 3 Рис. 45: Граф сети Рассмотрим сеть G 1 , показанную на рис. 45. В качестве d зафиксируем значение 0.8. Тогда матрица = (1 ? d) ONES |V | + d A T = ? ? ? ? ? ? 0, 04 0, 84 0, 84 0, 84 0, 24 0, 04 0, 04 0, 04 0, 04 0, 24 0, 04 0, 04 0, 04 0, 04 0, 24 0, 04 0, 04 0, 04 0, 04 0, 24 0, 84 0, 04 0, 04 0, 04 0, Начав вычисление рейтингов с равномерного распределения P 0 = (0.2, 0.2, 0.2, 0.2, получаем следующую последовательность значений P r : P 0 P 1 P 2 P 3 P 4 P 5 P 6 P 7 0,2 0,56 0,272 0,3296 0,42176 0,320384 0,357248 0,37641728 0,2 0,08 0,08 0,1376 0,09152 0,100736 0,1154816 0,09926144 0,2 0,08 0,08 0,1376 0,09152 0,100736 0,1154816 0,09926144 0,2 0,08 0,08 0,1376 0,09152 0,100736 0,1154816 0,09926144 0,2 0,2 0,488 0,2576 0,30368 0,377408 0,2963072 Квадрат расстояния между и меньше 0,0021. Поэтому можно использовать для ранжирования страниц ранги, полученные округлением P 7 , те. pageRank(1) = 0, 38; pageRank(2) = pageRank(3) = pageRank(4) = 0, 1; pageRank(5) = 0, 32. 10.5 Обнаружение сообществ (Community Сообщество. Пусть S = {s 1 , . . . , s это множество однотипных объектов. Сообщество это пара C = hT, Gi, в которой T это объединяющая данное сообщество тема, а G ? S это множество членов сообщества. Свойства. Это весьма общее определение сообществ. Алгоритмы для решения разных задач используют разные уточнения этого определения. • Темы. Темы определяют соответствующие сообщества. Можно ожидать, что если для двух сообществ C 1 = hT 1 , G 1 i и C 2 = hT 2 , G 2 i , T 1 = T 2 , то также G 1 = и, следовательно заметим, что обратное неверно. Вполне возможно, что у два разных сообщества образованы из одного итого же множества членов Темы сообществ могут быть самыми различными. Например, какие-то события, хобби, профессиональные интересы и т.д. • Каждый объект может быть членом многих сообществ. • Для некоторых приложений важен также временной аспект. Задача обнаружения сообществ для заданного множества данных, содержащего информацию об объектах, выявить (скрытые) сообщества этих объектов. Для каждого сообщества определить его тему и его членов. Обычно тема представляется набором некоторых ключевых слов Двудольное ядро сообществ, двудольное ядро это полный двудольный граф G = hF, C, Ei, такой что F, C ? S • F ? C = ? , • E = {(f, c)|f ? F, c ? C} , • |F | = i , • |C| = Элементы множества F называются фанами (fans), элементы множества C центрами. На рис. 46 показано (двудольное ядро. Двудольное ядро представляет группу объектов (фанов), которые ссылаются на одно и тоже множество центров. Поэтому двудольное ядро можно рассматривать как ядро некоторого сообщества, состоящего из фанов ядра, тема которого находится среди центров ядра Выявление двудольных ядер Двудольные ядра можно обнаружить, используя следующую процедуру: Вход: Граф G S = hS, E S i , S = {s 1 , . . . , s n } , E ? S Ч S. i, j - размер двудольного ядра. Шаг 1. Сокращение. Множество S уменьшают дважды: Шаг 1.1. Сокращение по степени захода. Удалить все вершины (pages) со степенью захода, превосходящей некоторую большую константу K. (например, K = 50). Причина этого сокращения в том, что страницы, на которые чересчур много ссылок, как правило, принадлежат универсальным сайтам типа Yahoo, Rambler и т.п. и не связаны с определенной темой или сообществом. |