Эмерджентность связана с приближенностью физического описания
Что-то не понял мысль. Вот есть такая известная «эмерджентность» как «дефект масс». — Масса ядра меньше массы образующих его нуклонов. Это следствие приближенности физического описания что ли?
Я неправильно написал, что это мнение «от всех молчунов». Только от той части, которым легче переваривать небольшими кусками. Решение о форме подачи в любом случае за автором.
Уже второй лонгрид на интересную тему. Поскольку комментариев нет, то рискну высказать пожелание от всех молчунов — может быть стоит следующие статьи оформлять более кратко? Выделить одну небольшую проблему и показать её решение. Не мешать все в кучу. Графы, циклы, маршруты — в одну корзину. Затраты, цены, спрос — в другую.
Имхо, не стоило смешивать Стирлинга со Шредингером. Первая «загогулина» ни о чем, а вторая — известная и интересная проблема.
Опять же имхо у Саскинда разложено наиболее чётко и доступно.
Как превратить данные о том, что участники 1, 2, 5 и 23 посетили одно мероприятие, в ребра? Необходимо создать шесть строк и отметить связь каждого участника с каждым: 1 и 2, 1 и 5, 1 и 23, 2 и 5, 2 и 23, 5 и 23
Так вы теряете связи между участниками, которые, например, никогда не ходили на одно и то же мероприятие, но зато всегда ходят с одними и теми же людьми. То есть очевидно, что между ними связь есть.
Поэтому связи считаются иначе. Участники уже связаны с мероприятиями. Эти связи образуют исходный граф. Его особенность в том, что он двудольный. Одна доля — участники, другая — мероприятия. В данном графе узлы одной доли между собой не связаны, что на руку.
На основании данного графа можно построить граф связанности для одной из долей. В статье вы строите граф для участников, но можно было бы посмотреть и на граф связанности мероприятий — они же тоже связаны между собой через участников.
Как построить граф связанности для узлов одной доли? Примерная схема такая.
Используется понятие (резистивных) расстояний. Исходный граф уже задал такие расстояния и при построении графа для доли мы требуем, чтобы все расстояния исходного графа (между участниками, если строим для них) сохранились. То есть мы ищем матрицу смежности для участников на основании матрицы резистивных расстояний между ними.
Слов много, но на деле — все сводится к одной матричной формуле (квадратичная форма). Используется обращение матрицы степеней (здесь — степени мероприятий). В двудольном графе данная матрица диагональна, поэтому ее обращение тривиально.
В полученной матрице смежности связи будут почти между всеми элементами, но можно отфильтровать шум, установив порог значимости для величины связи.
Вы все верно написали. И вообще от вас можно ожидать отдельной статьи с рекомендациями авторам, которая многим бы пригодилась ).
Но я бы все-таки не был так категоричен в «первейшей задаче автора». Между строгой научной статьей и доступной популярной есть еще серая зона «чего-то непонятного». Публикация статей в этой зоне больше нужна самим авторам для того, чтобы разобраться в теме. Если хабр позволяет это делать, то почему бы это не использовать? Публичность заставляет вникать в тему. Это работает, и я этим пользовался. Вполне возможно, что впоследствии автор начнет выдавать более качественное содержание. Ради этого можно и потерпеть ).
С другой стороны, я бы предложил отдельно тегировать такие статьи чем-то вроде «Вести из лабораторий» или «Мастерская», чтобы предупредить читателей.
Я не уверен, что правильно понял ваше замечание. Если вы вслед за автором намекаете на то, что «барицентрических координат требуется больше», то это неверно.
Для определения координат точки на плоскости достаточно двух любых координат. Так как 3-я всегда может быть определена из условия равенства суммы веса всех координат единице. В векторных координатах данное условие выполняется ввиду наличия начала координат. Это точка и ее вес равен 1. Вес самих векторов нулевой.
Опять же само это условие вытекает из-того, что мы заранее предполагаем, что речь идет именно о координатах точки (для вектора вес координат должен быть равен 0). Если же нужно различать точки и векторы (аффинное пространство), то понадобится еще одна координата. Опять же это требование справедливо для любого базиса.
Не люблю критиковать авторов, но все-таки здесь слишком легковесно написано. Пара замечаний для тех, кому важна суть дела:
1. Нет никакого смысла в разделении координат на барицентрические и аффинные. Есть просто разные базисы. Как правило, барицентрическими называют координаты, если базис состоит из одних точек пространства. А если точка всего одна (начало координат), а остальные элементы базиса являются векторами, то типа это привычный аффинный базис. Но могут быть и промежуточные варианты.
Важно лишь, пожалуй, что для определения координат точек пространства в базисе должна быть как минимум одна точка.
2. Из ненужного обособления барицентрических координат следуют их выдуманные недостатки. Нет никаких проблем в определении расстояния между точками. В любых координатах расстояние — это норма вектора. Вектор — это разность точек. Если метрика для базиса задана (скалярные произведения между всеми его элементами), то известны все расстояния в данном базисе.
Ну и т.д.
Пожалуй, ещё надо отметить важное свойство барицентрического базиса — в нем можно оперировать нормой точек, а не только векторов. Это следствие как раз наличия «лишней» координаты.
В целом довольно поверхностная статья, но зато доступна).
Когда вы пишите «вектор», — вы что имеете ввиду? Набор чисел или разность точек аффинного пространства (как вектор трансляции, например)? Барицентрические координаты у вас приведены для точек, а в тексте везде про векторы.
И еще. Как вы объясняете (или интерпретируете) наличие строки из единиц в матрицах аффинных преобразований?
Ну в общем-то и копать глубоко не пришлось. Значения компонент ортоцентра, умноженные на индекс Кирхгофа, отражают сумму компонент всех остовных деревьев, на которые раскладывается данный граф. В свою очередь компоненты деревьев считаются просто: c(i) = 1 — v(i). Здесь v(i) — степень (валентность) i-го узла.
В итоге получаем, что отрицательное значение компоненты какого-либо узла исходного графа означает, что данный узел чаще является точкой сочленения в остовах графа. То есть значения компонент ортоцентра — это статистика валентности по всем возможным конфигурациям деревьев на данном графе.
Нужен контрпример, в котором узлы вершинного покрытия не совпадут с минимальными компонентами ортоцентра.
Насчет вероятности «большого прорыва». Индекс Кирхгофа, например, тоже можно считать перебором всех возможных деревьев графа. А можно тупо определитель минора лапласиана посчитать и не париться ).
Компоненты ортоцентра очевидно связаны с комбинаторикой графа (и индексом Кирхгофа). Но надо чуть глубже тут копнуть.
Прямой расчет координат ортоцентра сводится к обращению лапласиана графа. Надо получить грамиан (можно через матрицу резистивных расстояний), окаймить его единицами (как матрицу Кэли-Менгера) и снова обратить. То есть сложность тут совпадает со сложностью обращения матриц. Но скорее всего должны быть и другие, менее затратные способы.
Я для хабра написал целую серию про подобие пространств симплексов и графов. Получилось не особо, но примерное представление о том, откуда в графах берется ортоцентр, надеюсь, дает. В первой статье, оказывается, я даже указал на связь весов ортоцентра и узлов сочленения графа.
Для простых типов графов существуют конечные формулы расчета компонент ортоцентра (деревья, цепочки, колеса, фаны).
Вот, чтоб понятнее было, — значения координат ортоцентра для графа из статьи:
Daniel -0.219
Bob -0.125
Fedor 0.031
Christos 0.125
Eric 0.344
Gerhard 0.344
Alice 0.500
Видим, что ключевые узлы тут — это Daniel, Bob и Fedor. Если удалять троих, то скорее всего надо удалять данные узлы. Но если удалять можно только двоих, то следует учитывать, что после какого-либо узла веса остальных меняются. После удаления Daniel ключевым узлом становится Fedor и надо удалять именно его (а не Bob):
Fedor -0.5
Bob 0
Christos 0
Alice 0.5
Gerhard 0.5
Eric 0.5
Да, немного посмотрел и похоже, что на основе данных весов как раз и решается задача вершинного покрытия. Как это доказать, пока не знаю, но на простых графах проверяется прямым вычислением.
Считаем координаты ортоцентра, сортируем компоненты по возрастанию, верхние k вершин и будут искомым решением.
Я не вникал в проблему «вершинного покрытия». Но срезонировал на термины «метрика» и «точки сочленения».
Поскольку связный граф обладает «резистивной метрикой», то в нем существует «ортоцентр». Данный центр определяется набором барицентрических координат (весов) вершин графа. Так вот,- точки сочленения графа имеют минимальные веса.
Возможно, это свойство как-то можно использовать в данной задаче.
Я, правда, не интересовался, как считаются данные (ортогональные) веса в графах из тысячи вершин. Возможно, тут сложность еще больше.
Кстати, да. Я в Бержа давно уже не заглядывал, но на начальном этапе тоже пытался разобраться, о чем он там толкует.
В целом все верно у него, только имхо переусложнено. Это следствие того, что он (как и многие другие) не использует явным образом понятие скалярного произведения элементов (привыкли только векторы перемножать). Тут как будто бы слепое пятно у людей. Не матрица Кэли-Менгера является основой, а грамиан. Не расстояния — а скалярные произведения.
Ну а второе ключевое понятие — нуль-вектор. С ним становится понятно, откуда появляется в грамиане окаймление из 1. Ну и в целом аффинная метрическая геометрия становится на твердую основу.
В аффинной геометрии плоскость определяется не 3-мя точками, а 4-мя. В этом ключ к пониманию.
Если вы хотите глубоко копнуть эту тему, то вам надо поднимать ссылки по теме Distance geometry. Народ выяснением условий для правильных дистанций давно интересовался. Одна из ключевых работ для своего времени — «Remarks to Maurice Frechet's Article» (Schoenberg ,1935).
Отрицательность детерминанта полного грамиана — это наиболее простое условие, из которого при желании можно вывести кучу разных других лемм. Скорее всего доказательство есть в какой-нибудь монографии про матрицу евклидовых расстояний.
Было бы круто. Необязательно более простое, достаточно более подробное.
Что-то не понял мысль. Вот есть такая известная «эмерджентность» как «дефект масс». — Масса ядра меньше массы образующих его нуклонов. Это следствие приближенности физического описания что ли?
Опять же имхо у Саскинда разложено наиболее чётко и доступно.
Так вы теряете связи между участниками, которые, например, никогда не ходили на одно и то же мероприятие, но зато всегда ходят с одними и теми же людьми. То есть очевидно, что между ними связь есть.
Поэтому связи считаются иначе. Участники уже связаны с мероприятиями. Эти связи образуют исходный граф. Его особенность в том, что он двудольный. Одна доля — участники, другая — мероприятия. В данном графе узлы одной доли между собой не связаны, что на руку.
На основании данного графа можно построить граф связанности для одной из долей. В статье вы строите граф для участников, но можно было бы посмотреть и на граф связанности мероприятий — они же тоже связаны между собой через участников.
Как построить граф связанности для узлов одной доли? Примерная схема такая.
Используется понятие (резистивных) расстояний. Исходный граф уже задал такие расстояния и при построении графа для доли мы требуем, чтобы все расстояния исходного графа (между участниками, если строим для них) сохранились. То есть мы ищем матрицу смежности для участников на основании матрицы резистивных расстояний между ними.
Слов много, но на деле — все сводится к одной матричной формуле (квадратичная форма). Используется обращение матрицы степеней (здесь — степени мероприятий). В двудольном графе данная матрица диагональна, поэтому ее обращение тривиально.
В полученной матрице смежности связи будут почти между всеми элементами, но можно отфильтровать шум, установив порог значимости для величины связи.
Но я бы все-таки не был так категоричен в «первейшей задаче автора». Между строгой научной статьей и доступной популярной есть еще серая зона «чего-то непонятного». Публикация статей в этой зоне больше нужна самим авторам для того, чтобы разобраться в теме. Если хабр позволяет это делать, то почему бы это не использовать? Публичность заставляет вникать в тему. Это работает, и я этим пользовался. Вполне возможно, что впоследствии автор начнет выдавать более качественное содержание. Ради этого можно и потерпеть ).
С другой стороны, я бы предложил отдельно тегировать такие статьи чем-то вроде «Вести из лабораторий» или «Мастерская», чтобы предупредить читателей.
Для определения координат точки на плоскости достаточно двух любых координат. Так как 3-я всегда может быть определена из условия равенства суммы веса всех координат единице. В векторных координатах данное условие выполняется ввиду наличия начала координат. Это точка и ее вес равен 1. Вес самих векторов нулевой.
Опять же само это условие вытекает из-того, что мы заранее предполагаем, что речь идет именно о координатах точки (для вектора вес координат должен быть равен 0). Если же нужно различать точки и векторы (аффинное пространство), то понадобится еще одна координата. Опять же это требование справедливо для любого базиса.
1. Нет никакого смысла в разделении координат на барицентрические и аффинные. Есть просто разные базисы. Как правило, барицентрическими называют координаты, если базис состоит из одних точек пространства. А если точка всего одна (начало координат), а остальные элементы базиса являются векторами, то типа это привычный аффинный базис. Но могут быть и промежуточные варианты.
Важно лишь, пожалуй, что для определения координат точек пространства в базисе должна быть как минимум одна точка.
2. Из ненужного обособления барицентрических координат следуют их выдуманные недостатки. Нет никаких проблем в определении расстояния между точками. В любых координатах расстояние — это норма вектора. Вектор — это разность точек. Если метрика для базиса задана (скалярные произведения между всеми его элементами), то известны все расстояния в данном базисе.
Ну и т.д.
Пожалуй, ещё надо отметить важное свойство барицентрического базиса — в нем можно оперировать нормой точек, а не только векторов. Это следствие как раз наличия «лишней» координаты.
В целом довольно поверхностная статья, но зато доступна).
И еще. Как вы объясняете (или интерпретируете) наличие строки из единиц в матрицах аффинных преобразований?
В итоге получаем, что отрицательное значение компоненты какого-либо узла исходного графа означает, что данный узел чаще является точкой сочленения в остовах графа. То есть значения компонент ортоцентра — это статистика валентности по всем возможным конфигурациям деревьев на данном графе.
Насчет вероятности «большого прорыва». Индекс Кирхгофа, например, тоже можно считать перебором всех возможных деревьев графа. А можно тупо определитель минора лапласиана посчитать и не париться ).
Компоненты ортоцентра очевидно связаны с комбинаторикой графа (и индексом Кирхгофа). Но надо чуть глубже тут копнуть.
Я для хабра написал целую серию про подобие пространств симплексов и графов. Получилось не особо, но примерное представление о том, откуда в графах берется ортоцентр, надеюсь, дает. В первой статье, оказывается, я даже указал на связь весов ортоцентра и узлов сочленения графа.
Для простых типов графов существуют конечные формулы расчета компонент ортоцентра (деревья, цепочки, колеса, фаны).
Daniel -0.219
Bob -0.125
Fedor 0.031
Christos 0.125
Eric 0.344
Gerhard 0.344
Alice 0.500
Видим, что ключевые узлы тут — это Daniel, Bob и Fedor. Если удалять троих, то скорее всего надо удалять данные узлы. Но если удалять можно только двоих, то следует учитывать, что после какого-либо узла веса остальных меняются. После удаления Daniel ключевым узлом становится Fedor и надо удалять именно его (а не Bob):
Fedor -0.5
Bob 0
Christos 0
Alice 0.5
Gerhard 0.5
Eric 0.5
Считаем координаты ортоцентра, сортируем компоненты по возрастанию, верхние k вершин и будут искомым решением.
Поскольку связный граф обладает «резистивной метрикой», то в нем существует «ортоцентр». Данный центр определяется набором барицентрических координат (весов) вершин графа. Так вот,- точки сочленения графа имеют минимальные веса.
Возможно, это свойство как-то можно использовать в данной задаче.
Я, правда, не интересовался, как считаются данные (ортогональные) веса в графах из тысячи вершин. Возможно, тут сложность еще больше.
В целом все верно у него, только имхо переусложнено. Это следствие того, что он (как и многие другие) не использует явным образом понятие скалярного произведения элементов (привыкли только векторы перемножать). Тут как будто бы слепое пятно у людей. Не матрица Кэли-Менгера является основой, а грамиан. Не расстояния — а скалярные произведения.
Ну а второе ключевое понятие — нуль-вектор. С ним становится понятно, откуда появляется в грамиане окаймление из 1. Ну и в целом аффинная метрическая геометрия становится на твердую основу.
В аффинной геометрии плоскость определяется не 3-мя точками, а 4-мя. В этом ключ к пониманию.
Отрицательность детерминанта полного грамиана — это наиболее простое условие, из которого при желании можно вывести кучу разных других лемм. Скорее всего доказательство есть в какой-нибудь монографии про матрицу евклидовых расстояний.