Рубрика «графы»

Индексируем миллиарды текстовых векторов - 1

При извлечении информации часто возникает задача поиска подобных фрагментов текста. В контексте поиска запрос может быть сгенерирован пользователем (например, текст, который пользователь вводит в поисковом движке) или самой системой. Часто нам нужно сопоставлять входящий запрос с уже проиндексированными запросами. В этой статье мы рассмотрим, как можно построить систему, решающую эту задачу применительно к миллиардам запросов без траты целого состояния на серверную инфраструктуру.
Читать полностью »

75%

3 из 4 — так Boston Consulting Group оценивает долю IT проектов, почивших по не-техническим причинам.

Уже вот две подряд редакции свода знаний по управлению проектами (PMBOK) выделяют процессы по управлению стейкхолдерами в отдельную область знаний под счастливым номером 13 и настоятельно рекомендуют учитывать:

1. связи между ними,
2. центры влияния, а также
3. культуру общения — для повышения шансов на успех.

Вопрос один:

 доколе инженеры о стейкхолдерах будут судить догадками?

image

ФОТО: Шариф Хамза для Dazed & Confuzed, модель — Люпита Нионго

В свете недавней безоговорочной победы русской математики над вопросом хроматических чисел рассмотрим сценарий применения стремительно набирающей популярность среди занимающихся машинным обучением теории графов к причине провала большинства IT проектов. Приложим вполне естественную науку о вычислениях к областям, ранее считавшимся 'мягкими'. И покажем, как современные модели позволяют организацию в эпоху перемен измерить. Стратегия решения — простая, двухшаговая — строим граф связей стейкхолдеров, а из него — нейросеть сворачиваем. И пока самообучаемые алгоритмы выполняют непростые управленческие задачи, снимая менеджерских проблем ворох с плеч человеческих — пьём кофе с пироженками.

Читать полностью »

Ваш выход, граф: как мы не нашли хороший сетевой граф и создали свой - 1

Расследуя дела, связанные с фишингом, бот-сетями, мошенническими транзакциями и преступными хакерскими группами, эксперты Group-IB уже много лет используют графовый анализ для выявления разного рода связей. В разных кейсах существуют свои массивы данных, свои алгоритмы выявления связей и интерфейсы, заточенные под конкретные задачи. Все эти инструменты являлись внутренней разработкой Group-IB и были доступны только нашим сотрудникам.

Графовый анализ сетевой инфраструктуры (сетевой граф) стал первым внутренним инструментом, который мы встроили во все публичные продукты компании. Прежде чем создавать свой сетевой граф, мы проанализировали многие подобные разработки на рынке и не нашли ни одного продукта, который бы удовлетворял нашим собственным потребностям. В этой статье мы расскажем о том, как мы создавали сетевой граф, как его используем и с какими трудностями столкнулись.

Дмитрий Волков, CTO Group-IB и глава направления киберразведки Читать полностью »

Сколько может рассказать о человеке профиль в соцсети? Фотографии, посты, комментарии, подписки – непаханное поле для анализа. Сегодня поговорим о том, как мы определяем интересы пользователей на основе их подписок в сети Instagram.

image

Источник
Читать полностью »

Многочлены – это не просто упражнения в абстрактных материях. Они прекрасно подходят для выявления структур в неожиданных местах.

Как правильно раскрашивать многочлены - 1

В 2015 году бывший поэт, ставший математиком, Джун Хо помог решить задачу, сформулированную около 50 лет назад. Она была связана со сложными математическими объектами, "матроидами", и графами (комбинациями точек и отрезков). А ещё она была связана с многочленами – знакомыми нам с уроков математики выражениями, состоящими из суммы переменных, возведённых в различные степени.

В какой-то момент в школе вы, наверное, проходили раскрытие скобок у многочленов. К примеру, вы можете помнить, что x2 + 2xy + y2 = (x + y)2. Удобный алгебраический трюк, но где он может пригодиться? Оказывается, что многочлены отлично помогают выявлять скрытые структуры – и в своём доказательстве Хо активно использовал этот факт. Вот простая загадка, иллюстрирующая это.
Читать полностью »

Визуализация больших графов для самых маленьких - 1
Что делать, если вам нужно нарисовать граф, но попавшиеся под руку инструменты рисуют какой-то комок волос или вовсе пожирают всю оперативную память и вешают систему? За последние пару лет работы с большими графами (сотни миллионов вершин и рёбер) я испробовал много инструментов и подходов, и почти не находил достойных обзоров. Поэтому теперь пишу такой обзор сам.
Читать полностью »

