UsingAAndMinimaxToStudyTheSmallWorldScenario

Baochen Sun
December 10, 2010

Attach:sun_small_world_scenario_Using_A*_&_Minimax.pdf

Overview

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.

Screenshot

Concepts Demonstrated

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.

Innovation

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.

Additional Remarks

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;