\documentclass[utf8x,xcolor=usenames,dvipsnames,svgnames,12pt]{beamer}

\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
\usepackage{graphicx,hyperref,url}
\usepackage{amsmath,amssymb}
\usepackage{ru}
\usepackage{pgfplots}
%\usepackage{parskip}
\setbeamercovered{transparent}
\usetikzlibrary{shapes}


% parskip
\makeatletter
\parskip=0.3\baselineskip \advance\parskip by 0pt plus 2pt
\def\@listI{\leftmargin\leftmargini
   \topsep\z@ \parsep\parskip \itemsep\z@}
\let\@listi\@listI
\@listi
\usepackage{setspace}
\setstretch{1.1}

\graphicspath{{./}{../paper/}}

\newcommand{\sectionWithTitle}[1]{\sectionWithTitleN{#1}{#1}}

\pgfplotscreateplotcyclelist{mystyle}{%
  mark=,RUBlue,densely dashed\\%
  mark=,RURed\\%
}

\newcommand{\trans}{^\text{T}}

\newcommand{\minput}[1]{\input{#1}}
% \newcommand{\minput}[1]{\addplot+[mark=] coordinates{(0,0)};} % DISABLE for speed reasons


\newcommand{\weight}[3][]{E#1(#2,#3)}
\newcommand{\degree}[1]{s_{#1}}
\newcommand{\vol}[1]{v_{#1}}
\newcommand{\within}[1]{w_{#1}}
\newcommand{\exit}[1]{\vol{#1} - \within{#1}}
\newcommand{\Obj}{Q}
\newcommand{\objpart}{q}
\newcommand{\disjointunion}{\uplus}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\RRnonneg}{\RR_{\ge 0}}
\newcommand{\condense}[2]{#1/\mathord{\sim}_#2}
\DeclareMathOperator{\argmax}{argmax}
\newcommand{\ifrac}[2]{#1/(#2)}
\newcommand{\qmod}{\Obj_\text{modularity}}
\newcommand{\qcoco}{\Obj_\text{coco}}
\newcommand{\qfixed}[1][M]{\Obj_\text{$#1$-fixed}}
\newcommand{\qext}[2]{\Obj_\text{$#1$,$#2$}}
\newcommand{\vamount}{\gamma}
\newcommand{\maxfrac}[1]{f_{#1}}
\newcommand{\indicator}{\mathbf{1}}
\newcommand{\agree}{a}
\newcommand{\cf}{\hat{C}}
\newcommand{\femph}[1]{\textbf{#1}}

\setbeamercolor{block title}{bg=RURed}
\setbeamercolor{block title formally}{parent=block title,bg=RUBlue}
\setbeamercolor{block body formally}{parent=normal text,use=block title formally,bg=block title formally.bg!15}
\setbeamerfont{block body formally}{parent=block body,size*={11}{15pt}}
\newenvironment{formally}{\begin{beamerboxesrounded}[upper=block title formally,lower=block body formally,shadow=true]{}\usebeamerfont{block body formally}}{\end{beamerboxesrounded}}

% fleqn:
%\setlength{\mathindent}{0pt}

\tikzset{
  node/.style={circle,draw,inner sep=0,minimum size=6mm},
  snode/.style={circle,draw,inner sep=0,minimum size=4mm},
  lbl/.style={fill=white,inner sep=0.2mm,minimum size=1mm},
}

% % for printing

% =============================================================================

\newcommand{\thetitle}{%
  Axioms for graph clustering%
  %Graph clustering: methods, quality functions and axioms
}
\newcommand{\insertlongtitle}{\Large\thetitle}
\title{\thetitle}

\author{Twan van Laarhoven}

\newcommand{\insertlongauthor}{Twan van Laarhoven}

\institute[Radboud University Nijmegen]{%
  Institute for Computing and Information Sciences\\% -- Intelligent Systems \\
  Radboud University Nijmegen, The Netherlands}

\date[2013-09-09]{9th September 2013}

% =============================================================================
\begin{document}

\begin{frame}%[plain]
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
\end{frame}

% =============================================================================
\section{Introduction}
% \begin{frame}
%   \frametitle{Outline}
%   \tableofcontents[currentsection]
% \end{frame}
\subsection{}

\begin{frame}[t]
  \frametitle{\only<1>{Graphs}\only<2>{Graph clustering}}
  %[plaatje1]
  \begin{center}
  \begin{tikzpicture}
    [baseline=-1mm
    ,scale=1.1
    ,thick]
    \only<1>{
      \draw[color=white] (0.8,0) circle [radius=1.2];
      \draw[color=white] (2.7+1.4,-0.2) circle [y radius=1.4, x radius=2.1,rotate=-10];
      \draw[color=white] (1.2+1.4+0.1,-1.5-0.7-0.05) circle [y radius=0.6,x radius=2,rotate=-3];
      \node[node] (a) at (0,0.2) {a};
      \node[node] (b) at (1.3,0.7) {b};
      \node[node] (c) at (0.9,-0.8) {c};
      \node[node] (e) at (2.7,-0.7) {e};
      \node[node] (d) at (3.1,0.7) {d};
      \node[node] (f) at (2.7+1.5,-0.7-0.1) {g};
      \node[node] (g) at (3.1+1.6,0.7-0.1) {f};
      \node[node] (h) at (1.2,-1.5-0.7) {h};
      \node[node] (i) at (1.2+1.4,-1.5-0.7) {i};
      \node[node] (j) at (1.2+3,-1.6-0.7) {j};
      \node[node] (k) at (2.7+3,-0.7) {k};
    }
    \only<2>{
      \draw[color=RURed] (0.8,0) circle [radius=1.2];
      \draw[color=RUBlue] (2.7+1.4,-0.2) circle [y radius=1.4, x radius=2.1,rotate=-10];
      \draw[color=DarkGreen] (1.2+1.4+0.1,-1.5-0.7-0.05) circle [y radius=0.6,x radius=2,rotate=-3];
      \node[node,fill=RURed!40] (a) at (0,0.2) {a};
      \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
      \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
      \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
      \node[node,fill=RUBlue!40] (d) at (3.1,0.7) {d};
      \node[node,fill=RUBlue!40] (f) at (2.7+1.5,-0.7-0.1) {g};
      \node[node,fill=RUBlue!40] (g) at (3.1+1.6,0.7-0.1) {f};
      \node[node,fill=DarkGreen!40] (h) at (1.2,-1.5-0.7) {h};
      \node[node,fill=DarkGreen!40] (i) at (1.2+1.4,-1.5-0.7) {i};
      \node[node,fill=DarkGreen!40] (j) at (1.2+3,-1.6-0.7) {j};
      \node[node,fill=RUBlue!40] (k) at (2.7+3,-0.7) {k};
    }
    \draw[line width=0.8pt] (a) to (b);
    \draw[line width=1.6pt] (a) to (c);
    \draw[line width=1.6pt] (b) to (c);
    \draw[line width=0.8pt] (d) to (e);
    \draw[line width=0.4pt] (c) to (e);
    \draw[line width=0.8pt] (f) to (g);
    \draw[line width=1.2pt] (d) to (f);
    \draw[line width=0.8pt] (d) to (g);
    \draw[line width=0.8pt] (e) to (f);
    \draw[line width=0.8pt] (c) to (h);
    \draw[line width=1.2pt] (h) to (i);
    \draw[line width=1.6pt] (i) to (j);
    \draw[line width=0.4pt] (e) to (i);
    \draw[line width=0.8pt] (f) to (k);
    \draw[line width=0.4pt] (j) to (k);
  \end{tikzpicture}
  \end{center}
  %
  \vfill
  \only<1>{\begin{formally}
    A symmetric weighted \femph{graph} (or network) is a pair $(V,E)$ of
    \begin{itemize}
      \item a finite set $V$ of \femph{nodes}, and
      \item a function $E : V \times V \to \RRnonneg$ of \femph{edge weights},
    \end{itemize}
    such that $E(i,j) = E(j,i)$ for all $i,j \in V$.%
  \end{formally}}
  \only<2>{\begin{formally}
    A \femph{clustering} $C$ of a graph $G=(V,E)$ is a {partition} of its nodes.
  \end{formally}}
\end{frame}

\begin{frame}
  \frametitle{Applications}
  \begin{itemize}
    \item Social networks
    \item Hyperlinks
    \item Protein interaction networks
    \item References between mathematical theorems
    \item Brain parcellation
  \end{itemize}
\end{frame}

% \begin{frame}
%   \frametitle{Related work}
%   \begin{theorem}[Kleinberg 2002]
%     There is no clustering function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
%   \begin{theorem}[Ackerman, Ben-David 2008]
%     There is a clustering quality function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
% \end{frame}

% \begin{frame}
%   \frametitle{The setting}
%   \begin{itemize}
%     \item Larger weight = stronger connection.
%     \item We allow self loops.
%   \end{itemize}
% \end{frame}
% \begin{frame}
%   \frametitle{The setting (cont.)}
%   \begin{definition}[Clustering]
%     A \emph{clustering} $C$ of a graph $G=(V,E)$ is a {partition} of its nodes.
%     %That is, $\bigcup C = V$ and for all $c_1,c_2 \in C$, $c_1 \cap c_2 \neq \emptyset$ if and only if $c_1 = c_2$.
%   \end{definition}
%   \begin{definition}[Clustering function]
%     A \emph{graph clustering function} $\cf$ is a function from graphs $G$ to clusterings of $G$.
%   \end{definition}
%   \begin{definition}[Objective function]
%     A \emph{graph clustering objective function} $\Obj$ is a function from graphs $G$ and clusterings of $G$ to $\RR$.
%   \end{definition}
%   \begin{itemize}
%     \item Larger objective value = better.
%   \end{itemize}
% \end{frame}

% =============================================================================
%\section{Methods}
% \begin{frame}
%   \frametitle{Outline}
%   \tableofcontents[currentsection]
% \end{frame}
% \subsection{}

% \begin{frame}
%   \frametitle{Louvain method}
%   [plaatje: graph]
%   [plaatje: clusters 1]
%   [plaatje: clusters 2]
% \end{frame}

\begin{frame}
  \frametitle{Clustering methods}
  1. Clustering function\\
  \qquad $\cf : \text{Graph} \to \text{Clustering}$
  \only<1>{\begin{equation*}
      \cf\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node] (a) at (0,0.2) {a};
        \node[node] (b) at (1.3,0.7) {b};
        \node[node] (c) at (0.9,-0.8) {c};
        \node[node] (e) at (2.7,-0.7) {e};
        \node[node] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = 
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
    \end{equation*}}%
  
  \pause
  2. Quality function\\
  \qquad $Q : \text{Graph} \times \text{Clustering} \to \mathbb{R}$
  \only<2>{\begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = 0.1234
    \end{equation*}}%
  
  \pause
  3. Quality relation\\
  \qquad $\cdot\preceq^G\cdot \subseteq \text{Clustering} \times \text{Clustering}$
  \only<3>{\begin{equation*}
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \preceq
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=orange!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RUBlue!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=DarkGreen!40] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
    \end{equation*}}%
  
%   \begin{block}{Things that define clusterings}
%     \begin{tabular}{lll}
%       & Form & Notation \\
%       \cline{2-3}
%       1 & Clustering function & $\cf(G) = \argmax_C Q(G,C)$   \\
%       2 & Objective function  & $Q(G,C)$  \\
%       3 & Objective relation  & $Q(G,C) \ge Q(G,D)$ or $C \ge_{Q}^{G} D$ \\
%     \end{tabular}
%   \end{block}
%   \begin{example}[Scale invariance]
%     \begin{tabular}{lp{0.9\textwidth}}
%       1 & {$\cf(G) = f(\alpha G)$.}  \\
%       2 & {$\Obj(G,C) = \Obj(\alpha G,C)$.} \\
%       3 & if $\Obj(G,C) \ge \Obj(G,D)$ then $\Obj(\alpha G,C) \ge \Obj(\alpha G,D)$. \\
%        % & (or: if $C \ge_{G} D$ then $C \ge_{\alpha G} D$.) \\
%     \end{tabular}\\[2mm]
%     (for all $\alpha > 0$, all graphs $G$, all clustering $C,D$ of $G$.)
%   \end{example}
\end{frame}

\begin{frame}
  \frametitle{Clustering by optimization}
  %Several methods exist:
  \begin{itemize}
    \item Graph clustering is NP hard.
    \item Top down: \\\qquad find best cut and repeat
    \item Bottom up: \\\qquad group nodes together
    \item Simulated annealing %: \\\qquad random local moves
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Louvain method}
  \begin{itemize}
    \setlength{\itemsep}{2mm}
    \item V.D. Blondel, JL. Guillaume, R. Lambiotte, E. Lefebvre \\
          \textit{Fast unfolding of communities in large networks} \\
          J. Stat. Mech. 2008
    \item Best graph clustering method in surveys.
    \item Method:
      \begin{enumerate}
        \item Move nodes into neighboring clusters to improve quality.
        \item Repeat until local maximum.
        \item Now cluster the clusters.
      \end{enumerate}
  \end{itemize}
\end{frame}
\begin{frame}
  \frametitle{Louvain method (example)}
  \begin{tikzpicture}
    % Style
    [scale=2,rotate=10,
     inner sep=0,minimum size=8mm,font=\small,
     h/.style={circle},
     node1/.style={circle,color=RUBlue!20!black,fill=RUBlue!40,draw},
     nodeF/.style={circle,color=RUBlue!20!black,fill=RUBlue!70,draw},
     edge/.style={draw=black,thick},
     gedge/.style={draw=gray},
     lbl/.style={circle,fill=bg,inner sep=0.3pt,minimum size=0}
    ];
    % Nodes
    \node(a1) [h] at (0,0) {};
    \node(a2) [h] at (1,-0.65) {};
    \node(a3) [h] at (1,0.65) {};
    \node(b1) [h] at (3.6,0) {};
    \node(b2) [h] at (3.6-1,-0.65) {};
    \node(b3) [h] at (3.6-1,0.65) {};
    
    % clusterings
    \visible<2-3>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10] (a1) circle (3.5mm);
      \draw[thick,dashed,draw=RURed,fill=RURed!10] (a2) circle (3.5mm);
      \draw[thick,dashed,draw=RURed,fill=RURed!10] (a3) circle (3.5mm);
    }
    \visible<3>{
      \node (a2p) [h,minimum size=14mm] at (a2) {};
      \draw [thick,->,bend right=45] (a1) to (a2p);
    }
    \visible<4>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=8mm] (-0.5,-0.1) -- (-0.2,0.5) -- (1.5,-0.5) -- (1.2,-1.3) -- cycle; % a1,a2
      \draw[thick,dashed,draw=RURed,fill=RURed!10] (a3) circle (3.5mm);
      \node (a12p) [h,minimum size=18mm] at (a2) {};
      \draw [thick,->,bend left=45] (a3) to (a12p);
    }
    \visible<5-6>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=12mm] (-0.6,0.0) -- (1.3,-1.3) -- (1.3,1.3) -- cycle; % a1,a2,a3
    }
    \visible<6>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=12mm] (3.6+0.6,0.0) -- (3.6-1.3,-1.3) -- (3.6-1.3,1.3) -- cycle;
    }
    
    \visible<7-8>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=15mm] (-0.8,0.0) -- (1.45,-1.6) -- (1.45,1.6) -- cycle;
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=15mm] (3.6+0.8,0.0) -- (3.6-1.45,-1.6) -- (3.6-1.45,1.6) -- cycle;
    }
    \visible<8>{
      \node (ap) [h,minimum size=13mm] at (a2) {};
      \node (bp) [h,minimum size=21mm] at (b2) {};
      \draw [thick,->,bend right=45] (ap) to (bp);
    }
    \visible<9>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=14mm] (-0.8,0.0) -- (1.0,-1.3) -- (3.6-1.0,-1.3) -- (3.6+0.8,0.0) -- (3.6-1.0,1.3) -- (1.0,1.3) -- cycle;
    }
    \visible<10>{
      \draw[thick,dashed,draw=RURed,fill=RURed!10, rounded corners=12mm] (-0.6,0.0) -- (0.9,-1.1) -- (3.6-0.9,-1.1) -- (3.6+0.6,0.0) -- (3.6-0.9,1.1) -- (0.9,1.1) -- cycle;
    }
    
    \visible<7-9>{
      % super nodes
      \draw[draw=RUBlue!20!black,fill=RUBlue!20, rounded corners=12mm] (-0.6,0.0) -- (1.3,-1.3) -- (1.3,1.3) -- cycle; % a1,a2,a3
      \visible<8>{
      \draw[draw=RUBlue!20!black,fill=RUBlue!50, rounded corners=12mm] (-0.6,0.0) -- (1.3,-1.3) -- (1.3,1.3) -- cycle; % a1,a2,a3
      }
      \draw[draw=RUBlue!20!black,fill=RUBlue!20, rounded corners=12mm] (3.6+0.6,0.0) -- (3.6-1.3,-1.3) -- (3.6-1.3,1.3) -- cycle;
    }
    
    % drawing nodes
    \node [node1] at (a1) {};
    \node [node1] at (a2) {};
    \node [node1] at (a3) {};
    \visible<3>{\node [nodeF] at (a1) {};}
    \visible<4>{\node [nodeF] at (a3) {};}
    
    % Edges
    \draw [edge] (a1) to (a2);
    \draw [edge] (a1) to (a3);
    \draw [edge] (a2) to (a3);
    
    \draw [gedge] (a1) to +(-0.75,0.45);
    \draw [gedge] (a1) to +(-0.75,-0.45);
    \draw [gedge] (a2) to +(-0.2,-0.8);
    \draw [gedge] (a3) to +(-0.4,0.75);
    \draw [gedge] (a3) to +(+0.3,0.75);
    
    \visible<1-5>{
      \draw [gedge] (a2) to (b2);
      \draw [gedge] (a3) to (b3);
    }
    \visible<6->{
      \node [node1] at (b1) {};
      \node [node1] at (b2) {};
      \node [node1] at (b3) {};
      
      \draw [edge] (a2) to (b2);
      \draw [edge] (a3) to (b3);
      
      \draw [edge] (b1) to (b2);
      \draw [edge] (b1) to (b3);
      \draw [edge] (b2) to (b3);
      
      \draw [gedge] (b1) to +(+0.8,0);
      \draw [gedge] (b2) to +(+0.2,-0.8);
    }
  \end{tikzpicture}
\end{frame}

\begin{frame}
  \frametitle{Some quality functions}
  \begin{itemize}
    \item Connected components
          %\\\quad$\displaystyle Q(G,C) = \indicator[C are connected components of G]$.
    \item Total weight of within cluster edges
          \\\quad$\displaystyle Q(G,C) %= \sum_{i,j\in V} E(i,j) \indicator[i \sim_C j]
                                        = \sum_{c\in C} w_c$
    %\item Total weight of within cluster edges
    \item Modularity
          \\\quad$\displaystyle Q(G,C) = \sum_{c\in C} \bigl( w_c/v_V - (v_c/v_V)^2\bigr)$
    %\item Parameterized families
    %      \\\quad$\displaystyle Q^\gamma_\text{RB}(G,C) = \sum_{c\in C} \bigl( w_c/v_V - \gamma(v_c/v_V)^2\bigr)$
    \item Many more
          \\\quad$\displaystyle Q(G,C) = \sum_{c\in C} - w_c \log (v_c/v_V)$
          \\\qquad$\cdots$
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Families of quality functions}
  \begin{itemize}
    \item Connected components with threshold
          %\\\quad$\displaystyle Q(G,C) = \indicator[C are connected components of G]$.
    \item Total weight of within cluster edges with penalty
          \\\quad$\displaystyle Q(G,C) = \sum_{c\in C} w_c - \alpha|C| $%= \sum_{i,j\in V} E(i,j) \indicator[i \sim_C j] - \alpha |C|$
    %\item Total weight of within cluster edges
    \item Modularity
          \\\quad$\displaystyle Q^\gamma_\text{RB}(G,C) = \sum_{c\in C} \bigl( w_c/v_V - \gamma(v_c/v_V)^2\bigr)$
    \item Many more
          \\\quad$\displaystyle Q(G,C) = \sum_{c\in C} - w_c \log (v_c/\alpha)$
          \\\qquad$\cdots$
  \end{itemize}
\end{frame}

% 
% \begin{frame}
%   \frametitle{Clustering by optimization}
%   $\cf$
%   $\Obj$
%   $\Obj\le$
% \end{frame}

% \begin{frame}
%   \frametitle{Families}
%   $\cf$
%   $\Obj$
%   $\Obj\le$
% \end{frame}


% =============================================================================
\section{Axioms}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{Why axioms?}
%   \begin{theorem}[Kleinberg 2002]
%     There is no clustering function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
%   \begin{theorem}[Ackerman, Ben-David 2008]
%     There is a clustering quality function that is permutation invariant, scale invariant, monotonic and rich.
%   \end{theorem}
  \begin{itemize}
    \item Which of these quality functions are good?
    \item There is no good definition of clustering.
    \item Can we formalize our intuition?
    \item Previous work is about distance based clustering (hierarchical clustering, K-means, etc.)
    \item What about graphs?
  \end{itemize}
\end{frame}

\begin{frame}[t]
  \frametitle{Axiom 1: Scale invariance}
  \vspace*{8mm}
  Intuition: The absolute value of the edge weights shouldn't matter.
  %
  %\\[5mm]
  \vfill
  %\begin{overlayarea}{\textwidth}{0.4\textheight}
    \only<1>{\begin{equation*}
      \cf\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node] (a) at (0,0.2) {a};
        \node[node] (b) at (1.3,0.7) {b};
        \node[node] (c) at (0.9,-0.8) {c};
        \node[node] (e) at (2.7,-0.7) {e};
        \node[node] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = 
      \cf\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node] (a) at (0,0.2) {a};
        \node[node] (b) at (1.3,0.7) {b};
        \node[node] (c) at (0.9,-0.8) {c};
        \node[node] (e) at (2.7,-0.7) {e};
        \node[node] (d) at (3,0.7) {d};
        \draw[line width=2*0.8pt] (a) to (b);
        \draw[line width=2*1.6pt] (a) to (c);
        \draw[line width=2*1.6pt] (b) to (c);
        \draw[line width=2*0.8pt] (d) to (e);
        \draw[line width=2*0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}}%
    \only<2-3>{\begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=0.8pt] (a) to (b);
        \draw[line width=1.6pt] (a) to (c);
        \draw[line width=1.6pt] (b) to (c);
        \draw[line width=0.8pt] (d) to (e);
        \draw[line width=0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
      = \visible<3>{\alpha}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=2*0.8pt] (a) to (b);
        \draw[line width=2*1.6pt] (a) to (c);
        \draw[line width=2*1.6pt] (b) to (c);
        \draw[line width=2*0.8pt] (d) to (e);
        \draw[line width=2*0.4pt] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}}%
    \only<4>{\begin{equation*}
      \begin{array}{ccc}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,line width=0.6pt]
        \node[snode,fill=RURed!40] (a) at (0,0.2) {};
        \node[snode,fill=RURed!40] (b) at (1.3,0.7) {};
        \node[snode,fill=RURed!40] (c) at (0.9,-0.8) {};
        \draw[line width=0.8*0.8pt] (a) to (b);
        \draw[line width=0.8*1.6pt] (a) to (c);
        \draw[line width=0.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
      &\ge&
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,line width=0.6pt]
        \node[snode,fill=DarkGreen!40] (a) at (0,0.2) {};
        \node[snode,fill=RUBlue!40] (b) at (1.3,0.7) {};
        \node[snode,fill=purple!40] (c) at (0.9,-0.8) {};
        \draw[line width=0.8*0.8pt] (a) to (b);
        \draw[line width=0.8*1.6pt] (a) to (c);
        \draw[line width=0.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)\\
      &\Updownarrow&\\
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,line width=0.6pt]
        \node[snode,fill=RURed!40] (a) at (0,0.2) {};
        \node[snode,fill=RURed!40] (b) at (1.3,0.7) {};
        \node[snode,fill=RURed!40] (c) at (0.9,-0.8) {};
        \draw[line width=1.8*0.8pt] (a) to (b);
        \draw[line width=1.8*1.6pt] (a) to (c);
        \draw[line width=1.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
      &\ge&
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,line width=0.6pt]
        \node[snode,fill=DarkGreen!40] (a) at (0,0.2) {};
        \node[snode,fill=RUBlue!40] (b) at (1.3,0.7) {};
        \node[snode,fill=purple!40] (c) at (0.9,-0.8) {};
        \draw[line width=1.8*0.8pt] (a) to (b);
        \draw[line width=1.8*1.6pt] (a) to (c);
        \draw[line width=1.8*0.4pt] (b) to (c);
      \end{tikzpicture}
      \right)
      \end{array}
    \end{equation*}}%
    \only<5>{\begin{formally}
      A quality function $\Obj$ is \femph{scale invariant} if
      \begin{itemize}
        \item for all graphs $G=(V,E)$,
        \item all constants $\alpha > 0$,
        \only<2-3>{\item all clusterings $C$ of $G$,}
        \only<4>{\item all clusterings $C_1,C_2$ of $G$,}
      \end{itemize}
      \only<1>{ $\cf(G) = \cf(\alpha G)$. }%
      \only<2>{ $\Obj(G,C) = \Obj(\alpha G,C)$. }%
      \only<3>{ $\Obj(G,C) = \alpha \Obj(\alpha G,C)$ ??? }%
      \only<4->{ $\Obj(G,C_1) \ge \Obj(G,C_2)$ if and only if $\Obj(\alpha G,C_1) \ge \Obj(\alpha G,C_2)$. }%
    \end{formally}}
  %\end{overlayarea}
