Конкурс GraphHPC-2017 на найшвидшу реалізацію завдання Betweenness Centrality


Лабораторія DISLab ВАТ «НИЦЭВТ») спільно з НИВЦ МДУ проводять четверту щорічну науково-практичну конференцію з проблем паралельної обробки великих графів з використанням суперкомп'ютерних комплексів і кластерних систем.
Мета конференції — залучення уваги до тематики завдань по суперкомпьютерной обробки графів та надання майданчика для спілкування розробників технологій суперкомпьютерной обробки графів і розробників графових додатків, обговорення перспектив даного напрямку.
Зовсім скоро, в рамках даної науково-технічної конференції GraphHPC-2017, стартує конкурс GraphHPC, присвячений проблемам паралельної обробки великих графів з використанням суперкомп'ютерів. На цей раз учасникам належить отримати найшвидшу реалізацію завдання Betweenness Centrality (Центральність з посередництва) в неориентированном графі.
Для реалізації завдання учасникам пропонуються дві категорії обчислювальних систем:
  • Один вузол, що містить в собі 2x CPU Intel Xeon E5-2683v3 та GPU NVIDIA GPU K20x. Можливе використання тільки двох CPU, або одного GPU, або все разом;
  • Багатовузловий кластер з 36ю обчислювальними вузлами, об'єднаними високошвидкісний мережею «Ангара»
До участі у конкурсі запрошуються студенти, аспіранти, молоді вчені та IT-фахівці, для яких GraphHPC може стати реальним шансом заявити про себе перед науковим співтовариством і провідними ІТ-компаніями. На сайті змагання можна ознайомитися з умовою задачі і завантажити приклад реалізації, написаної на С++ (який включає в себе шаблон для реалізації свого рішення, необхідну інфраструктуру для генерації графів, програму для перевірки коректності реалізованого рішення для налагодження).
Конкурс буде проводитися з 1 по 27 лютого 2017 за допомогою автоматичної системи, яка почне працювати з 1 лютого. Але вже зараз можна починати працювати над вирішенням. Підведення підсумків 2 березня 2017 року на конференції GraphHPC-2017.
Переможців і творчо найбільш активних учасників чекають цінні призи, а також вони зможуть виступити на конференції, розповівши про свою реалізації завдання. Для студентів передбачена окрема номінація!
Практичне застосування аналізу графів.
Аналіз соціальних мереж являє собою дослідження соціальних мереж, що розглядає соціальні відносини у термінах теорії мереж. Ці терміни включають в себе поняття вузла (відображає окремого учасника в межах мережі) та зв'язку (відображає такі відношення між індивідами, як дружба, спорідненість, положення в організації, інтимні стосунки, тощо). Ці мережі часто описують у вигляді соціальних мережевих схем, де вузли представлені у вигляді точок, а зв'язки представлені у вигляді ліній.
Для аналізу мереж існує певний набір загальновідомих показників:
Зв'язку
  • Гомогенність (Homophily): ступінь, з якою схожі учасники формують зв'язки між собою в порівнянні з несхожими. Схожість може бути визначена за ознакою статі, раси, віку, роду занять, досягнень в галузі навчання, статусу, цінностей або за іншим виділяється характеристиками. Поняття гомогенності пов'язано з ассортативностью.

  • Множинність (Multiplexity): кількість форм, що містяться у зв'язку. Наприклад, дві людини, які є друзями і працюють разом будуть мати множинність, що дорівнює 2. Множинність пов'язана з міцністю відносин.

  • Обопільність/Взаємність (Mutuality/Reciprocity): ступінь, з якої двоє учасників відповідають один одному взаємністю у сфері дружніх чи інших взаємодій.

  • Закритість мережі (Network Closure): міра повноти реляційних тріад. Присвоєння індивідам ступеня закритості мережі (тобто той факт, що їх друзі також є друзями між собою) називається транзитивностью. Транзитивність є наслідком індивідуального або ситуаційної особливості, що полягає в потребі когнітивної закритості.

  • Сусідство (Propinquity): схильність учасників мати більше зв'язків з тими, хто знаходиться ближче з точки зору географії.
Розподіл
  • Міст (Bridge): індивід, чиї слабкі зв'язки заповнюють структурні прогалини, забезпечуючи єдине з'єднання між двома індивідами або кластерами. Він так само включає в себе найкоротший шлях, коли більш довгий шлях неможливий з-за високого ризику спотворення повідомлення або неможливості доставки.

  • Центральність (Centrality): центральність відноситься до групи показників, метою яких є визначення «значущості» або «впливу» (у різних значеннях) певного вузла (або групи) в мережі. Прикладами загальних методів вимірювання «центральності» є визначення центральності з посередництва, центральність по близькості, центральності власного вектора, альфа центральності та центральності за ступенем.

  • Щільність (Density): відношення прямих зв'язків у мережі до загального можливій кількості зв'язків.

  • Відстань (Distance): мінімальна кількість зв'язків, необхідне для з'єднання двох певних учасників, показане Стенлі Милгремом в його експерименті і в теорії шести рукостискань.

  • Структурних прогалини (Structural holes): відсутність зв'язків між двома частинами мережі. Пошук і використання структурного пробілу може дати підприємцю конкурентну перевагу. Ця концепція була розроблена соціологом Рональдом Бертом. Іноді його відносять до альтернативної концепції соціального капіталу.

  • Сила зв'язку (Tie Strength): визначається лінійною комбінацією часу, емоційної інтенсивності, близькості і взаємності (тобто принципі взаємності). Сильні зв'язки визначаються гомогенністю, спорідненням і транзитивностью, в той час як слабкі — мостами.
Сегментація
  • Група визначається як «кліка», якщо кожен індивід в ній безпосередньо пов'язаний з іншим індивідом. Група визначається як «коло спілкування», якщо в ній менше вимог до прямого контакту, який може бути не визначений.

  • Коефіцієнт кластеризації: міра ймовірності, з якою два партнера одного вузла є приятелями. Високий коефіцієнт кластеризації відповідає значній «кликовости».

  • Згуртованість: ступінь, з якою учасники безпосередньо пов'язані один з одним за допомогою соціальних зв'язків. Структурна згуртованість означає мінімальну кількість учасників, які, будучи віддаленими з групи, розвалять групу.

Посилання:

  1. Аналіз соціальних мереж
  2. Betweenness centrality
  3. U. Brandes. A Faster Algorithm for Betweenness Centrality. 2001. A Faster Algorithm for Betweenness Centrality (English paper, PDF)
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.