Masterarbeit
Context
Consider a finite connected graph G were initially each of the n nodes has a color from a range {0, ..., C−1} . A minority process is a dynamic process in which each node repeatedly changes its color to the color which is least frequent in its neighborhood. As a motivation consider a WiFi network. One common behavior is to choose the least crowded frequency in order to minimize interference with your neighbors. Unfortunately, this least crowded frequency will change over time if some of your neighbors also follow this advice. Minority processes arise in many application areas such as economics, social sciences, cellular biology, and crystallization mechanics.
There are several questions in the context of minority processes: Will they converge to a stable state and if, how long does it take? Which are the remaining states? Are stable states immune against small perturbations? What is the influence of the structure of the graph on these issues?
To complete the description of a minority process interaction models are defined. Such a model defines when nodes check their neighborhood and update their color. The two basic models are the sequential and the concurrent model. Both operate in rounds. In the first model in each round a single node can update its color (random node, a node specified by an adversarial, etc.). In the second model in each round each node that wants to change its color will do so. There are also other models.
It has been shown that in models where simultaneous neighboring changes are excluded, O(n²) is upper bound on the stabilization time for minority processes. Some lower bounds have also been proved, these hold for special graphs with a special initial coloring 1.
Task
The task of this thesis is to analyze different aspects of minority processes for random graphs, e.g. G(n,p) or the Barabási-Albert-Modell. In particular the behavior of the stabilization time in the relation to p is of interest. The analysis should begin with the case C=2. A simulation tool should be implemented to get some empirical data as a starting point for a more formal analysis. In this analysis the dependency of the stabilization time on p should be analyzed. Also the influence of perturbations should be researched.
| Startdatum | 15. Juni 2020 |
| Enddatum | 17. Februar 2021 |
| Dokumente | Flyer |
| Betreuer |
Prof. Dr. rer. nat. Volker Turau
|