Прогноз появления рёбер

Есть такая задача — Link Prediction Problem, на русский язык нет однозначного перевода, но что-то типа «прогнозирование появления/исчезновения рёбер». В статическом варианте проблемы — дан граф (как правило, социальной сети), необходимо предсказать, какие рёбра в нём появятся в ближайшее время (и/или какие удалятся). В динамическом может быть дано несколько графов (в разные моменты времени) и прогноз может потребоваться на разные моменты времени. В варианте с фиксированным тестом — задано множество пар вершин, для которого нужно дать прогноз (например, какие из этих пар станут рёбрами). Из-за того, что чаще рассматривают графы соцсетей, возникает интересная терминология, например, смежные вершины называются друзьями, вершина, смежная с двумя другими вершинами, — их общим другом и т.д.

graph Читать далее

Мой спецсем: анализ твитов и разбиение графа

Спецсеминар для моих студентов и аспирантов будет проходить по средам в 607 ауд. ВМК МГУ, начало в 18:10. Завтра (16.09.2015) будет Читать далее

Спектральная теория графов

Завтра (23 марта) на своём спецсеминаре я сделаю доклад про СТГ (Spectral Graph Theory). Эта теория изучает свойства графов с помощью анализа собственных значений / собственных векторов / характеристических многочленов матриц, которые связаны с графами (матрица сопряжённости, матрица Лапласа, беззнаковая матрица Лапласа и т.п.). Читать далее