An Improved Node Ranking for Label Propagation and Modularity based Clustering
\IEEEauthorblockN{Alessandro Berti
\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1
In this paper I'll speak about non-spectral clustering techniques and see how a node ordering based on centrality measures can improve the quality of communities detected. I'll also discuss an improvement to existing techniques, which further improves modularity.
ranking.tex
\documentclass[conference]{IEEEtran}

% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  % \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at: 
% http://www.ctan.org/tex-archive/macros/latex/required/graphics/
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found as epslatex.ps or
% epslatex.pdf at: http://www.ctan.org/tex-archive/info/
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex


\usepackage{tikz}
\usepackage{bbm}
\usepackage{booktabs}

% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/





% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithmic}
\renewcommand{\algorithmiccomment}[1]{\begin{small}\textcolor{gray}{$\triangleright$ #1}\end{small}}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later 
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.





% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
%\hyphenation{op-tical net-works semi-conduc-tor}
\usepackage{color}
\usepackage[cmex10]{amsmath}
\usepackage{amssymb}
\DeclareMathOperator{\argmax}{\arg\,max}
\DeclareMathOperator{\argmin}{\arg\,min}

\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{An Improved Node Ranking for Label Propagation and Modularity based Clustering}

% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Alessandro Berti}
\IEEEauthorblockA{Department of Mathematics\\
University of Padova\\
35121 Padova\\
Email: berti@math.unipd.it}}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
% 
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3}, 
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}




% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle


\begin{abstract}
In this paper I'll speak about non-spectral clustering techniques and see how a node ordering based
on centrality measures can improve the quality of communities detected. I'll also discuss an
improvement to existing techniques, which further improves modularity.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the conference you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals/conferences frown on
% math in the abstract anyway.

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle

\section{Introduction}

There is a growing interest, in community detection, for non-spectral clustering techniques.
These don't require to work with matrices (i.e. they don't have to find eigenvalues \cite{spectral}, or to
find a Non-Negative Matrix factorization \cite{nmf}), so they are eventually simpler to implement,
and can be applied to larger graphs. These methods require the nodes to be visited iteratively in a certain order.
While for LP algorithm \cite{labelpropagation} the effect of ordering has been considered (at least for
unweighed graphs \cite{xing2014node}), for Modularity based approaches (like \cite{multilevel}) the interest on initial node ordering
has been low. In this paper I'll show how the choice of an appropriate ordering can improve a lot the quality of the communities
detected.

\section{Background}

I'll consider in this paper undirected weighted graphs $G = (V,E,W)$ where $V$ are the vertices, $E$ the edges and $W$ are the (non-negative) weights associated to the edges.

(Crisp) clustering is the task of assigning each node to a single cluster / community.
A very fast non-spectral method is Label Propagation algorithm (LP, \cite{labelpropagation}), which is an iterative
method visiting nodes in a given order and assigning them the ``label'' which has the greatest appearance in the neighbourhood of the node.
If there are two labels with the same weight, one of them is randomly chosen. The method stops when the label of each node is stabilised
to a value.
Another method is based on Modularity maximization. Modularity (see \cite{multilevel}) is a quantity that takes in account
both the internal cohesion and the separation of the found clusters, and is a widely adopted approach in judging quality of a clustering.
Finding the global maximum of modularity is an hard task, infeasible for large
graphs, but finding a good local maximum can be done in a near linear time, using the algorithm described in \cite{multilevel}, which I'll refer as
Multilevel algorithm. This is an agglomerative method, starting from each node forming a distinct cluster, which visits nodes in a given order, taking
them away from their cluster and putting them in the most appropriate cluster, in order to maximize modularity.
So, both methods considered \cite{labelpropagation,multilevel} take in account the ordering of nodes.

An effective way to order nodes is according to a centrality measure \cite{centrality} on the graph. There are various centrality measures,
which are useful to understand how much a node $v$ is important in the description of the community structure:
\begin{itemize}
\item {\bf Weighted ``degree'' centrality} ({\it deg}): A very simple measure that is the sum of the weights of the edges adjacent to $v$.
\item {\bf PageRank centrality} ({\it pag}): An approach described in \cite{pagerank}.
\item {\bf Closeness centrality} ({\it clo}): Defined as the inverse of the sum of the shortest path between $v$ and other nodes in the graph.
$${\mbox clo}(v) = \frac{1}{\sum_{i \neq v} d(i,v)}$$
$$d(i,v) = \min_{e1,\ldots,e_n \in E, i \in e_1, v \in e_n} \sum_{1 \leq j \leq n} \frac{1}{w_{e_j}}$$
\item {\bf Betweenness centrality} ({\it bet}): Defined as the number of shortest paths between nodes that pass through $v$.
\end{itemize}

