streamalism.org

1. Uvod

Obrada grafova korisna je za mnoge aplikacije od društvenih mreža do oglasa. Unutar scenarija velikih podataka potreban nam je alat za raspodjelu tog opterećenja obrade.

U ovom ćemo uputstvu učitati i istražiti mogućnosti grafikona pomoću Apache Spark u Javi. Da bismo izbjegli složene strukture, koristit ćemo jednostavan API visoke razine Apache Spark: API GraphFrames.

2. Grafovi

Prije svega, definirajmo graf i njegove komponente. Graf je struktura podataka koja ima rubove i vrhove. The rubovi nose informacije koji predstavlja odnose između vrhova.

Vrhovi su točke u an n-dimenzionalni prostor, a rubovi povezuju vrhove prema njihovim odnosima:

Na gornjoj slici imamo primjer društvene mreže. Možemo vidjeti vrhove predstavljene slovima i rubove koji nose kakav je odnos između vrhova.

3. Postavljanje Mavena

Počnimo projekt postavljanjem konfiguracije Maven.

Dodajmo spark-graphx 2.11,grafički okviri, i iskra-sql 2.11:

 org.apache.spark spark-graphx_2.11 2.4.4 grafički okviri grafički okviri 0.7.0-spark2.4-s_2.11 org.apache.spark spark-sql_2.11 2.4.4 

Ove verzije artefakata podržavaju Scala 2.11.

Također se događa da GraphFrames nije u Maven Central. Pa, dodajmo i potrebno spremište Maven:

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

4. Konfiguracija iskre

Da bismo mogli raditi s GraphFramesima, trebamo preuzeti Hadoop i definirati HADOOP_HOME varijabla okoline.

U slučaju Windows-a kao operativnog sustava, preuzet ćemo i odgovarajući winutils.exe prema HADOOP_HOME / bin mapu.

Dalje, započnimo naš kôd izradom osnovne konfiguracije:

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

Trebat ćemo stvoriti i SparkSession:

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

5. Izgradnja grafa

Sad smo spremni za početak s našim glavnim kodom. Dakle, definirajmo entitete za naše vrhove i bridove i stvorimo GraphFrame primjer.

Radit ćemo na odnosima između korisnika s hipotetske društvene mreže.

5.1. Podaci

Prvo, za ovaj primjer, definirajmo oba entiteta kao Korisnik i Odnos:

