Cvičení 9: Vlastnosti náhodných modelů grafů

Gnuplot

Tento program se hodí k vykreslování větších grafů a je možné jej využít např. k fitování křivky nějakou funkcí. Program gnuplot můžeme buď spouštět přímo a zadávat mu příkazy, anebo pro něj připravit skript. Pěkný úvodní přehled všech možností je například v následujícím návodu: https://www.sci.muni.cz/~mikulik/gnuplot/gp.html

Networkx obsahuje implementace některých modelů náhodných grafů: https://networkx.org/documentation/stable/reference/generators.html#module-networkx.generators.random_graphs

Úloha 1: Napiš funkci, která pro zadanou distribuci stupňů vrcholů vrátí náhodně vygenerovanou síť pomocí konfiguračního modelu.

Úloha 2: Napiš funkci, která pro zadané váhy vrcholů vrátí náhodně vygenerovanou síť pomocí Chung-Lu modelu.

Úloha 3: Vygeneruj náhodné sítě velikosti $10^4$ pomocí modelů

• Barabási-Albert model s $m=4$ a počátečním grafem $I_4$ (odpovídá implementaci v networkx).
• konfigurační model s vygenerovanou posloupností stupňů odpovídající Barabási-Albert modelu vygenerovaném v prvním kroku
• Chung-Lu model s váhami $w_i$ odpovídajícími odpovídající Barabási-Albert modelu vygenerovaném v prvním kroku

Následně pro vygenerované sítě porovnej

• průměrnou délku cest
• clustering coefficent

Úloha 4: V Barabási-Albert modelu začínáme s grafem na $m_0$ vrcholech takovým, že stupeň každého vrcholu je alespoň jedna.

• Naimplementuj funkci, která pro zadané $m$, graf na $m_0$ vrcholech a cílovou velikost vygeneruje odpovídající náhodnou síť typu Barabási-Albert. Můžeš se inspirovat implementací tohoto modelu v networkx.

Pro $m_0 = 4$:

• Vygeneruj všechny neisomorfní grafy na $m_0$ vrcholech, kde každý vrchol má stupeň alespoň 1. Můžeš u toho využít soubor všech neisomorfních grafů na čtyřech vrcholech: https://users.cecs.anu.edu.au/~bdm/data/graph4.g6
• Pro každý z grafů v předchozím kroku vygeneruj 100 náhodných sítí velikosti $10^2$ a $10^3$ podle Barabási-Albert modelu a zanes do grafu průměrnou distribuci stupňů.
• Srovnej výsledné distribuce. Jaký je vliv výchozího grafu?