Computationally wise, degree centrality is the easiest to compute, followed by PageRank, while closeness centrality is a bit more difficult
as it require to compute the length of the shortest paths. Betweenness centrality also require to compute shortest paths and observe the number of these
passing over a node.

\begin{table*}[t]
\centering
\caption{\label{tbl:lp} Average (on 1000 graphs) Label Propagation clustering modularity with different nodes order. I get the best results with ``my'' centrality measure.}
\begin{tabular}{l|cccccc}
\toprule
{\bf Parameters} & {\bf random ord.} & {\bf deg ord.} & {\bf pag ord.} & {\bf clo ord.} & {\bf bet ord.} & {\bf my ord.} \\
\midrule
n=50, ~nei=4 & 0.0895 & 0.5675 & 0.5677 & 0.5679 & 0.5710 & {\bf 0.5714} \\
n=50, ~nei=5 & 0.0047 & 0.5184 & 0.5201 & 0.5126 & 0.5192 & {\bf 0.5202} \\
n=50, ~nei=6 & -0.0001 & 0.4669 & 0.4681 & 0.4574 & 0.4654 & {\bf 0.4685} \\
n=100, nei=7 & -0.0001 & 0.5964 & 0.5967 & 0.6012 & 0.6010 & {\bf 0.6018} \\
n=100, nei=8 & -0.0001 & 0.5716 & 0.5719 & 0.5754 & 0.5729 & {\bf 0.5763} \\
n=100, nei=9 & -0.0001 & 0.5460 & 0.5479 & 0.5449 & 0.5474 & {\bf 0.5510} \\
\bottomrule
\end{tabular}
\end{table*}

\begin{table*}[t]
\centering
\caption{\label{tbl:ml} Average (on 1000 graphs) Multilevel clustering modularity with different nodes order. I get the best results with ``my'' centrality measure. Natural ordering means the order in which nodes were added to the graph.}
\begin{tabular}{l|cccccc}
\toprule
{\bf Parameters} & {\bf natural ord.} & {\bf deg ord.} & {\bf pag ord.} & {\bf clo ord.} & {\bf bet ord.} & {\bf my ord.} \\
\midrule
n=50, ~nei=4 & 0.5841 & 0.5880 & {\bf 0.5886} & 0.5881 & 0.5884 & 0.5885 \\
n=50, ~nei=5 & 0.5312 & 0.5376 & 0.5373 & 0.5371 & 0.5375 & {\bf 0.5377} \\
n=50, ~nei=6 & 0.4869 & 0.4937 & 0.4933 & 0.4936 & 0.4933 & {\bf 0.4938} \\
n=100, nei=7 & 0.5910 & 0.6142 & 0.6144 & {\bf 0.6147} & 0.6137 & {\bf 0.6147} \\
n=100, nei=8 & 0.5599 & 0.5869 & 0.5869 & 0.5870 & 0.5869 & {\bf 0.5873} \\
n=100, nei=9 & 0.5320 & 0.5623 & 0.5623 & 0.5615 & 0.5620 & {\bf 0.5624} \\
\bottomrule
\end{tabular}
\end{table*}

I'll consider the ordering that takes as first the lower centrality nodes, as they are less important in the definition of communities
and can be suddenly merged, by the considered iterative methods \cite{labelpropagation,multilevel}, to high centrality nodes.
If two or more nodes have the same centrality, then the order between them is chosen randomly.
This type of ordering shows, in applications, big gains for each of the considered centrality measures, in comparison to a random ordering.

\section{My method}

In applications, we'll see that closeness and betweenness have the best behaviour. I will try now to merge them, in order to obtain a better ordering.
Firstly, we can note that betweenness is an integer quantity (the number of shortest paths passing through the node) and that is not uncommon that two
nodes share the same betweenness. Now, I introduce a quantity that can be called ``relative'' closeness of a node:
$$C(i) = \frac{c(i)}{2 \cdot \max_{v \in G} c(v) + 1}$$
The above quantity is surely contained in the interval $[0,1/2)$. The idea is to define the quantity
$$\mbox{my}(v) = \mbox{bet}(v) + C(v)$$
and doing the ordering according to it. We can see that if $\mbox{bet}(v) < \mbox{bet}(w)$ then $\mbox{my}(v) < \mbox{my}(w)$, so the only effect
of this measure is to do a correct ordering in the cases where $\mbox{bet}(v) = \mbox{bet}(w)$, which are indeed critical.

