Cvičení 11: Algoritmy na detekci komunit

Obarvování vrcholů grafu

Pro obarvení vrcholů grafu můžeme použít parametr node_color pro funkci draw_networkx, který můžeme použít i ve funkci draw:

import networkx as nx

wheel = nx.wheel_graph(10)
colors = ['red' for i in range(10)]
colors[0] = 'blue'
nx.draw(wheel, node_color=colors)

Kromě přímého přiřazení barev můžeme vrcholům určit číslo mezi 0 a 1 a jako další parametr vykreslovací funkce použít barevnou paletu, pomocí které se číslo převede na odpovídající barvu. Přehled palet: https://matplotlib.org/stable/tutorials/colors/colormaps.html

Podrobnější informace viz dokumentace: https://networkx.org/documentation/stable/reference/generated/networkx.drawing.nx_pylab.draw_networkx.html#networkx.drawing.nx_pylab.draw_networkx

Detekce komunit

V networkx je naimplementováno několik algoritmů souvisejících s detekcí komunit a dělením grafu na části (graph partitioning):

• Kerninghan-Lin na rozdělení grafu na dvě části
• Girvan-Newmanův algoritmus
• algoritmy na detekci komunit na základě k-clique, maximalizace modularity a další a také například počítání modularity pro zadané rozdělení grafu na komunity.

Pro použití těchto funkcí je potřeba naimportovat namespace pro komunity. Více viz https://networkx.org/documentation/stable/reference/algorithms/community.html

Úlohy

Úloha 1: Spusť algoritmus na detekci komunit pomocí maximalizace modularity na grafu sociální sítě delfínů (http://networkrepository.com/soc-dolphins.php). Zjisti výsledný počet komunit $k$.

Úloha 2: Newmanův algoritmus využívající hranovou mezilehlost vrátí hierarchii komunit. Porovnej (opticky) jeho výstup odpovídající $k$ komunitám s výsledkem z předchozí úlohy. K porovnání můžeš například použít vykreslení grafu s různým obarvením vrcholů v odlišných komunitách.