Deenya
будет обход графа на предмет ближайших вершин определенного уровня от случайной вершины на графе. Т.е. ближайшие страницы, связанные с некой случайной страницей
Yurii
В монге есть методы работы с графами
Таймураз
будет обход графа на предмет ближайших вершин определенного уровня от случайной вершины на графе. Т.е. ближайшие страницы, связанные с некой случайной страницей
В реляционках две таблицы- вершины и связи
Вся магия
Deenya
ну а все же, что лучше из этих двух?
Vadim
neo4j
Deenya
я уже сделал прототип на монго, но слышал что она плохо справляется с >миллиона записей
Deenya
Deenya
вот такая радость получилась, но с 20 миллионами вершин браузер не справляется к сожалению, поэтому собираюсь отображать по частям
Дима
Лучше бы просто кластеризовал при выводе
Deenya
подробнее
Дима
Объединение смежных точек
Дима
Можно вплоть до нативных браузерных стримов дооптимизировать, тогда хоть Infinity точек рендери)
Deenya
я собираюсь показывать смежные со страницей страницы. Например в центре страница с 500 ошибкой, а рядом страницы, которые затрагивает эта бага
Deenya
а как их можно кластеризовать? Связность не потеряется?
Deenya
не допираю
Deenya
кластеризовать интересная идея
Artsyom
Только кластеризуют обычно несвязные точки на карте
Deenya
Deenya
если свернуть вот такую страницу с большим с разделом на сайте, то свернутся и все ветки
Дима
Только кластеризуют обычно несвязные точки на карте
Это не принципиально, если у тебя изначально на один пиксель приходится несколько точек
Дима
Но связность конечно слегка усложняет задачу)
Deenya
можно свернуть только прилегающие страницы без подветвей - это облегчит граф. Но я не представляю как это сделать
Таймураз
можно свернуть только прилегающие страницы без подветвей - это облегчит граф. Но я не представляю как это сделать
Отображать граф на матрице, разные участки матрицы хранить в разных в разных базах
Дима
Не, тут принципиальный вопрос, адаптивная деградация типа 😄 Чтобы не держать в памяти трлн узлов, а запрашивая их, в поточном режиме оптимизировать
Дима
Это кстати можно статически предрассчитать, вот тебе и практика с бд будет
Дима
Если на экране нарисован граф на триллион точек, то ad-hoc кластеризация у нас есть по факту)
Дима
Поэтому если не можешь победить - надо возглавить 😄
Александр
есть такой прием при отображении графиков, когда на первом уровне показывпется усредненный график, а при приближении показывается более точный (типа как в google maps, только графики). возможно я сказал это не в тему, но может натолкнет на какие-нибудь мысли
Александр
еще можно на сервере отрендерить на гигантской картинке, а потом разбить на тайлы и отображать как google maps с динамической подгрузкой слоев. для этого даже библиотеки есть - см. пирамиды изображений
Александр
причем можно даже сделать чтобы при наведении на узлы информация показывалась
Deenya
сформулировал для себя хотя бы задачу. Есть лимит в 50к вершин, которые сможет отрендерить браузер. Нужен некий алгоритм, который кластеризует по некому правилу все ноды, что бы вписать весь граф в лимит
Deenya
Дима
Красиво
Deenya
https://habrahabr.ru/company/dca/blog/264811/
Deenya
щас хабру читаю
Deenya
было бы круто такое же получить
Александр
я так понимаю у тебя расстояние между точками ничем не характеризуется, тогда можно попробовать задать матрицу расстояний так, что если связь есть, то расстояние равно 1, если нет, то 0.
Алимжан
Александр
тогда кластер будет в себе объединять несколько твоих точек. толщина линии между такими кластерами - количество связей между входящими в нее точками
Александр
размер кластера - количество входящих в него узлов
Deenya
я могу индексировать глубину вершины внутри ветви в процессе парсинга
Deenya
но горизонтальная глубина между соседними ветвями неизвестна
Александр
что значит глубина?
Deenya
уровень удаленности страницы от корня сайта
Deenya
проблема в том, что сайт - это на самом деле не дерево а сеть
Deenya
а значит ветви могут быть связаны случайным образом
Александр
а значит ветви могут быть связаны случайным образом
случайности не случайны, да простит меня тервер))
Александр
проблема в том, что сайт - это на самом деле не дерево а сеть
поэтому необходимо строить матрицу расстояний из 0 и 1
Deenya
+ надо как-то сказать пользователю что содержится в кластере и по какому принципу он объеденен
Александр
расстояний от чего к чему?
матрица расстояний - это термин из кластеризации. надо как-то задать расстояние между точками, какие из них к кому ближе, а какие дальше. у тебя по идее расстояние равно 1 если есть связь и 0 если связи нет. также за расстояние можно взять степень насколько страницы связаны друг с другом логически.
Александр
хотя, наверное, наоборот, расстояние 0 если связаны и бесконечность если нет
Александр
+ надо как-то сказать пользователю что содержится в кластере и по какому принципу он объеденен
в кластере будут содержаться страницы, между которыми много связей
Michael 🌌
матрица расстояний - это термин из кластеризации. надо как-то задать расстояние между точками, какие из них к кому ближе, а какие дальше. у тебя по идее расстояние равно 1 если есть связь и 0 если связи нет. также за расстояние можно взять степень насколько страницы связаны друг с другом логически.
А разве не кратчайшее число шагов между узлами, если есть путь из одного в другой?
Александр
Michael 🌌
1/0 это скорее матрица связей получается
Александр
математика - всего лишь инструмент для моделирования, как определишь, так и будет
Deenya
а как я определю область для кластеризации?
Deenya
обычно страницы ничем не выделяются, что бы именно вокруг них создать кластер с соседними
Александр
да, как правильно подсказал товарищ расстояния можно попробовать взять как наименьшее число шагов от узла до узла. тогда в один кластер будут попадать разделы сайты, которые часто друг на друга ссылаются. например кластер "биология", "математика", "история" если распарсить википедию
Deenya
то бишь просто кластеризовать вокруг страниц с большим количествои исходящих ссылок?
Александр
да
Александр
то бишь просто кластеризовать вокруг страниц с большим количествои исходящих ссылок?
но тут вопрос к тебе что ты хочешь прлучить
Александр
если кластеризуешь как я написал, то по идее получишь кластеры по количеству взаимосвязей
Deenya
я пока не решил на каком принципе объединять вершины
Александр
я пока не решил на каком принципе объединять вершины
это ключевой вопрос) может там и кластеризация не нужна
Deenya
тогда вопрос как определить у каждой страницы количество исходящих ссылок
Александр
а для чего?
Deenya
что бы определить кластер это или не кластер
Александр
количество исходящих ссылок - количество страниц, на которые можно с нее попасть
Deenya
это же перебор всего графа
Александр
кластер - это объединение точек. как их объединять решать тебе в зависимости от цели
Deenya
цель - не дать браузеру зависнуть
Александр
в плане отображения что хочешь получииь?
Александр
что я как пользователь смогу для себя понять из графа?
Александр
от этого и отталкиваться надо
Anonymous
пасаны, а вы че юзаете, express или koa?
倫太郎