\section{Assessment}

The assessment has been done on Watts-Strogatz graphs, all generated with parameters p $= 0$ (rewiring probability) and dim $= 1$
(dimension of the starting lattice).
For each of the considered methods (Label Propagation \cite{labelpropagation} and Multilevel \cite{multilevel}), and each choice of the parameters
(n is the number of nodes, while nei is the neighborhood within which the vertices of the lattice will be connected) I have calculated
the average modularity (on $1000$ graphs), by ordering the nodes in the indicated ways, of the clustering, and reported the results
in Table \ref{tbl:lp} and Table \ref{tbl:ml}.

The biggest gains are produced by ordering based on betweenness and closeness measures. Initially avoiding nodes with high betweenness is
indeed related to treating later possible overlapping nodes, which are between communities and risk to ruin clustering. Closeness is important
because nodes with low closeness are farther from the others and so have less influence, and taking in account the distance, instead of the ``direct'' arc, is
more meaningful.

\section{Conclusions}

In this paper I have examined how, ordering the nodes according to a centrality measure, I can get better quality of the clustering produced, according
to modularity. I have also introduced a measure that, while can't be called ``novel'' approach, has shown good behaviour in applications. Although not obtaining
the best results, calculation of degree centrality is very easy and I suggest it as a plausible pre-processing step, without ruining the performance at all,
to easily improve the modularity.

\section{Acknowledgements}

This work has been supported by FSE fellowship 2105/201/17/1148/2013.

\bibliographystyle{IEEEtran}
\bibliography{ranking}
\end{document}
ranking.bbl
% Generated by IEEEtran.bst, version: 1.13 (2008/09/30)
\begin{thebibliography}{1}
\providecommand{\url}[1]{#1}
\csname url@samestyle\endcsname
\providecommand{\newblock}{\relax}
\providecommand{\bibinfo}[2]{#2}
\providecommand{\BIBentrySTDinterwordspacing}{\spaceskip=0pt\relax}
\providecommand{\BIBentryALTinterwordstretchfactor}{4}
\providecommand{\BIBentryALTinterwordspacing}{\spaceskip=\fontdimen2\font plus
\BIBentryALTinterwordstretchfactor\fontdimen3\font minus
  \fontdimen4\font\relax}
\providecommand{\BIBforeignlanguage}[2]{{%
\expandafter\ifx\csname l@#1\endcsname\relax
\typeout{** WARNING: IEEEtran.bst: No hyphenation pattern has been}%
\typeout{** loaded for the language `#1'. Using the pattern for}%
\typeout{** the default language instead.}%
\else
\language=\csname l@#1\endcsname
\fi
#2}}
\providecommand{\BIBdecl}{\relax}
\BIBdecl

\bibitem{spectral}
A.~Y. Ng, M.~I. Jordan, Y.~Weiss \emph{et~al.}, ``On spectral clustering:
  Analysis and an algorithm,'' \emph{Advances in neural information processing
  systems}, vol.~2, pp. 849--856, 2002.

\bibitem{nmf}
D.~D. Lee and H.~S. Seung, ``Algorithms for non-negative matrix
  factorization,'' in \emph{Advances in neural information processing systems},
  2001, pp. 556--562.

\bibitem{labelpropagation}
U.~N. Raghavan, R.~Albert, and S.~Kumara, ``Near linear time algorithm to
  detect community structures in large-scale networks,'' \emph{Physical Review
  E}, vol.~76, no.~3, p. 036106, 2007.

\bibitem{xing2014node}
Y.~Xing, F.~Meng, Y.~Zhou, M.~Zhu, M.~Shi, and G.~Sun, ``A node influence based
  label propagation algorithm for community detection in networks,'' \emph{The
  Scientific World Journal}, vol. 2014, 2014.

\bibitem{multilevel}
V.~D. Blondel, J.-L. Guillaume, R.~Lambiotte, and E.~Lefebvre, ``Fast unfolding
  of communities in large networks,'' \emph{Journal of Statistical Mechanics:
  Theory and Experiment}, vol. 2008, no.~10, p. P10008, 2008.

\bibitem{centrality}
L.~C. Freeman, ``Centrality in social networks conceptual clarification,''
  \emph{Social networks}, vol.~1, no.~3, pp. 215--239, 1979.

\bibitem{pagerank}
Y.~Ding, E.~Yan, A.~Frazho, and J.~Caverlee, ``Pagerank for ranking authors in
  co-citation networks,'' \emph{Journal of the American Society for Information
  Science and Technology}, vol.~60, no.~11, pp. 2229--2243, 2009.

\end{thebibliography}
