Без темы
<<  «Мир открытий» вместе с родителями «Мир «киригами»  >>
«Мир Тесен» по Джону Клайнбергу
«Мир Тесен» по Джону Клайнбергу
Краткое содержание
Краткое содержание
Введение
Введение
Введение(2)
Введение(2)
Эксперимент Стэнли Милграма
Эксперимент Стэнли Милграма
Открытия Милграма
Открытия Милграма
Исследования Пула и Кочена
Исследования Пула и Кочена
Модель Ватса и Строгатца
Модель Ватса и Строгатца
Исследования Джона Клайнберга
Исследования Джона Клайнберга
Открытия Джона Клайнберга
Открытия Джона Клайнберга
Другие работы по теме
Другие работы по теме
Сетевая модель
Сетевая модель
Описание модели
Описание модели
Описание модели(2)
Описание модели(2)
Пример: Сеточная модель
Пример: Сеточная модель
Пример: Сеточная модель (2)
Пример: Сеточная модель (2)
Описание модели(3)
Описание модели(3)
Децентрализованные алгоритмы
Децентрализованные алгоритмы
Децентрализованные алгоритмы
Децентрализованные алгоритмы
Результаты применения модели
Результаты применения модели
Результаты применения модели (2)
Результаты применения модели (2)
Фундаментальное следствие
Фундаментальное следствие
Главные предположения теорем
Главные предположения теорем
Теорема
Теорема
Ожидаемое время
Ожидаемое время
K - мерная сеть
K - мерная сеть
Скорость передачи
Скорость передачи
Сети, поддерживающие эффективный поиск
Сети, поддерживающие эффективный поиск
Иерархическая сетевая модель
Иерархическая сетевая модель
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Естественные интерпретации модели
Естественные интерпретации модели
Полученные результаты
Полученные результаты
Полученные результаты
Полученные результаты
Групповые структуры
Групповые структуры
Индуцированная групповая модель cтепени
Индуцированная групповая модель cтепени
Полученные результаты
Полученные результаты
Выводы
Выводы
Открытые вопросы
Открытые вопросы
Ссылки
Ссылки
Ссылки(2)
Ссылки(2)
Вопросы
Вопросы

Презентация: ««Мир Тесен» по Джону Клайнбергу». Автор: Юрий. Файл: ««Мир Тесен» по Джону Клайнбергу.ppt». Размер zip-архива: 84 КБ.

«Мир Тесен» по Джону Клайнбергу

содержание презентации ««Мир Тесен» по Джону Клайнбергу.ppt»
СлайдТекст
1 «Мир Тесен» по Джону Клайнбергу

«Мир Тесен» по Джону Клайнбергу

Мельников Иван Еремин Юрий

2 Краткое содержание

Краткое содержание

1. Введение 2. История 3. Сетевая модель 4. Сети, поддерживающие эффективный поиск 5. Выводы 6. Открытые вопросы 7. Ссылки

3 Введение

Введение

“Мир тесен” тема анекдотических исследований и фольклора часто бывает, что мы встречаем незнакомца и оказывается, что у нас есть общий знакомый

4 Введение(2)

Введение(2)

Задача поиска информации поведение пользователей web поведение агентов поисковые протоколы (gnutella, freenet)

5 Эксперимент Стэнли Милграма

Эксперимент Стэнли Милграма

проведенный в 1960х, остается одним из самых удачных в понимании проблемы человек из Небраски должен был передать письмо человеку, живущему в Массачусетсе шесть ступеней разделения людей в США

6 Открытия Милграма

Открытия Милграма

Короткие пути в сетях знакомств существуют люди могут находить эти пути, зная только информацию о конечной цели

7 Исследования Пула и Кочена

Исследования Пула и Кочена

случайные сети имеют маленький диаметр если А и Б два индивидуума с общим другом, то скорее всего они сами друзья. НО, очень разветвленная сеть знакомств, не имеет малого диаметра

