Menschen/Soziale Interaktion/Graph/Beispiel

Es sei eine Menge ${}P$ von Personen gegeben und wir interessieren uns für eine gewisse soziale Interaktion, die zwischen je zwei Personen bestehen kann oder nicht. Die Interaktion soll symmetrisch sein, also keine Richtung besitzen. Beispiele sind: kennen sich, sind befreundet, sind miteinander verwandt, waren schon mal zusammen im Kino, waren schon mal zusammen im Bett, waren schon mal miteinander verheiratet, haben ein gemeinsames Hobby, haben eine gemeinsame wissenschaftliche Arbeit publiziert. Wenn man einen solchen Sachverhalt mit einem ungerichteten Graphen ausdrücken möchte, so interpretiert man die Personenmenge als Punktmenge und erklärt die Kantenmenge dadurch, dass ${}x$ und ${}y$ aus ${}P$ genau dann durch eine Kante miteinander verbunden sind, wenn zwischen ${}x$ und ${}y$ die soziale Interaktion besteht. Fragestellung, die graphentheoretisch untersucht werden können, sind: Gibt es Personen, die mit besonders vielen Personen in der Interaktion stehen, mit wie vielen Personen steht durchschnittlich eine Person in Interaktion, gibt es Clusterbildungen (also Teilmengen von ${}P$ derart, dass innerhalb der Teilmenge viele Interaktionen stattfinden, aber wenige oder keine Interaktionen aus dieser Gruppe heraus), gibt es isolierte Personen ohne diese Interaktion, lässt sich die Personenmenge in Teilgruppen aufteilen, wo untereinander keine Interaktion stattfindet (heterosexuelles Verhalten, bipartiter Graph, Färbungsprobleme), über wie viele direkte Interaktionen stehen Personen in einer indirekten Beziehung zueinander (man kennt sich um ein paar Ecken, ist entfernt miteinander verwandt), wie ändert sich das soziale Gefüge, wenn man eine Person herausnimmt (wegzieht, die Firma verlässt, stirbt).