\end{frame}

\begin{frame}[t]
  %\frametitle{Basic axioms}
  \frametitle{Axiom 2: Permutation invariance}
  %\begin{block}{Intuition}
  \vspace*{8mm}
  Intuition: Only the edge weights should matter.
  
  %\vspace*{8mm}
  \vfill
  %\end{block}
  %\begin{example}
  \only<1>{
    \begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[] (a) to (b);
        \draw[ultra thick] (a) to (c);
        \draw[] (b) to (c);
        \draw[ultra thick] (d) to (e);
        \draw[] (c) to (e);
      \end{tikzpicture}
      \right)
      = 
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=teal!40] (a) at (0.1,0.2) {z};
        \node[node,fill=teal!40] (b) at (-0.9,-0.8) {v};
        \node[node,fill=teal!40] (c) at (-1.3,0.7) {y};
        \node[node,fill=purple!40] (e) at (-2.8,0.8) {x};
        \node[node,fill=purple!40] (d) at (-2.7,-0.8) {u};
        \draw[] (a) to (b);
        \draw[ultra thick] (a) to (c);
        \draw[] (b) to (c);
        \draw[ultra thick] (d) to (e);
        \draw[] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}
  }%
  \only<2>{
  \begin{formally}
    A quality function $\Obj$ is \femph{permutation invariant} if
       \[\Obj(G,C) = \Obj(f(G),f(C)).\]
    for all 
    \begin{itemize}
    \item graphs $G=(V,E)$ and
    \item all isomorphisms $f : V \to V'$,
    \end{itemize}%\\[2mm]
    where $f$ is extended to graphs and clusterings in the obvious way.
  \end{formally}}
