Pregel: Message Passing.
Focus on the process, no matter each vertex computation.
Steps [1]:
(this part was referenced from a blog)
A node passes a message to an adjacent node only when it has received all incoming messages, excluding the message from the destination node to itself. Below shows an example of a message being passed from x1 to x2 .
Node x1 waits for messages from nodes A,B,C,D before sending its message to . As a reminder, it does not send the message from x2->x1 back to x1 (no feedback) .
An easy version of algo given by me:
Input: Graph g, number of iteration n.
Output: the “best” label for each vertex.
_________________________________________
function LoopyBP (Graph g, int n):
for each vertex in Graph g:
initialise message.
for each edge in Graph g:
initialise conditional probability.
// to avoid wait-forever problem ( a random state can be chosen, intend to testing)
for n times of iteration:
(simultaneously) pass message to the peer node(?)
calculate dot-product
find the best label as the belief
_________________________________________
Five key questions
1. message init
for each vertex, we can have multiple states with a random probability of each, but sum up to 1(normalisation).
etc. (0.3,0.6,0.1)
2. edge init
for each edge, init, same as question 1.
3. message update
when sending message, if A->B
message (A->B) =( Neighbours exclude B Sum-up in Vertex A )* Edge (A->B)
4. calculate belief
after received every message from peer vertex,
choose the best label for the node, marked as the belief
5. loops
do BP for many times.
A question to think about(difficult):
How to synchronize? A vertex can only send a message to another one when it receives every msg exclude this one. How to start the whole process?
IreneLi 