Без темы
<<  «Мир открытий» вместе с родителями «Мир «киригами»  >>
Пример: Сеточная модель
Пример: Сеточная модель
Пример: Сеточная модель (2)
Пример: Сеточная модель (2)
Ожидаемое время
Ожидаемое время
Ожидаемое время
Ожидаемое время
Ожидаемое время
Ожидаемое время
Ожидаемое время
Ожидаемое время
Иерархическая сетевая модель
Иерархическая сетевая модель
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Модель с полилогарифмическим внешним уровнем
Картинки из презентации ««Мир Тесен» по Джону Клайнбергу» к уроку географии на тему «Без темы»

Автор: Юрий. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока географии, скачайте бесплатно презентацию ««Мир Тесен» по Джону Клайнбергу.ppt» со всеми картинками в zip-архиве размером 84 КБ.

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

содержание презентации ««Мир Тесен» по Джону Клайнбергу.ppt»
Сл Текст Сл Текст
1«Мир Тесен» по Джону Клайнбергу. 23позволяет алгоритму использовать скрытые
Мельников Иван Еремин Юрий. «ключи» геометрии решетки алгоритм A
2Краткое содержание. 1. Введение 2. второй теоремы: на каждом шаге держатель
История 3. Сетевая модель 4. Сети, сообщения выбирает контакт наиболее
поддерживающие эффективный поиск 5. Выводы близкий к цели в смысле сетчатой метрики.
6. Открытые вопросы 7. Ссылки. 24Теорема. 0 <= r < 2 Существует
3Введение. “Мир тесен” тема константа ar, зависящая от p, q, r,
анекдотических исследований и фольклора независимая от n, такая что ожидаемое
часто бывает, что мы встречаем незнакомца время доставки любого децентрализованного
и оказывается, что у нас есть общий алгоритма не меньше arn(2-r)/3 r > 2
знакомый. Существует константа ar, зависящая от p,
4Введение(2). Задача поиска информации q, r, независимая от n, такая что
поведение пользователей web поведение ожидаемое время доставки любого
агентов поисковые протоколы (gnutella, децентрализованного алгоритма не меньше
freenet). arn(r-2)/(r-1).
5Эксперимент Стэнли Милграма. 25Ожидаемое время. Зависимость
проведенный в 1960х, остается одним из ожидаемого времени от коэффициента
самых удачных в понимании проблемы человек кластеризации.
из Небраски должен был передать письмо 26K - мерная сеть. Обобщение результатов
человеку, живущему в Массачусетсе шесть алгоритм может строить пути с длиной,
ступеней разделения людей в США. полиноминально зависящей от log n, если
6Открытия Милграма. Короткие пути в только r = k.
сетях знакомств существуют люди могут 27Скорость передачи. «Скорость передачи»
находить эти пути, зная только информацию класса сетей минимизация диаметра не то же
о конечной цели. самое что минимизация ожидаемого времения
7Исследования Пула и Кочена. случайные поиска сеть должна содержать структурные
сети имеют маленький диаметр если А и Б ключи которые могут быть использованы для
два индивидуума с общим другом, то скорее направления к цели.
всего они сами друзья. НО, очень 28Сети, поддерживающие эффективный
разветвленная сеть знакомств, не имеет поиск. Иерархическая сетевая модель Модель
малого диаметра. с полилогарифмическим внешним уровнем
8Модель Ватса и Строгатца. Балансирует Модель с постоянным внешним уровнем
между ограничениями разветвленности сети Групповые структуры.
знакомств и диаметра сети пример - 29Иерархическая сетевая модель. B -
«сетчатый круг» простая структура, но при арное дерево T, b = const V – набор
этом несколько ребер произведены случайным листьев из T, n – размер V для v и w, h
процессом, который эта структуры не (v, w) - высота их последнего общего
описывает. предка в T монотонная невозрастающая
9Исследования Джона Клайнберга. Почему функция f(?) - вероятность возникновения
незнакомые люди могут найти, соединяющую связи для v ? V, f(h(v,w))/?x?v f(h(v, x))
их короткую цепь знакомств? Существуют число связей к - внешний уровень модели.
скрытые навигационные ключи, лежащие в 30Модель с полилогарифмическим внешним
социальной сети Децентрализованные уровнем. K = c log2n, где с = const растет
алгоритмы. асимптотически как.
10Открытия Джона Клайнберга. 31Естественные интерпретации модели. WWW
существующих моделей недостаточно, чтобы иерархия тем (yahoo.Com)
объяснить успех децентрализованного science/computer_science/algorithms более
алгоритма для одной из моделей класса вероятно будет связана с
обобщенных сетей Ватса и Строгатца science/computer_science/machine_learning,
существует децентрализованный алгоритм, чем с arts/music/opera.
способный находить короткие пути с большой 32Полученные результаты. Теорема ?
вероятностью. существует уникальная модель иерархическая модель степени ? = 1 с
в этом семействе, для которой полилогарифмическим внешним уровнем, у
децентрализованные алгоритмы эффективны. которой время поиска децентрализованным
11Другие работы по теме. как индивидуумы алгоритмом оценивается O(log n).
выбирают следующего адресата Бернард и 33Полученные результаты.
Килворф : «обратные эксперименты тесного Теорема(продолжение) ? ? ? 1, не
мира» Вайт – «смерть» цепи Хантер и существует иерархической модели степени ?
Шотланд - прохождение цепи по разным с полилогарифмическим внешним уровнем, у
социальным категориям людей Альберта, Йонг которой децентрализованный алгоритм может
и Барабаси - способность агентов находить достичь полилогарифмическое время поиска.
пути. 34Групповые структуры. Набор узлов V
12Сетевая модель. Описание модели собрание подмножеств V константы ? < 1
Децентрализованные алгоритмы Результаты и ? > 1: R - группа размером q>= 2,
применения модели k – мерная сеть. v ? R, ? R? ? R, v ? R? , R? строго
13Описание модели. Квадратная сетка n ? меньшая R, |R?| ? ?q R1,R2,R3, . . . –
n , {(i; j) : i ? {1; 2; : : : ; n}; j ? группы, имеющие размер не больше q и
{1; 2; : : : ; n}} сетчатое расстояние содержащие общий узел v, то их объединение
d((i; j); (k; l)) = |k - i| + |l – j|. имеет размер не больше ?q.
14Описание модели(2). P >= 1 - 35Индуцированная групповая модель
локальные контакты q >= 0 - удаленные cтепени ? (V, {ri}) q(v, w) - размер
контакты r >= 0 [d(u; v)]-r- наименьшей подгруппы f (?) – монотонная,
вероятность ребра из u в v [d(u; v)]-r / невозрастающая f (?) растет асимптотически
?v[d(u; v)]-r - введем такую величину, как q-?
обратное распределение степени r. 36Полученные результаты. Теорема: Для
15Пример: Сеточная модель. Двухмерная каждой групповой структуры существует
сетка с n = 6, p = 1, q = 0. индуцированная групповая модель степени ?
16Пример: Сеточная модель (2). Контакты = 1 с полилогарифмическим внешним уровнем,
узла u при p = 1, q = 2, где v и w – у которой время поиска децентрализованным
дальние контакты. алгоритмом оценивается O (log n). Для
17Описание модели(3). считая p и q каждого ? < 1, не существует
фиксированными константами получаем индуцированной групповой модели степени ?
однопараметрическое семейство сетей, с полилогарифмическим внешним уровнем, у
зависящее от показателя r r – базовый которой децентрализованный алгоритм может
параметр, измеряющий как широко достичь полилогарифмическое время поиска.
разветвлена данная сеть при r = 0 37Выводы. Соотношение между локальной
получается модель Ватса Строгаца. структурой и дальними контактами вблизи
18Децентрализованные алгоритмы. На критического порога – появляются «ключи»
каждом шаге держатель сообщения знает: сети. Ниже критического значения эти ключи
множество локальных контактов исчезают в пределе короткие цепи
местоположение цели на решетке * существуют, но индивидуумы,
местоположение и дальние контакты всех дезориентированные в социальных контактах,
узлов, которые были держателями сообщения. не могут их найти.
19Децентрализованные алгоритмы. 38Открытые вопросы. Вопрос Фрагно Какие
Ожидаемое время доставки ожидаемое из развивающихся процессов могут сделать
количество шагов по пути порождаем граф в поиск по сетям более эффективным?
соответствии с обратным распределение Осознанность узлов-посредников
степени r начальная и целевая точки Реконструкция сетей.
выбираются случайно равномерно. 39Ссылки. J. Kleinberg. Navigation in a
20Результаты применения модели. Теорема Small World. Nature 406 (2000) J.
1: Существует константа a0, зависящая от p Kleinberg. The small-world phenomenon: An
и q, не зависящая от n, такая что при r = algorithmic perspective. Proc 32nd
0, ожидаемое время доставки любого Symposium on Theory of Computing, 2000 J.
децентрализованного алгоритма не меньше Kleinberg. Small-world Phenomena and the
a0n2/3. Dynamics of Information. Advances in
21Результаты применения модели (2). Neural Information Processing Systems
Теорема 2: Существует децентрализованный (NIPS) 14, 2001.
алгоритм А и константа a2, независящая от 40Ссылки(2). J. Kleinberg, P.Raghavan.
n, так что при r = 2 и p = q = 1, Query Incentive Networks. Proc 46 th IEEE
ожидаемое время доставки не больше a2(log Symposium of Foundations of Computer
n)2. Science, 2005. S. Milgram, The small world
22Фундаментальное следствие. Когда problem. Psychology Today 1 (1967)/ J.
дальние контакты создаются процессом, Kleinberg. The small world phenomenon and
связывающих их определенным образом с Decentralized Search, SIAM News, Volume
геометрией решетки поиск эффективен. 37, number 3, april 2004 Домашняя страница
23Главные предположения теорем. В первой Джона Клайнберга.
теореме равномерное распределение не 41Вопросы? Всем спасибо.
«Мир Тесен» по Джону Клайнбергу.ppt
http://900igr.net/kartinka/geografija/mir-tesen-po-dzhonu-klajnbergu-249956.html
cсылка на страницу

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

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