\end{frame}

\begin{frame}
  \frametitle{Axiom 3: Richness}
  Intuition:
  \begin{itemize}\item All clusterings must be possible.
  \end{itemize}
  So,
  \begin{itemize}
    \item no trivial quality functions.
    \item no fixed number of clusters.
  \end{itemize}
  \vfill
  \begin{formally}
    A quality function $\Obj$ is \femph{rich} if
    \begin{itemize}
      \item for all sets $V$ and
      \item all partitions $C^*$ of $V$,
    \end{itemize}
    there is
    \begin{itemize}
      \item a graph $G=(V,E)$
      \item such that $C^*$ is the optimal clustering of $G$.
    \end{itemize}
  \end{formally}
\end{frame}

\begin{frame}[t]
  \frametitle{Axiom 4: Monotonicity}
  \vspace*{8mm}
  Intuition:
  Adding edges inside a cluster or removing edges between clusters does not make the clustering worse.
  \vfill
  
    \only<1>{\begin{equation*}
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[line width=1.8pt] (a) to (b);
        \draw[line width=1.8pt] (a) to (c);
        \draw[] (b) to (c);
        \draw[ultra thick] (d) to (e);
        \draw[line width=0.5pt] (c) to (e);
      \end{tikzpicture}
      \right)
      \ge
      Q\left(
      \begin{tikzpicture}
        [baseline=-1mm
        ,scale=0.8
        ,thick]
        \node[node,fill=RURed!40] (a) at (0,0.2) {a};
        \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
        \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
        \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
        \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
        \draw[] (a) to (b);
        \draw[very thick] (a) to (c);
        \draw[] (b) to (c);
        \draw[very thick] (d) to (e);
        \draw[line width=1.8pt] (c) to (e);
      \end{tikzpicture}
      \right)
    \end{equation*}}
    \only<2>{%
      \begin{formally}
        Let
        \begin{itemize}
        \item $G=(V,E)$ and $G'=(V,E')$ be graphs, and
        \item $C$ be a clustering of $G$ and $G'$.
        \end{itemize}
        Then $G'$ is a \femph{$C$-consistent improvement of $G$} if
        \begin{itemize}
        \item $\weight[']{i}{j} \ge \weight{i}{j}$ for all $i \sim_C j$ and
        \item $\weight[']{i}{j} \le \weight{i}{j}$ for all $i \not\sim_C j$.
        \end{itemize}
      \end{formally}}
    \only<3>{\begin{formally}
        A quality function $\Obj$ is \femph{monotonic} if
        \par\qquad $\Obj(G',C) \ge \Obj(G,C).$\par
        for all 
        \begin{itemize}
        \item graphs $G$,
        \item all clusterings $C$ of $G$ and
        \item all $C$-consistent improvements $G'$ of $G$.
        \end{itemize}
      \end{formally}
    }
\end{frame}

%--------------------

%\subsection{Locality}
\newcommand<>{\raisebox}[2]{%
 \alt#3\beameroriginal{\raisebox{#1}{#2}}{#2}%
}

\begin{frame}[t]
  \frametitle{Axiom 5: Locality}
  \vspace*{5mm}
  Intuition: Local changes should have local effects.
  \vfill
  
  \only<1>{\begin{equation*}
    Q\left(
    \begin{tikzpicture}
      [baseline=-1mm
      ,scale=0.8
      ,thick]
      \node[node,fill=RURed!40] (a) at (0,0.2) {a};
      \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
      \node[node,fill=purple!40] (c) at (0.9,-0.8) {c};
      \node[node,fill=DarkGreen!40] (e) at (2.7,-0.7) {e};
      \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
      \draw[line width=1.8pt] (a) to (b);
      \draw[line width=1.8pt] (a) to (c);
      \draw[] (b) to (c);
      \draw[ultra thick] (d) to (e);
    \end{tikzpicture}
    \right)
    =
    Q\left(
    \begin{tikzpicture}
      [baseline=-1mm
      ,scale=0.8
      ,thick]
      \node[node,fill=RURed!40] (a) at (0,0.2) {a};
      \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
      \node[node,fill=purple!40] (c) at (0.9,-0.8) {c};
      \draw[line width=1.8pt] (a) to (b);
      \draw[line width=1.8pt] (a) to (c);
      \draw[] (b) to (c);
    \end{tikzpicture}
    \right)
    +
    Q\left(
    \begin{tikzpicture}
      [baseline=-1mm
      ,scale=0.8
      ,thick]
      \node[node,fill=DarkGreen!40] (e) at (2.7,-0.7) {e};
      \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
      \draw[ultra thick] (d) to (e);
    \end{tikzpicture}
    \right)
  \end{equation*}}
  \only<2>{\begin{equation*}
      % {a,b,c}
      \begin{array}{ccc}
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.2) {a};
          \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
          \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
          \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
          \draw[] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[] (b) to (c);
          \draw[ultra thick] (d) to (e);
          \draw[] (c) to (e);
        \end{tikzpicture}
        \right)
        & \ge &
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.2) {a};
          \node[node,fill=purple!40] (b) at (1.3,0.7) {b};
          \node[node,fill=orange!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
          \node[node,fill=RUBlue!40] (d) at (3,0.7) {d};
          \draw[] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[] (b) to (c);
          \draw[ultra thick] (d) to (e);
          \draw[] (c) to (e);
        \end{tikzpicture}
        \right)
        \\
         & \Updownarrow & \\
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.2) {a};
          \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
          \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
          \node[node,fill=DarkGreen!40] (d) at (3,0.7) {d};
          \draw[] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[] (b) to (c);
          \draw[ultra thick] (d) to (e);
          \draw[] (c) to (e);
        \end{tikzpicture}
        \right)
        & \ge &
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.2) {a};
          \node[node,fill=purple!40] (b) at (1.3,0.7) {b};
          \node[node,fill=orange!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=RUBlue!40] (e) at (2.7,-0.7) {e};
          \node[node,fill=DarkGreen!40] (d) at (3,0.7) {d};
          \draw[] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[] (b) to (c);
          \draw[ultra thick] (d) to (e);
          \draw[] (c) to (e);
        \end{tikzpicture}
        \right)
      \end{array}
    \end{equation*}}
  \only<3>{\begin{equation*}
      % {a,b,c}
      \begin{array}{ccc}
        % a
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.62
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.2) {a};
          \node[node,fill=RURed!40] (b) at (1.3,0.7) {b};
          \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=gray!40,draw=gray] (d) at (-1.2,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=gray!40,draw=gray] (a1) at (-1.3,0.7) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (f) to (e);
          \draw[draw=gray] (d) to (a1);
        \end{tikzpicture}
        \right)
        & \ge &
        Q\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.62
          ,thick]
          \node[node,fill=purple!40] (a) at (0,0.2) {a};
          \node[node,fill=RUBlue!40] (b) at (1.3,0.7) {b};
          \node[node,fill=purple!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=gray!40,draw=gray] (d) at (-1.2,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=white!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=gray!40,draw=gray] (a1) at (-1.3,0.7) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (f) to (e);
          \draw[draw=gray] (d) to (a1);
        \end{tikzpicture}
        \right)
        \\
         & \Updownarrow & \\
        %\rotatebox{90}{$\le$} & \Longrightarrow & \rotatebox{90}{$\le$} \\
        Q\left(
        \begin{tikzpicture}
          [baseline=-4.2mm
          ,scale=0.62
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,0.5) {a};
          \node[node,fill=RURed!40] (b) at (1.5,0.7) {b};
          \node[node,fill=RURed!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=green!40!gray!40,draw=gray] (d) at (-1,-0.7) {$\cdot$};
          \node[node,fill=black!40!gray!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (a2) at (4,0.0) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a3) at (0.6,-1.9) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a4) at (3,-1.9) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (a2) to (e);
          \draw[draw=gray,very thick] (a2) to (f);
          \draw[draw=gray] (d) to (a3);
          \draw[draw=gray] (e) to (a3);
          \draw[draw=gray,very thick] (a4) to (a3);
          \draw[draw=gray] (a4) to (a2);
        \end{tikzpicture}
        \right)
        & \ge &
        %\delimitershortfall=2pt
        Q\left(
        \begin{tikzpicture}
          [baseline=-4.2mm
          ,scale=0.62
          ,thick]
          \node[node,fill=purple!40] (a) at (0,0.5) {a};
          \node[node,fill=RUBlue!40] (b) at (1.5,0.7) {b};
          \node[node,fill=purple!40] (c) at (0.9,-0.8) {c};
          \node[node,fill=green!40!gray!40,draw=gray] (d) at (-1,-0.7) {$\cdot$};
          \node[node,fill=black!40!gray!40,draw=gray] (e) at (2.7,-0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (f) at (3,0.7) {$\cdot$};
          \node[node,fill=yellow!40!gray!40,draw=gray] (a2) at (4,0.0) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a3) at (0.6,-1.9) {};
          \node[node,fill=green!40!gray!40,draw=gray] (a4) at (3,-1.9) {};
          \draw[line width=0.5] (a) to (b);
          \draw[ultra thick] (a) to (c);
          \draw[line width=0.5] (b) to (c);
          \draw[very thick] (d) to (a);
          \draw[] (d) to (c);
          \draw[line width=1.8pt] (c) to (e);
          \draw[] (f) to (b);
          \draw[draw=gray] (a2) to (e);
          \draw[draw=gray,very thick] (a2) to (f);
          \draw[draw=gray] (d) to (a3);
          \draw[draw=gray] (e) to (a3);
          \draw[draw=gray,very thick] (a4) to (a3);
          \draw[draw=gray] (a4) to (a2);
        \end{tikzpicture}
        \right)
      \end{array}
    \end{equation*}}
   \only<4>{%
%     \begin{definition}[agreement]
%       Let
%       \begin{itemize}
%         \item $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be two graphs and
%         \item $V_\agree \subseteq V_1 \cap V_2$.
%       \end{itemize}
%       The graphs \emph{agree on $V_\agree$} if
%       {$E_1(i,j) = E_2(i,j)$} for all $i,j \in V_\agree$.
%     \end{definition}
%     \pause
    \begin{formally}
      Two graphs $G_1$ and $G_2$ \femph{agree on the neighborhood of\\ $V_\agree \subseteq V_1 \cap V_2$} if
      \\[2mm]
      \begin{tabular}{@{\quad}l@{ }l}
      $E_1(i,j) = E_2(i,j)$ &for all $i \in V_\agree$, $j \in V_1 \cap V_2$, and \\
      $E_1(i,j) = 0$ &for all $i \in V_\agree$, $j \in V_1 \setminus V_2$, and \\
      $E_2(i,j) = 0$ &for all $i \in V_\agree$, $j \in V_2 \setminus V_1$.
      \end{tabular}
      \\[2mm]
      So, for nodes/clusters in $V_\agree$, all incident edges are the same.
    \end{formally}
  }
  \only<5>{\begin{formally}
    A quality function $\Obj$ is \femph{local} if
    \begin{itemize}
    \item for all graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$\\ that agree on a set $V_\agree$ and its neighborhood,
    \item for all clusterings $C_1$ of $V_1 \setminus V_\agree$,\\ $C_2$ of $V_2 \setminus V_\agree$ and\\ $C_\agree,D_\agree$ of $V_\agree$.
    %\begin{tabular}{@{}l@{ }l}$C_\agree,D_\agree$ &of $V_\agree$,\\ $C_1$ &of $V_1 \setminus V_\agree$ and\\ $C_2$ &of $V_2 \setminus V_\agree$,\end{tabular}
    \end{itemize}
    \vspace*{2mm}
    \begin{tabular}{@{}l@{ }l@{}}
    if   &$\Obj(G_1, C_\agree \cup C_1) \ge \Obj(G_1, D_\agree \cup C_1)$\\
    then &$\Obj(G_2, C_\agree \cup C_2) \ge \Obj(G_2, D_\agree \cup C_2)$.
    \end{tabular}
  \end{formally}}
