streamalism.org

1. Inleiding

Grafiekverwerking is handig voor veel toepassingen, van sociale netwerken tot advertenties. Binnen een big data-scenario hebben we een tool nodig om die verwerkingsbelasting te verdelen.

In deze tutorial zullen we grafiekmogelijkheden laden en verkennen met Apache Spark in Java. Om complexe structuren te vermijden, gebruiken we een eenvoudige en hoogwaardige Apache Spark-grafiek-API: de GraphFrames-API.

2. Grafieken

Laten we eerst een grafiek en zijn componenten definiëren. Een grafiek is een datastructuur met randen en hoekpunten. De randen dragen informatie dat staat voor relaties tussen de hoekpunten.

De hoekpunten zijn punten in een n-dimensionale ruimte en randen verbinden de hoekpunten volgens hun relaties:

In de bovenstaande afbeelding hebben we een voorbeeld van een sociaal netwerk. We kunnen de hoekpunten zien die worden voorgesteld door letters en de randen die aangeven welk soort relatie er is tussen de hoekpunten.

3. Maven-instellingen

Laten we nu het project starten door de Maven-configuratie in te stellen.

Laten we toevoegen spark-graphx 2.11,grafische frames, en 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 

Deze artefactversies ondersteunen Scala 2.11.

Het gebeurt ook zo dat GraphFrames niet in Maven Central staat. Laten we dus ook de benodigde Maven-repository toevoegen:

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

4. Spark-configuratie

Om met GraphFrames te kunnen werken, moeten we Hadoop downloaden en het HADOOP_HOME omgevingsvariabele.

In het geval van Windows als besturingssysteem, zullen we ook het juiste downloaden winutils.exe naar de HADOOP_HOME / bin map.

Laten we vervolgens onze code beginnen door de basisconfiguratie te maken:

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

We zullen ook een SparkSession:

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

5. Grafiekconstructie

Nu zijn we helemaal klaar om te beginnen met onze hoofdcode. Laten we dus de entiteiten voor onze hoekpunten en randen definiëren en de GraphFrame voorbeeld.

We werken aan de relaties tussen gebruikers vanuit een hypothetisch sociaal netwerk.

5.1. Gegevens

Laten we voor dit voorbeeld eerst beide entiteiten definiëren als Gebruiker en Relatie:

openbare klasse Gebruiker {privé Lange id; private String naam; // constructor, getters and setters} public class Relationship implementeert Serializable {private String type; private String src; privé String dst; privé UUID-id; openbare relatie (String type, String src, String dst) {this.type = type; this.src = src; this.dst = dst; this.id = UUID.randomUUID (); } // getters en setters}

Laten we er vervolgens een paar definiëren Gebruiker en Relatie gevallen:

Lijst gebruikers = nieuwe ArrayList (); users.add (nieuwe gebruiker (1L, "John")); users.add (nieuwe gebruiker (2L, "Martin")); users.add (nieuwe gebruiker (3L, "Peter")); users.add (nieuwe gebruiker (4L, "Alicia")); Lijstrelaties = nieuwe ArrayList (); relations.add (nieuwe relatie ("Vriend", "1", "2")); relations.add (nieuwe relatie ("Volgend", "1", "4")); relations.add (nieuwe relatie ("Vriend", "2", "4")); relations.add (nieuwe relatie ("Relatief", "3", "1")); relations.add (nieuwe relatie ("Relatief", "3", "4"));

5.2. GraphFrame Voorbeeld

Nu, om onze grafiek met relaties te maken en te manipuleren, maken we een instantie van GraphFrame. De GraphFrame constructor verwacht er twee Dataset gevallen, waarbij de eerste de hoekpunten vertegenwoordigt en de tweede de randen:

Dataset userDataset = session.createDataFrame (gebruikers, User.class); Dataset relationshipDataset = session.createDataFrame (relaties, Relation.class); GraphFrame graph = nieuw GraphFrame (userDataframe, relationshipDataframe);

Ten slotte loggen we onze hoekpunten en randen in de console om te zien hoe het eruit ziet:

graph.vertices (). show (); graph.edges (). show ();

+ --- + ------ + | id | naam | + --- + ------ + | 1 | John | | 2 | Martin | | 3 | Peter | | 4 | Alicia | + --- + ------ + + --- + -------------------- + --- + -------- - + | dst | id | src | type | + --- + -------------------- + --- + --------- + | 2 | 622da83f-fb18-484 ... | 1 | Vriend | | 4 | c6dde409-c89d-490 ... | 1 | Volgen | | 4 | 360d06e1-4e9b-4ec ... | 2 | Vriend | | 1 | de5e738e-c958-4e0 ... | 3 | Relatief | | 4 | d96b045a-6320-4a6 ... | 3 | Relatief | + --- + -------------------- + --- + --------- +

6. Grafiekoperatoren

Nu we een GraphFrame Laten we bijvoorbeeld eens kijken wat we ermee kunnen doen.

6.1. Filter

GraphFrames stelt ons in staat om randen en hoekpunten te filteren op een query.

Laten we vervolgens de hoekpunten filteren op de naam eigendom op Gebruiker:

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

Op de console kunnen we het resultaat zien:

+ --- + ------ + | id | naam | + --- + ------ + | 2 | Martin | + --- + ------ +

We kunnen ook direct op de grafiek filteren door te bellen filterEdges of filterVertices:

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

Nu we de randen hebben gefilterd, hebben we mogelijk nog enkele geïsoleerde hoekpunten. Dus we bellen dropIsolatedVertices ().

Als resultaat hebben we een subgraaf, nog steeds een GraphFrame bijvoorbeeld met alleen de relaties met de status 'Vriend':

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

6.2. Graden

Een andere interessante functieset is de graden reeks bewerkingen. Deze bewerkingen retourneren het aantal randen dat op elk hoekpunt valt.

De graden operatie retourneert alleen de telling van alle randen van elk hoekpunt. Aan de andere kant, in graden telt alleen inkomende randen, en outDegrees telt alleen uitgaande randen.

Laten we de inkomende graden van alle hoekpunten in onze grafiek tellen:

graph.inDegrees (). show ();

Als gevolg hiervan hebben we een GraphFrame dat toont het aantal binnenkomende randen naar elk hoekpunt, met uitzondering van die zonder:

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

7. Grafiekalgoritmen

GraphFrames biedt ook populaire algoritmen die klaar zijn voor gebruik - laten we er een paar bekijken.

7.1. Paginabeoordeling

Het Page Rank-algoritme weegt de binnenkomende randen naar een hoekpunt en zet deze om in een score.

Het idee is dat elke inkomende rand een goedkeuring vertegenwoordigt en het hoekpunt relevanter maakt in de gegeven grafiek.

Als een persoon bijvoorbeeld in een sociaal netwerk wordt gevolgd door verschillende mensen, zal hij of zij hoog scoren.

Het uitvoeren van het algoritme voor paginarangschikking is vrij eenvoudig:

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

Om dit algoritme te configureren, hoeven we alleen het volgende op te geven:

• maxIter - het aantal iteraties van de paginarangschikking dat moet worden uitgevoerd - 20 wordt aanbevolen, te weinig zullen de kwaliteit verminderen en te veel zullen de prestaties verslechteren
• reset Waarschijnlijkheid - de kans op willekeurige reset (alfa) - hoe lager deze is, hoe groter de scorespreiding tussen de winnaars en verliezers zal zijn - geldige bereiken zijn van 0 tot 1. Gewoonlijk is 0,15 een goede score

Het antwoord is vergelijkbaar GraphFrame, hoewel we deze keer een extra kolom zien met de paginarangschikking van elk hoekpunt:

+ --- + ------ + ------------------ + | id | naam | pagerank | + --- + ------ + ------------------ + | 4 | Alicia | 1.9393230468864597 | | 3 | Peter | 0.4848822786454427 | | 1 | John | 0.7272991738542318 | | 2 | Martin | 0,848495500613866 | + --- + ------ + ------------------ +

In onze grafiek is Alicia het meest relevante hoekpunt, gevolgd door Martin en John.

7.2. Aangesloten componenten

Het algoritme voor verbonden componenten vindt geïsoleerde clusters of geïsoleerde subgrafieken. Deze clusters zijn sets van verbonden hoekpunten in een grafiek waarbij elk hoekpunt bereikbaar is vanaf elk ander hoekpunt in dezelfde set.

We kunnen het algoritme zonder parameters aanroepen via de connectedComponents () methode:

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

Het algoritme retourneert een GraphFrame met elk hoekpunt en het onderdeel waarmee elk is verbonden:

+ --- + ------ + ------------ + | id | naam | onderdeel | + --- + ------ + ------------ + | 1 | John | 154618822656 | | 2 | Martin | 154618822656 | | 3 | Peter | 154618822656 | | 4 | Alicia | 154618822656 | + --- + ------ + ------------ +

Onze grafiek heeft maar één component - dit betekent dat we geen geïsoleerde subgrafieken hebben. De component heeft een automatisch gegenereerde id, in ons geval 154618822656.

Hoewel we hier nog een kolom hebben - de component-id - is onze grafiek nog steeds hetzelfde.

7.3. Driehoeken tellen

Triangle-telling wordt vaak gebruikt als gemeenschapsdetectie en -telling in een grafiek van een sociaal netwerk. Een driehoek is een set van drie hoekpunten, waarbij elk hoekpunt een relatie heeft met de andere twee hoekpunten in de driehoek.

In een sociale netwerkgemeenschap is het gemakkelijk om een ​​aanzienlijk aantal driehoeken te vinden die met elkaar zijn verbonden.

We kunnen eenvoudig een driehoekentelling rechtstreeks vanuit ons uitvoeren GraphFrame voorbeeld:

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

Het algoritme retourneert ook een GraphFrame met het aantal driehoeken dat door elk hoekpunt gaat.

+ ----- + --- + ------ + | tellen | id | naam | + ----- + --- + ------ + | 1 | 3 | Peter | | 2 | 1 | John | | 2 | 4 | Alicia | | 1 | 2 | Martin | + ----- + --- + ------ +

8. Conclusie

Apache Spark is een geweldige tool om een ​​relevante hoeveelheid gegevens op een geoptimaliseerde en gedistribueerde manier te berekenen. En de GraphFrames-bibliotheek stelt ons in staat verdeel grafiekbewerkingen eenvoudig over Spark.

Zoals altijd is de volledige broncode voor het voorbeeld beschikbaar op GitHub.