- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Мир Тесен по Джону Клайнбергу презентация
Содержание
- 1. Мир Тесен по Джону Клайнбергу
- 2. Краткое содержание 1. Введение 2.
- 3. Введение “Мир тесен” тема анекдотических исследований
- 4. задача поиска информации поведение пользователей Web поведение агентов поисковые протоколы (Gnutella, Freenet) Введение(2)
- 5. Эксперимент Стэнли Милграма проведенный в 1960х,
- 6. короткие пути в сетях знакомств существуют
- 7. Исследования Пула и Кочена случайные сети
- 8. Модель Ватса и Строгатца балансирует между
- 9. Исследования Джона Клайнберга Почему незнакомые люди
- 10. Открытия Джона Клайнберга существующих моделей недостаточно, чтобы
- 11. Другие работы по теме как индивидуумы
- 12. Сетевая модель Описание модели Децентрализованные алгоритмы Результаты применения модели k – мерная сеть
- 13. Описание модели квадратная сетка n ×
- 14. Описание модели(2) p >= 1 - локальные
- 15. Пример: Сеточная модель
- 17. считая p и q фиксированными константами получаем
- 18. Децентрализованные алгоритмы На каждом шаге
- 19. Децентрализованные алгоритмы Ожидаемое время доставки ожидаемое
- 20. Результаты применения модели Теорема 1:
- 21. Теорема 2: Существует децентрализованный алгоритм
- 22. Фундаментальное следствие когда дальние контакты создаются процессом,
- 23. Главные предположения теорем В первой теореме
- 24. 0 2 Существует константа
- 25. Зависимость ожидаемого времени от коэффициента кластеризации Ожидаемое время
- 26. k - мерная сеть обобщение результатов
- 27. Скорость передачи «скорость передачи» класса сетей
- 28. Сети, поддерживающие эффективный поиск Иерархическая сетевая
- 29. Иерархическая сетевая модель b - арное
- 30. k = c log2n, где с =
- 31. Естественные интерпретации модели WWW иерархия тем (yahoo.com)
- 32. Полученные результаты Теорема ∃ иерархическая
- 33. Полученные результаты Теорема(продолжение) ∀ α ≠ 1,
- 34. Групповые структуры набор узлов V собрание
- 35. (V, {Ri}) q(v, w) -
- 36. Полученные результаты Теорема: Для каждой
- 37. Выводы соотношение между локальной структурой и дальними
- 38. Открытые вопросы Вопрос Фрагно Какие из
- 39. Ссылки J. Kleinberg. Navigation in a Small
- 40. Ссылки(2) J. Kleinberg, P.Raghavan. Query Incentive Networks.
- 41. Вопросы? Всем спасибо
Краткое содержание 1. Введение 2. История 3. Сетевая модель 4. Сети, поддерживающие эффективный поиск 5. Выводы 6. Открытые вопросы 7. Ссылки
Слайд 2Краткое содержание
1. Введение
2. История
3. Сетевая модель
4. Сети, поддерживающие эффективный
поиск
5. Выводы
6. Открытые вопросы
7. Ссылки
5. Выводы
6. Открытые вопросы
7. Ссылки
Слайд 3Введение
“Мир тесен”
тема анекдотических исследований и фольклора
часто бывает, что мы встречаем незнакомца
и оказывается, что у нас есть общий знакомый
Слайд 4задача поиска информации
поведение пользователей Web
поведение агентов
поисковые протоколы (Gnutella, Freenet)
Введение(2)
Слайд 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|
сетчатое расстояние
d((i; j); (k; l)) = |k - i| + |l – j|
Слайд 14Описание модели(2)
p >= 1 - локальные контакты
q >= 0 - удаленные
контакты
r >= 0
[d(u; v)]-r- вероятность ребра из u в v
[d(u; v)]-r / ∑v[d(u; v)]-r - введем такую величину, обратное распределение степени r
r >= 0
[d(u; v)]-r- вероятность ребра из u в v
[d(u; v)]-r / ∑v[d(u; v)]-r - введем такую величину, обратное распределение степени r
Слайд 17считая p и q фиксированными константами получаем однопараметрическое семейство сетей, зависящее
от показателя r
r – базовый параметр, измеряющий как широко разветвлена данная сеть
при r = 0 получается модель Ватса Строгаца
r – базовый параметр, измеряющий как широко разветвлена данная сеть
при r = 0 получается модель Ватса Строгаца
Описание модели(3)
Слайд 18Децентрализованные алгоритмы
На каждом шаге держатель сообщения знает:
множество локальных
контактов
местоположение цели на решетке
* местоположение и дальние контакты всех узлов, которые были держателями сообщения
местоположение цели на решетке
* местоположение и дальние контакты всех узлов, которые были держателями сообщения
Слайд 19Децентрализованные алгоритмы
Ожидаемое время доставки
ожидаемое количество шагов по пути
порождаем граф в
соответствии с обратным распределение степени r
начальная и целевая точки выбираются случайно равномерно
начальная и целевая точки выбираются случайно равномерно
Слайд 20Результаты применения модели
Теорема 1:
Существует константа a0, зависящая от
p и q, не зависящая от n, такая что при r = 0, ожидаемое время доставки любого децентрализованного алгоритма не меньше a0n2/3
Слайд 21Теорема 2:
Существует децентрализованный алгоритм А и константа a2, независящая
от n, так что при r = 2 и p = q = 1, ожидаемое время доставки не больше a2(log n)2.
Результаты применения модели (2)
Слайд 22Фундаментальное следствие
когда дальние контакты создаются процессом, связывающих их определенным образом с
геометрией решетки поиск эффективен
Слайд 23Главные предположения теорем
В первой теореме равномерное распределение не позволяет алгоритму
использовать скрытые «ключи» геометрии решетки
алгоритм A второй теоремы: на каждом шаге держатель сообщения выбирает контакт наиболее близкий к цели в смысле сетчатой метрики
алгоритм A второй теоремы: на каждом шаге держатель сообщения выбирает контакт наиболее близкий к цели в смысле сетчатой метрики
Слайд 240
от p, q, r, независимая от n, такая что ожидаемое время доставки любого децентрализованного алгоритма не меньше arn(2-r)/3
r > 2
Существует константа ar, зависящая от p, q, r, независимая от n, такая что ожидаемое время доставки любого децентрализованного алгоритма не меньше arn(r-2)/(r-1)
r > 2
Существует константа ar, зависящая от p, q, r, независимая от n, такая что ожидаемое время доставки любого децентрализованного алгоритма не меньше arn(r-2)/(r-1)
Теорема
Слайд 26k - мерная сеть
обобщение результатов
алгоритм может строить пути с длиной,
полиноминально зависящей от log n, если только
r = k
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))
число связей к - внешний уровень модели
для v и w, h (v, w) - высота их последнего общего предка в T
монотонная невозрастающая функция f(⋅) - вероятность возникновения связи
для v ∈ V, f(h(v,w))/∑x≠v f(h(v, x))
число связей к - внешний уровень модели
Слайд 30k = 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
R - группа размером q>= 2, v ∈ R, ∃ R′ ⊆ R, v ∈ R′ , R′ строго меньшая R, |R′| ≤ λq
R1,R2,R3, . . . – группы, имеющие размер не больше q и содержащие общий узел v, то их объединение имеет размер не больше βq
Слайд 35 (V, {Ri})
q(v, w) - размер наименьшей подгруппы
f (⋅) –
монотонная, невозрастающая
f (⋅) растет асимптотически как q-α
f (⋅) растет асимптотически как q-α
Индуцированная групповая модель cтепени α
Слайд 36Полученные результаты
Теорема:
Для каждой групповой структуры существует индуцированная групповая модель
степени α = 1 с полилогарифмическим внешним уровнем, у которой время поиска децентрализованным алгоритмом оценивается O (log n).
Для каждого α < 1, не существует индуцированной групповой модели степени α с полилогарифмическим внешним уровнем, у которой децентрализованный алгоритм может достичь полилогарифмическое время поиска.
Для каждого α < 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.
J. Kleinberg. Small-world Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS) 14, 2001.
Слайд 40Ссылки(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
Домашняя страница Джона Клайнберга.
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
Домашняя страница Джона Клайнберга.
