MLClass
Компания
32,66
рейтинг
5 марта 2015 в 11:49

Разработка → Social Network Analysis: Spark GraphX

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



Сегодня мы подробно познакомимся с задачами Анализа Социальных Сетей (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 — API которой частично используется в 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, 6L, 3),
  Edge(4L, 1L, 1),
  Edge(5L, 2L, 2),
  Edge(5L, 3L, 8),
  Edge(5L, 6L, 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, да и вообще обзор инструментов и в будущем сосредоточимся больше на алгоритмах и конкретных задачах!
Автор: @akrot
MLClass
рейтинг 32,66
Компания прекратила активность на сайте

Комментарии (23)

  • 0
    (известными инструментами, являются, например, GraphLab — нынешний Dato.com или Pregel — на котором GraphX и основан)

    не верно: Pregel не инструмент, а computational model, потому что существует только в виде white paper. GraphX никак не основан на Pregel. Для pregel в graphx есть один класс обертки, который реализует pregel API, при этом что computational model совсем не pregelевская.
    • 0
      Спасибо!

      >Pregel не инструмент, а computational model
      Да, я это и имел ввиду

      >pregel API, при этом что computational model совсем не pregelевская.
      А можно вот тут поподронее? computational model — тут понятно, что другая, я имел ввиду API как раз — изначально сигнатуры многие из Pregel и брались, но могу ошибаться
      • 0
        Computational model другая, а API действительно прегелевской. не могу сказать за сигнатуры, ибо процесс мапинья google white paper на scala сигнатуры — процесс творческий и насколько они точь в точь, сказать сложно.

        Мне кажется здесь важно понимать и подчеркнуть, что GraphX не может рассматривать как идеальный implementation of pregel по причине того, что он не гарантирует вычислительную модель а значит и свойства pregel. Если внимательно читать Pregel часть graphx то можно увидеть, что он писался 2-3 людьми и использовался в 2 example. Это очень очень очень молодая фигня
        • 0
          Тут конечно со всем соглашусь, это и было отмечено выше. Незнаю, как сейчас, но когда я писал этот мануал — это вообще была некоторая alpha-версия
  • 0
    В индустрии не известно не одного случая использования GraphX для работы с реально большими графами. Чтобы в этом убедиться достаточно просмотреть Spark Summitы за последние 3 года и почитать блог DataBricks(компания коммерциализруящая спарк).

    Более того, конкретно с Pregel оберткой в dev-list существует описание проблемы, что при большом кол-во итерации на больших данных каждая следующая итерация исполняется дольше. Лично мне не удавалось сделать более 100 итераций на 1 гб. Я связываю это с большим кол-вом presist unpersist в pregel обертке, но это на уровне гипотезы.
    • 0
      >В индустрии не известно не одного случая использования GraphX для работы с реально большими графами
      Реально большими — это сколько?

      >Более того, конкретно с Pregel оберткой в dev-list существует описание проблемы, что при большом кол-во итерации на больших данных каждая следующая итерация исполняется дольше
      С этим мы с моей командой столкнулись несколько месяцев назад на практике как раз

      >Лично мне не удавалось сделать более 100 итераций на 1 гб.
      Можно подробнее — про размер графа и что за итерации?

      Вообще, интересно услышать Ваш опыт, т.к. мы много этим занимаемся на реальных примерах (10^6 — 10^8 вершин) — и сложности действительно есть
      • 0
        Сложности решенные или вы в стадии — почему же он делает какждую следующую итерацию дольше?
        • 0
          Мы в стадии, как раз вот это мы и не понимаем. У нас там просто еще есть оверхэд по памяти, с которым боремся
          • 0
            Тот который memoryOverhead параметр? Дай угадаю — у вас Yarn?
          • +1
            Оверхед всегда надо увеличивать дефолтный параметр. Про это есть даже тикет в Spark Jira. Для scala меньше увеличивать для Python сильно больше. И с этим надо смириться))

            А то будешь как одна команда у одного из моих бывших работодателей — выкинули спарк отчасти потому что не смогли найти причину почему он внезапно падает без всяких причин. А ответ оказался в NodeManager логах — yarn прибивал контейнер текущий по памяти.
    • 0
      Здраствуйте, знаете ли вы о опытах связанные с кластеризацией в полном графе с большим количеством данных?
      От 100к вершин? Где задача бы сводилась к semi clustering на основании флагов в вершинах в данный момент?
      • 0
        Вы не могли бы развернуть вопрос — о каких флагах идет речь и как они именно должны использоваться для кластеризации?
        • 0
          Действительно нужно расширить вопрос. Флаги бинарные.

          У нас есть полный или практически полный граф. У каждой вершины и у каждого ребра есть разные свойства. Одним из них является свойство «активен»: вкл/выкл. Уто свойство/флаг активности меняется в зависимости от состояния системы. Мы как бы включаем и выключаем некоторые вершины.

          Задача сводилась бы к тому, чтобы бы относительно быстро можно было получить:
          — С одной сторон view такого графа, где ок. 90% вершин выключены
          — Получить свойства ребер случайно выбранной вершины. Ребра с теми вершинами, которые включены

          Точность не критична. Good enough pricision это ок.
          • 0
            А в чем тут сложность — не очень понятно. И кластеризация тут, кажется, не причем — попробуйте сформулировать еще раз
            • 0
              Это не сложность, скорей вопрос. Куда записывать данные с такой структурой. Что даст 20/80? На выходных думал провести тесты на своем cassandra кластере и на одном mongo сервере. Вот думаю где еще.
              На основании этого под-графа уже нужна будет кластеризация.

              Вопрос по сути о том, был ли кого положительный/негативный опыт с полными графами.
  • 0
    Выделение сообществ в социальных сетях
    Задача, которую сложно отнести к какому-то конкретному задач. Зачастую она рассматривается в контексте задачи «кластеризации на графах». Методов решения тут масса — от простого выделения компонент связности (алгоритм упоминался выше) при правильно определенном подмножестве вершин, до последовательного удаления ребер из графа до тех пор пока не останется нужная компонента. Здесь, опять же — очень важно сперва понимать, какие именно сообщества мы хотим выделять в сети, т.е. сперва поработать с описанием вершин и ребер, а уже потом думать, как в полученном подграфе выделять сами сообщества.


    Занимался я таким в Яндексе для одного проекта на GraphX. Первое что тут надо понимать — что тут речь не о graph clustering, а graph semi-clustering. В Pregel есть описание semi-clustering алгоритма, но для больших групп он должен падать по OOM. Это мое прочтение — информации в инете по практики реализации его совсем нету.

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

    На эту тему есть несколько white paper но они очень теоритические без проверки работы алгоритма на больших данных.

    Я все сделал на pregel модели, с самопальным алгоритмом — разбросать k центров кластеров по крупнейшим группам в вк(соц графф был из ВК) и на каждой итерации красить соседние вершины. А вершины красят дальше. Проверить эффективность не получилось нормально — я принадлежность кластерам использовал как feature set для machine learning и эти кластера не дали дополнительного сигнала. Почему не дали, я не понял, то ли кластеры не так важны, то ли я нашел их плохо, то ли шума много в данных.

    Если кому код понадобитсья — я могу у себя поискать. Он не под NDA, так как я его на выходных по своей инициативе писал
    • 0
      >Первое что тут надо понимать — что тут речь не о graph clustering, а graph semi-clustering
      Смотря что Вы подразумеваете под этими понятиями

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

      • 0
        Я так понимаю речь о социальном графе? Как именно можно переопределить ребра, чтобы поиск компонент связаности make sense?
        • 0
          Вот этого к сожалению, я писать не имею права — это текущая задача на моей работе, по которой комментариев давать не могу. Постараюсь привести пример отвлеченный от контекста задачи: допустим, есть вершины графа, а ребра строятся по принципу сходства между атрибутами вершин (определенным образом вводится метрика — «похожесть» вершин) — так вот можно придумать такую метрику, что граф будет примерно следующий: довольно плотные компоненты с мостами между ними — есть даже визуализация. Тогда тут остается удалить мосты — и будут как раз необходимые компоненты.

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

          • 0
            Кажется что когда есть метрики схожести между вершинами кластеризация по этим метрикам первична, а по графовой состовляющей вторична. Так что это не идеальный пример
            • 0
              Последнее мое предложение в комментарии выше — как раз об этом, да. Лучше примера, который бы был отвлечен от самого контекста задачи, сходу в голову не приходит
      • 0
        semi-clustering — такой вид кластеризации, когда вершина может принадлежать сразу нескольким кластерам. все статьи по кластеризации соц сеточек, которые я читал юзают только этот метод
        • 0
          Это видимо в контексте соц. сетей. В то же время на других графах не всегда кластеризация сразу означает semi-clustering. Ок, кстати, если поделишься ссылками — буду благодарен!

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

Самое читаемое Разработка