streamalism.org

1. Úvod

Spracovanie grafov je užitočné pre mnoho aplikácií od sociálnych sietí po reklamy. Vo scenári veľkých dát potrebujeme nástroj na distribúciu tohto zaťaženia spracovania.

V tomto tutoriále načítame a preskúmame možnosti grafov pomocou Apache Spark v Jave. Aby sme sa vyhli zložitým štruktúram, budeme používať jednoduché a vysoko kvalitné rozhranie API Apache Spark: API GraphFrames.

2. Grafy

Najskôr si definujme graf a jeho komponenty. Graf je dátová štruktúra, ktorá má hrany a vrcholy. The hrany nesú informáciu ktorá predstavuje vzťahy medzi vrcholmi.

Vrcholy sú body v n-dimenzionálny priestor a hrany spájajú vrcholy podľa ich vzťahov:

Na obrázku vyššie máme príklad sociálnej siete. Vidíme vrcholy predstavované písmenami a hrany nesúce druh vzťahu medzi vrcholmi.

3. Nastavenie Maven

Teraz začnime projekt nastavením konfigurácie Maven.

Pridajme spark-graphx 2.11,graficke ramya 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 

Tieto verzie artefaktov podporujú Scala 2.11.

Tiež sa stáva, že GraphFrames nie sú v Maven Central. Pridajme teda aj potrebné úložisko Maven:

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

4. Konfigurácia iskry

Aby sme mohli pracovať s GraphFrames, musíme si stiahnuť Hadoop a definovať HADOOP_HOME premenná prostredia.

V prípade operačného systému Windows si stiahneme aj príslušné winutils.exe do HADOOP_HOME / bin priečinok.

Ďalej začnime náš kód vytvorením základnej konfigurácie:

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

Budeme tiež musieť vytvoriť SparkSession:

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

5. Konštrukcia grafu

Teraz sme pripravení začať s našim hlavným kódom. Definujme teda entity pre naše vrcholy a hrany a vytvorme GraphFrame inštancia.

Budeme pracovať na vzťahoch medzi používateľmi z hypotetickej sociálnej siete.

5.1. Údaje

Najprv si v tomto príklade definujeme obe entity ako Používateľ a Vzťah:

