streamalism.org

1. Introduksjon

Grafbehandling er nyttig for mange applikasjoner fra sosiale nettverk til annonser. Inne i et big data-scenario trenger vi et verktøy for å distribuere denne prosessbelastningen.

I denne opplæringen vil vi laste inn og utforske grafmuligheter ved hjelp av Apache Spark i Java. For å unngå komplekse strukturer bruker vi et enkelt og høyt nivå Apache Spark graph API: GraphFrames API.

2. Grafer

La oss først definere en graf og dens komponenter. En graf er en datastruktur som har kanter og hjørner. De kanter bærer informasjon som representerer forhold mellom toppunktene.

Hjørnepunktene er punkter i et n-dimensjonalt rom og kanter forbinder toppunktene i henhold til deres forhold:

På bildet over har vi et eksempel på et sosialt nettverk. Vi kan se toppunktene representert med bokstaver og kantene som bærer hvilken type forhold som er mellom toppunktene.

3. Maven-oppsett

La oss nå starte prosjektet ved å sette opp Maven-konfigurasjonen.

La oss legge til spark-graphx 2.11,grafiske rammer, og 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 gjenstandsversjonene støtter Scala 2.11.

Det skjer også slik at GraphFrames ikke er i Maven Central. Så la oss legge til det nødvendige Maven-arkivet også:

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

4. Gnistkonfigurasjon

For å kunne jobbe med GraphFrames, må vi laste ned Hadoop og definere HADOOP_HOME miljøvariabel.

I tilfelle Windows som operativsystem, vil vi også laste ned det aktuelle winutils.exe til HADOOP_HOME / søppel mappe.

Deretter, la oss begynne koden vår ved å lage den grunnleggende konfigurasjonen:

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

Vi må også lage en SparkSession:

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

5. Grafkonstruksjon

Nå er vi klar til å starte med hovedkoden. Så la oss definere enhetene for våre hjørner og kanter, og lage GraphFrame forekomst.

Vi vil jobbe med forholdet mellom brukere fra et hypotetisk sosialt nettverk.

5.1. Data

Først, for dette eksemplet, la oss definere begge enhetene som Bruker og Forhold:

