{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Przygotowali\n",
    "Wojciech Jarmosz <br>\n",
    "Michał Kubiak <br>\n",
    "Przemysław Owczarczyk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Temat:\n",
    "Spacery losowe po grafach: algorytm wyszukiwania klastrów.\n",
    "Dla dużych grafów istotną informacją jest wykrycie podgrafów, które są silnie ze sobą powiązane. Za pomocą spacerów losowych po grafach zaprojektuj algorytm, który odkrywa strukturę klastrów w grafie (clustering algorithm). Wykorzystaj swój algorytm do wskazania krytycznych wierzchołków, tj. wierzchołków, których usunięcie rozspójnia graf. Przeanalizuj wariant algorytmu dla grafów skierowanych i grafów nieskierowanych.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wstęp\n",
    "W tym projekcie opiszemy i przedstawimy skuteczny algorytm grupowania oparty na grafach, zwany grupowaniem Markowa. Podobnie jak inne algorytmy klastrowania oparte na grafach i w przeciwieństwie do klastrowania K- średnich, algorytm ten nie wymaga wcześniejszej znajomości liczby klastrów. Algorytm ten jest bardzo popularny w klastrowaniu danych bioinformatycznych, w szczególności do klastrowania sekwencji białek i klastrowania genów. Algorytm ten nadaje się również do obliczeń rozproszonych."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spacery losowe\n",
    "* Spacery losowe są podstawą algorytmu MCL.\n",
    "* Poruszając się losowo od węzła do węzła, istnieje większe prawdopodobieństwo poruszania się wewnątrz klastru, niż przecinania klastrów. Dzieje się tak, ponieważ z definicji klastry są wewnętrznie gęste, a są oddzielone rzadkimi regionami. W grupowaniu grafów gęstość i rzadkość definiuje się jako proporcję szczelin krawędziowych, które mają w sobie krawędzie.\n",
    "* Przeprowadzając spacery losowe, mamy większą szansę na znalezienie trendu gromadzenia się wierzchołków i definicji klastrów w grafie.\n",
    "* Spacery losowe w grafie są obliczane za pomocą łańcuchów Markowa.\n",
    "\n",
    "## Markov Chains\n",
    "\n",
    "* Przykład ilustrujący działania łańcuchów Markova:\n",
    "<img src=\"graph.png\" width=\"350\">\n",
    "\n",
    "* Będąc w węźlę 1 \"random walker\" ma 33% szansy na przejścia do węzłów 2, 3 i 4 oraz 0% do węzłów 5, 6 i 7.\n",
    "* Z węzła 2 ma 25% szansy na przejście do węzłów 1, 3, 4, 5 oraz 0% do węzłów 6 i 7.\n",
    "* Dla tego grafu macierz przejścia wygląda następująco. Można na nią patrzeć jako macierz prawdopodobieństwa, ponieważ każda kolumna sumuję się do 1.\n",
    "<img src=\"matrix.png\" width=\"350\">\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorytm MCL\n",
    "* Korzystając z łańcuchów Markowa, rozważ dla każdej pary wezłów u i v prawdopodobieństwo rozpoczęcia od węzła u i zakończenia w węźle v po przejściu k kroków. Prawdopodobieństwo przejścia z u do v wynosi 1/u.\n",
    "* Znormalizuj macierz do wartości w przedziale <0,1>\n",
    "* Dla tak powstałej macierzy prawdopodobieństw P, obliczamy P(k) mnożąc P przez siebie k razy. (k wynosi zazwyczaj 2 lub 3). Dla początkowych potęg macierzy, poszczególne wagi połączeń będą większe w przypadku wierzchołków znajdujących się w obrębie klastra oraz niższe w przypadku połączeń pomiędzy klastrami.\n",
    "* Wzmocnij obserwację z poprzedniego punktu stosując tzw. inflację z parametrem r, wpływa ona na \"ziarnistość\" klastrów.\n",
    "<img src=\"inflation.png\" width=\"350\">\n",
    "* Powtarzaj kroki 3 i 4 do momentu osiągnięcia ustalonego stanu (konwergancja) - suma wartości w pojedynczej kolumnie sumuje się do tej samej liczby, w praktyce taka własność zachodzi często ale nie zawsze.\n",
    "<img src=\"convergance.png\" style=\"margin-top:10px\" width=\"440\">\n",
    "* Zinterpretuj powstałą macierz w celu odkrycia klastrów. {1}, {2, 4}, {3}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wizualizacja przykładowych klastrów\n",
    "![title](klaster1.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}