100 vertices

From Master Projects
Jump to: navigation, search


has title::100 vertices
status: finished
Master: project within::High Performance Distributed Computing
Student name: student name::Emiel Suilen
Dates
Start start date:=2011/10/31
End end date:=2012/05/31
Supervision
Supervisor: Daan van den Berg (until 2012/04/01), Rena Bakhshi (from 2012/04/01)
Second reader: has second reader::Maarten van Steen
Company: has company::VU
Poster: has poster::Media:Media:Posternaam.pdf

Signature supervisor



..................................

Abstract

While graphs have been studied extensively during the past 280 years, they have never been mapped in a statespace with regards to their cluster coefficient and average path length. Even though such a statespace of a graph of 100 vertices and 300 edges is known, the shape of such a statespace with an alternate number of edges, is not. It is currently unknown how the statespace of a graph of 100 vertices and 200 edges looks, or how it differs from the statespace of a graph with 100 vertices and 2000 edges. Therefore, in this master project, the entire statespace of graphs with 100 vertices will be explored, with specific intervals.

To define such a statespace, the found graphs for the upper and lower limits of a specific configuration will be researched and proven. Also, the distribution and the total number of graphs for a specific configuration is currently not known, and should be researched and determined. Due to the huge number of possible graphs (for example, the statespace of 100 vertices and 300 edges is 7.56 10E479) a full examination of the statespace is not possible, and mathematical analysis has to be used to provide an insight into the distribution. Currently, it is believed that a full quantitative analysis is impossible, but that qualitative "hints" can be obtained by analyzing the individual graphs of a certain statespace.

Finally, the possibility to turn the individual statespaces into a full body will be researched. The number of discrete steps between statespaces will be researched, and formula's to obtain the upper and lower bounds will be analyzed.