%\documentclass[landscape]{article}
\documentclass{article}
\usepackage{amssymb}
\usepackage{amsmath}
%\usepackage{slide-article-tom}
\usepackage[landscape]{slide-article-tom}

\ifx\pdfoutput\undefined
     \usepackage[dvips]{graphicx}
\else
     \usepackage[pdftex]{graphicx}
     \pdfcompresslevel9
\fi

\usepackage{hyperref}

\hypersetup{colorlinks,
            linkcolor=blue,
            %pdfpagemode=FullScreen
            pdfpagemode=None
            }


%\def\@linkcolor{red}
%\def\@linkcolor{blue}
%\def\@anchorcolor{black}
%\def\@citecolor{green}
%\def\@filecolor{cyan}
%\def\@urlcolor{magenta}
%\def\@menucolor{red}
%\def\@pagecolor{red}


\def\pagedone{\newpage}

\def\tthdump#1{#1}

%% \tthdump{\def\sectionhead#1{\begin{center}{\LARGE\hypertarget{#1}
%%      {#1}\hyperlink{Our general topics:}{\hfil$\leftarrow$}}\end{center}}}
%%      
%% %%tth:\def\sectionhead#1{{\LARGE#1\hypertarget{#1}{#1}}
%% %%tth:     \special{html: <A NAME="#1"></A><a href="\#Top of file">       Top</a>}}

%% \def\sectionhead#1{\section{#1}\hyperlink{Contents}{\hfil$\leftarrow$}}
%% \def\sectionhead#1{\section*{#1}\addcontentsline{toc}{section}{#1}\hyperlink{Contents}{$\leftarrow$}}

\tthdump{\def\sectionhead#1{\begin{center}\section*{#1 \hyperlink{Contents}{\hfil$\leftarrow$}}
             \end{center}
     \addcontentsline{toc}{section}{#1}
     \vspace{-\baselineskip}
     }}

%%tth:\def\sectionhead#1{\begin{center}\section{#1}\end{center}
%%tth:     {\special{html: <a href="\#Top of file">       <--</a>}}}

%% %%tth:     \addcontentsline{toc}{section}{#1}}

\tthdump{\def\exercises#1{\begin{center}\subsection*{#1 -~exercises
            \hyperlink{Contents}{\hfil$\leftarrow$}}\end{center}
%     \addcontentsline{toc}{subsection}{#1 (ex)}
     \vspace{-\baselineskip}
     }}
     