verejná trieda Používateľ {private Long id; súkromné ​​meno reťazca; // constructor, getters and setters} public class Relationship implements Serializable {private String type; súkromný reťazec src; private String dst; súkromné ​​ID UUID; public relations (typ reťazca, reťazec src, reťazec dst) {this.type = typ; this.src = src; this.dst = dst; this.id = UUID.randomUUID (); } // zakladatelia a zakladatelia}

Ďalej si niektoré zadefinujeme Používateľ a Vzťah prípady:

Zoznam používateľov = nový ArrayList (); users.add (nový užívateľ (1L, "John")); users.add (nový užívateľ (2L, "Martin")); users.add (nový používateľ (3L, "Peter")); users.add (nový používateľ (4L, "Alicia")); Zoznam vzťahov = nový ArrayList (); relationships.add (nový vzťah ("priateľ", "1", "2")); relationships.add (nový vzťah („nasledujúci“, „1“, „4“)); relationships.add (nový vzťah („priateľ“, „2“, „4“)); relationships.add (nový vzťah („relatívny“, „3“, „1“)); relationships.add (nový vzťah („relatívny“, „3“, „4“));

5.2. GraphFrame Inštancia

Teraz, aby sme vytvorili a manipulovali s našim grafom vzťahov, vytvoríme inštanciu GraphFrame. The GraphFrame konštruktor očakáva dva Množina údajov inštancie, prvý predstavuje vrcholy a druhý, hrany:

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

Nakoniec v konzole zaznamenáme naše vrcholy a hrany, aby sme videli, ako to vyzerá:

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

+ --- + ------ + | id | meno | + --- + ------ + | 1 | John | | 2 | Martin | | 3 | Peter | | 4 | Alicia | + --- + ------ + + --- + -------------------- + --- + -------- - + | dst | id | src | typ | + --- + -------------------- + --- + --------- + | 2 | 622da83f-fb18-484 ... | 1 | Priateľ | | 4 | c6dde409-c89d-490 ... | 1 | Sledovaní | | 4 | 360d06e1-4e9b-4ec ... | 2 | Priateľ | | 1 | de5e738e-c958-4e0 ... | 3 | Relatívny | | 4 | d96b045a-6320-4a6 ... | 3 | Relatívny | + --- + -------------------- + --- + --------- +

6. Grafické operátory

Teraz, keď máme GraphFrame Napríklad sa pozrime, čo s tým môžeme urobiť.

6.1. Filtrovať

GraphFrames nám umožňujú filtrovať hrany a vrcholy pomocou dotazu.

Ďalej potom poďme filtrovať vrcholy podľa názov majetok na Používateľ:

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

Na konzole vidíme výsledok:

+ --- + ------ + | id | meno | + --- + ------ + | 2 | Martin | + --- + ------ +

Môžeme tiež priamo filtrovať graf volaním filterEdges alebo filterVertices:

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

Keď sme teraz filtrovali okraje, mohli by sme mať nejaké izolované vrcholy. Takže zavoláme dropIsolatedVertices ().

Vo výsledku máme podgraf, stále a GraphFrame napríklad iba so vzťahmi, ktoré majú status „priateľ“:

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

6.2. Stupne

Ďalšou zaujímavou sadou funkcií je stupňov súbor operácií. Tieto operácie vrátia počet hrán dopadajúcich na každý vrchol.

The stupňov operácia iba vráti počet všetkých hrán každého vrcholu. Na druhej strane, stupne počíta iba prichádzajúce hrany a stupne mimo počíta iba odchádzajúce hrany.

Počítajme prichádzajúce stupne všetkých vrcholov v našom grafe:

graph.inDegrees (). show ();

Vo výsledku máme a GraphFrame , ktorý zobrazuje počet prichádzajúcich hrán ku každému vrcholu, s výnimkou tých, ktoré nemajú:

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

7. Grafové algoritmy

GraphFrames tiež poskytuje populárne algoritmy pripravené na použitie - pozrime sa na niektoré z nich.

7.1. Poradie stránky

Algoritmus Page Rank zváži prichádzajúce hrany do vrcholu a transformuje ich na skóre.

Myšlienka je taká, že každá prichádzajúca hrana predstavuje odporúčanie a robí vrchol relevantnejším v danom grafe.

Napríklad na sociálnej sieti, ak človeka sledujú rôzni ľudia, dostane sa na vysokej priečke.

Spustenie algoritmu hodnotenia stránok je celkom jednoduché:

graph.pageRank () .maxIter (20) .resProbability (0,15) .run () .vertices () .show ();

Ak chcete nakonfigurovať tento algoritmus, musíme len poskytnúť:

• maxIter - počet iterácií poradia stránky, ktoré sa majú spustiť - odporúča sa 20, príliš málo zníži kvalitu a príliš veľa zníži výkon
• resetProbability - pravdepodobnosť náhodného vynulovania (alfa) - čím je nižšia, tým väčšie bude rozpätie skóre medzi víťazmi a porazenými - platné rozpätia sú od 0 do 1. Zvyčajne je dobré skóre 0,15

Odozva je podobná GraphFrame, aj keď tentokrát vidíme ďalší stĺpec, ktorý dáva stránke hodnotenie každého vrcholu:

+ --- + ------ + ------------------ + | id | meno | pagerank | + --- + ------ + ------------------ + | 4 | Alicia | 1.9393230468864597 | | 3 | Peter | 0,4848822786454427 | | 1 | Ján | 0,7272991738542318 | | 2 | Martin | 0,848495500613866 | + --- + ------ + ------------------ +

V našom grafe je najdôležitejším vrcholom Alicia, za ktorou nasledujú Martin a John.

7.2. Pripojené komponenty

Algoritmus pripojených komponentov nájde izolované zhluky alebo izolované čiastkové grafy. Tieto zhluky sú množiny spojených vrcholov v grafe, kde je každý vrchol dosiahnuteľný z ktoréhokoľvek iného vrcholu v tej istej množine.

Algoritmus môžeme zavolať bez akýchkoľvek parametrov cez connectedComponents () metóda:

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

Algoritmus vráti a GraphFrame obsahujúci každý vrchol a komponent, ku ktorým je každý pripojený:

+ --- + ------ + ------------ + | id | meno | zložka | + --- + ------ + ------------ + | 1 | Ján | 154618822656 | | 2 | Martin | 154618822656 | | 3 | Peter | 154618822656 | | 4 | Alicia | 154618822656 | + --- + ------ + ------------ +

Náš graf má iba jednu zložku - to znamená, že nemáme izolované čiastkové grafy. Komponent má automaticky generované ID, v našom prípade 154618822656.

Aj keď tu máme ešte jeden stĺpec - id súčasti - náš graf je stále rovnaký.

7.3. Počítanie trojuholníkov

Počítanie trojuholníkov sa bežne používa ako detekcia a počítanie v komunite v grafe sociálnej siete. Trojuholník je množina troch vrcholov, kde každý vrchol má vzťah k ďalším dvom vrcholom v trojuholníku.

V komunite sociálnych sietí je ľahké nájsť značný počet navzájom spojených trojuholníkov.

Môžeme ľahko vykonať trojuholník počítajúci priamo z našej GraphFrame inštancia:

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

Algoritmus tiež vráti a GraphFrame s počtom trojuholníkov prechádzajúcich každým vrcholom.

+ ----- + --- + ------ + | počet | id | meno | + ----- + --- + ------ + | 1 | 3 | Peter | | 2 | 1 | John | | 2 | 4 | Alicia | | 1 | 2 | Martin | + ----- + --- + ------ +

8. Záver

Apache Spark je vynikajúci nástroj na optimalizáciu a distribúciu výpočtov relevantného množstva dát. Knižnica GraphFrames nám to umožňuje ľahko distribuovať operácie grafov cez Spark.

Úplný zdrojový kód príkladu je ako vždy k dispozícii na serveri GitHub.