December 10, 2010
In this project, A* search algorithm is utilized to find the shortest path between two friends in a social network. And a Voting Game based on Minimax algorithm is designed to study the information propagation through the social network.
- A* search is used to find the shortest between two friends in a social network.
- Minimax Algorithm is used to study the information propagation through the social network.
- Using the degree of an vertex in a graph as the heuristic in A* search;
- Using dynamic two dimension array to store sparse matrix, which is not only efficient but also can deal with very large data set;
- Both simulated data and Facebook data are used;
- A funny game--Voting Game--is designed to analysis the structure of a social network.
Technology Used Block Diagram
Evaluation of Results
In this project, I have successfully implemented the A* search algorithm to find the shortest path in a social network. This algorithm works efficiently on both simulated data and Facebook data. The Voting Game is very funny and useful in analyzing the structure of a social network.
Legend of the visualization:
- The first player always plays first;
- Generated data. Red: nothing; Blue: nothing;
- Graph Analysis. Red: the first player sometime loses, these vertices are the weakly connected vertices in the social network; Blue: the first player always wins;