8 Модель Ватса и Строгатца

Модель Ватса и Строгатца

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

9 Исследования Джона Клайнберга

Исследования Джона Клайнберга

Почему незнакомые люди могут найти, соединяющую их короткую цепь знакомств? Существуют скрытые навигационные ключи, лежащие в социальной сети Децентрализованные алгоритмы

10 Открытия Джона Клайнберга

Открытия Джона Клайнберга

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

11 Другие работы по теме

Другие работы по теме

как индивидуумы выбирают следующего адресата Бернард и Килворф : «обратные эксперименты тесного мира» Вайт – «смерть» цепи Хантер и Шотланд - прохождение цепи по разным социальным категориям людей Альберта, Йонг и Барабаси - способность агентов находить пути

12 Сетевая модель

Сетевая модель

Описание модели Децентрализованные алгоритмы Результаты применения модели k – мерная сеть

13 Описание модели

Описание модели

Квадратная сетка n ? n , {(i; j) : i ? {1; 2; : : : ; n}; j ? {1; 2; : : : ; n}} сетчатое расстояние d((i; j); (k; l)) = |k - i| + |l – j|

14 Описание модели(2)

Описание модели(2)

P >= 1 - локальные контакты q >= 0 - удаленные контакты r >= 0 [d(u; v)]-r- вероятность ребра из u в v [d(u; v)]-r / ?v[d(u; v)]-r - введем такую величину, обратное распределение степени r

15 Пример: Сеточная модель

Пример: Сеточная модель

Двухмерная сетка с n = 6, p = 1, q = 0

16 Пример: Сеточная модель (2)

Пример: Сеточная модель (2)

Контакты узла u при p = 1, q = 2, где v и w – дальние контакты

17 Описание модели(3)

Описание модели(3)

считая p и q фиксированными константами получаем однопараметрическое семейство сетей, зависящее от показателя r r – базовый параметр, измеряющий как широко разветвлена данная сеть при r = 0 получается модель Ватса Строгаца

18 Децентрализованные алгоритмы

Децентрализованные алгоритмы

На каждом шаге держатель сообщения знает: множество локальных контактов местоположение цели на решетке * местоположение и дальние контакты всех узлов, которые были держателями сообщения

19 Децентрализованные алгоритмы

Децентрализованные алгоритмы

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

20 Результаты применения модели

Результаты применения модели

Теорема 1: Существует константа a0, зависящая от p и q, не зависящая от n, такая что при r = 0, ожидаемое время доставки любого децентрализованного алгоритма не меньше a0n2/3

21 Результаты применения модели (2)

Результаты применения модели (2)

Теорема 2: Существует децентрализованный алгоритм А и константа a2, независящая от n, так что при r = 2 и p = q = 1, ожидаемое время доставки не больше a2(log n)2.

22 Фундаментальное следствие

Фундаментальное следствие

Когда дальние контакты создаются процессом, связывающих их определенным образом с геометрией решетки поиск эффективен

23 Главные предположения теорем

Главные предположения теорем

В первой теореме равномерное распределение не позволяет алгоритму использовать скрытые «ключи» геометрии решетки алгоритм A второй теоремы: на каждом шаге держатель сообщения выбирает контакт наиболее близкий к цели в смысле сетчатой метрики

24 Теорема

Теорема

0 <= r < 2 Существует константа ar, зависящая от p, q, r, независимая от n, такая что ожидаемое время доставки любого децентрализованного алгоритма не меньше arn(2-r)/3 r > 2 Существует константа ar, зависящая от p, q, r, независимая от n, такая что ожидаемое время доставки любого децентрализованного алгоритма не меньше arn(r-2)/(r-1)

25 Ожидаемое время

Ожидаемое время

Зависимость ожидаемого времени от коэффициента кластеризации

26 K - мерная сеть

K - мерная сеть

Обобщение результатов алгоритм может строить пути с длиной, полиноминально зависящей от log n, если только r = k