«Система мира» - Основные сооружения Майя сохранились до наших дней. Солнце и кометы на старинных изображениях астрономов. История астрономии. Египет находится в центре Земли. Определение положения в открытом море с помощью секстанта. Астрономические представления в Индии. Как и многие другие народы, др.греки представляли себе Землю плоской.

«Мир природы» - Начальная школа. Научить обобщать, систематизировать представления о многообразии природы. Участники: Проблемные вопросы : Окружающий мир Природоведение. Дидактические цели: Формирование представлений о мире растений и животных на Земле. Развитие экологически грамотной личности. Нуждина Т. Д. Энциклопедия для малышей: Чудо – всюду.

«Классификация стран мира» - Назови страны - нефтеэкспортеры. Выдели страны - архипелаги. Япония Франция Австралия Китай. Повторение по теме «Классификация и типология стран мира». Оман Япония Венесуэла Ирак. Фиджи Австралия Новая Зеландия Индия. Выдели приморские страны. Назови островные государства. Алжир Мексика Индия Австралия.

«Путешествия по странам мира» - Самыми недоступными и дорогими остаются Антарктида и Африка. Мир не опаснее России. Все страхи идут изнури – человека пугает все неизвестное. Что делал. Долларов расходов * *) - включая авиаперелеты, без покупок. Мир гораздо дружественнее, чем кажется из России. Намного сильнее. Я ушел весной, 4 апреля 2010 года.

«Проблемы в мире» - Назад. Глобальные проблемы. Проблемы, которые решатся в будущем. Новая модель цивилизации. Прослушав курс «Глобальные проблемы человечества», представить модель будущей цивилизации. Виды важнейших глобальных проблем. Сохранение мира на земле Энергетические и сырьевые Продовольственные Межнациональных отношений Демографическая Отсталости Здоровья.

«Урок мира 1 сентября» - Праздник установлен В 1965 году. 1 октября. 30 сентября. День знаний. С особой торжественностью встречают в школах первоклассников. Сейчас праздник 1 сентября знаменует начало нового учебного года. Мне нужно стараться не опаздывать на уроки. День народного единства. Бегать по лестницам, толкаться и кричать в школе не разрешается.

Без темы

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

География

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