Social Network Analysis: Spark GraphX

Привіт, хабр!

image

Сьогодні ми детальніше познайомимося з завданнями Аналізу Соціальних Мереж (SNA), а також закінчимо огляд бібліотеки Apache Spark, призначеної для аналізу Великих Даних. А саме, як і було обіцяно в попередніх статтях (раз і два) ми розглянемо одну з компонент Apache Spark, призначену для аналізу графів — GraphX. Постараємося зрозуміти, як в цій бібліотеці реалізовано розподілене зберігання графів та обчислення на них. А також покажемо на конкретних прикладах, як ця бібліотека може використовуватися на практиці: пошук спаму, ранжування пошукової видачі, виділення спільнот в соціальних мережах, пошук лідерів думки — далеко не повний список застосувань методів аналізу графів.

Отже, почнемо з того, що нагадаємо (для тих, хто не занурений в теорію графів) основні об'єкти, з якими ми будемо працювати в цій статті і поринемо в алгоритми і всю красиву математику, яка за цим стоїть.

Теорія графів, випадкові і веб-графи
Напевно, краще всього в цьому розділі відправити читача дивитися чудові відео-лекції та брошури мого наукового керівника Андрія Михайловича Райгородського, наприклад, тут — ніхто краще за нього так зрозуміло і доступно про це не розповість. Дуже рекомендується переглянути також ось або . А ще краще — записатися на курс Андрія Михайловича на Coursera. Тому тут лише дамо основні поняття і не будемо вдаватися в деталі.

Граф — це пара G = (V,E) — де, V — безліч вершин (скажімо, сайти в інтернеті), а E — безліч ребер, що з'єднують вершини (відповідно, посилання між сайтами). Цілком зрозуміла структура, аналізом якою займаються вже багато років. Однак, на практиці при аналізі реальних мереж виникає виникає питання — а як цей граф будується? Скажімо, з'являється новий сайт в інтернеті — на кого він буде засилати в першу чергу, скільки в середньому з'явиться нових посилань, наскільки добре ранжируватиметься цей сайт в пошуковій видачі?

Цим завданням (пристроєм веб-графа) люди займаються майже з моменту появи Інтернету. За цей час було придумано чимало моделей. Не так давно у Яндексі була запропонована узагальнена модель, а також досліджено властивості.

Якщо ж граф нам вже дано — його властивості, а також подальші обчислення на графі цілком визначені. Наприклад, можна досліджувати як себе ступінь конкретної вершини (кількість друзів людини в соціальній мережі), або міряти відстані між конкретними вершинами (через скільки рукостискань знайомі 2 заданих людини в мережі), обчислювати компоненти зв'язності (група людей, де за «зв'язків» між людьми за будь-які 2 людини знайомі) і багато іншого.

Класичними алгоритмами є:

PageRank — відомий алгоритм обчислення «авторитетності» вершини в графі, запропонований Google в 1998 році і довгий час використовується для ранжирування пошукової видачі

Пошук (сильно) зв'язних компонент — алгоритм пошуку підмножин вершин графа таких, що між будь-якими двома вершинами з конкретного підмножини існує шлях, і не існує шляхів між вершинами різних підмножин

Підрахунок найкоротших шляхів у графі — між будь-якою парою вершин, між конкретними двома вершинами, на зважених графах і в інших постановках

А також підрахунок числа трикутників, кластеризація, розподіл ступенів вершин, пошук клік у графі і багато іншого. Варто відзначити, що більшість алгоритмів є итеративными, і тому, в даному контексті дуже добре показує себе бібліотека GraphX зважаючи на те, що кешування даних в оперативній пам'яті. Далі, ми розглянемо, які можливості надає нам дана бібліотека.

Spark GraphX
Відразу відзначимо, що GraphX — далеко не перший і не єдиний інструмент для аналізу графів (відомими інструментами, є, наприклад, GraphLab — нинішній Dato.com або Pregel — на якому GraphX і заснований), а також те, що на момент написання даного поста бібліотека перебувала ще в розробці і можливості її не так великі. Тим не менш, практично для будь-яких завдань, які виникають на практиці своє застосування GraphX так чи інакше виправдовує.

У GraphX поки немає підтримки Python, тому код будемо писати на Scala, припускаючи, що вже створений SparkContext (у коді нижче — змінна sc). Велика частина коду нижче взята з документації і відкритих матеріалів. Отже, для початку завантажимо всі необхідні бібліотеки:

import org.apache.spark.graphx._
import org.apache.spark.rdd.RDD

У спарці концепція графа реалізована у вигляді так званого Property Graph — це мультиграф з мітками (додатковою інформацією) на вершинах і ребрах. Мультиграф — це орієнтований (ребра мають напрямку) граф, в якому можна кратні ребра (може бути декілька ребер між двома вершинами), петлі (ребро з вершини в саму себе). Відразу скажемо, що в разі орієнтованих графів — визначені такі поняття, як входить ступінь (число вхідних ребер) і вихідна ступінь (число вихідних з вершини ребер). Розглянемо на прикладах, як можна побудувати конкретний граф.

Побудова графа

Побудувати граф можна за допомогою конструктора Graph, передавши на вхід масиви вершин і ребер з локальної програми (не забувши зробити з них RDD за допомогою функції .parallelize()):

val vertexArray = Array(
(1L, ("Alice", 28)),
(2L, ("Bob", 27)),
(3L, ("Charlie", 65)),
(4L, ("David", 42)),
(5L, ("Ed", 55)),
(6L, ("Fran", 50))
)
val edgeArray = Array(
Edge(2L, 1L, 7),
Edge(2L, 4L, 2),
Edge(3L, 2L, 4),
Edge(3L, 6Л, 3),
Edge(4L, 1L, 1),
Edge(5L, 2L, 2),
Edge(5L, 3L, 8),
Edge(5L, 6Л, 3)
)

val vertexRDD = sc.parallelize(vertexArray)
val edgeRDD = sc.parallelize(edgeArray)

val graph = Graph(vertexRDD, edgeRDD)

Або, якщо вершини і ребра спочатку необхідно побудувати на основі якихось даних, що лежать, скажімо у HDFS, необхідно спочатку обробити самі вихідні дані (як це часто буває — з допомогою .map() — перетворення). Наприклад, якщо у нас є статті з Вікіпедії, які зберігаються у вигляді (id title), а також посилання між статтями, які зберігаються у вигляді пар, то граф будується досить легко — для цього треба відокремити id title у першому випадку і сконструювати самі ребра (для цього є конструктор Edge) — у другому випадку, на виході отримавши список вершин і ребер, які можна передати конструктору Graph:

val articles = sc.textFile("articles.txt")
val links = sc.textFile("links.txt")

val vertices = articles.map { line =>
val fields = line.split('\t')
(fields(0).toLong, fields(1))
}

val edges = links.map { line =>
val fields = line.split('\t')
Edge(fields(0).toLong, fields(1).toLong, 0)
}

val graph = Graph(vertices, edges, "").cache()

Після побудови графа для нього можна обчислювати деякі характеристики а також запускати на ньому алгоритми, в тому числі і перераховані вище. Поки ми не продовжили, варто відзначити тут, що в спарці крім концепції вершин і ребер реалізовано також поняття триплет (Triplet) — це об'єкт, який у певному сенсі трохи розширює об'єкт ребро (Edge) — у ньому зберігається крім інформації про ребрі також інформація про вершинах, до нього примикають.

Обчислення на графах

Чудовий факт полягає в тому, що в більшості пакетів (і GraphX в цьому не є винятком) — після побудови графа стає легко робити на ньому обчислення, а також запускати стандартні алгоритми. Дійсно, самі по собі методи обчислення на графах вивчені досить добре, і в конкретних прикладних задачах найскладніше — це правило визначити граф, а саме — визначити, що є вершинами, а що — ребрами (на якій підставі їх проводити). Нижче наведемо перелік деяких доступних методів у обьекта Graph з коментарями:

class Graph[VD, ED] {
// Базові статистики графа
val numEdges: Long // кількість ребер
val numVertices: Long // кількість вершин
val inDegrees: VertexRDD[Int] // входять ступеня вершин
val outDegrees: VertexRDD[Int] // вихідні ступеня вершин
val degrees: VertexRDD[Int] // сумарні ступеня вершин

// Окремі подання вершин, ребер і триплетів
val vertices: VertexRDD[VD]
val edges: EdgeRDD[ED]
val triplets: RDD[EdgeTriplet[VD, ED]]

// Зміна атрибутів (додаткової інформації) у вершин і ребер
def mapVertices[VD2](map: (VertexID, VD) => VD2): Graph[VD2, ED]
def mapEdges[ED2](map: Edge[ED] => ED2): Graph[VD, ED2]
def mapEdges[ED2](map: (PartitionID, Iterator[Edge[ED]]) => Iterator[ED2]): Graph[VD, ED2]
def mapTriplets[ED2](map: EdgeTriplet[VD, ED] => ED2): Graph[VD, ED2]

// Модифікації графів
def reverse: Graph[VD, ED] // звернення - всі ребра змінюють напрямок на протилежне
def subgraph(
epred: EdgeTriplet[VD,ED] => Boolean = (x => 'true'),
vpred: (VertexID, VD) => Boolean = ((v, d) => true))
: Graph[VD, ED] // виділення подграфов, що задовольняють певним умовам
def groupEdges(merge: (ED ED) => ED): Graph[VD, ED] // злиття ребер

// Базові алгоритми графові
def pageRank(tol: Double, resetProb: Double = 0.15): Graph[Double, Double] // обчислення PageRank
def connectedComponents(): Graph[VertexID, ED] // пошук компонент зв'язності
def triangleCount(): Graph[Int, ED] // підрахунок числа трикутників
def stronglyConnectedComponents(numIter: Int): Graph[VertexID, ED] // пошук сильних компонент зв'язності
}

Варто відзначити, що в поточна реалізація SparkX містить досить мало реалізованих алгоритмів, тому поки ще залишається актуальним використання перерахованих вище відомих пакетів замість Apache Spark, однак, є впевненість, що GraphX в майбутньому буде суттєво доопрацьований, а завдяки можливості кешування даних в оперативній пам'яті, ймовірно, отримає достатню популярність в графових завданнях. Насамкінець, наведемо приклади практичних завдань, де доводиться застосовувати графові методи.

Практичні завдання

Як було сказано вище — основна проблема в практичних завданнях полягає більше не в тому, щоб запустити складні алгоритми, а саме у правильному визначенні графа, в його правильної попередньої обробки і зведенні задачі до класичної вирішеною. Розглянемо це на прикладах, де залишимо читачеві велику кількість питань для роздумів:

Прогнозування появляения нового ребра (Link Prediction)
Завдання достататочно поширена — дана послідовність ребер, які додаються до граф до якогось моменту. Необхідно передбачити, які ребра з'являться в майбутньому у нашому графі. З точки зору реального життя — ця задача являє собою частину рекомендаційної системи — наприклад, прогнозування зв'язків («дружба») між двома користувачами соц. мережі. У цій задачі фактично треба для кожної пари довільно вибраних вершин передбачити — яка ймовірність того, що між ними в майбутньому буде ребро — тут треба працювати з ознаками та з описом вершин. Наприклад, в якості одного з ознак може бути перетин множин друзів, або міра Жаккарда. Читачеві пропонується подумати над можливими метриками подібності між вершинами і написати свій варіант у коментарях).

Виділення спільнот у соціальних мережах
Завдання, яке важко віднести до якогось конкретного завдань. Найчастіше вона розглядається в контексті задачі «кластеризації на графах». Методів рішення тут маса — від простого виділення компонент зв'язності (алгоритм згадувався вище) при правильно певній підмножині вершин, до послідовного видалення ребер з графа до тих пір, поки не залишиться потрібна компонента. Тут, знову ж таки — дуже важливо спершу розуміти, які саме спільноти ми хочемо виділяти в мережі, тобто спершу попрацювати з описом вершин та ребер, а вже потім думати, як в отриманому подграфе виділяти самі спільноти.

Найкоротші відстані на графах
Це завдання є також класичної та реалізована, наприклад, в тому ж Яндекс.Метро або інших сервісах, які допомагають знайти найкоротші шляхи в деякому графі — будь то граф зв'язків між точками міста або граф знайомств.

Або завдання, з якою легко може зіткнутися, наприклад, стільниковий оператор:

Визначення лідерів думки в мережі
Для просування, скажімо, деякою нової опції, наприклад мобільного інтернеті, з метою оптимізації рекламного бюджету хотілося б виділити людей, які в деякому сенсі оточені увагою з боку. В наших термінах — це вершини графа, що мають велику авторитетність в мережі — тому дана задача при правильному побудові графа зводиться до задачі PageRank.

Отже, ми розглянули типові прикладні задачі аналізу графів, які можуть виникати на практиці, а також один з інструментів, який можна застосовувати для їх вирішення. На цьому ми закінчуємо огляд бібліотеки Apache Spark, та й взагалі огляд інструментів і в майбутньому більше зосередимося на алгоритмах і конкретних завданнях!

Джерело: Хабрахабр

0 коментарів

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