offentlig klasse bruker {privat Lang id; privat strengnavn; // constructor, getters and setters} public class Relationship implementer Serializable {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}

La oss deretter definere noen Bruker og Forhold forekomster:

Liste brukere = ny ArrayList (); users.add (ny bruker (1L, "John")); brukere.add (ny bruker (2L, "Martin")); brukere.add (ny bruker (3L, "Peter")); brukere.add (ny bruker (4L, "Alicia")); Listeforhold = ny ArrayList (); relationss.add (nytt forhold ("venn", "1", "2")); relationss.add (nytt forhold ("Følger", "1", "4")); relationss.add (nytt forhold ("venn", "2", "4")); relationss.add (nytt forhold ("Relativ", "3", "1")); relationss.add (nytt forhold ("Relativ", "3", "4"));

5.2. GraphFrame Forekomst

Nå, for å lage og manipulere vår graf over forhold, oppretter vi en forekomst av GraphFrame. De GraphFrame konstruktør forventer to Datasett forekomster, den første som representerer toppunktene og den andre, kantene:

Datasett userDataset = session.createDataFrame (brukere, User.class); Dataset relationshipDataset = session.createDataFrame (relations, Relation.class); GraphFrame graph = new GraphFrame (userDataframe, relationshipDataframe);

Til slutt logger vi våre hjørner og kanter i konsollen for å se hvordan det ser ut:

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 | Venn | | 4 | c6dde409-c89d-490 ... | 1 | Følger | | 4 | 360d06e1-4e9b-4ec ... | 2 | Venn | | 1 | de5e738e-c958-4e0 ... | 3 | Relativ | | 4 | d96b045a-6320-4a6 ... | 3 | Relativ | + --- + -------------------- + --- + --------- +

6. Grafoperatører

Nå som vi har en GraphFrame La oss se hva vi kan gjøre med det.

6.1. Filter

GraphFrames lar oss filtrere kanter og hjørner etter et spørsmål.

La oss deretter filtrere hjørnene etter Navn eiendom på Bruker:

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

På konsollen kan vi se resultatet:

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

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

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

Nå, siden vi filtrerte kantene, kan vi fortsatt ha noen isolerte hjørner. Så vi ringer dropIsolatedVertices ().

Som et resultat har vi en subgraf, fortsatt en GraphFrame eksempel, med bare forholdene som har statusen "venn":

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

6.2. Grader

Et annet interessant funksjonssett er grader sett med operasjoner. Disse operasjonene returnerer antall kanter som hender på hvert toppunkt.

De grader operasjonen returnerer bare tellingen av alle kantene på hvert toppunkt. På den andre siden, inDegrees teller bare innkommende kanter, og ut Grader teller bare utgående kanter.

La oss telle innkommende grader av alle hjørner i grafen vår:

graph.inDegrees (). show ();

Som et resultat har vi en GraphFrame som viser antall innkommende kanter til hvert toppunkt, unntatt de uten:

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

7. Grafalgoritmer

GraphFrames gir også populære algoritmer klare til bruk - la oss ta en titt på noen av dem.

7.1. Side rangering

Page Rank-algoritmen veier innkommende kanter til et toppunkt og forvandler det til et partitur.

Tanken er at hver innkommende kant representerer en påtegning og gjør toppunktet mer relevant i den gitte grafen.

For eksempel i et sosialt nettverk, hvis en person blir fulgt av forskjellige mennesker, vil han eller hun bli rangert høyt.

Å kjøre siderangeringsalgoritmen er ganske grei:

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

For å konfigurere denne algoritmen trenger vi bare å oppgi:

• maksIter - antall iterasjoner av siderangering som skal kjøres - 20 anbefales, for få vil redusere kvaliteten, og for mange vil forringe ytelsen
• resetSannsynlighet - den tilfeldige tilbakestillingssannsynligheten (alfa) - jo lavere den er, jo større blir poengspredningen mellom vinnerne og taperne - gyldige områder er fra 0 til 1. Vanligvis er 0,15 en god score

Svaret er et lignende GraphFrame, skjønt denne gangen ser vi en ekstra kolonne som gir siderangeringen til hvert toppunkt:

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

I grafen vår er Alicia det mest relevante toppunktet, etterfulgt av Martin og John.

7.2. Tilkoblede komponenter

Den tilkoblede komponentens algoritme finner isolerte klynger eller isolerte undergrafer. Disse klyngene er sett med koblede hjørner i en graf der hvert toppunkt kan nås fra et hvilket som helst annet toppunkt i samme sett.

Vi kan ringe algoritmen uten parametere via connectedComponents () metode:

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

Algoritmen returnerer a GraphFrame inneholder hvert toppunkt og komponenten som hver er koblet til:

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

Grafen vår har bare en komponent - dette betyr at vi ikke har isolerte undergrafer. Komponenten har en automatisk generert ID, som er 154618822656, i vårt tilfelle.

Selv om vi har en kolonne til - komponent-IDen - er grafen vår fortsatt den samme.

7.3. Trekanttelling

Trekanttelling brukes ofte som deteksjon og telling av fellesskap i en graf for sosiale nettverk. En trekant er et sett med tre hjørner, hvor hvert toppunkt har et forhold til de to andre hjørnene i trekanten.

I et sosialt nettverkssamfunn er det lett å finne et betydelig antall trekanter koblet til hverandre.

Vi kan enkelt utføre en trekanttelling direkte fra vår GraphFrame forekomst:

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

Algoritmen returnerer også a GraphFrame med antall trekanter som går gjennom hvert toppunkt.

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

8. Konklusjon

Apache Spark er et flott verktøy for å beregne en relevant datamengde på en optimalisert og distribuert måte. Og GraphFrames-biblioteket tillater oss det distribuer enkelt grafoperasjoner over Spark.

Som alltid er den komplette kildekoden for eksemplet tilgjengelig på GitHub.