27 Скорость передачи

Скорость передачи

«Скорость передачи» класса сетей минимизация диаметра не то же самое что минимизация ожидаемого времения поиска сеть должна содержать структурные ключи которые могут быть использованы для направления к цели

28 Сети, поддерживающие эффективный поиск

Сети, поддерживающие эффективный поиск

Иерархическая сетевая модель Модель с полилогарифмическим внешним уровнем Модель с постоянным внешним уровнем Групповые структуры

29 Иерархическая сетевая модель

Иерархическая сетевая модель

B - арное дерево T, b = const V – набор листьев из T, n – размер V для v и w, h (v, w) - высота их последнего общего предка в T монотонная невозрастающая функция f(?) - вероятность возникновения связи для v ? V, f(h(v,w))/?x?v f(h(v, x)) число связей к - внешний уровень модели

30 Модель с полилогарифмическим внешним уровнем

Модель с полилогарифмическим внешним уровнем

K = c log2n, где с = const растет асимптотически как

31 Естественные интерпретации модели

Естественные интерпретации модели

WWW иерархия тем (yahoo.Com) science/computer_science/algorithms более вероятно будет связана с science/computer_science/machine_learning, чем с arts/music/opera

32 Полученные результаты

Полученные результаты

Теорема ? иерархическая модель степени ? = 1 с полилогарифмическим внешним уровнем, у которой время поиска децентрализованным алгоритмом оценивается O(log n).

33 Полученные результаты

Полученные результаты

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

34 Групповые структуры

Групповые структуры

Набор узлов V собрание подмножеств V константы ? < 1 и ? > 1: R - группа размером q>= 2, v ? R, ? R? ? R, v ? R? , R? строго меньшая R, |R?| ? ?q R1,R2,R3, . . . – группы, имеющие размер не больше q и содержащие общий узел v, то их объединение имеет размер не больше ?q

35 Индуцированная групповая модель cтепени

Индуцированная групповая модель cтепени

(V, {ri}) q(v, w) - размер наименьшей подгруппы f (?) – монотонная, невозрастающая f (?) растет асимптотически как q-?

36 Полученные результаты

Полученные результаты

Теорема: Для каждой групповой структуры существует индуцированная групповая модель степени ? = 1 с полилогарифмическим внешним уровнем, у которой время поиска децентрализованным алгоритмом оценивается O (log n). Для каждого ? < 1, не существует индуцированной групповой модели степени ? с полилогарифмическим внешним уровнем, у которой децентрализованный алгоритм может достичь полилогарифмическое время поиска.

37 Выводы

Выводы

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

38 Открытые вопросы

Открытые вопросы

Вопрос Фрагно Какие из развивающихся процессов могут сделать поиск по сетям более эффективным? Осознанность узлов-посредников Реконструкция сетей

39 Ссылки

Ссылки

J. Kleinberg. Navigation in a Small World. Nature 406 (2000) J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc 32nd Symposium on Theory of Computing, 2000 J. Kleinberg. Small-world Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS) 14, 2001.

40 Ссылки(2)

Ссылки(2)

J. Kleinberg, P.Raghavan. Query Incentive Networks. Proc 46 th IEEE Symposium of Foundations of Computer Science, 2005. S. Milgram, The small world problem. Psychology Today 1 (1967)/ J. Kleinberg. The small world phenomenon and Decentralized Search, SIAM News, Volume 37, number 3, april 2004 Домашняя страница Джона Клайнберга.

41 Вопросы

Вопросы

Всем спасибо

««Мир Тесен» по Джону Клайнбергу»
http://900igr.net/prezentacija/geografija/mir-tesen-po-dzhonu-klajnbergu-249956.html
cсылка на страницу

Без темы

1126 презентаций
Урок

География

196 тем
Слайды
900igr.net > Презентации по географии > Без темы > «Мир Тесен» по Джону Клайнбергу