Graphx

Question 1

Web graphs

Answer 1

*Vertices represent pages
*edges represent hyder links

Question 2

Knowledge graphs

Answer 2

*Vertices represent entities, eg; locations,people,events
*edges represent relationships, eg; capital of, occured in

Question 3

Graph model

Answer 3

Graph[VD,ED]
VD: verteice
ED : edge

Question 4

examples of
Knowledge Graph

Answer 4

graph[String,String]
DV: String= entity names
ED: String = relationship

Question 5

examples of graph[String,String]
Road Network

Answer 5

DV: (longitude, latitude)
ED: (streedName, speedLimit)

Question 6

slides show graph creation code

Question 7

Graph partitioning; Edge cut

Answer 7

*Each vertex is assigned to one partition
*Some edges are replicated

Question 8

Graph partitioning; Vertex cut

Answer 8

*Each edge is assigned one partition
*Some vertices are replicated

Question 9

GraphX adopts which graph partitioning for what function

Answer 9

adopts Vertex cut to minimize communication cost

Question 10

Simple graph processing

Answer 10

• Vertices and edges can be treated as RDDs
• Regular RDD operations can operate on them

Question 11

Vertex Operations

Answer 11

• Filter
• mapValues
  *diff(other: VertexRDD[VD])

Question 12

Vertex Operation; Filter

Answer 12

Keeps only a subset of vertices that satisfy the predicated

Question 13

Vertex Operation; mapValues

Answer 13

Modify the value on each
vertex

Question 14

Vertex Operation; diff(other: VertexRDD[VD]):

Answer 14

Removes all
vertices in the other set of vertices

Question 15

Edge operations

Answer 15

*mapValues
*reverse

Question 16

Edge operations; mapValues

Answer 16

Modify the value on each
edge

Question 17

Edge operations;Reverse

Answer 17

Reverse the direction of each
edge (V1 -> V2) → (V2 -> V2)

Question 18

Iterative Graph Processing operations

Answer 18

• Each vertex send a
  message along outgoing
  edges
• Each vertex updates its
  vertex data by
  aggregating incoming
  messages
• Repeat until a stopping
  condition

Question 19

Pregel API

Answer 19

def pregelA(
vprog: (VertexId, VD, A) => VD,
sendMsg: EdgeTriplet[VD, ED] =>
Iterator[(VertexId, A)],
mergeMsg: (A, A) => A)
: Graph[VD, ED]

Question 20

Graph Analytics: Connected
Components
Goal

Answer 20

Assign each vertex the smallest ID in
its connected component

Question 21

Graph Analytics: Connected
Components
message

Answer 21

Each vertex sends its current
label (initially its own ID) to neighbors.

Question 22

Graph Analytics: Connected
Components
Update Rule

Answer 22

On each superstep, a vertex
adopts the smallest label received from its
neighbors if it’s smaller than its current
label

Question 23

Graph Analytics: Connected
Components
Terminiation

Answer 23

When no vertex changes its
label (i.e., messages stop propagating),
the algorithm converges

Question 24

Graph Analytics: Single-source Shortest
Path (SSSP)
Goal

Answer 24

Find the minimum distance from a
source vertex to all others.

Question 25

Graph Analytics: Single-source Shortest Path (SSSP) message

Answer 25

Each vertex sends updated distance estimates to neighbors (e.g., its own distance + edge weight).

Question 26

Graph Analytics: Single-source Shortest Path (SSSP) Update rule

Answer 26

A vertex keeps the smallest distance received and forwards new distance estimates if updated

Question 27

Graph Analytics: Single-source Shortest Path (SSSP) Termination

Answer 27

When no shorter distances are propagated, the algorithm halts.

Question 28

Graph Analytics: Page Rank Goal

Answer 28

Compute an "importance" score for each vertex based on its incoming links

Question 29

Graph Analytics: Page Rank Message

Answer 29

Each vertex sends a fraction of its current rank (e.g., rank / out-degree) to neighbors.

Question 30

Graph Analytics: Page Rank Update rule

Answer 30

Each vertex sums incoming contributions, applies damping (e.g., new_rank = 0.15 + 0.85 * sum), and updates its rank

Question 31

Graph Analytics: Page Rank Termination

Answer 31

After a fixed number of iterations or when rank changes fall below a threshold