\end{frame}

% ----------------------------
\begin{frame}
  \frametitle{Interlude: Related work}
  \begin{theorem}[Kleinberg 2002]
    There is \emph{no} clustering function that is permutation invariant, scale invariant, monotonic and rich.
  \end{theorem}
  \vspace*{5mm}
  \begin{theorem}[Ackerman, Ben-David 2008]
    There is a clustering quality function that is permutation invariant, scale invariant, monotonic and rich.
  \end{theorem}
\end{frame}

\begin{frame}
  \frametitle{Discontinuity is magic}
  %\transdissolve<2,3>
  \begin{theorem}
    There \emph{is} a graph clustering function that is scale invariant, permutation invariant, monotonic, rich and local.
  \end{theorem}
  \pause
  \vspace*{8mm}
  \begin{formally}
    \begin{equation*}
      \cf_\text{coco}(G) = \text{the connected components of $G$}
    \end{equation*}
    \begin{equation*}
     Q_\text{coco}(G,C) = \indicator[\text{$C$ are the connected components of $G$}]
    \end{equation*}
  \end{formally}
  %\pause
  %\begin{block}{Huh!?!?}
    \begin{itemize}
      \item Doesn't this contradict Kleinberg's theorem?
      \item No: edge weight 0 = distance $\infty$.
      \item Connected components are unstable.
    \end{itemize}
  %\end{block}
