Wednesday, 3 April 2013

Friendwheel

Errrrrr three months from my last entry...

Anyway if you haven't heard of friendwheel, a facebook apps that generates the graph of friendship links of all your friends:

(I blurred the names of my friends for privacy. These blurred pixel looks awesome right?)

In general, they put similar friends closer (this is how the wheel works --- grouping in similar colour)

However as you can see some of the points are emitting a lot of linkage far from the neighbouring group. It turns out that their alogarithm is not very effective.

Definition. Distance between two points are defined by (number of points between them)+1

Definition. Circular n-tuple (a_1,...,a_n) is n numbers in order, and a_1 is supposed to be the next term of a_n. Due to the cyclic structure, it is equivalent to (a_2,a_3,...a_n, a_1) and so on.

Definition. Given a graph G = (V,E), the optimal permutation is a circular |V|-tuple where the tuple is the permutation of vertices so that sum of distance between any two linked vertices is the minimal.

Definition Given a graph G = (V,E). Optimal distance is the sum of distance between any two linked vertices.

The optimal permutation is not necessarily unique. For example consider:

G = (V,E); V = {1,2,3,4}, E = {(1,2),(3,4)}, then both (1,2,3,4) and (1,2,4,3) are optimal permutations with optimal distacnce 2.

Now the problem is, how should we reduce the sum of distance given G and an arbitrary permutation of V? I'll propose a heuristic here:

begin;
local_min_reached = FALSE
while not local_min_reached:
---swapping = FALSE
---for i in 1 to n:
------check if swapping a_i and a_{i+1} reduces sum of distance
------if yes then swap the two vertices
------swapping = TRUE
---if swapping = FALSE:
------local_min_reached = TRUE
return permutation of edges.

I'm so lazy to calculate its preformance ratio as well as other stuffs since it would take me quite a lot of time to do the simulation (like my research topic), but I'm sure that this one is qutie near to the optimal solution. I have no idea to construct G so that the procedure stuck at local optimum and fail to reach the global optimum with the above alogarithm.

Any idea?