%%tth:\def\exercises#1{\begin{center}\subsection{#1 -~exercises}\end{center}
%%tth:     {\special{html: <a href="\#Top of file">       <--</a>}}}

     
%% \tthdump{\def\exercises#1{\begin{center}{\LARGE Exercises: \hypertarget{#1.ex}
%%      {#1}\hyperlink{Contents}{\hfil$\leftarrow$}}\end{center}}}
%%      
%% %%tth:\def\exercises#1{{\LARGE Exercises: #1\hypertarget{#1.ex}{#1.ex}}
%% %%tth:     \special{html: <A NAME="#1.ex"></A><a href="\#Top of file">       Top</a>}}

\tthdump{\def\quotesection#1{\begin{center}{\LARGE\hypertarget{#1}
     {#1}\hyperlink{The quotes}{\hfil$\twoheadleftarrow$}}\end{center}}}
     
%%tth:\def\quotesection#1{{\LARGE#1\hypertarget{#1}{#1}}
%%tth:     \special{html: <A NAME="#1"></A><a href="\#The quotes">       <-</a>}}

%%tth:\def\makehyperlink#1{\special{html: <a href="\##1">}{\large#1}\special{html: </a>}}

%%tth:\def\makehyperlinkex#1{\ \ \special{html: <a href="\##1">}{\large (ex)}\special{html: </a>}}

%%tth:\def\binom#1#2{\left(\begin{array}{c}#1\\#2\end{array}\right)}

\tthdump{\def\httimes{\times}}
%%tth:\def\httimes{x\ }

\tthdump{\def\mybigtriangledown{\bigtriangledown}}
%%tth:\def\mybigtriangledown{\mathrm{Del}}

\tthdump{\def\htvec#1{\vec{#1}}}
%%tth:\def\htvec#1{{\bf #1}}

\def\myspan{\mathrm{span}}
\def\matrix{\mathrm{matrix}}

\tthdump{\def\myreal{\mathbb{R}}}
%%tth:\def\myreal{\mathbf{R}}
%%\def\myreal{\Re}
\tthdump{\def\mycomplex{\mathbb{C}}}
%%tth:\def\mycomplex{\mathbf{C}}
\tthdump{\def\myfield{\mathbb{F}}}
%%tth:\def\myfield{\mathbf{F}}
\tthdump{\def\myquaternions{\mathbb{H}}}
%%tth:\def\myquaternions{\mathbf{H}}
\tthdump{\def\myrationals{\mathbb{Q}}}
%%tth:\def\myrationals{\mathbf{Q}}
\tthdump{\def\myintegers{\mathbb{Z}}}
%%tth:\def\myintegers{\mathbf{Z}}

%\def\dim\mathrm{dim}
\def\im{\mathrm{im}}
\def\deriv{\mathrm{D}}
\def\trace{\mathrm{trace}}
\def\detm{\mathrm{det}_m}
\def\detv{\mathrm{det}_v}
\def\perm{\mathrm{perm}}
\def\sign{\mathrm{sign}}

% kets and bras etc.
\def\ket#1{|{#1}\rangle}
\def\bra#1{\langle{#1}|}
\def\braket#1#2{\langle{#1}|{#2}\rangle}

%\def\sectionhead#1{\begin{center}{\LARGE #1}\end{center}}
%\def\sectionhead#1{\section{#1}}

% defines a 2 element column vector.
\def\col#1#2{\left(\begin{array}{c}#1\\#2\end{array}\right)}
\def\tcol#1#2{(#1, #2)^T}


\begin{document}
\raggedright
%%tth:\special{html: <A NAME="Top of file"></A>}


\pagestyle{myfooters}
%\pagestyle{plain}

\thispagestyle{empty}


%%tth:\special{html:<title> Clustering in Networks</title>}

%Slide 1
\title{{\LARGE\bf Clustering in Networks}\newline
              (Spectral Clustering with \newline the Graph Laplacian \newline
               \ldots a brief introduction)
\newline
}
\author{Tom Carter \newline
\newline
Computer Science\newline
CSU Stanislaus
\vfill
\tthdump{\href
{http://csustan.csustan.edu/\~tom/Clustering}{http://csustan.csustan.edu/\~\ tom/Clustering}}
%%tth:\href{http://csustan.csustan.edu/~tom/Clustering}{http://csustan.csustan.edu/\~tom/Clustering}
}


%\date{Spring, 2011}
\date{\today}


\maketitle

%Slide 2
%% \sectionhead{Our general topics:}
%% %%tth:\begin{itemize}
%% %%tth:\item
%% \tthdump{\hyperlink{Why differentiable manifolds}
%%                {\ $\circledcirc$ Why differentiable manifolds\newline}}
%% %%tth:\makehyperlink{Why differentiable manifolds}
%% %%tth:\item
%% \tthdump{\hyperlink{References}
%% 	        {$\circledcirc$ References\newline}} 
%% %%tth:\makehyperlink{References}
%% %%tth:\end{itemize}
%% 
%% (ex):  exercises.
%% 
%% \pagedone

\tthdump{\renewcommand\contentsname{Our general topics:\hypertarget{Contents}{}}}
%% \newcommand\listfigurename{List of Figures}
%% \newcommand\listtablename{List of Tables}

\tableofcontents

\pagedone




\sectionhead{What is Clustering?}
%% %%tth:\section{What is Clustering}

\begin{itemize}
       \item Many real-world data sets consist of (or refer to) collections of entities of some general
            type.  Some example data sets might be:
            
            \begin{itemize}
                \item Points in space (e.g., a set of $(x, y)$ coordinates)
                \item Populations of people (e.g., census data \ldots)
                \item Financial instruments (e.g., stocks, with data set the daily closing prices)
                \item Collections of texts (e.g., a set of emails, or blog posts, or \ldots)
                \item A social network (e.g., Facebook, or phone contacts)
            \end{itemize}
            
       Our data sets give us views into collections of entities, and we would like to use
       the data sets to better understand the entities \ldots

 %\pagedone
        
       \item Often we can think of our data set as telling us something about the
            "relatedness" of our collection of entities.  In some cases, the "relatedness"
            might be very simply and directly represented in the data set.  For example,
            on Facebook, two members might be related if they are "friends" of each
            other.  Two emails might be related if they are from the same person.  In the
            census, two people might be "related" if they live in the same town, or if
            they have the same job, or etc.  Two web pages might be related if one
            contains a link to the other.
            
            More generally, we may be able to develop a "relatedness" metric associated
            with the data set.  For example, the relatedness between two stocks might be
            the degree to which their prices are correlated with each other over time.  The
            relatedness between two texts might be the number of distinct words
            they have in common.

 %\pagedone
 
      \item  One useful starting point to understanding such data sets is to look for
           subsets of the collection of entities which are more closely related to
           each other than they are to other members of the collection.  We can
           think of such closely related subsets as "clusters".
           
           Our goal, then, would be to find (automated or algorithmic) ways to
           find such clusters in our data sets.  If we are lucky, we can also develop
           techniques for visualizing our data set through the lens of the clusters
           we have found.  For example, we might develop a graphical display
           of the data set where things in a particular cluster are near each other,
           or have the same color.
           
           In the case of very large data sets, we can use clustering to reduce the
           effective size (or dimensionality) of the data set by collapsing clusters
           into single points, and proceeding from there with our analysis.  There
           are even likely to be times when we want to iterate this process \ldots
           
           The general approach I'll briefly describe here is sometimes called
           "spectral clustering."  It involves representing the "relatedness" as
           a weighted graph ( or network), and applying various mathematical/algorithmic
           techniques.  We can represent the graph as an "adjacency" matrix -- i.e., we
           can construct a symmetric square matrix $A$ from the data set where $A(i, j)$
           is the "level of relatedness" between entities $i$ and $j$.  In simple
           traditional graph theory, two nodes (or vertices) are "related" if there is
           an edge between them, and the adjacency matrix has  $A(i,j) =1$, and
           $0$ otherwise.  Many of our examples will be of the more general "weighted
           graph" type.
           
\end{itemize}
 
 \pagedone
  
\sectionhead{An Example}
%% %%tth:\section{An Example}

\begin{itemize}
	\item Let's start with a (relatively) simple example.  Consider the following,
	     a collection of points in 2-dimensional space:

              \vspace{0.5cm}
              
	      \centerline{\includegraphics[width = 6in]{8-clusters-1}}
	      
%	      We would like to have an algorithm that can find clusters in
%	      such a data set.
	
 \pagedone
 
      \item  Two points in this data set are related by being
           near each other.  A comparatively naive "clustering" algorithm might
           find this:
           
           \vspace{0.5cm}
           
           \centerline{\includegraphics[width = 6in]{8-clusters-kmeans}}
           
 \pagedone
 
      \item  But we can see that there is more structure to the data set.  We would
           really like something more like this:
           
           \vspace{0.1cm}
           
           \centerline{\includegraphics[width = 6in]{8-clusters-3}}
           
           This version of clustering was done via an algorithm in a general class often
           called spectral clustering.
\pagedone

\end{itemize}

 \pagedone
 
 \sectionhead{Spectral Clustering (a general outline)}
 %% %%tth:\section{Spectral Clustering (a general outline)}
 
 \begin{itemize}
        \item A general outline of a useful approach to a spectral clustering is
             as follows:
             
             \begin{itemize}
                  \item Through some mechanism, generate an "adjacency" matrix.  I'll
                       sometimes call this an "affinity" matrix.  This will be an $n$ x $n$ matrix,
                       where each entry is an "affinity" between a pair of elements in the
                       collection we are studying.
                       
                  \item Massage the affinity matrix appropriately  (  art, not science :-)
                  
                  \item Compute the (a \ldots) graph Laplacian from the affinity matrix (see below)
                  
                  \item Calculate eigenvalues and associated eigenvectors from the graph Laplacian
                  
                  \item Choose an appropriate number $k$ of clusters  (art, not science :-)
                  
                  \item Select the eigenvectors associated with the largest $k$ eigenvalues
                  
                  \item Make an $n$ x $k$ matrix with those eigenvectors
                  
                  \item Perform k-means clustering on the rows of the $n$ x $k$ matrix
                  
                  \item Display the results, lather, rinse, and repeat \ldots
                  
             \end{itemize}
               
\end{itemize}
 \pagedone
 

 
 \sectionhead{Graph Laplacian(s)}
 %% %%tth:\section{Graph Laplacian(s)}
 
 \begin{itemize}
      \item  The general idea of the "graph Laplacian" is to derive a new matrix
           from the adjacency matrix that can tell us something about the
           structure of the graph.  These have enough similarity to the Laplacian
           found elsewhere in mathematics that they share the name.  There are
           actually several variations in use.  Some versions are outlined in the
           following.  In practice, it is typical for people to work with the
           eigenvalues and eigenvectors of these derived matrices.
           
           \begin{itemize}
                \item Let $A$ (with entries $A(i,j)$) be the adjacency (or affinity) matrix.
                     Note:  in the general case, these are frequently labeled $W$
                     (with entries $W(i,j)$), the weight matrix.
 \pagedone
                
                \item We now compute the (generalized) degrees $D$ of the nodes in the graph:
                
                     $$ D(i,i) = \sum_{j} A(i, j)$$
                     $$ D(i,j) = 0 \mbox{ if } i \neq j$$
                     
                     A convenient abbreviation is $D(i) = D(i,i)$.
                     
                     In the simple case of an unweighted graph, $D(i)$ tells how many
                     other nodes are connected to node $i$.  In the more general case,
                     it tells the total weight of edges emanating from a node.
                     
                \item The easiest version of a graph laplacian is
                
                     $$ L = D - A $$
                    
 \pagedone                    
                \item A second version is often called a "normalized graph laplacian":
                
                     $$ L_{norm_1} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}} $$
                
                Or, in coordinate form:
                \begin{eqnarray*}
                   L_{norm_1}(i,j) & = & \begin{cases}
                              1 \mbox{\ \ \ \ \ \ \ if}\ i = j\ \mbox{and}\ D(i) \neq 0\\
                               -\frac{A(i,j)}{\sqrt{D(i) * D(j)}} 
                                            \mbox{\ \ if}\ i \neq j\ \mbox{and}A(i,j) \neq 0 \\
                              0 \mbox{\ \ \ \ \ \ otherwise}.
                        \end{cases} \\
               \end{eqnarray*}

                     

\pagedone

          \item A slightly simpler, but still useful, version of this is:
          
               $$ L_{norm_2} = D^{-\frac{1}{2}} A D^{-\frac{1}{2}} $$
               
               In other words,
               
               $$ L_{norm_2}(i,j) = \frac{A(i,j)}{\sqrt{D(i)D(j)}} $$
               
          \item An alternate version of a normalized laplacian is:
          
               $$ L_{norm_3} = D^{-1}A $$
               
               This version has the nice property that if we think about a random walk
               on the graph, with the likelihood of moving from node $i$ to node $j$
               being proportional to $A(i,j)$, then the corresponding matrix of probabilities
               will be:
               
               $$ P = D^{-1}A $$
               
     \end{itemize}
     
     \item more later \ldots
     
 \end{itemize}
 
\pagedone



 \footnotesize
 \bibliographystyle{plain} 
 
%% \tthdump{\hypertarget{References}{}\hyperlink{Contents}{\hfil To top $\leftarrow$}}
%% %%tth:{\special{html: <A NAME="References"></A><a href="\#Top of file">       Top</a>}}


\marginpar{\hyperlink{Contents}{\hfil$\leftarrow$}}

\vspace{-\baselineskip}
\vspace{-\baselineskip}
\vspace{-\baselineskip}
 
 \begin{thebibliography}{12}
%%tth:{\special{html: <font size="+0">}}

\addcontentsline{toc}{section}{References}

\bibitem{chung}
Chung, Fan,\newline
Course notes for UCSD Math 261C (Probabilistic Combinatorics and Algorithms III), Spring 2010\newline
 \hyperref{http://math.ucsd.edu/~jthughes/Math261C/Math261C.html}{}{}
 {http://math.ucsd.edu/~jthughes/Math261C/Math261C.html}

\bibitem{chung2}
Chung, Fan,\newline
Graph Theory in the Information Age, Notices of the AMS, Vol. 57, No. 6, pp. 726-732\newline
 \hyperref{http://www.math.ucsd.edu/~fan/wp/graph.pdf}{}{}
 {http://www.math.ucsd.edu/~fan/wp/graph.pdf}
 
\bibitem{horaud}
Horaud, Radu, \newline
A Short Tutorial on Graph Laplacians, Laplacian Embedding, and Spectral Clustering\newline
 \hyperref{http://perception.inrialpes.fr/~Boyer/ReadingGroup/GraphLaplacian-tutorial.pdf}{}{}
 {http://perception.inrialpes.fr/\~\ Boyer/ReadingGroup/GraphLaplacian-tutorial.pdf}

\bibitem{luxburg}
von Luxburg, Ulrike,\newline
A Tutorial on Spectral Clustering\newline
\hyperref{http://people.kyb.tuebingen.mpg.de/ule/publications/publication_downloads/Luxburg07_tutorial.pdf}{}{}
{http://people.kyb.tuebingen.mpg.de/ule/
publications/publication\_downloads/Luxburg07\_tutorial.pdf}

\bibitem{spielman}
Spielman, Daniel, and Srivastava, Nikhil,\newline
Graph Sparsification by Effective Resistances\newline
Abstract: \hyperref{http://arxiv.org/abs/0803.0929}{}{}
{http://arxiv.org/abs/0803.0929}\newline
Full text: \hyperref{http://arxiv.org/pdf/0803.0929v4}{}{}
{http://arxiv.org/pdf/0803.0929v4}

\bibitem{vejmelka}
Vejmelka, Martin,\newline
Spectral Graph Clustering\newline
\hyperref{http://ai.ms.mff.cuni.cz/~sui/Seminar2009MartinVejmelka.pdf}{}{}
{http://ai.ms.mff.cuni.cz/~sui/Seminar2009MartinVejmelka.pdf}
 
\bibitem{ng}
Ng, Andrew, Jordan, Michael, and Weiss, Yair,\newline
On Spectral Clustering: Analysis and an Algorithm\newline
\hyperref{http://www.stat.washington.edu/wxs/Stat593-s03/Literature/ng-jordan-weiss-nips01.pdf}{}{}
{http://www.stat.washington.edu/wxs/Stat593-s03/Literature/ng-jordan-weiss-nips01.pdf}

\bibitem{zhu}
Zhu, Xiaojin,\newline
Course notes, Advanced Natural Language Processing\newline
 \hyperref{http://pages.cs.wisc.edu/~jerryzhu/cs769.html}{}{}
 {http://pages.cs.wisc.edu/~jerryzhu/cs769.html}


\end{thebibliography}

\tthdump{\hyperlink{Contents}{\hfil To top $\leftarrow$}}
%%tth:{\special{html: <a href="\#Top of file">       Back to top of file</a>}}


\end{document}