\end{frame}
\begin{frame}
  \frametitle{Axiom 6: continuity}
  Intuition:
  \begin{itemize}
    \item Don't allow such unstable quality functions.
    %\item A small change in edge weights should lead to only a small change in quality.
  \end{itemize}
  \vfill

%   \begin{block}{Why I don't like it}
%     \begin{itemize}
%       \item Adding/removing an edge with tiny weight $\epsilon$ changes the graph slightly, but the clustering completely.
%       \item Possibly unstable.
%       \item So don't allow it.
%     \end{itemize}
%   \end{block}
  \begin{formally}
    A quality function $\Obj$ is \femph{continuous} if for every graph $G$ and every clustering $C$ of $G$, a sufficiently small change in the edge weights leads to a small change in the objective value.
    %$\Obj$ is \fempf{continuous} if for every $\epsilon > 0$ and every graph $G=(V,E)$ there exists a $\delta > 0$ such that for all graphs $G'=(V,E')$, if $E(i,j) - \delta < E'(i,j) < E(i,j) + \delta$ for all nodes $i$ and $j$, then $\Obj(G',C) - \epsilon < \Obj(G,C) < \Obj(G',C) + \epsilon$ for all clusterings $C$ of $G$.
  \end{formally}
%   \begin{example}
%     \begin{equation*}
%       Q(G+\epsilon,C) \approx Q(G,C)
%     \end{equation*}
%   \end{example}
\end{frame}



% =============================================================================
\section{Modularity}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{Modularity}
  Intuition:
  \begin{itemize}
    \item Balance within cluster edges against cluster volume.
  \end{itemize}
  \vfill
  
  \begin{formally}
%In this expression $v_c = \sum_{i \in c}\sum_{j \in V} \weight{i}{j}$ is the volume of a cluster, while $w_c = \sum_{i,j \in c} \weight{i}{j}$ is the within cluster weight. $v_V$ is the volume of the entire graph. Then
    \begin{equation*}
      \qmod(G,C) = \sum_{c \in C}\biggl( \frac{\within{c}}{\vol{V}} - \Bigl( \frac{\vol{c}}{\vol{V}} \Bigr)^2 \biggr).
    \end{equation*}
    
    Where\\
    \begin{tabular}{@{\quad}ll}
      $v_c = \displaystyle\sum_{i \in c}\sum_{j \in V} \weight{i}{j}$ & volume of cluster \\
      $w_c = \displaystyle\sum_{i \in c}\sum_{j \in c} \weight{i}{j}$ & within cluster weight.
    \end{tabular}
  \end{formally}
\end{frame}

\begin{frame}
  \frametitle{Properties}
  The obvious:
  \begin{itemize}
    \item Modularity is permutation invariant.
    \item Modularity is scale invariant.
    \item Modularity is continuous.
  \end{itemize}
  The less obvious:
  \begin{itemize}
    \item Modularity is rich.
  \end{itemize}
  The bad:
  \begin{itemize}
    \item Modularity is \emph{not} local.
    \item Modularity is \emph{not} monotonic.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Modularity is not local}
    \begin{align*}
      %\hspace*{-5mm}
      &
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=RURed!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[line width=1.2] (a) to node[above] {2} (b);
          \draw[line width=0.6] (b) to node[above] {1} (c);
          \draw[line width=1.2] (c) to node[above] {2} (d);
        \end{tikzpicture}
      \right) = 0.3
    %\end{equation*}
    %\begin{equation*}
    %  \hspace*{-5mm}
    \\&
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=RURed!40] (b) at (2,-0) {b};
          \node[node,fill=RURed!40] (c) at (2*2,-0) {c};
          \node[node,fill=RURed!40] (d) at (3*2,-0) {d};
          \draw[line width=1.2] (a) to node[above] {2} (b);
          \draw[line width=0.6] (b) to node[above] {1} (c);
          \draw[line width=1.2] (c) to node[above] {2} (d);
        \end{tikzpicture}
        \right) = 0
    %\end{equation*}
    %\begin{equation*}
    %  \hspace*{-5mm}
    \\&
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=RURed!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \node[node,fill=DarkGreen!40] (x) at (4*2,-0) {x};
          \node[node,fill=DarkGreen!40] (y) at (5*2,-0) {y};
          \draw[line width=1.2] (a) to node[above] {2} (b);
          \draw[line width=0.6] (b) to node[above] {1} (c);
          \draw[line width=1.2] (c) to node[above] {2} (d);
          \draw[line width=2] (x) to node[above] {20} (y);
        \end{tikzpicture}
      \right) = 0.3
    %\end{equation*}
    %\begin{equation*}
    %  \hspace*{-5mm}
    \\&
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.6
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=RURed!40] (b) at (2,-0) {b};
          \node[node,fill=RURed!40] (c) at (2*2,-0) {c};
          \node[node,fill=RURed!40] (d) at (3*2,-0) {d};
          \node[node,fill=DarkGreen!40] (x) at (4*2,-0) {x};
          \node[node,fill=DarkGreen!40] (y) at (5*2,-0) {y};
          \draw[line width=1.2] (a) to node[above] {2} (b);
          \draw[line width=0.6] (b) to node[above] {1} (c);
          \draw[line width=1.2] (c) to node[above] {2} (d);
          \draw[line width=2] (x) to node[above] {20} (y);
        \end{tikzpicture}
        \right) = 0.32
    \end{align*}
