Лаборатория DISLab (ОАО «НИЦЭВТ») совместно с НИВЦ МГУ проводят четвертую ежегодную научно-практическую конференцию по проблемам параллельной обработки больших графов с использованием суперкомпьютерных комплексов и кластерных систем.
Цель конференции — привлечение внимания к тематике задач по суперкомпьютерной обработке графов и предоставление площадки для общения разработчиков технологий суперкомпьютерной обработки графов и разработчиков графовых приложений, обсуждения перспектив данного направления.
Совсем скоро, в рамках данной научно-технической конференции GraphHPC-2017, стартует конкурс GraphHPC, посвященный проблемам параллельной обработки больших графов с использованием суперкомпьютеров. В этот раз участникам предстоит получить самую быструю реализацию задачи Betweenness Centrality (Центральность по посредничеству) в неориентированном графе.
Для реализации задачи участникам предлагаются две категории вычислительных систем:
- Один узел, содержащий в себе 2x CPU Intel Xeon E5-2683v3 и GPU NVIDIA GPU K20x. Возможно использование либо только двух CPU, либо одного GPU, либо все вместе;
- Многоузловой кластер с 36ю вычислительными узлами, объединенными высокоскоростной сетью «Ангара»
К участию в конкурсе приглашаются студенты, аспиранты, молодые ученые и IT-специалисты, для которых GraphHPC может стать реальным шансом заявить о себе перед научным сообществом и ведущими IT-компаниями. На сайте состязания можно ознакомиться с условием задачи и скачать пример реализации, написанной на С++ (который включает в себя шаблон для реализации своего решения, необходимую инфраструктуру для генерации графов, программу для проверки корректности реализованного решения для отладки).
Конкурс будет проводиться с 1 по 27 февраля 2017 года при помощи автоматической системы, которая начнет работать с 1 февраля. Но уже сейчас можно начинать работать над решением. Подведение итогов 2 марта 2017 года на конференции GraphHPC-2017.
Победителей и творчески отличившихся участников ждут ценные призы, а также они смогут выступить на конференции, рассказав о своей реализации задачи. Для студентов предусмотрена отдельная номинация!
Практическое применение анализа графов.
Анализ социальных сетей представляет собой исследование социальных сетей, рассматривающее социальные отношения в терминах теории сетей. Эти термины включают в себя понятие узла (отображает отдельного участника в пределах сети) и связи (отображает такие отношения между индивидами, как дружба, родство, положение в организации, интимные отношения, и т. д.). Эти сети часто описывают в виде социальных сетевых схем, где узлы представлены в виде точек, а связи представлены в виде линий.
Для анализа сетей существует некоторый набор общеизвестных метрик:
Связи
- Гомогенность (Homophily): степень, с которой схожие участники формируют связи между собой в сравнении с несхожими. Схожесть может быть определена по половому признаку, расе, возрасту, роду занятий, достижениям в области учёбы, статусу, ценностям или по другим выделяющимся характеристикам. Понятие гомогенности связано с ассортативностью.
- Множественность (Multiplexity): количество форм, содержащихся в связи. Например, два человека, которые являются друзьями и работают вместе будут иметь множественность, равную 2. Множественность связана с прочностью отношений.
- Обоюдность/Взаимность (Mutuality/Reciprocity): степень, с которой двое участников отвечают друг другу взаимностью в сфере дружеских или других взаимодействий.
- Закрытость сети (Network Closure): мера полноты реляционных триад. Присвоение индивидам степени закрытости сети (то есть тот факт, что их друзья также являются друзьями между собой) называется транзитивностью. Транзитивность является последствием индивидуальной или ситуационной особенности, заключающейся в потребности когнитивной закрытости.
- Соседство (Propinquity): склонность участников иметь больше связей с теми, кто находится ближе с точки зрения географии.
Распределение
- Мост (Bridge): индивид, чьи слабые связи заполняют структурные пробелы, обеспечивая единственное соединение между двумя индивидами или кластерами. Он так же включает в себя кратчайший путь, когда более длинный путь невозможен из-за высокого риска искажения сообщения или невозможности доставки.
- Центральность (Centrality): центральность относится к группе метрик, целью которых является определение «значительности» или «влияния» (в различных значениях) определённого узла (или группы) в сети. Примерами общих методов измерения «центральности» являются определение центральности по посредничеству, центральность по близости, центральности собственного вектора, альфа центральности и центральности по степени.
- Плотность (Density): отношение прямых связей в сети к общему возможному количеству связей.
- Расстояние (Distance): минимальное количество связей, необходимое для соединения двух определённых участников, показанное Стэнли Милгремом в его эксперименте и в теории шести рукопожатий.
- Структурные пробелы (Structural holes): отсутствие связей между двумя частями сети. Поиск и использование структурного пробела может дать предпринимателю конкурентное преимущество. Эта концепция была разработана социологом Рональдом Бертом. Иногда её относят к альтернативной концепции социального капитала.
- Сила связи (Tie Strength): определяется линейной комбинацией времени, эмоциональной интенсивности, близости и взаимности (то есть обоюдности). Сильные связи определяются гомогенностью, родством и транзитивностью, в то время как слабые — мостами.
Сегментация
- Группа определяется как «клика», если каждый индивид в ней напрямую связан с другим индивидом. Группа определяется как «круг общения», если в ней меньше требований к прямому контакту, который может быть не определён.
- Коэффициент кластеризации: мера вероятности, с которой два партнёра одного узла являются приятелями. Высокий коэффициент кластеризации соответствует значительной «кликовости».
- Сплоченность: степень, с которой участники связаны напрямую друг с другом при помощи социальных связей. Структурная сплоченность означает минимальное количество участников, которые, будучи удаленными из группы, развалят группу.
Ссылки:
- Анализ социальных сетей
- Betweenness centrality
- U. Brandes. A Faster Algorithm for Betweenness Centrality. 2001. A Faster Algorithm for Betweenness Centrality (English paper, PDF)
