Introduktion til gnistgrafbehandling med GraphFrames

1. Introduktion

Grafbehandling er nyttig til mange applikationer fra sociale netværk til reklamer. Inde i et big data-scenario har vi brug for et værktøj til at distribuere denne behandlingsbelastning.

I denne vejledning indlæser og udforsker vi grafmuligheder ved hjælp af Apache Spark i Java. For at undgå komplekse strukturer bruger vi et let og højt niveau Apache Spark graph API: GraphFrames API.

2. Grafer

Lad os først definere en graf og dens komponenter. En graf er en datastruktur med kanter og hjørner. Det kanter bærer information der repræsenterer forholdet mellem hjørnerne.

Hjørnerne er punkter i et n-dimensionelt rum og kanter forbinder hjørnerne i henhold til deres forhold:

På billedet ovenfor har vi et eksempel på et socialt netværk. Vi kan se hjørnerne repræsenteret af bogstaver og kanterne, der bærer hvilken slags forhold der er mellem hjørnerne.

3. Maven-opsætning

Lad os nu starte projektet ved at konfigurere Maven-konfigurationen.

Lad os tilføje spark-graphx 2.11,graframmerog gnist-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 

Disse artefaktversioner understøtter Scala 2.11.

Det sker også, at GraphFrames ikke er i Maven Central. Så lad os også tilføje det nødvendige Maven-arkiv:

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

4. Gnistkonfiguration

For at arbejde med GraphFrames skal vi downloade Hadoop og definere HADOOP_HOME miljøvariabel.

I tilfælde af Windows som operativsystem downloader vi også det relevante winutils.exe til HADOOP_HOME / bin folder.

Lad os derefter starte vores kode ved at oprette den grundlæggende konfiguration:

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

Vi bliver også nødt til at oprette en SparkSession:

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

5. Grafkonstruktion

Nu er vi klar til at starte med vores hovedkode. Så lad os definere enhederne for vores hjørner og kanter og oprette GraphFrame eksempel.

Vi arbejder på forholdet mellem brugere fra et hypotetisk socialt netværk.

5.1. Data

Lad os først definere begge enheder i dette eksempel Bruger og Forhold:

offentlig klasse bruger {privat Lang id; privat strengnavn; // constructor, getters and setters} public class Relationsværktøjer Serialiserbare {private String type; private String src; private String dst; privat UUID-id; public Relationship (String type, String src, String dst) {this.type = type; this.src = src; this.dst = dst; this.id = UUID.randomUUID (); } // getters og setters}

Lad os derefter definere nogle Bruger og Forhold tilfælde:

Listebrugere = ny ArrayList (); users.add (ny bruger (1L, "John")); users.add (ny bruger (2L, "Martin")); users.add (ny bruger (3L, "Peter")); users.add (ny bruger (4L, "Alicia")); Listeforhold = ny ArrayList (); relationss.add (nyt forhold ("ven", "1", "2")); relationss.add (nyt forhold ("Følger", "1", "4")); relationss.add (nyt forhold ("ven", "2", "4")); relationss.add (nyt forhold ("Relativt", "3", "1")); relationss.add (nyt forhold ("Relativt", "3", "4"));

5.2. GraphFrame Instans

For at oprette og manipulere vores graf over relationer opretter vi nu en forekomst af GraphFrame. Det GraphFrame konstruktør forventer to Datasæt forekomster, hvor den første repræsenterer hjørnerne og den anden kanterne:

Datasæt userDataset = session.createDataFrame (brugere, User.class); Dataset relationshipDataset = session.createDataFrame (relations, Relation.class); GraphFrame-graf = ny GraphFrame (userDataframe, relationshipDataframe);

Endelig logger vi vores hjørner og kanter i konsollen for at se, hvordan det ser ud:

graph.vertices (). show (); graph.edges (). show ();
+ --- + ------ + | id | navn | + --- + ------ + | 1 | John | | 2 | Martin | | 3 | Peter | | 4 | Alicia | + --- + ------ + + --- + -------------------- + --- + -------- - + | dst | id | src | type | + --- + -------------------- + --- + --------- + | 2 | 622da83f-fb18-484 ... | 1 | Ven | | 4 | c6dde409-c89d-490 ... | 1 | Følger | | 4 | 360d06e1-4e9b-4ec ... | 2 | Ven | | 1 | de5e738e-c958-4e0 ... | 3 | Relativ | | 4 | d96b045a-6320-4a6 ... | 3 | Relativ | + --- + -------------------- + --- + --------- +

6. Grafoperatører

Nu hvor vi har en GraphFrame Lad os se, hvad vi kan gøre med det.

6.1. Filter

GraphFrames giver os mulighed for at filtrere kanter og hjørner efter en forespørgsel.

Lad os derefter filtrere hjørnerne efter navn ejendom på Bruger:

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

På konsollen kan vi se resultatet:

+ --- + ------ + | id | navn | + --- + ------ + | 2 | Martin | + --- + ------ +

Vi kan også filtrere direkte på grafen ved at ringe filterKanter eller filterVertices:

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

Nu, da vi filtrerede kanterne, har vi muligvis stadig nogle isolerede hjørner. Så vi ringer dropIsolatedVertices ().

Som et resultat har vi en undergraf, stadig en GraphFrame eksempel med kun de forhold, der har status "Ven":

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

6.2. Grader

Et andet interessant funktionssæt er grader sæt operationer. Disse operationer returnerer antallet af kanter, der er hændende på hvert toppunkt.

Det grader operation returnerer bare tællingen af ​​alle kanter på hvert toppunkt. På den anden side, i Grader tæller kun indgående kanter, og outDegrees tæller kun udgående kanter.

Lad os tælle de indkommende grader af alle hjørner i vores graf:

graph.inDegrees (). show ();

Som et resultat har vi en GraphFrame der viser antallet af indgående kanter til hvert toppunkt eksklusive dem uden:

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

7. Grafalgoritmer

GraphFrames giver også populære algoritmer klar til brug - lad os se på nogle af dem.

7.1. Side rank

Page Rank-algoritmen vejer de indkommende kanter til et toppunkt og omdanner det til en score.

Ideen er, at hver indkommende kant repræsenterer en godkendelse og gør toppunktet mere relevant i den givne graf.

For eksempel i et socialt netværk, hvis en person følges af forskellige mennesker, vil han eller hun blive rangordnet højt.

At køre siderangeringsalgoritmen er ret ligetil:

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

For at konfigurere denne algoritme skal vi bare angive:

  • maxIter - antallet af iterationer af siderangering, der skal køres - 20 anbefales, for få nedsætter kvaliteten, og for mange forringer ydelsen
  • nulstil Sandsynlighed - sandsynligheden for tilfældig nulstilling (alfa) - jo lavere den er, jo større vil score spredt mellem vinderne og taberne være - gyldige intervaller er fra 0 til 1. Normalt er 0,15 en god score

Svaret er et lignende Graframme, men denne gang ser vi en ekstra kolonne, der giver siderangering for hvert toppunkt:

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

I vores graf er Alicia det mest relevante toppunkt efterfulgt af Martin og John.

7.2. Tilsluttede komponenter

Den tilsluttede komponents algoritme finder isolerede klynger eller isolerede undergrafer. Disse klynger er sæt forbundne hjørner i en graf, hvor hvert toppunkt kan nås fra ethvert andet toppunkt i samme sæt.

Vi kan kalde algoritmen uden parametre via connectedComponents () metode:

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

Algoritmen returnerer a GraphFrame indeholdende hvert toppunkt og den komponent, som hver er tilsluttet:

+ --- + ------ + ------------ + | id | navn | komponent | + --- + ------ + ------------ + | 1 | John | 154618822656 | | 2 | Martin | 154618822656 | | 3 | Peter | 154618822656 | | 4 | Alicia | 154618822656 | + --- + ------ + ------------ +

Vores graf har kun en komponent - det betyder, at vi ikke har isolerede undergrafer. Komponenten har et automatisk genereret id, som er 154618822656, i vores tilfælde.

Selvom vi har endnu en kolonne her - komponent-id'et - er vores graf stadig den samme.

7.3. Trekanttælling

Trekantetælling bruges ofte som detektion og tælling af samfund i en graf for et socialt netværk. En trekant er et sæt med tre hjørner, hvor hvert hjørne har et forhold til de to andre hjørner i trekanten.

I et socialt netværkssamfund er det let at finde et betydeligt antal trekanter forbundet med hinanden.

Vi kan let udføre en trekant, der tæller direkte fra vores GraphFrame eksempel:

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

Algoritmen returnerer også a GraphFrame med antallet af trekanter, der passerer gennem hvert toppunkt.

+ ----- + --- + ------ + | antal | id | navn | + ----- + --- + ------ + | 1 | 3 | Peter | | 2 | 1 | John | | 2 | 4 | Alicia | | 1 | 2 | Martin | + ----- + --- + ------ +

8. Konklusion

Apache Spark er et fantastisk værktøj til beregning af en relevant mængde data på en optimeret og distribueret måde. Og GraphFrames-biblioteket tillader os at distribuer let grafhandlinger over Spark.

Som altid er den komplette kildekode til eksemplet tilgængelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found