\end{frame}

\begin{frame}
  \frametitle{Modularity is not monotonic}
  %Modularity is not monotonic
  %\begin{proof}[]
    \begin{align*}
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=DarkGreen!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[] (a) to node[above] {1} (b);
          %\draw[] (b) to node[above] {1} (c);
          \draw[] (c) to node[above] {1} (d);
        \end{tikzpicture}
      \right) &= 0.125 \\
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=DarkGreen!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[line width=0.1*0.8] (a) to node[above] {0.1} (b);
          %\draw[] (b) to node[above] {1} (c);
          \draw[] (c) to node[above] {1} (d);
        \end{tikzpicture}
      \right) &= 0.079 \\
      \qmod\left(
        \begin{tikzpicture}
          [baseline=-1mm
          ,scale=0.8
          ,thick]
          \node[node,fill=RURed!40] (a) at (0,-0) {a};
          \node[node,fill=DarkGreen!40] (b) at (2,-0) {b};
          \node[node,fill=RUBlue!40] (c) at (2*2,-0) {c};
          \node[node,fill=RUBlue!40] (d) at (3*2,-0) {d};
          \draw[] (a) to node[above] {1} (b);
          %\draw[] (b) to node[above] {1} (c);
          \draw[line width=2] (c) to node[above] {10} (d);
        \end{tikzpicture}
      \right) &= 0.079
    \end{align*}
  %\end{proof}
