Modelling and simulation of processes on large graphs.

OData support
Supervisor:
Dr. Katona Gyula
Department of Computer Science and Information Theory

The large-scale networks present in real world applications have multiple special properties that simple random graphs do not, for e.g. the small world phenomenon and scale-freeness. Therefore we need special algorithms to generate "real world" random graphs. One of the possible methods is the Barabási-Albert model detailed in this paper.

The generation of "real world" hypergraphs hasn't been researched as excessively as "real world" graphs. I present two approaches: one is based on finding the communities in a graph, the other generates the hypergraph directly. I used multiple methods to find the communities in a given graph: listing the maximal cliques (Bron-Kerbosh algorithm), k-clique percolation (Palla), iterative k-clique percolation based on the strict clique overlap criterion (Zahoránszky), and information communities (Zubcsek). I examined and evaluated the degree and edge size distribution of the generated hypergraphs.

I present a simple, graph-based epidemic model and its generalisation using hypergraphs. I show the details of their implementations, and examine and evaluate the results of the simulations based on multiple graphs and hypergraphs.

Downloads

Please sign in to download the files of this thesis.