Komunita je množina vrcholů, které mají větši pravděpodobnost, že jsou propojené mezi sebou, než že jsou propojené s vrcholy v ostatních komunitách. Nechť komunita $C$ je podmnožina vrcholů. Pro vrchol $v \in C$ definujeme vnitřní stupeň $k_v^{\text{in}}(C)$ jako $|\{w \in N(v)\ |\ w \in C\}|$ a vnější stupeň $k_v^{\text{out}}(C) = |\{w \in N(v)\ |\ w \notin C\}|$.
Souhrnný vnitřní stupeň a souhrnný vnější stupeň pak definujeme jako $k_C^{\text{in}} = \sum_{v_\in V(C)} k_v^{\text{in}}$ a $k_C^{\text{ext}} = \sum_{v_\in V(C)} k_v^{\text{ext}}$. Souhrnný stupeň $C$ je $k_C = k_C^{\text{in}} + k_C^{\text{ext}}$. Komunita $C$ je silná, pokud $k_v^{\text{in}}(C) > k_v^{\text{ext}}(C)$ pro všechna $v\in C$, nebo slabá, pokud $k_C^{\text{in}} > k_C^{\text{ext}}$.
Hustota komunity $C$ v grafu $G$, kde $|C| = n_c$ a $|G| = n$, může být definovaná jako interní neboli $$\rho_{\text{int}} = \frac{|E(C)|}{{n_c \choose 2}}$$ anebo externí neboli $$\rho_{\text{ext}} = \frac{|E(C,G\setminus C)|}{(n_c(n - n_c))}.$$ Pro $\rho = |E(G)| / {n \choose 2}$ průměrnou hustotu grafu a komunitu $C$ klademe podmínku $$\rho_{\text{int}} \gg \rho \gg \rho_{\text{ext}}.$$ V algoritmech poté maximalizujeme $\rho_{\text{int}} - \rho_{\text{ext}}$.
Další podmínky na strukturu komunit:
Typicky chceme, aby komunity tvořily rozklad grafu, neboli měly prázdné průniky a jejich sjednocení obsahovalo všechny vrcholy grafu. V některých případech ale můžeme mít i překrývající se komunity. Potom je členství v komunitách udáno pomocí $váhy$.
$k$-klika je maximální podgraf takový, že $\forall u,v,~ d_G(u,v) \leq k$. Nejkratší cesty mohou vést mimo $C$, neboli může se stát, že $\text{diam}(G[C]) > k$.
$k$-klub je $k$-klika s $\text{diam}(G[C]) \leq k$. Na rozdíl od $k$-kliky zaručuje souvislost v rámci $C$.
$k$-plex je množina vrcholů, které sousedí v $C$ se všemi vrcholy až na $k-1$ výjímek, neboli $\deg_{G[C]}(v) = |N[v] \cap C | \geq |C| - k$ pro všechna $v\in C$.
$k$-PLEX je problém, kdy pro zadaný graf $G$ a čísla $c$ a $k$ máme nalézt $k$-plex velikosti $c$. Pro $k=1$ obsahuje problém nalezení maximální kliky, tj. je NP-těžký.
Věta (Balasundaram, Butenko, Hicks, Sachdeva 2011) $k$-PLEX je NP-úplný pro libovolné fixní $k$.
Problém též můžeme zformulovat pomocí celočíselného programování následovně:
Nechť
Pro $k > 1$ mějme program
kde proměnná $x_i = 1$ reprezentuje, že $i\in V$ je v $k$-plexu a jinak $x_i = 0$. Prostřední pomdínka zaručuje, že $i$ má alespoň $k - 1$ sousedů v $k$-plexu.
Vrcholy můžeme dělit do komunit i na základě jejich podobnosti. Můžeme dostat nějaký externí vektor vlastností anebo použít například vzdálenost vrcholů. Pokud je $G$ možné (rozumně) vnořit do nějakého prostoru, položíme $$d^E(u,v) = \sqrt{\sum_{i=1}^n (u_i - v_i)^2}$$ a předpokládáme, že blízké vrcholy jsou si podobné.
V opačném případě odvozujeme podobnost vrcholů na základě sousednosti. Například strukturální ekvivalence $$d^S(i,j) = \sqrt{\sum_{k\neq i,j} (A_{ik} - A_{jk})^2}$$ anebo průniku sousedství $$d^N(i,j) = \frac{|N(i) \cap N(j)|}{|N(i) \cup N(j)|}.$$
Klustery mají hierarchickou strukturu - větší klustery/komunity se skládají z menších. Algoritmy jsou často založené na podobnosti vrcholů, kde pro každou dvojici spočítáme podobnost a výsledek zapíšeme do matice podobnosti. Výstupem algoritmu je dendrogram, neboli stromová reprezentace klusterů.
Typické druhy algoritmů:
Poznámka: Může být potřebné definovat podobnost mezi dvěma skupinami vrcholů.
je dělící algoritmus používající mezilehlostní centralitu pro hrany: $$C_{EB}(e) = \sum_{u,v \notin e} \frac{\sigma_{uv}(e)}{\sigma_{uv}}$$ kde $\sigma_{uv}(e)$ je počet nejkratších cest procházejících hranou $e$.
V algoritmu předpokládáme, že hrana $e_{i,j}$ má velkou centralitu, pokud spojuje vrcholy v různých komunitách, a malou centralitu, pokud vede mezi vrcholy ve stejné komunitě.
Algoritmus:
Způsob ohodnocení kvality rozdělení na komunity. Každé rozdělení vrcholů do disjunktních množin dostane reálné číslo - čím vyšší, tím lepší. Hlavní myšlenkou je srovnání s náhodným grafem, kde neočekáváme komunitní strukturu.
Modularita je definována jako $$Q = \frac{1}{2m} \sum_{ij} (A_{ij} - P_{ij})\delta(C_i,C_j)$$ kde $P_{ij}$ odpovídá očekávanému počtu hran mezi komunitami $C_i$ a $C_j$ v referenčním náhodném modelu a $\delta(C_i,C_j)$ je indikátor, zda jsou dva clustery stejné.
Pokud zvolíme referenční náhodný model:
Pokud použijeme jako referenční model konfigurační model, můžeme vzorec pro modularitu zjednodušit na $$Q = \sum_{c=1}^{n_c} \left[\frac{m_c}{m} - \left(\frac{d_c}{2m}\right)^2\right],$$ kde $n_c$ a $m_c$ jsou počty vrcholů a hran v komunitě $C_c$ a $d_c$ je souhrnný stupeň vrcholu $c$ v komunitě $C_c$.
Maximalizování modularity vede na $$Q_{max} = \frac{1}{m} \max_{\mathcal{P}} \left\{\sum_{c=1}^{n_c} \left[m_c - \mathbb{E}[m_c]\right]\right\} = - \frac{1}{m} \min_{\mathcal{P}} \left\{\sum_{c=1}^{n_c} \left[m_c - \mathbb{E}[m_c]\right]\right\}$$ což můžeme upravit na $$Q_{max} = -\frac{1}{m} \min_{\mathcal{P}} \left( |\text{Cut}_{\mathcal{P}}| - |\text{ExpCut}_{\mathcal{P}}|\right)$$ kde
Problém rozdělení vrcholů grafu na předem daný počet skupin dané velikosti s cílem minimalizovat počty hran mezi skupinami. Speciální případ je rozdělení grafu na dvě části, kterou řeší následující algoritmus.
Kernighan-Lin
Při dělení vrcholů na dvě části $V_1 \cup V_2 = V(G)$ a použití konfiguračního modelu jakožto referenčního modelu dostáváme $$Q = \frac{1}{4m} \sum_{ij} B_{ij}s_is_j$$ kde $B_{ij} = A_{ij} - P_{ij} = A_{ij} - \frac{k_ik_j}{2m}$ a $s_i = -1$ pro $i \in V_1$ a $s_i = +1$ pro $i \in V_2$.
V maticové formě dostáváme $$Q = \frac{1}{4m}s^T B s.$$
Podobně můžeme vyjádřit velikost řezu $R$ jako $$R = \frac{1}{4} s^T L s,$$ kde $L$ je Laplacova matice definovaná jako $L = D - A$ kde $D$ diagonální matice obsahující stupně vrcholů.
Problém je možné vyřešit
Věta Souvislý graf má největší vlastní číslo matice modularity rovné nule právě tehdy, když se jedná o úplný multipartitní graf.
Věta (Petrovic) Souvislý graf má právě jedno kladné vlastní číslo matice sousednosti právě tehdy když se jedná o úplný multipartitní graf.
Úloha 1: Urči asymptotickou složitost Kerninghan-Li algoritmu.
Úloha 2: Nechť $V(G) = n = n_1 + n_2$. Jaká je (odhadem) složitost řešení problému rozdělení vrcholů na dvě disjunktní množiny o velikostech $n_1$ a $n_2$ hrubou silou? Pro jaké hodnoty $n_1$ a $n_2$ složitost největší?
Úloha 3: Nechť $P$ je graf isomorfní cestě na $n$ vrcholech. Spočítej modularitu pro rozdělení vrcholů $P$ na dvě části, které odpovídá odebrání jedné hrany cesty, tj. dostaneme dvě cesty obsahující po řadě $r$ a $n-r$ vrcholů.