\end{frame}

% =============================================================================
% \section{Adaptive Modularity}
% \begin{frame}
%   \frametitle{Outline}
%   \tableofcontents[currentsection]
% \end{frame}
% \subsection{}

\begin{frame}
  \frametitle{Idea 1: Fix the scale}
  
  \begin{formally}
    \begin{equation*}
      \qfixed(G,C) = \sum_{c \in C}\biggl( \frac{\within{c}}{M} - \Bigl( \frac{\vol{c}}{M} \Bigr)^2 \biggr)
    \end{equation*}
  \end{formally}
  \vspace*{5mm}
  Is it monotonic?
  \vspace*{5mm}
  
  \pause
  Take $v_c = w_c + b_c$ (within + between)
  \begin{equation*}
    \frac{\partial \qfixed(G,C)}{\partial w_c}
    %= 1/M - 2 v_c / M^2.
    = \frac{1}{M} - \frac{2 w_c + 2 b_c }{M^2}.
  \end{equation*}
  This is negative when $2 v_c > M$, so not monotonic.
\end{frame}

\begin{frame}
  \frametitle{Idea 2: Add some $v_c$ to the denominator}
  %Idea 2: Add some $v_c$ to the denominator
  \begin{formally}
    \begin{equation*}
      \qext{M}{\gamma}(G,C) = \sum_{c \in C}\biggl( \frac{\within{c}}{M + \vamount\vol{c}} - \Bigl( \frac{\vol{c}}{M + \vamount\vol{c}} \Bigr)^2 \biggr)
  .
    \end{equation*}
  \end{formally}
  \pause
  \vspace*{5mm}
  %\begin{block}{Theorem}
  Adaptive scale modularity is
  \begin{itemize}
    \item permutation invariant, continuous and local.
    \item 
     monotonic for all $M \ge 0$ and $\vamount \ge 2$.
  %\end{block}
  %\pause
  %\begin{block}{Theorem}
    \item 
     rich for all $M \ge 0$ and $\vamount \ge 1$.
  %\end{block}
  %\pause
  %\begin{block}{Theorem}
    \item 
     scale invariant for $M=0$.
  %\end{block}
  \end{itemize}