AntipovSN and MihhaCF

Часть вторая, в которой Атосу все норм, а вот Графу де ля Фер чего-то не хватает

Вступление от авторов:

Добрый день! Сегодня мы продолжаем цикл статей, посвященный скорингу и использованию в оном теории графов. С первой статьей Вы можете ознакомиться здесь.

Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения

Цель данной статьи: не более, чем за 30 минут, описать основные способы хранения данных о графах и описать правила и принципы построения нашей модели для скоринга заемщика.

Термины и определения:

  • Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Поиск по хеш-таблице, в среднем, осуществляется за время О(1).

Аудиторы, нанятые ПАО «Король» для оценки кредитоспособности НПАО «Один за всех», столкнулись с некоторыми проблемами. С одной стороны, описать схему взаимодействия 10-15 компаний и провести первичную оценку взаимодействия между компаниями очень просто, достаточно иметь под рукой лист бумаги и ручку. Но, что делать, если у вас имеется информация о взаимодействии десятков или сотен тысяч компаний? Например, если Вам нужно описать взаимодействия Арамиса со всеми его пассиями или Д’артаньяна со всеми, с кем он дрался?

Читать полностью »

AntipovSN and MihhaCF

Часть первая, в которой Граф еще не стал Атосом, не встретил Миледи и все у него хорошо

Вступление от авторов:

Добрый день! Сегодня мы начинаем цикл статей, посвященных скорингу и использованию в оном теории графов (Т.Г.). Надеюсь, нам хватит запала, сил и терпения, т.к. тема достаточно объемная и, на наш взгляд, интересная.

Несмотря на шуточное название, мы постараемся затронуть отнюдь не шуточные темы, которые уже сейчас влияют на жизнь многих из нас, а в ближайшем будущем могут коснуться всех, без исключения.

Все шуточные аллегории, вставки и прочее призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения

А теперь к делу.

Цель данной статьи: не более, чем за 30 минут, ввести читателя в проблематику исследования, определить уровень рассмотрения проблемы, описать основную концепцию исследования и познакомить с базовыми терминами.

Термины и определения:

  • Скоринг – система бальной оценки объекта, основанная на численных статистических методах.
  • Граф – способ моделирования связей объектов. Представьте, что Вы с друзьями играете в покер и хотите смоделировать, кто кому сейчас должен. Например, «Д’Артаньян должен Атосу 10 луидоров»

Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора - 1

Полный граф может выглядеть следующим образом:
Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора - 2
Арамис всегда был хитрож… себе на уме, ему должен даже Атос. Портос, пока не встретил госпожу Кокнар, перевязь не мог себе нормальную купить и умудрился задолжать нищеброду Д’артаньяну, хотя, честно говоря, они всю дорогу что-то мутили вместе…

Читать полностью »

Всего три страницы потребовалось российскому математику, чтобы описать способ раскраски сетей определённого типа, превзошедший ожидания экспертов

Российский математик опроверг 53-летнюю гипотезу о раскраске сетей - 1

В опубликованной в онлайне работе опровергается гипотеза 53-летней давности, касающаяся наилучшего способа назначения цветов узлам сети. В работе всего на трёх страничках показано существование способов раскраски определённых цветов, превзошедших все ожидания экспертов.

Задачи по раскраске сетей [см. хроматическое число / прим. перев.], вдохновлённые вопросом такой раскраски карт, при которой соседние страны имеют разные цвета, находятся в фокусе исследований математиков почти 200 лет. Задача состоит в том, чтобы понять, как раскрашивать узлы некоей сети (или графа, как зовут их математики) так, чтобы у любых двух связанных узлов были разные цвета. В зависимости от контекста, эта раскраска может предоставить эффективный способ рассадки гостей на свадьбе, расстановке производственных задач по свободным временным промежуткам, или даже решения судоку.
Читать полностью »

Представим типичную ситуацию на первом курсе: вы прочитали про алгоритм Диница, реализовали, а он не заработал, и вы не знаете, почему. Стандартное решение — это начать отлаживать по шагам, каждый раз рисуя текущее состояние графа на листочке, но это жутко неудобно. Я попробовала исправить положение в рамках семестрового проекта по Software Engineering, а в посте расскажу, как у меня в итоге получился плагин для Visual Studio. Скачать можно тут, исходный код и документацию можно посмотреть тут. Вот скриншот графа, который получился для алгоритма Диница.

Отладка алгоритмов на графах — теперь с картинками - 1Читать полностью »