Demonstrates triangle closing in simple,
unweighted graphs for Giraph.
Triangle Closing: Vertex A and B maintain out-edges to C and D
The algorithm, when finished, populates all vertices' value with an
array of Writables representing all the vertices that each
should form an out-edge to (connect with, if this is a social
In this example, vertices A and B would hold empty arrays
since they are already connected with C and D. Results:
If the graph is undirected, C would hold value, D and D would
hold value C, since both are neighbors of A and B and yet both
were not previously connected to each other.
In a social graph, the result values for vertex X would represent people
that are likely a part of a person X's social circle (they know one or more
people X is connected to already) but X had not previously met them yet.
Given this new information, X can decide to connect to vertices (peoople) in
the result array or not.
Results at each vertex are ordered in terms of the # of neighbors
who are connected to each vertex listed in the final vertex value.
The more of a vertex's neighbors who "know" someone, the stronger
your social relationship is presumed to be to that vertex (assuming
a social graph) and the more likely you should connect with them.
In this implementation, Edge Values are not used, but could be
adapted to represent additional qualities that could affect the
ordering of the final result array.