\end{frame}

\newenvironment{cequation*}{\\[2mm]\qquad$\displaystyle}{$\\[2mm]}

\begin{frame}
  \frametitle{Related quality functions}
  \begin{itemize}
    \item When $\gamma = 0$, we get fixed scale modularity.
          \\Equivalent to other modularity variants.
    \item When $\gamma = 0$ and $M = v_V$, we get modularity.
    \item When $M = 0$ we get
    %\begin{equation*}
    \begin{cequation*}
      \qext{0}{\gamma}(G,C) \propto \sum_{c \in C}\Bigl( \frac{\within{c}}{\vol{c}} - \frac1\vamount\Bigr),
    \end{cequation*}
    i.e. normalized cut.
    \item When $M \to \infty$ we get
    \begin{cequation*}
      \qext{\infty}{\gamma}(G,C) \propto \sum_{c \in C} \within{c},
    \end{cequation*}
    i.e. unnormalized cut.
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Adaptive Scale Modularity behavior}
  Take a simple graph: 
    \begin{tikzpicture}[scale=1,baseline=-1mm]
      \node[node] (a) at (0,0) {$w$};
      \node[node] (b) at (1.5,0) {$w$};
      \draw[] (a) to node[above] {$b$} (b);
    \end{tikzpicture}
  \begin{itemize}
    \item Two cliques each with $w$ within weight
    \item Connected by edges with total weight $b$.
    \item Total volume $2w + 2b$.
    \item What is the behavior of adaptive scale modularity?
  \end{itemize}
\end{frame}
\begin{frame}
  \begin{center}
    \begin{minipage}[c]{0.78\linewidth}
      \includegraphics[width=1\linewidth]{plot-qext-wb}
    \end{minipage}\hspace*{2mm}
    \begin{minipage}[c]{0.15\linewidth}
      \def\legendscale{0.7}
      Legend:
      %\setlength{\mathindent}{0pt}
      \begin{align*}
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \path[fill=white] (-0.5,-0.5) rectangle (0.5,0.5);
          \node[node,fill=white] (1) at (0,0) {1};
        \end{tikzpicture}}
        &=
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \node[node,fill=RURed!40] (a) at (0,0) {};
          \node[node,fill=RURed!40] (b) at (1,0) {};
          \draw[] (a) to (b);
        \end{tikzpicture}}
        \\
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \path[fill=blue!40] (-0.5,-0.5) rectangle (0.5,0.5);
          \node[node,fill=white] (1) at (0,0) {2};
        \end{tikzpicture}}
        &=
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \node[node,fill=RURed!40] (a) at (0,0) {};
          \node[node,fill=RUBlue!40] (b) at (1,0) {};
          \draw[] (a) to (b);
        \end{tikzpicture}}
        \\
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \path[fill=red!40] (-0.5,-0.5) rectangle (0.5,0.5);
          \node[node,fill=white] (1) at (0,0) {3};
        \end{tikzpicture}}
        &=
%         \begin{tikzpicture}[scale=0.8,baseline=-1mm]
%           \node[snode,fill=RURed!40] (a) at (0.41,0) {};
%           \node[snode,fill=purple!40] (a1) at (0,-0.23) {};
%           \node[snode,fill=teal!40] (a2) at (0,0.23) {};
%           \node[snode,fill=RUBlue!40] (b) at (1.6-0.41,0) {};
%           \node[snode,fill=DarkGreen!40] (b1) at (1.6,-0.23) {};
%           \node[snode,fill=yellow!40] (b2) at (1.6,0.23) {};
%           \draw[] (a) to (b);
%           \draw[ultra thick] (a) to (a1);
%           \draw[ultra thick] (a) to (a2);
%           \draw[ultra thick] (a1) to (a2);
%           \draw[ultra thick] (b) to (b1);
%           \draw[ultra thick] (b) to (b2);
%           \draw[ultra thick] (b1) to (b2);
%         \end{tikzpicture}
        \scalebox{\legendscale}{\begin{tikzpicture}[scale=0.8,baseline=-1mm]
          \draw[thin] (0,0.25) to (1,0.25);
          \draw[thin] (0,0.25) to (1,-0.25);
          \draw[thin] (0,-0.25) to (1,-0.25);
          \draw[thin] (0,-0.25) to (1,0.25);
          \draw[ultra thick] (0,0.25) to (0,-0.25);
          \draw[ultra thick] (1,0.25) to (1,-0.25);
          \node[draw,inner sep=0,minimum width=5mm,semicircle,fill=RURed!40] (a1) at (0,0.25) {};
          \node[draw,inner sep=0,minimum width=5mm,semicircle,shape border rotate=180,fill=yellow!40] (a1) at (0,-0.25) {};
          \node[draw,inner sep=0,minimum width=5mm,semicircle,fill=RUBlue!40] (b1) at (1,0.25) {};
          \node[draw,inner sep=0,minimum width=5mm,semicircle,shape border rotate=180,fill=DarkGreen!40] (b2) at (1,-0.25) {};
%           \draw[thin] (a1) to (b1);
%           \draw[thin] (a1) to (b2);
%           \draw[thin] (a2) to (b1);
%           \draw[thin] (a2) to (b2);
%           \draw[ultra thick] (a1) to (a2);
%           \draw[ultra thick] (b1) to (b2);
        \end{tikzpicture}}
      \end{align*}
    \end{minipage}
  \end{center}
\end{frame}

% -----------------------------------------------------------------------------
\section{Conclusion}
\begin{frame}
  \frametitle{Outline}
  \tableofcontents[currentsection]
\end{frame}
\subsection{}

\begin{frame}
  \frametitle{Summary}
  \begin{itemize}
    \item Graph clustering by optimization.
    \item 6 axioms for graph clustering quality functions.
    \item Graph setting allows for locality.
    \item Modularity is not monotonic.
    \item Non-monotonicity leads to splitting of cliques.
    \item Adaptive scale modularity satisfies all axioms.
    \item Generalizes both modularity and normalized cut.
    \item Two parameters to control size of clusters.
  \end{itemize}
\end{frame}

% -----------------------------------------------------------------------------
\section{}
\begin{frame}
  %\frametitle{End of talk}
  \vfill
  \begin{beamercolorbox}[sep=12pt,center]{title}
    %\Huge End of talk \\[1em]
    \Large Thank you for your attention.
  \end{beamercolorbox}
  \vskip1.5em
  \vfill
  \begin{beamercolorbox}[sep=8pt]{author}
     \usebeamerfont{author}\Large\insertlongtitle%
  \end{beamercolorbox}%
  \begin{beamercolorbox}[sep=8pt]{author}
    \ifx\insertlongauthor\@empty%
    \usebeamerfont{author}\insertauthor%
    \else%
    \usebeamerfont{author}\insertlongauthor%
    \fi%
  \end{beamercolorbox}
  \begin{beamercolorbox}[sep=8pt]{institute}
    \usebeamerfont{institute}\insertinstitute
  \end{beamercolorbox}
  \begin{beamercolorbox}[sep=8pt]{date}
    \usebeamerfont{date}\insertdate
  \end{beamercolorbox}
  \vfill
\end{frame}

\end{document}