Introduzione all'elaborazione di grafici Spark con GraphFrames

1. Introduzione

L'elaborazione del grafico è utile per molte applicazioni, dai social network alle pubblicità. All'interno di uno scenario di big data, abbiamo bisogno di uno strumento per distribuire il carico di elaborazione.

In questo tutorial, caricheremo ed esploreremo le possibilità dei grafici utilizzando Apache Spark in Java. Per evitare strutture complesse, utilizzeremo un'API per grafici Apache Spark semplice e di alto livello: l'API GraphFrames.

2. Grafici

Prima di tutto, definiamo un grafico e le sue componenti. Un grafico è una struttura dati con bordi e vertici. I bordi trasportano informazioni che rappresentano le relazioni tra i vertici.

I vertici sono punti in uno spazio n- dimensionale e i bordi collegano i vertici in base alle loro relazioni:

Nell'immagine sopra, abbiamo un esempio di social network. Possiamo vedere i vertici rappresentati dalle lettere e i bordi che trasportano il tipo di relazione tra i vertici.

3. Installazione di Maven

Ora, iniziamo il progetto impostando la configurazione di Maven.

Aggiungiamo spark-graphx 2.11, graphframes e 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 

Queste versioni di artefatti supportano Scala 2.11.

Inoltre, accade che GraphFrames non sia in Maven Central. Quindi, aggiungiamo anche il repository Maven necessario:

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

4. Configurazione Spark

Per lavorare con GraphFrames, dovremo scaricare Hadoop e definire la variabile d'ambiente HADOOP_HOME .

Nel caso di Windows come sistema operativo, scaricheremo anche il winutils.exe appropriato nella cartella HADOOP_HOME / bin .

Successivamente, iniziamo il nostro codice creando la configurazione di base:

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

Dovremo anche creare una SparkSession :

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

5. Costruzione del grafico

Ora, siamo tutti pronti per iniziare con il nostro codice principale. Quindi, definiamo le entità per i nostri vertici e bordi e creiamo l' istanza GraphFrame .

Lavoreremo sulle relazioni tra gli utenti da un ipotetico social network.

5.1. Dati

Per prima cosa, per questo esempio, definiamo entrambe le entità come Utente e Relazione :

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 }

Successivamente, definiamo alcune istanze di utente e relazione :

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. Istanza GraphFrame

Ora, per creare e manipolare il nostro grafico delle relazioni, creeremo un'istanza di GraphFrame . Il costruttore GraphFrame si aspetta due istanze di Dataset , la prima che rappresenta i vertici e la seconda, i bordi:

Dataset userDataset = session.createDataFrame(users, User.class); Dataset relationshipDataset = session.createDataFrame(relationships, Relation.class); GraphFrame graph = new GraphFrame(userDataframe, relationshipDataframe);

Alla fine, registreremo i nostri vertici e bordi nella console per vedere come appare:

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. Operatori grafici

Ora che abbiamo un'istanza GraphFrame , vediamo cosa possiamo fare con essa.

6.1. Filtro

GraphFrames ci consente di filtrare bordi e vertici tramite una query.

Successivamente, quindi, filtriamo i vertici in base alla proprietà name su User :

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

Alla console, possiamo vedere il risultato:

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

Inoltre, possiamo filtrare direttamente sul grafico chiamando filterEdges o filterVertices :

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

Ora, poiché abbiamo filtrato i bordi, potremmo ancora avere alcuni vertici isolati. Quindi, chiameremo dropIsolatedVertices ().

Di conseguenza, abbiamo un sottografo, sempre un'istanza GraphFrame , con solo le relazioni che hanno lo stato "Amico":

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

6.2. Gradi

Un altro set di funzionalità interessanti è il set di gradi delle operazioni. Queste operazioni restituiscono il numero di archi incidenti su ogni vertice.

The degrees operation just returns the count of all edges of each vertex. On the other hand, inDegrees counts only incoming edges, and outDegrees counts only outgoing edges.

Let's count the incoming degrees of all vertices in our graph:

graph.inDegrees().show();

As a result, we have a GraphFrame that shows the number of incoming edges to each vertex, excluding those with none:

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

7. Graph Algorithms

GraphFrames also provides popular algorithms ready to use — let's take a look at some of them.

7.1. Page Rank

The Page Rank algorithm weighs the incoming edges to a vertex and transforms it into a score.

The idea is that each incoming edge represents an endorsement and makes the vertex more relevant in the given graph.

For example, in a social network, if a person is followed by various people, he or she will be ranked highly.

Running the page rank algorithm is quite straightforward:

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

To configure this algorithm, we just need to provide:

  • maxIter – the number of iterations of page rank to run – 20 is recommended, too few will decrease the quality, and too many will degrade the performance
  • resetProbability – the random reset probability (alpha) – the lower it is, the bigger the score spread between the winners and losers will be – valid ranges are from 0 to 1. Usually, 0.15 is a good score

The response is a similar GraphFrame, though this time we see an additional column giving the page rank of each vertex:

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

In our graph, Alicia is the most relevant vertex, followed by Martin and John.

7.2. Connected Components

The connected components algorithm finds isolated clusters or isolated sub-graphs. These clusters are sets of connected vertices in a graph where each vertex is reachable from any other vertex in the same set.

We can call the algorithm without any parameters via the connectedComponents() method:

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

The algorithm returns a GraphFrame containing each vertex and the component to which each is connected:

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

Our graph has only one component — this means that we do not have isolated sub-graphs. The component has an auto-generated id, which is 154618822656, in our case.

Although we have one more column here – the component id – our graph is still the same.

7.3. Triangle Counting

Triangle counting is commonly used as community detection and counting in a social network graph. A triangle is a set of three vertices, where each vertex has a relationship to the other two vertices in the triangle.

In a social network community, it's easy to find a considerable number of triangles connected to each other.

We can easily perform a triangle counting directly from our GraphFrame instance:

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

The algorithm also returns a GraphFrame with the number of triangles passing through each vertex.

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

8. Conclusion

Apache Spark is a great tool for computing a relevant amount of data in an optimized and distributed way. And, the GraphFrames library allows us to easily distribute graph operations over Spark.

Come sempre, il codice sorgente completo per l'esempio è disponibile su GitHub.