Вместо вступления: обнаружил, что в сообществе нет статей хоть о каком-либо алгоритме поиска сильно связанных компонент. Посему решил чуток пополнить базу данных Хабра небольшой статьей.
Читать полностью »
Рубрика «графы» - 6
Поиск компонент сильной связности: алгоритм Косарайю
2017-06-29 в 9:02, admin, рубрики: Алгоритмы, графыКод Прюфера
2017-06-28 в 12:01, admin, рубрики: Алгоритмы, графы, деревья, дискретная математика, код прюфера, теория графовДеревья. Кратко напомним
Дерево – частный случай графа. Деревья широко применяются в программировании. Дерево – это связный граф без циклов. Дерево называется помеченным, если каждой вершине соответствует уникальная метка. Обычно это число.
Алгоритмические задачи в биоинформатике. Лекция в Яндексе
2017-05-14 в 11:08, admin, рубрики: overlay, Алгоритмы, белки, биоинформатика, биоинформатические алгоритмы, биология, Блог компании Яндекс, выравнивание, геном, генотип, генотипирование, графы, днк, машинное обучение, нуклеотид, расшифровка днк, сборка геномаМы уже несколько раз упоминали серию мероприятий Data & Science, где специалисты по анализу данных и учёные рассказывают друг другу о своих задачах и ищут способы для взаимодействия. Одна из встреч была посвящена биоинформатике. Это отличный пример отрасли, где есть масса ещё не решённых задач для разработчиков.
Под катом вы найдёте расшифровку лекции Игната Колесниченко — выпускника мехмата МГУ и Школы анализа данных. Сейчас Игнат работает ведущим разработчиком службы технологий распределённых вычислений Яндекса.
Исследование связности в мозге на основе электрофизиологических данных. Лекция в Яндексе
2017-02-04 в 9:55, admin, рубрики: Блог компании Яндекс, графы, Исследования и прогнозы в IT, когерентность, мозг, нейробиология, нейрон, нейронные сети, связность, физика, физический эксперимент, ээгРаз уж идеология нейросетей в IT строилась с оглядкой на реальный прототип, о нем тоже иногда полезно вспомнить. Предлагаем посмотреть или почитать лекцию Ильи Захарова, выпускника кафедры психофизиологии факультета психологии МГУ. Илья объясняет, как можно анализировать сети в мозге, какие данные для этого нужны, какие подводные камни могут возникать при анализе, а главное — что нового позволили узнать подобные исследования.
Под катом — расшифровка и большинство слайдов.
Часть 1. Платформа СППР Универсальные алгоритмы
2016-07-31 в 19:55, admin, рубрики: Delphi, Firebird/Interbase, python, sqlite, Алгоритмы, графы, дизайнер, медицина, навигатор, системы поддержки принятие решений, служба поддержки, сппр, экспертные системыПриветствую, уважаемое сообщество!
Забегая вперед прошу прощения у тех, кто ожидает новизны или революционных идей. Их тут нет. Но есть вполне хорошая прикладная система.
Системы поддержки принятия решений сейчас набирают обороты. Причем я не буду особо останавливаться на перечислении способов реализации. Оговорюсь только об основных свойствах.
Я бы очень упрощенно и обобщенно назвал эти системы вероятностными. То есть они выдают рекомендации с известной долей вероятности используя накопленную и проанализированную статистику. Не скажу что это плохо. Тема BigData и Machine learning нынче в тренде. Так же эти системы работают по принципу черного ящика. Поэтому проверить достоверность работы заложенной модели не всегда можно выявить.Читать полностью »
Создание собственного приложения для обработки графов в Giraph
2016-07-19 в 9:27, admin, рубрики: big data, giraph, java, Алгоритмы, Блог компании Mail.Ru Group, графы, метки: giraph
Be my friend by oosDesign
Перед крупными интернет-компаниями часто встают такие сложные задачи, как обработка больших данных и анализ графов социальных сетей. Помогают в их решении фреймворки, но сперва необходимо проанализировать возможные варианты и выбрать подходящий. В лаборатории при Техносфере Mail.Ru мы изучаем эти вопросы на реальных примерах из проектов Mail.Ru Group (myTarget, Поиск Mail.Ru, Антиспам). Задачи могут быть как сугубо практические, так и с исследовательской составляющей. По мотивам одной из таких задач и появилась эта статья.
Во время сборки и запуска своего первого проекта на Giraph сотрудники лаборатории анализа данных Техносферы Mail.Ru столкнулись с рядом проблем, в связи с чем родилась идея написать краткий туториал, как же собрать и запустить свой первый Giraph-проект.
В этой статье мы расскажем, как создавать свои приложения под фреймворк Giraph, который является надстройкой над популярной системой обработки данных Hadoop.
Читать полностью »
МФТИ запустил онлайн-магистратуру по современной комбинаторике
2016-07-11 в 11:54, admin, рубрики: Блог компании Московский физико-технический институт (МФТИ), графы, комбинаторика, магистратура, МФТИ, современная комбинаторика, Учебный процесс в ITСо следующего года десять студентов смогут обучаться в полноценной магистратуре МФТИ и получить диплом государственного образца, не выходя из дома. Ведущие зарубежные вузы, такие как Гарвард и Стенфорд, уже имеют подобного рода программы, но для России это беспрецедентный образовательный эксперимент. Уверенности в его успехе добавляет уже развитая на Физтехе культура онлайн-обучения, связанная с такими проектами, как курсы на Coursera, НПОО и «Лекторий», запущенных той же командой, которая будет отвечать за онлайн-магистратуру в МФТИ.
Обучение в онлайн-магистратуре будет осуществляться по направлению «Современная комбинаторика». Для преподавания разделов прикладной и фундаментальной математики в новом формате нужны передовые преподаватели. Одним из таких специалистов является Андрей Райгородский — ученый с мировым именем и заведующий кафедрой дискретной математики МФТИ.
Мы расскажем, как будет строиться образовательный процесс!
Читать полностью »
Что такое пространство-время на самом деле?
2016-06-22 в 9:06, admin, рубрики: a new kind of science, nks, Stephen Wolfram, Блог компании Wolfram Research, графы, Занимательные задачки, клеточные автоматы, математика, новый вид науки, общая теория относительности, Профессиональная литература, сети, специальная теория относительности, Стивен Вольфрам, теория струн, эйнштейн
Перевод поста Стивена Вольфрама "What Is Spacetime, Really?".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации.
Примечание: данный пост Стивена Вольфрама неразрывно связан с теорией клеточных автоматов и других смежных понятий, а также с его книгой A New Kind of Science (Новый вид науки), на которую из этой статьи идёт большое количество ссылок. Пост хорошо иллюстрирует применение программирования в научной сфере, в частности, Стивен показывает (код приводится в книге) множество примеров программирования на языке Wolfram Language в области физики, математики, теории вычислимости, дискретных систем и др.
Содержание
Простая теория всего?
Структура данных Вселенной
Пространство как граф
Может быть, нет ничего, кроме пространства
Что есть время?
Формирование сети
Вывод СТО
Вывод ОТО (Общей теории относительности)
Частицы, квантовая механика и прочее
В поисках вселенной
Ок, покажите мне Вселенную
Заниматься физикой или нет — вот в чем вопрос
Что требуется?
Но пришло ли время?
Сто лет назад Альберт Эйнштейн опубликовал общую теорию относительности — блестящую, элегантную теорию, которая пережила целый век и открыла единственный успешный путь к описанию пространства-времени (пространственно-временного континуума).
Есть много различных моментов в теории, указывающих, что общая теория относительности — не последняя точка в истории о пространстве-времени. И в самом деле, пускай мне нравится ОТО как абстрактная теория, однако я пришел к мысли, что она, возможно, на целый век увела нас от пути познания истинной природы пространства и времени.
Я размышлял об устройстве пространства и времени немногим более сорока лет. В начале, будучи молодым физиком-теоретиком, я просто принимал эйнштейновскую математическую постановку задачи специальной и общей теории относительности, а так же занимался некоторой работой в квантовой теории поля, космологии и других областях, основываясь на ней.
Но около 35 лет назад, отчасти вдохновленный своим опытом в технических областях, я начал более детально исследовать фундаментальные вопросы теоретической науки, с чего и начался мой длинный путь выхода за рамки традиционных математических уравнений и использования вместо них вычислений и программ как основных моделей в науке. Вскоре после этого мне довелось выяснить, что даже очень простые программы могут демонстрировать очень сложное поведение, а затем, спустя годы, я обнаружил, что системы любого вида могут быть представлены в терминах этих программ.
Воодушевившись этим успехом, я стал размышлять, может ли это иметь отношение к важнейшему из научных вопросов — физической теории всего.
Во-первых, такой подход казался не слишком перспективным — хотя бы потому, что модели, которые я изучал (клеточные автоматы), казалось, работали так, что это полностью противоречило всему тому, что я знал из физики. Но где-то в 88-м году — в то время, когда вышла первая версия Mathematica, я начал понимать, что если бы я изменил свои представления о пространстве и времени, возможно, это к чему то бы меня привело.
Читать полностью »
Граф цитирования статей Хабрахабра
2016-06-13 в 6:19, admin, рубрики: big data, data mining, визуализация, визуализация данных, графы, математика, наука и искусство, теги всё равно никто не читаетОднажды, мне стало интересно: насколько статьи на Хабре связаны между собой? Поэтому сегодня мы займемся исследованием связности статей, и конечно не только посчитаем численные метрики, но и увидим картину целиком.
(это не просто картинка для привлечения внимания, а граф цитирования статей внутри Хабрахабра, где размер вершин определяется числом входящих рёбер, i.e., "количеством цитат внутри Хабра")
Началось всё с того, что в комментариях к статье про Хабра-граф и карму Tiberius и Loriowar озвучили идею, фактически витающую в воздухе: а почему бы не взглянуть на граф цитирования статьёй внутри самого Хабра?
Вы спрашивали? Мы отвечаем. Для того чтобы рассказ не был размахиванием рук, конкретизируем разбираемые вопросы:
-
Q1: Как выглядит граф цитирования Хабрахабра и какие в нём хабы (hubs and authorities)?
-
Q2: Насколько связным является сообщество (граф цитирования) и какие в нём кластеры?
- Q3: Как изменится граф, если из него убрать самоцитирование?
Под катом трафик. Все картинки кликабельны.
Теория графов в Игре Престолов
2016-06-09 в 7:05, admin, рубрики: c++, valar morghulis, Алгоритмы, анализ данных, графы, Занимательные задачки, игра престолов, песнь льда и пламени, Программирование, теория графов
Недавно, на Geektimes я опубликовал статью, где привёл немного поверхностной статистики из серии книг «Песнь льда и пламени». Но я не стал углубляться в самую интересную часть, в граф социальных связей, ибо тема заслуживает отдельного внимания. В этой статье я продемонстрирую как теория графов может помочь при анализе подобных данных и приведу реализации алгоритмов, которыми я пользовался.
Всем кому интересно, добро пожаловать под кат.
Читать полностью »