Diese Masterarbeit beschäftigt sich mit verschiedenen Modellen von Zufallsgraphen für biologische Netzwerke. Nach einer kurzen Einführung, in der benötigte graphentheoretische Begriffe sowie Anwendungsbeispiele der Graphentheorie erläutert werden, erfolgt die Vorstellung von drei einfachen Zufallsgraphenmodellen: das Erd ˝ os-Rényi-Modell, das Gilbert-Modell und das p1-Modell. Außerdem werden in diesem Kapitel zwei spezielle Zufallsgraphenmodelle, zum einen die Exponential Random Graph Models und zum anderen die Small-World Models, ausführlich dargestellt. Anschließend werden alle Modelle für ein konkretes biologisches Netzwerk, das Protein-Protein-Interaktions-Netzwerk des Bakteriums Escherichia coli, auf ihre Anwendbarkeit überprüft und diesbezüglich bewertet.
A classical topic in the theory of random graphs is the probability of at least one isolated vertex in a given random graph. An isolated node has a huge impact on social networks which can be given by a random graph. We present a distribution on the number of isolated vertex using the probability generating function. We discuss the relationship between isolated edges and extended cut polynomials, extended matching polynomials using the principle of inclusion exclusion. We introduce an algorithm based on colored graphs for general graphs. We apply this to the components of a graph as well. Finally, we implement the idea on a special class of graphs like cycle, bipartite graph, path, and others. We discuss recursive procedure based on the analogous coloring rules for ladder and fan graphs.