Pengantar Pemrosesan Grafik Spark dengan GraphFrames

1. Perkenalan

Pemrosesan grafik berguna untuk banyak aplikasi dari jejaring sosial hingga iklan. Di dalam skenario data besar, kita membutuhkan alat untuk mendistribusikan beban pemrosesan tersebut.

Dalam tutorial ini, kita akan memuat dan mengeksplorasi kemungkinan grafik menggunakan Apache Spark di Java. Untuk menghindari struktur yang kompleks, kita akan menggunakan API grafik Apache Spark tingkat tinggi dan mudah: API GraphFrames.

2. Grafik

Pertama-tama, mari kita tentukan grafik dan komponennya. Grafik adalah struktur data yang memiliki tepi dan simpul. The tepi membawa informasi yang mewakili hubungan antara simpul.

Simpul adalah titik dalam ruang berdimensi - n , dan tepi menghubungkan simpul menurut hubungannya:

Pada gambar di atas, kami memiliki contoh jejaring sosial. Kita dapat melihat simpul-simpul yang diwakili oleh huruf-huruf dan ujung-ujungnya membawa jenis hubungan apa yang ada di antara simpul-simpul tersebut.

3. Pengaturan Maven

Sekarang, mari kita mulai proyek dengan menyiapkan konfigurasi Maven.

Mari tambahkan spark-graphx 2.11, graphframes , dan 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 

Versi artefak ini mendukung Scala 2.11.

Juga, kebetulan GraphFrames tidak ada di Maven Central. Jadi, mari tambahkan repositori Maven yang diperlukan juga:

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

4. Konfigurasi Spark

Untuk bekerja dengan GraphFrames, kita perlu mengunduh Hadoop dan menentukan variabel lingkungan HADOOP_HOME .

Dalam kasus Windows sebagai sistem operasi, kami juga akan mengunduh winutils.exe yang sesuai ke folder HADOOP_HOME / bin .

Selanjutnya, mari kita mulai kode kita dengan membuat konfigurasi dasar:

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

Kami juga perlu membuat SparkSession :

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

5. Konstruksi Grafik

Sekarang, kita siap untuk memulai dengan kode utama kita. Jadi, mari kita definisikan entitas untuk simpul dan tepi kita, dan membuat instance GraphFrame .

Kami akan mengerjakan hubungan antara pengguna dari jaringan sosial hipotetis.

5.1. Data

Pertama, untuk contoh ini, mari kita definisikan kedua entitas sebagai Pengguna dan Hubungan :

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 }

Selanjutnya, mari kita tentukan beberapa contoh User dan 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. Contoh GraphFrame

Sekarang, untuk membuat dan memanipulasi grafik hubungan kita, kita akan membuat instance GraphFrame . The GraphFrame konstruktor mengharapkan dua Dataset contoh, yang pertama mewakili simpul dan kedua, ujung-ujungnya:

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

Akhirnya, kita akan mencatat simpul dan tepi kita di konsol untuk melihat tampilannya:

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. Operator Grafik

Sekarang kita memiliki instance GraphFrame , mari kita lihat apa yang bisa kita lakukan dengannya.

6.1. Saring

GraphFrames memungkinkan kita untuk memfilter edge dan vertices berdasarkan kueri.

Selanjutnya, mari kita filter simpul dengan properti name di User :

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

Di konsol, kita bisa melihat hasilnya:

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

Selain itu, kita dapat langsung memfilter grafik dengan memanggil filterEdges atau filterVertices :

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

Sekarang, karena kita memfilter tepinya, kita mungkin masih memiliki beberapa simpul yang terisolasi. Jadi, kami akan memanggil dropIsolatedVertices ().

Hasilnya, kami memiliki subgraf, masih berupa instance GraphFrame , dengan hanya hubungan yang berstatus "Teman":

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

6.2. Derajat

Set fitur menarik lainnya adalah rangkaian derajat operasi. Operasi ini mengembalikan jumlah sisi yang datang pada setiap simpul.

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.

Seperti biasa, kode sumber lengkap untuk contoh tersedia di GitHub.