Рубрики
Без рубрики

Введение в обработку искровых графов с помощью фреймов графов

Узнайте, как применять PageRank, Треугольный подсчет и другие графические операции с Apache Spark и графическими фреймами

Автор оригинала: Norberto Ritzmann.

1. введение

Обработка графиков полезна для многих приложений, от социальных сетей до рекламы. В сценарии больших данных нам нужен инструмент для распределения этой нагрузки на обработку.

В этом уроке мы загрузим и изучим возможности графа с помощью Apache Spark в Java. Чтобы избежать сложных структур, мы будем использовать простой и высокоуровневый API Apache Spark graph: Graph Frame sAPI.

2. Графики

Прежде всего, давайте определим график и его компоненты. Граф-это структура данных, имеющая ребра и вершины. Ребра несут информацию , которая представляет отношения между вершинами.

Вершины являются точками в n -мерном пространстве, а ребра соединяют вершины в соответствии с их отношениями:

На изображении выше у нас есть пример социальной сети. Мы можем видеть вершины, представленные буквами, и ребра, несущие информацию о том, какие отношения существуют между вершинами.

3. Настройка Maven

Теперь давайте начнем проект с настройки конфигурации Maven.

Давайте добавим spark-graphx 2.11 , |/graph frames и spark-sql 2.11 : 


    org.apache.spark
    spark-graphx_2.11
    2.4.4


   graphframes
   graphframes
   0.7.0-spark2.4-s_2.11


   org.apache.spark
   spark-sql_2.11
   2.4.4

Эти версии артефактов поддерживают Scala 2.11.

Кроме того, бывает так, что фреймы графа не находятся в Maven Central. Итак, давайте также добавим необходимый репозиторий Maven:


     
          SparkPackagesRepo
          http://dl.bintray.com/spark-packages/maven

4. Конфигурация искры

Чтобы работать с графическими фреймами, нам нужно загрузить Hadoop и определить переменную окружения HADOOP_HOME .

В случае Windows в качестве операционной системы мы также загрузим соответствующую winutils.exe в папку HADOOP_HOME/bin .

Далее, давайте начнем наш код с создания базовой конфигурации:

SparkConf sparkConf = new SparkConf()
  .setAppName("SparkGraphFrames")
  .setMaster("local[*]");
JavaSparkContext javaSparkContext = new JavaSparkContext(sparkConf);

Нам также нужно будет создать сеанс Spark :

SparkSession session = SparkSession.builder()
  .appName("SparkGraphFrameSample")
  .config("spark.sql.warehouse.dir", "/file:C:/temp")
  .sparkContext(javaSparkContext.sc())
  .master("local[*]")
  .getOrCreate();

5. Построение графика

Теперь мы все готовы начать с нашего основного кода. Итак, давайте определим сущности для наших вершин и ребер и создадим экземпляр Graph Frame .

Мы будем работать над отношениями между пользователями из гипотетической социальной сети.

5.1. Данные

Во-первых, для этого примера давайте определим обе сущности как User и Relationship :

public class User {
    private Long id;
    private String name;
    // constructor, getters and setters
}
 
public class Relationship implements Serializable {
    private String type;
    private String src;
    private String dst;
    private UUID id;

    public Relationship(String type, String src, String dst) {
        this.type = type;
        this.src = src;
        this.dst = dst;
        this.id = UUID.randomUUID();
    }
    // getters and setters
}

Далее давайте определим некоторые экземпляры User и Relationship :

List users = new ArrayList<>();
users.add(new User(1L, "John"));
users.add(new User(2L, "Martin"));
users.add(new User(3L, "Peter"));
users.add(new User(4L, "Alicia"));

List relationships = new ArrayList<>();
relationships.add(new Relationship("Friend", "1", "2"));
relationships.add(new Relationship("Following", "1", "4"));
relationships.add(new Relationship("Friend", "2", "4"));
relationships.add(new Relationship("Relative", "3", "1"));
relationships.add(new Relationship("Relative", "3", "4"));

5.2. Экземпляр графического фрейма

Теперь, чтобы создать и манипулировать нашим графом отношений, мы создадим экземпляр Graph Frame . Конструктор Graph Frame ожидает два экземпляра Dataset , первый из которых представляет вершины, а второй-ребра:

Dataset userDataset = session.createDataFrame(users, User.class);
Dataset relationshipDataset = session.createDataFrame(relationships, Relation.class);

GraphFrame graph = new GraphFrame(userDataframe, relationshipDataframe);

Наконец, мы запишем наши вершины и ребра в консоль, чтобы посмотреть, как это выглядит:

graph.vertices().show();
graph.edges().show();
+---+------+
| id|  name|
+---+------+
|  1|  John|
|  2|Martin|
|  3| Peter|
|  4|Alicia|
+---+------+

+---+--------------------+---+---------+
|dst|                  id|src|     type|
+---+--------------------+---+---------+
|  2|622da83f-fb18-484...|  1|   Friend|
|  4|c6dde409-c89d-490...|  1|Following|
|  4|360d06e1-4e9b-4ec...|  2|   Friend|
|  1|de5e738e-c958-4e0...|  3| Relative|
|  4|d96b045a-6320-4a6...|  3| Relative|
+---+--------------------+---+---------+