korisnik javne klase {private Long id; privatni naziv niza; // konstruktor, getteri i postavljači} odnos javne klase implementira Serializable {private String type; private String src; private String dst; privatni UUID id; odnos s javnošću (vrsta niza, niz src, niz dst) {this.type = type; ovo.src = src; this.dst = dst; this.id = UUID.randomUUID (); } // geteri i postavljači}

Dalje, definirajmo neke Korisnik i Odnos primjerci:

Popis korisnika = novi ArrayList (); users.add (novi korisnik (1L, "John")); users.add (novi korisnik (2L, "Martin")); users.add (novi korisnik (3L, "Peter")); users.add (novi korisnik (4L, "Alicia")); Popis odnosa = novi ArrayList (); odnosi.add (novi odnos ("Prijatelj", "1", "2")); odnosi.add (novi odnos ("Slijedi", "1", "4")); odnosi.add (novi odnos ("Prijatelj", "2", "4")); odnosi.add (novi odnos ("Relativni", "3", "1")); odnosi.add (novi odnos ("Relativni", "3", "4"));

5.2. GraphFrame Primjer

Sada, kako bismo stvorili i manipulirali našim grafom odnosa, stvorit ćemo primjerak GraphFrame. The GraphFrame konstruktor očekuje dvije Skup podataka primjerci, prvi koji predstavlja vrhove, a drugi rubove:

Skup podataka userDataset = session.createDataFrame (korisnici, User.class); Skup podataka: relationshipDataset = session.createDataFrame (odnosi, Relation.class); GraphFrame graph = novi GraphFrame (userDataframe, relationshipDataframe);

Napokon ćemo zabilježiti svoje vrhove i rubove u konzoli kako bismo vidjeli kako to izgleda:

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

+ --- + ------ + | id | ime | + --- + ------ + | 1 | Ivan | | 2 | Martin | | 3 | Petar | | 4 | Alicia | + --- + ------ + + --- + -------------------- + --- + -------- - + | dst | id | src | upišite | + --- + -------------------- + --- + --------- + | 2 | 622da83f-fb18-484 ... | 1 | Prijatelj | | 4 | c6dde409-c89d-490 ... | 1 | Slijedi | | 4 | 360d06e1-4e9b-4ec ... | 2 | Prijatelj | | 1 | de5e738e-c958-4e0 ... | 3 | Relativni | | 4 | d96b045a-6320-4a6 ... | 3 | Relativni | + --- + -------------------- + --- + --------- +

6. Operatori grafikona

Sad kad imamo GraphFrame primjerice, da vidimo što možemo učiniti s tim.

6.1. filtar

GraphFrames omogućuje filtriranje rubova i vrhova upitom.

Zatim, filtrirajmo vrhove prema Ime nekretnina na Korisnik:

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

Na konzoli možemo vidjeti rezultat:

+ --- + ------ + | id | ime | + --- + ------ + | 2 | Martin | + --- + ------ +

Također, pozivanjem možemo na grafikonu izravno filtrirati filterEdges ili filterVertices:

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

Sad, budući da smo filtrirali rubove, možda još uvijek imamo neke izolirane vrhove. Dakle, nazvat ćemo dropIsolatedVertices ().

Kao rezultat, imamo podgraf, još uvijek a GraphFrame primjerice, samo s vezama koje imaju status "Prijatelj":

+ --- + ------ + | id | ime | + --- + ------ + | 1 | Ivan | | 2 | Martin | | 4 | Alicia | + --- + ------ +

6.2. Stupnjevi

Još jedan zanimljiv skup značajki je stupnjeva skup operacija. Te operacije vraćaju broj bridova koji padaju na svaki vrh.

The stupnjeva operacija samo vraća broj svih bridova svakog vrha. S druge strane, u stupnjevima broji samo dolazne rubove i outDegrees broji samo odlazne rubove.

Izbrojimo dolazne stupnjeve svih vrhova u našem grafu:

graph.inDegrees (). show ();

Kao rezultat, imamo GraphFrame koji pokazuje broj dolaznih bridova za svaki vrh, isključujući one bez njih:

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

7. Grafički algoritmi

GraphFrames također nudi popularne algoritme spremne za upotrebu - pogledajmo neke od njih.

7.1. Page Rank

Algoritam Page Rank odmjerava dolazne rubove u vrh i pretvara ih u rezultat.

Ideja je da svaki dolazni rub predstavlja potvrdu i čini vrh relevantnijim u danom grafu.

Na primjer, u društvenoj mreži, ako osobu prate različiti ljudi, ona će biti visoko rangirana.

Pokretanje algoritma za rang stranice prilično je jednostavno:

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

Da bismo konfigurirali ovaj algoritam, samo trebamo navesti:

• maksimalno - broj ponavljanja ranga stranice za pokretanje - preporučuje se 20, premalo će smanjiti kvalitetu, a previše će pogoršati izvedbu
• resetProbability - vjerojatnost slučajnog resetiranja (alfa) - što je niža, to će biti veći raspon rezultata između pobjednika i poraženih - važeći rasponi su od 0 do 1. Obično je 0,15 dobar rezultat

Odgovor je sličan GraphFrame, iako ovaj put vidimo dodatni stupac koji daje rang stranice svakog vrha:

+ --- + ------ + ------------------ + | id | ime | PageRank | + --- + ------ + ------------------ + | 4 | Alicia | 1.9393230468864597 | | 3 | Petar | 0,4848822786454427 | | 1 | Ivan | 0,7272991738542318 | | 2 | Martin | 0,848495500613866 | + --- + ------ + ------------------ +

Na našem je grafikonu Alicia najrelevantniji vrh, a slijede ga Martin i John.

7.2. Povezane komponente

Algoritam povezanih komponenata pronalazi izolirane klastere ili izolirane podgrafe. Ti su skupovi skupovi povezanih vrhova u grafu gdje je svaki vrh dostupan iz bilo kojeg drugog vrha u istom skupu.

Algoritam možemo pozvati bez ikakvih parametara putem connectedComponents () metoda:

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

Algoritam vraća a GraphFrame koji sadrži svaki vrh i komponentu na koju je svaki povezan:

+ --- + ------ + ------------ + | id | ime | komponenta | + --- + ------ + ------------ + | 1 | Ivan | 154618822656 | | 2 | Martin | 154618822656 | | 3 | Petar | 154618822656 | | 4 | Alicia | 154618822656 | + --- + ------ + ------------ +

Naš graf ima samo jednu komponentu - to znači da nemamo izolirane podgrafove. Komponenta ima automatski generirani id, koji je u našem slučaju 154618822656.

Iako ovdje imamo još jedan stupac - id komponente - naš graf je i dalje isti.

7.3. Brojanje trokuta

Brojanje trokuta obično se koristi kao otkrivanje i brojanje zajednice u grafikonu društvene mreže. Trokut je skup od tri vrha, pri čemu svaki vrh ima odnos prema druga dva vrha u trokutu.

U zajednici društvene mreže lako je pronaći znatan broj međusobno povezanih trokuta.

Jednostavno možemo izvesti trokut brojeći izravno od našeg GraphFrame primjer:

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

Algoritam također vraća a GraphFrame s brojem trokuta koji prolaze kroz svaki vrh.

+ ----- + --- + ------ + | brojanje | id | ime | + ----- + --- + ------ + | 1 | 3 | Petar | | 2 | 1 | Ivan | | 2 | 4 | Alicia | | 1 | 2 | Martin | + ----- + --- + ------ +

8. Zaključak

Apache Spark izvrstan je alat za izračunavanje relevantne količine podataka na optimiziran i distribuiran način. A, knjižnica GraphFrames nam to omogućuje lako distribuirati operacije grafikona preko Sparka.

Kao i uvijek, cjeloviti izvorni kod za primjer dostupan je na GitHub-u.