6. Операторы графа

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

6.1. Фильтр

Рамки графа позволяют нам фильтровать ребра и вершины по запросу.

Далее, давайте отфильтруем вершины по свойству name на User :

graph.vertices().filter("name = 'Martin'").show();

На консоли мы можем увидеть результат:

+---+------+
| id|  name|
+---+------+
|  2|Martin|
+---+------+

Кроме того, мы можем напрямую фильтровать граф, вызывая ребра фильтра или вершины фильтра :

graph.filterEdges("type = 'Friend'")
  .dropIsolatedVertices().vertices().show();

Теперь, поскольку мы отфильтровали ребра, у нас все еще могут быть некоторые изолированные вершины. Итак, мы вызовем drop Isolated Vertices().

В результате у нас есть подграф, все еще являющийся графическим фреймом экземпляром, только с отношениями, имеющими статус “Друг”.:

+---+------+
| id|  name|
+---+------+
|  1|  John|
|  2|Martin|
|  4|Alicia|
+---+------+

6.2. Градусы

Еще одним интересным набором функций является набор операций degrees . Эти операции возвращают количество ребер инцидента на каждой вершине.

Операция degrees просто возвращает количество всех ребер каждой вершины. С другой стороны, в градусах подсчитывает только входящие ребра, а outDegrees подсчитывает только исходящие ребра.

Давайте подсчитаем входящие степени всех вершин в нашем графе:

graph.inDegrees().show();

В результате у нас есть фрейм графика , который показывает количество входящих ребер в каждую вершину, исключая те, у которых их нет:

+---+--------+
| id|inDegree|
+---+--------+
|  1|       1|
|  4|       3|
|  2|       1|
+---+--------+

7. Графовые алгоритмы

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

7.1. PageRank

Алгоритм PageRank взвешивает входящие ребра в вершину и преобразует их в балл.

Идея заключается в том, что каждое входящее ребро представляет одобрение и делает вершину более релевантной в данном графе.

Например, в социальной сети, если за человеком следят разные люди, он будет высоко оценен.

Запуск алгоритма pagerank довольно прост:

graph.pageRank()
  .maxIter(20)
  .resetProbability(0.15)
  .run()
  .vertices()
  .show();

Чтобы настроить этот алгоритм, нам просто нужно предоставить:

  • MaxIter – количество итераций ранга страницы для запуска – рекомендуется 20, слишком мало снизит качество, а слишком много снизит производительность
  • Вероятность сброса – вероятность случайного сброса (альфа) – чем она ниже, тем больше будет разброс баллов между победителями и проигравшими – допустимые диапазоны от 0 до 1. Обычно 0,15 – это хороший результат

Ответ похож на Фрейм графика, хотя на этот раз мы видим дополнительный столбец, дающий ранг страницы каждой вершины:

+---+------+------------------+
| id|  name|          pagerank|
+---+------+------------------+
|  4|Alicia|1.9393230468864597|
|  3| Peter|0.4848822786454427|
|  1|  John|0.7272991738542318|
|  2|Martin| 0.848495500613866|
+---+------+------------------+

В нашем графике Алисия является наиболее релевантной вершиной, за которой следуют Мартин и Джон.

7.2. Подключенные Компоненты

Алгоритм связанных компонентов находит изолированные кластеры или изолированные подграфы. Эти кластеры представляют собой наборы связанных вершин в графе, где каждая вершина достижима из любой другой вершины в том же наборе.

Мы можем вызвать алгоритм без каких-либо параметров с помощью метода connected Components() :

graph.connectedComponents().run().show();

Алгоритм возвращает Фрейм графа , содержащий каждую вершину и компонент, с которым каждая из них связана:

+---+------+------------+
| id|  name|   component|
+---+------+------------+
|  1|  John|154618822656|
|  2|Martin|154618822656|
|  3| Peter|154618822656|
|  4|Alicia|154618822656|
+---+------+------------+

Наш граф имеет только один компонент — это означает, что у нас нет изолированных подграфов. Компонент имеет автоматически сгенерированный идентификатор, который в нашем случае равен 154618822656.

Хотя у нас здесь есть еще один столбец – идентификатор компонента, наш график все еще остается прежним.

7.3. Подсчет треугольников

Подсчет треугольников обычно используется для обнаружения сообщества и подсчета в графе социальной сети. Треугольник-это набор из трех вершин, где каждая вершина имеет отношение к двум другим вершинам в треугольнике.

В сообществе социальных сетей легко найти значительное количество треугольников, связанных друг с другом.

Мы можем легко выполнить подсчет треугольников непосредственно из нашего Графического фрейма экземпляра:

graph.triangleCount().run().show();

Алгоритм также возвращает Фрейм графика с количеством треугольников, проходящих через каждую вершину.

+-----+---+------+
|count| id|  name|
+-----+---+------+
|    1|  3| Peter|
|    2|  1|  John|
|    2|  4|Alicia|
|    1|  2|Martin|
+-----+---+------+

8. Заключение

Apache Spark-отличный инструмент для вычисления соответствующего объема данных оптимизированным и распределенным способом. Кроме того, библиотека графических фреймов позволяет нам легко распределять операции с графами по Spark .

Как всегда, полный исходный код для примера доступен на GitHub .

Читайте ещё по теме: