text:
\section{Introduction}

Centrality metrics, such as closeness or betweenness, quantify how central a
node is in a network. They have been successfully used to carry analysis for
various purposes such as structural analysis of knowledge
networks~\cite{Pham10,Shi10}, power grid contingency analysis~\cite{Jin10},
quantifying importance in social networks~\cite{LeMerrer2009}, analysis of
covert networks~\cite{Krebs02}, decision/action networks~\cite{simsekb08},
and even for finding the best store locations in cities~\cite{Porta09}. Several
works which have been conducted to rapidly compute these metrics exist in the
literature. The algorithm with the best asymptotic complexity to compute
centrality metrics~\cite{brandes2001} is believed to be asymptotically
optimal~\cite{Kintali08}. Research have focused on either approximation
algorithms for computing centrality metrics~\cite{Chan09,Eppstein01,Okamoto08}
or on high performance computing techniques~\cite{Madduri2009,Shi11}. Today, it
is common to find large networks, and we are always in a quest for better
techniques which help us while performing centrality-based
analysis on them.

When the network topology is modified, ensuring the correctness of the
centralities is a challenging task. This problem has been studied for
dynamic and streaming networks~\cite{Green2012,Lee2012}. Even for some
applications involving a static network such as the contingency analysis
of power grids and robustness evaluation of networks, to be prepared
and take proactive measures, we need to know how the centrality values
change when the network topology is modified by an adversary and outer
effects such as natural disasters.

A similar problem arises in network management for which not only
knowing but also setting the centrality values in a controlled manner
via topology modifications is of concern to speed-up or contain the
entity dissemination. The problem is hard: there are $m$ candidate
edges to delete and $\mathcal{O}(n^2)$ candidate edges to insert where
$n$ and $m$ are the number of nodes and edges in the network,
respectively. Here, the main motivation can be calibrating the
importance/load of some or all of the vertices as desired, matching
their loads to their capacities, boosting the content spread, or
making the network immune to adversarial attacks. Similar problems,
such as finding the most cost-effective way which reduces the entity
dissemination ability of a network~\cite{Phillips1993} or finding a
small set of edges whose deletion maximizes the shortest-path
length~\cite{Israeli02}, have been investigated in the literature. The
problem recently regained a lot of attention: A generic study which
uses edge insertions and deletions is done by
Tong~et~al.~\cite{Tong12}. They use the changes on the leading
eigenvalue to control/speed-up the dissemination process. Other recent
works investigate edge insertions to minimize the average shortest
path distance~\cite{Papagelis2011} or to boost the content
spread~\cite{Chaoji2012}. From the centrality point of view, there
exist studies which focus on maximizing the centrality of a node
set~\cite{Everett2005,Ishakian2012} or a single
node~\cite{Ishakian2012} by edge insertions. In generic
centrality-based network management problem, the desired centralities
of all the nodes need to be obtained or approximated with a small set
of topology modifications. As Figure~\ref{fig:gseq} shows, the effect
of a local topology modification is usually global. Furthermore,
existing algorithms for incremental centrality computation
are not efficient enough to be used in practice. Thus,
novel incremental algorithms are essential to quickly evaluate the
effects of topology modifications on centrality values.

\begin{figure}[htbp]
\vspace*{-1ex}
\center
~~~\includegraphics[width=0.38\textwidth]{graphseq.pdf}
\includegraphics[width=0.47\textwidth]{closeness-toy.pdf}
\vspace*{-1ex}
\caption{\small A toy network with nine nodes, three consecutive edge~($ah$,
$fh$, and $ab$, respectively) insertions/deletions, and values of
closeness centrality
}  \label{fig:gseq}
\vspace*{-1ex}
\end{figure}

Our contributions can be summarized as follows:
\begin{enumerate}[topsep=4pt, itemsep=0pt]
\item{To attack the variants of the centrality-based network
  management problem, we propose incremental algorithms which
  efficiently update the closeness centralities upon edge insertions
  and deletions.}

\item{The proposed algorithms can serve as a fundamental building
  block for other shortest-path-based network analyses such as the
  temporal analysis on the past network data,
  maintaining centrality on streaming networks, or
  minimizing/maximizing the average shortest-path distance via edge
  insertions and deletions.}

\item{Compared with the existing algorithms, our algorithms have a
  low-memory footprint making them practical and applicable to very
  large graphs. For random edge insertions/deletions to the Wikipedia
  users' communication graph, we reduced the centrality
  (re)computation time from 2 days to 16 minutes. And for the
  real-life temporal DBLP coauthorship network, we reduced the time
  from 1.3 days to 4.2 minutes.}

\item{The proposed techniques can easily be adapted to algorithms for
  approximating centralities. As a result, one can employ a more
  accurate and faster sampling and obtain better approximations.}
\end{enumerate}

The rest of the paper is organized as follows: Section~\ref{sec:bac}
introduces the notation and formally defines the closeness centrality
metric. Section~\ref{sec:manage} defines network management problems
we are interested. Our algorithms explained in detail in
Section~\ref{sec:main}. Existing approaches are described in
Section~\ref{sec:rel} and the experimental analysis is given in
Section~\ref{sec:exp}. Section~\ref{sec:con} concludes the
paper.

\section{Background}\label{sec:bac}

Let $G = (V,E)$ be a network modeled as a simple graph with $n = |V|$
vertices and $m = |E|$ edges where each node is represented by a vertex in
$V$, and a node-node interaction is represented by an edge in $E$.
Let $\Gamma_G(v)$ be the set of vertices which are connected to $v$ in
$G$.

A graph $G' = (V', E')$ is a {\em subgraph} of $G$ if $V' \subseteq V$
and $E' \subseteq E$. A \textit{path} is a sequence of vertices such
that there exists an edge between consecutive vertices. A path between
two vertices $s$ and $t$ is denoted by $s \leadsto t$~(we sometimes use $s
 \stackrel{P}{\leadsto} t$ to denote a specific path $P$ with
 endpoints $s$ and $t$). Two vertices
$u, v \in V$ are \textit{connected} if there is a path from $u$ to
$v$.  If all vertex pairs are connected we say that $G$ is
\textit{connected}. If $G$ is not connected, then it is {\em
disconnected} and each maximal connected subgraph of $G$ is a {\em
connected component}, or a component, of $G$. We use ${d}_G(u,v)$ to
denote the length of the shortest path between two vertices $u, v$ in
a graph $G$. If $u = v$ then ${d}_G(u,v) = 0$. And if $u$ and $v$ are
disconnected, then ${d}_G(u,v) = \infty$.

Given a graph $G = (V,E)$, a vertex $v \in V$ is called an {\em
  articulation vertex} if the graph $G-v$ (obtained by removing $v$)
has more connected components than $G$. Similarly, an edge $e \in E$
is called a {\em bridge} if $G-e$ (obtained by removing $e$ from $E$)
has more connected components than $G$. $G$ is {\em biconnected} if it
is connected and it does not contain an articulation vertex. A maximal
biconnected subgraph of $G$ is a {\em biconnected component}.

\subsection{Closeness Centrality}

Given a graph $G$, the {\em farness} of a vertex $u$ is
defined as $${\tt far}\xspace[u] = \sum_{\stackrel{v \in V}{{d}_G(u,v) \neq
    \infty}} {d}_G(u,v).$$ And the
closeness centrality of $u$ is defined as
\begin{equation}
{\tt cc}\xspace[u] = \frac{1}{{\tt far}\xspace[u]}. \label{eq:first}
\end{equation}
If $u$ cannot reach any vertex in the graph ${\tt cc}\xspace[u] = 0$.

For a sparse unweighted graph $G \ (V,E)$ with $|V| = n$ and $|E| =
m$, the complexity of {\tt cc}\xspace computation is $\mathcal{O}(n(m+n))$.  For
each vertex $s$, Algorithm~\ref{alg:cc} executes a Single-Source Shortest
Paths~(SSSP) algorithm.  It initiates a breadth-first search~(BFS)
from $s$, computes the distances to the other vertices, compute
${\tt far}\xspace[s]$, the sum of the distances which are different than $\infty$.
And, as the last step, it computes ${\tt cc}\xspace[s]$. Since a BFS takes $\mathcal{O}(m+n)$
time, and $n$ SSSPs are required in total, the complexity follows.

\renewcommand{\baselinestretch}{0.70}
\begin{algorithm}[htbp]
\DontPrintSemicolon
\SetKwComment{tcp}{$\triangleright$}{} \small
\caption{\textsc{CC}\xspace: Basic centrality computation}
\label{alg:cc}
\KwData{${G = (V,E)}$}
\KwOut{$cc[.]$}
  \lnl{line:bfs}\For{{\bf each} $s \in V$} {
  	\tcp{SSSP($G$, $s$) with centrality computation}
    $Q \leftarrow$ empty queue \;
    ${d}[v] \gets \infty, \forall v \in V\setminus{\{s\}}$ \;
    $Q$.push($s$),\ ${d}[s] \gets 0$ \;
    ${\tt far}\xspace[s] \gets 0$ \;
    \While{$Q$ is not empty} {
      $v \leftarrow Q$.pop()\;
      \For{{\bf all} $w \in \Gamma(v)$}{
        \If{${d}[w] = \infty$}{
          $Q$.push($w$) \;
          ${d}[w] \gets {d}[v] + 1$ \;
	  ${\tt far}\xspace[s] \gets {\tt far}\xspace[s] + {d}[w]$\;
        }
      }
    }
    ${\tt cc}\xspace[s] = \frac{1}{{\tt far}\xspace[s]}$
  }
  \Return{${\tt cc}\xspace[.]$}\;
 \end{algorithm}
\renewcommand{\baselinestretch}{1}

\section{Problem Definitions}\label{sec:manage}
The following problem can be considered as a generalized version of
the problems investigated in~\cite{Everett2005,Ishakian2012}.

\begin{definition} \emph{(Centrality-based network management)}
  Let $G = (V,E)$ be a graph. Given a centrality metric $\cal C$, a
  target centrality vector ${\mathbf c}'$, and an upper bound $U$ on the
  number of inserted/deleted edges, construct a graph $G' = (V, E')$,
  s.t., $|E \Delta E'| \leq U$ and $||{\mathbf c}' - {\mathbf c}_{G'}||$ is minimized.
\label{def:gencen}
\end{definition}

In this work, we are interested in the closeness metric which is based
on shortest paths. Hence, implicitly, we are also interested in the
following problem partly investigated
in~\cite{Israeli02,Papagelis2011,Phillips1993}.

\begin{definition} \emph{(Shortest-path-based network management)}
  Let $G = (V,E)$ be a graph. Given an upper bound $U$ on the number
  of inserted/deleted edges, construct a graph $G' = (V, E')$ where
  $|E \Delta E'| \leq U$ and the (average) shortest-path in $G'$ is
  minimized/maximized.
\label{def:genshor}
\end{definition}

These problems and their variants have several applications such as
slowing down pathogen outbreaks, increasing the efficiency of the
advertisements, and analyzing the robustness of a network. Consider an
airline company with flights to thousands of airports and aim to add
some new routes to increase the load of some underutilized
airports. When a new route is inserted, in order to evaluate its
overall impact, all the airport centralities need to be
re-computed which is a quite expensive task. Hence, we need to have
efficient incremental algorithms to tackle this problem. Such
algorithms can be used as a fundamental building block to centrality-
and shortest-path-based network management problems (and their variants)
as well as temporal centrality/shortest-path analyses and dynamic
network analyses. In this work, we investigate this subproblem.

\begin{definition} \emph{(Incremental closeness centrality)}
  Given a graph $G = (V,E)$, its centrality vector ${\tt cc}\xspace$, and an edge
  $uv$, find the centrality vector ${\tt cc}\xspace'$ of the graph $G' = (V,E
  \cup \{uv\})$~(or $G' = (V,E \setminus \{uv\})$).
\end {definition}

\section{Maintaining Centrality}\label{sec:main}

Many interesting real-life networks are scale free. The diameters of
these networks grow proportional to the logarithm of the number of
nodes. That is, even with hundreds of millions of vertices, the
diameter is small, and when the graph is modified with minor updates,
it tends to stay small. Combining this with their power-law degree
distribution, we obtain the spike-shaped shortest-distance
distribution as shown in Figure~\ref{fig:levels}. We use two main
approaches: {\em work filtering} and {\em SSSP hybridization} to
exploit these observations and reduce the centrality computation
time.

\subsection{Work Filtering}

For efficient maintenance of closeness centrality in case of an edge
insertion/deletion, we propose a {\em work filter} which reduces the
number of SSSPs in Algorithm~\ref{alg:cc} and the cost of each
SSSP. Work filtering uses three techniques: filtering with {\em level
differences}, with {\em biconnected component decomposition}, and with
{\em identical vertices}.

\subsubsection{Filtering with level differences}

The motivation of level-based filtering is detecting the unnecessary
updates and filtering them.  Let $G = (V, E)$ be the current graph and
$uv$ be an edge to be inserted to $G$. Let $G' = (V, E \cup {uv})$
be the updated graph. The centrality definition in~\eqref{eq:first}
implies that for a vertex $s \in V$, if ${d}_G(s,t) = {d}_{G'}(s,t)$
for all $t \in V$ then ${\tt cc}\xspace[s] = {\tt cc}\xspace'[s]$. The following theorem is
used to detect such vertices and filter their SSSPs.

\begin{theorem}
Let $G = (V,E)$ be a graph and $u$ and $v$ be two vertices in $V$
s.t. $uv \notin E$. Let $G' = (V,E \cup {uv})$. Then ${\tt cc}\xspace[s] =
{\tt cc}\xspace'[s]$ if and only if $|{d}_G(s,u) - {d}_G(s,v)|
\leq 1$.\label{thm:add}
\end{theorem}

\begin{proof}
If $s$ is disconnected from $u$ and $v$, $uv$'s insertion will not
change the closeness centrality of $s$. Hence, ${\tt cc}\xspace[s] = {\tt cc}\xspace'[s]$. If $s$
is only connected to one of $u$ and $v$ in $G$ the difference $|{d}_G(s,u) -
{d}_G(s,v)|$ is $\infty$, and the closeness centrality score of $s$ needs
to be updated by using the new, larger connected component containing
$s$.

When $s$ is connected to both $u$ and $v$ in $G$, we investigate the edge
insertion in three cases as shown in Figure~\ref{fig:leveldiffs}:

Case 1. ${d}_G(s,u) = {d}_G(s,v)$: Assume that the path $s
  \stackrel{P}{\leadsto} u$--$v \stackrel{P'}{\leadsto} t$ is a
  shortest $s \leadsto t$ path in $G'$ containing $uv$. Since
  ${d}_G(s,u) = {d}_G(s,v)$ there exist another path $s
  \stackrel{P''}{\leadsto} v \stackrel{P'}{\leadsto} t$ in $G'$ with
  one less edge. Hence, $uv$ cannot be in a shortest path:
  $\forall t \in V, {d}_G(s,t) = {d}_{G'}(s,t)$.

Case 2. $|{d}_G(s,u) - {d}_G(s,v)| = 1$: Let ${d}_G(s,u) <
  {d}_G(s,v)$ and assume that $s \stackrel{P}{\leadsto} u$--$v
  \stackrel{P'}{\leadsto} t$ is a shortest path in $G'$ containing
  $uv$. Since ${d}_G(s,v) = {d}_G(s,u) + 1$, there exist another
  path $s \stackrel{P''}{\leadsto} v \stackrel{P'}{\leadsto} t$ in
  $G'$ with the same number of edges. Hence, $\forall t \in V, {d}_G(s,t) =
  {d}_{G'}(s,t)$.

Case 3. $|{d}_G(s,u) - {d}_G(s,v)| > 1$: Let ${d}_G(s,u) <
  {d}_G(s,v)$. The path $s \leadsto u$--$v$ in $G'$ is shorter than
  the shortest $s \leadsto v$ path in $G$ since ${d}_G(s,v) > {d}_G(s,u)
  + 1$. Hence, an update on ${\tt cc}\xspace[s]$ is necessary.
\end{proof}

\begin{figure}[htbp]
\vspace*{-1ex}
\center
\includegraphics[width=0.45\textwidth]{levels.pdf}
\vspace*{-1ex}
\caption{\small (1) Three cases of edge insertion: when an edge $uv$ is inserted to the
 graph $G$, for each vertex $s$, one of them is true:
 (a) ${d}_G(s,u) = {d}_G(s,v)$, (b) $|{d}_G(s,u) - {d}_G(s,v)| =
 1$, and (c) $|{d}_G(s,u) - {d}_G(s,v)| > 1$.}
\label{fig:leveldiffs}
\vspace*{-1ex}
\end{figure}

Although Theorem~\ref{thm:add} yields to a filter only in case
of edge insertions, the following corollary which is used for edge
deletion easily follows.
\begin{corollary}
Let $G = (V, E)$ be a graph and $u$ and $v$ be two vertices in $V$
s.t. $uv \in E$. Let $G' = (V,E \setminus \{uv\})$. Then ${\tt cc}\xspace[s] =
{\tt cc}\xspace'[s]$ if and only if $|{d}_{G'}(s,u) - {d}_{G'}(s,v)|
\leq 1$.
\end{corollary}
With this corollary, the work filter can be implemented for both
edge insertions and deletions.
The pseudocode of the update algorithm in case of
an edge insertion is given in Algorithm~\ref{alg:filtered}.
When an edge $uv$ is inserted/deleted, to employ the filter, we first compute
the distances from $u$ and $v$ to all other vertices. And, it filters
the vertices satisfying the statement of Theorem~\ref{thm:add}.

\renewcommand{\baselinestretch}{0.70}
\begin{algorithm}[htbp]
\DontPrintSemicolon
\SetKwComment{tcp}{$\triangleright$}{} \small
\caption{Simple work filtering}
\label{alg:filtered}
\KwData{${G = (V,E)}$, ${\tt cc}\xspace[.]$, $uv$}
\KwOut{${\tt cc}\xspace'[.]$}
  $G' \gets (V, E \cup \{uv\})$\;
  ${d} u[.] \gets $ SSSP($G$, $u$) \tcp{\ distances from $u$ in $G$}
  ${d} v[.] \gets $ SSSP($G$, $v$) \tcp{\ distances from $v$ in $G$}

  \For{{\bf each} $s \in V$} {
	\If{$|{d} u[s] - {d} v[s]| \leq 1$} {
		${\tt cc}\xspace'[s] = {\tt cc}\xspace[s]$\;
     } \Else {
     	\tcp{\ use the computation in Algorithm~\ref{alg:cc} with $G'$}
     }
  }
  \Return{${\tt cc}\xspace'[.]$}\;
 \end{algorithm}
\renewcommand{\baselinestretch}{1}

In theory, filtering by levels can reduce the update time
significantly. However, in practice, its effectiveness depends on the
underlying structure of $G$. Many real-life networks have been
repeatedly shown to possess unique characteristics such as a small
diameter and a power-law degree distribution~\cite{McGlohon11}.  And
the spread of information is extremely
fast~\cite{Doerr11,Doerr12}. The proposed filter exploits one of these
characteristics for efficient closeness centrality updates: the
distribution of shortest-path lengths. Its efficiency is based on the
phenomenon shown in Figure~\ref{fig:levels} for a set of graphs used
in our experiments: the probability distribution function for a
shortest-path length being equal to $x$ is unimodular and spike-shaped
for many social networks and also some others. This is the outcome of
the short diameter and power-law degree distribution. On the other
hand, for some spatial networks such as road networks, there are no
sharp peaks and the shortest-path distances are distributed in a more
uniform way. The work filter we propose here prefer the former.

\begin{figure}[htbp]
\vspace*{-1ex}
\center
\includegraphics[width=0.9\columnwidth]{levelsocial.pdf}
\vspace*{-1ex}
\caption{\small Probability of the distance between two~(connected) vertices
is equal to $x$ for four social and web networks.}
\label{fig:levels}
\vspace*{-1ex}
\end{figure}

\subsubsection{Filtering with biconnected components}

Our work filter can be enhanced by employing and maintaining a
biconnected component decomposition~(BCD) of $G = (V,E)$.  A BCD is a
partitioning $\Pi$ of the edge set $E$ where $\Pi(e)$ indicates the
component of each edge $e \in E$. A toy graph and its BCDs before and
after edge insertions are given in Figure~\ref{fig:bcd}.

\begin{figure}[htbp]
\vspace*{-1ex}
\center
\hspace*{-1ex}
\subfigure[$G$]{\includegraphics[height=1.7cm]
{graph0.pdf}\label{fig:graph}}
\hspace*{1ex}
\subfigure[$\Pi$]{\includegraphics[height=1.85cm]
{bicon.pdf}\label{fig:pig}}
\hspace*{1ex}
\subfigure[$\Pi'$]{\includegraphics[height=1.9cm]
{biconup.pdf}\label{fig:pig2}}
\vspace*{1ex}
\caption{\small A graph $G$~(left), its biconnected component decomposition
$\Pi$ into $4$ components~(middle), and the updated $\Pi'$ with $3$
components when the edge $bd$ is inserted~(right). The sets of
articulation vertices before and after the edge insertion are
$\{b,c,d\}$ and $\{b,d\}$, respectively. After the edge addition, $cid
= 2$. That is to say, the second component contains the new
edge. Hence, the biconnected component $2$ is extracted first and
executes an update algorithm only for the vertices $\{b,c,d\}$. It
also initiates a fixing phase to update the closeness centrality
values for the rest of the vertices. After the edge insertion,
${rep}[a] = b$, and ${rep}[e] = {rep}[f] = {rep}[g] = {rep}[h] = b$. Hence,
${\tt R}[b] = 2$, ${\tt R}[c] = 1$, and ${\tt R}[d] = 5$. And, ${\tt RF}[b]
= 1$, ${\tt RF}[c] = 0$, and ${\tt RF}[d] = 6$.}
\label{fig:bcd}
\vspace*{-1ex}
\end{figure}

When $uv$ is inserted to $G = (V,E)$ and $G' = (V,E' \cup \{uv\})$
is obtained, we check if
$$\{\Pi(uw): w \in \Gamma_G(u)\} \cap \{\Pi(vw): w \in \Gamma_G(v)\}$$
is empty or not. If the intersection is not empty, there will be only
one element in it, $cid$, which is the id of the biconnected component
of $G'$ containing $uv$~(otherwise $\Pi$ is not a valid BCD). In this case, $\Pi'(e)$ is set to $\Pi(e)$ for all $e \in
E$ and $\Pi'(uv)$ is set to $cid$. If there is no biconnected
component containing both $u$ and $v$~(see Figure~\ref{fig:pig2}), i.e.,
if the intersection above is empty, we construct $\Pi'$ from
scratch and set $cid = \Pi'(uv)$. $\Pi$ can be computed in linear, $\mathcal{O} (m +
n)$ time~\cite{Hopcroft10}. Hence, the
cost of BCD maintenance is negligible compared to the cost of
updating closeness centrality.

Let $G'_{cid} = (V_{cid}, E'_{cid}) $ be the biconnected component of $G'$ containing $uv$ where
\begin{align*}
V_{cid} &= \{v \in V: cid \in \{\Pi'(vw): vw \in E'\}\}, \\
E'_{cid} &= \{e \in E': \Pi'(e) = cid\}.
\end{align*}
Let ${\cal A}_{cid} \subseteq V_{cid}$ be the set of articulation vertices in
$G'_{cid}$. Given $\Pi'$, it is easy to detect the articulation
vertices since  $u$ is an articulation vertex if and only if it is
part of at least
two components in the BCD: $|\{\Pi'(uw): uw \in E'\}| > 1$.

We will execute SSSPs only for the vertices in $G'_{cid}$ and use
the new values to fix the centralities for the rest of the graph. The
contributions of the vertices in $V \setminus V_{cid}$ are integrated
to the SSSPs by using a representative function
${rep}: V \rightarrow V_{cid} \cup \{\tt{null}\}$ which maps each
vertex $v \in V$ either to a representative in $G'_{cid}$ or to
$\tt{null}$ (if $v$ and the vertices in $V_{cid}$
are in different connected components of $G'$).

For each vertex $u \in V_{cid}$, we set ${rep}[u] = u$.  For the other
vertices, let $\overline{G'_{cid}} = \{V, E' \setminus E'_{cid}\}$. If
a vertex $v \in V \setminus V_{cid}$ and an articulation vertex $u \in
{\cal A}_{cid}$ are connected in $\overline{G'_{cid}}$, i.e.,
${d}_{\overline{G'_{cid}}}(u,v) \neq \infty$, we say that $v$ is
represented by $u$ in $G'_{cid}$ and set ${rep}[v] = u$. Otherwise,
${rep}[v]$ is set to ${\tt null}$. The following theorem states that
${rep}$ is well defined: each vertex is represented by at most one vertex.

\begin{theorem}\label{thm:rep}
 For each $v$ in $V \setminus V_{cid}$, there is at most
 one articulation vertex $u \in {\cal A}_{cid}$ such that
 ${d}_{\overline{G'_{cid}}}(u,v) \neq \infty$.
\end{theorem}
\begin{proof}
The proof directly follows from the definition of BCD and is omitted.
\end{proof}

Since all the~(shortest) paths from a vertex $v \in V\setminus V_{cid}$ to a
vertex in $V_{cid}$ are passing through ${rep}[v]$, the following is a
corollary of the theorem.
\begin{corollary}\label{cor:path}
For each vertex $v \in V \setminus V_{cid}$ with ${rep}[v] \neq {\tt
null}$,
${d}_{\overline{G'_{cid}}}(v, {rep}[v]) = {d}_{G'}(v, {rep}[v]),$
which is different than $\infty$.  Furthermore, for a vertex $w \in V$
which is also represented in $G'_{cid}$ but not in the connected
component of ${\overline{G'_{cid}}}$ containing $v$, ${d}_{G'}(v,w)$
is equal to
$${d}_{G'}(v,{rep}[v]) + {d}_{G'}({rep}[v],{rep}[w]) + {d}_{G'}({rep}[w],w).$$
If $w \in V_{cid}$ the last term on the right is $0$, since ${rep}[w] =
w$.
\end{corollary}

To correctly update the new centrality values, we compute two
extra values for each vertex $u \in V_{cid}$,
\begin{align}
{\tt R}[u] &= \left|\{v \in V: {rep}[v] = u\}\right|,\label{eq:card}\\
{\tt RF}[u] &= \sum_{\stackrel{v \in V}{{rep}[v] = u}}{d}_{G'}(u,v).\label{eq:sumcard}
\end{align}
That is, ${\tt R}[u]$ is the number of vertices in $V$ which are
represented by $u$~(including $u$). And ${\tt RF}[u]$ is the farness of
$u$ to these vertices in $G'$. The modified update
algorithm is given in Algorithm~\ref{alg:combined}.

\renewcommand{\baselinestretch}{0.70}
\begin{algorithm}[h]
\DontPrintSemicolon
\SetKwComment{tcp}{$\triangleright$}{} \small
\caption{Update with BCD and level differences}
\label{alg:combined}
\KwData{${G = (V,E)}$, $\Pi$, ${\tt cc}\xspace$, ${\tt far}\xspace$, $uv$}
\KwOut{${\tt cc}\xspace'[.]$, ${\tt far}\xspace'[.]$}
  \lnl{line:filter}\tcp{\ prepare for filtering}
  $G' \gets (V, E')$ where $E' \gets E \cup \{uv\}$\;
  $cSet_u \gets \{\Pi(uw): w \in \Gamma_G(u)\}$\;
  $cSet_v \gets \{\Pi(vw): w \in \Gamma_G(v)\}$\;

  \If{$cSet_u \cap cSet_v \neq \emptyset$} {
    $cid \gets $ \#the common component\;
    $\Pi'(e) \gets \Pi(e)$ $\forall e \in E$, $\Pi'(uv) \gets cid$\;
  } \lElse {
    construct $\Pi'$ from $G'$, $cid \gets \Pi'(uv)$\;
  }

  $V_{cid} \gets \{v \in V: cid \in \{\Pi'(vw): vw \in E'\}\}$ \;
  $E'_{cid} \gets \{e \in E': \Pi'(e) = cid\}$ \;
  $G'_{cid} = (V_{cid}, E'_{cid})$ \;
  $G_{cid} = (V_{cid}, E'_{cid} \setminus \{uv\})$\;

  Set ${rep}[v]$, $\forall v \in V$\;
  ${\tt R}[u] \gets \left|\{v \in V, {rep}[v] = u\}\right|$, $\forall u \in V_{cid}$\;
  ${\tt RF}[u] \gets \sum_{v \in V, {rep}[v] = u}{d}_{G'}(u,v)$, $\forall u \in V_{cid}$\;

  ${d} u[.] \gets $ SSSP($G_{cid}$, $u$), ${d} v[.] \gets $ SSSP($G_{cid}$, $v$)\;

  \lnl{line:update}\tcp{\ update phase}
  \For{{\bf each} $s \in V_{cid}$} {
	\lIf{$|{d} u[s] - {d} v[s]| \leq 1$} {
	  ${\tt cc}\xspace'[s] = {\tt cc}\xspace[s]$\;
     } \Else {
	\lnl{line:source}$Q \leftarrow$ empty queue \;
	  ${d}[v] \gets \infty$, $\forall v \in V_{cid} \setminus{\{s\}}$ \;
	  $Q$.push($s$),\ ${d}[s] \gets 0$ \;
	  ${\tt far}\xspace'[s] \gets 0$ \;
	  \While{$Q$ is not empty} {
	    $v \leftarrow Q$.pop()\;
	    \For{{\bf all} $w \in \Gamma_{G'_{cid}}(v)$}{
              \If{${d}[w] = \infty$}{
		$Q$.push($w$) \;
		${d}[w] \gets {d}[v] + 1$ \;
		\lnl{line:far}${\tt far}\xspace'[s] \gets {\tt far}\xspace'[s] + ({d}[w] \times {\tt R}[w]) + {\tt RF}[w]$\;
              }
	    }
	  }
	  ${\tt cc}\xspace'[s] = \frac{1}{{\tt far}\xspace'[s]}$
	}
  }

  \lnl{line:fix}\tcp{\ fix phase}
  \For{{\bf each} $v \in V \setminus V_{cid}$} {
    $r \gets {rep}[v]$\;
    \If{$r \neq {\tt{null}}$ {\bf and} ${\tt far}\xspace[r] \neq {\tt far}\xspace'[r]$} {
      \lnl{line:farup}${\tt far}\xspace'[v] \gets {\tt far}\xspace[v] - ({\tt far}\xspace[r] - {\tt far}\xspace'[r])$\;
      ${\tt cc}\xspace'[v] \gets \frac{1}{{\tt far}\xspace'[v]}$\;
    }
  }

  \Return{${\tt cc}\xspace'[.]$}\;
 \end{algorithm}
\renewcommand{\baselinestretch}{1}

\begin{lemma}\label{lem:bcd1}
For each vertex $v \in V_{cid}$, Algorithm~\ref{alg:combined} computes
the correct ${\tt cc}\xspace'[v]$ value.
\end{lemma}

\begin{proof}
We will prove that ${\tt far}\xspace'[v]$ is correct for all $v \in V_{cid}$. Let
$v = s$ be the vertex whose closeness centrality update is started at
line~\ref{line:source}. At line~\ref{line:far} of
Algorithm~\ref{alg:combined}, the update on ${\tt far}\xspace'[v]$ is
${d}_{G'}(v,w) \times {\tt R}[w] + {\tt RF}[w]$
which can be rewritten as
$$\sum_{\stackrel{u \in V}{{rep}[u] =  w}}{d}_{G'}(v,w) + {d}_{G'}(w,u),$$
by using~\eqref{eq:card} and~\eqref{eq:sumcard}. According to
Corollary~\ref{cor:path}, this is equal to
$$\sum_{\stackrel{u \in V}{{rep}[u] = w}}{d}_{G'}(v,u).$$
Due to the definition of ${rep}$, only the
vertices which are connected to $v$ will have an effect on ${\tt far}\xspace'[v]$.
And due to Theorem~\ref{thm:rep}, each vertex can contribute to
at most one update. Hence
$$\sum_{w \in V_{cid}}\sum_{\stackrel{u \in V} {{rep}[u] =
w}}{d}_{G'}(v,u) = \sum_{\stackrel{u \in V}{{d}_{G'}(v,u) \neq
\infty}}{d}_{G'}(v,u),$$ which is the ${\tt far}\xspace'[v]$ in $G'$ as
desired.
\end{proof}

\begin{lemma}\label{lem:bcd2}
For each vertex $v \in V \setminus V_{cid}$, Algorithm~\ref{alg:combined} computes
the correct ${\tt cc}\xspace'[v]$ value.
\end{lemma}

\begin{proof}
We will prove that ${\tt far}\xspace'[v]$ is correct for all $v \in V \setminus
V_{cid}$ after the fix phase. Let $u = {rep}[v]$. If $u$ is {\tt
null} then $v$'s farness and hence closeness value will remain the
same.

Assume that $u$ is not null. Let $w$ be a vertex with ${rep}[w] \neq
{\tt null}$. If $w$ and $v$ are in the same connected component of
$\overline{G'_{cid}}$ then ${d}_G(v,w) = {d}_{G'}(v,w)$ and
${d}_G(u,w) = {d}_{G'}(u,w)$. Hence, the change on ${\tt far}\xspace[v]$ and
${\tt far}\xspace[u]$ due to $w$ are both $0$. On the other hand, if $w$
is in a different connected component of $\overline{G'_{cid}}$
according to Corollary~\ref{cor:path},
$${d}_{G'}(v,w) = {d}_{G'}(v,u) + {d}_{G'}(u,{rep}[w]) + {d}_{G'}({rep}[w],w),$$
where the sum of the second and the third terms is equal
to ${d}_{G'}(u,w)$. Since the first term does not change by the
insertion of $uv$, the change on ${d}_{G'}(u,w)$ is equal to the
change on ${d}_{G'}(v,w)$. That is when aggregated, the change on
${\tt far}\xspace[v]$ is equal to the change on ${\tt far}\xspace[u]$. Lemma~\ref{lem:bcd1}
implies that ${\tt far}\xspace[u]$ is correct. Hence, ${\tt far}\xspace'[v]$, computed at
line~\ref{line:farup}, must also be correct.
\end{proof}

\begin{theorem}
For each vertex $v \in V$, Algorithm~\ref{alg:combined} computes
the correct ${\tt cc}\xspace'[v]$ value.
\end{theorem}
\begin{proof}
Follows from Lemma~\ref{lem:bcd1} and~\ref{lem:bcd2}.
\end{proof}

The complexity of the update algorithm is $\mathcal{O}(n(m+n))$. And
the overhead of filter preparation~(line~\ref{line:filter}
through~\ref{line:update}) is $\mathcal{O}(m+n)$ since it only
contains a constant number of graph traversals. In case of an edge
deletion, it is enough to get $G'_{cid}$ as the biconnected component
which was containing the deleted edge. The rest of the procedure can
be adapted in a straightforward manner.

\subsubsection{Filtering with identical vertices}

Our preliminary analyses on various networks show that some of the
graphs contain a significant amount of {\em identical} vertices which
have the same/a similar neighborhood structure. This can be exploited
to reduce the number of SSSPs further. We investigate two types of
identical vertices.

\begin{definition}
In a graph $G$, two vertices $u$ and $v$ are \em{type-I-identical} if and only if
$\Gamma_G(u) = \Gamma_G(v)$.
\end{definition}

\begin{definition}
In a graph $G$, two vertices $u$ and $v$ are \em{type-II-identical} if
and only if $\{u\} \cup \Gamma_G(u) = \{v\} \cup \Gamma_G(v)$.
\end{definition}

Both types form an equivalance
class relation since they are reflexive, symmetric, and
transitive. Furthermore, all the non-trivial classes they form (i.e.,
the ones containing more than one vertex) are
disjoint.

Let $u, v \in V$ be two identical vertices. One can see that for any
vertex $w \in V \setminus \{u,v\}$, ${d}_{G}(u,w) =
{d}_{G}(v,w)$. Then the following is true.

\begin{corollary}
Let ${\cal I} \subseteq V$ be a vertex-class containing type-I or type-II
identical vertices. Then the closeness centrality values of all the
vertices in ${\cal I}$ are equal.
\end{corollary}

To construct these equivalance classes for the initial graph, we first
use a hash function to map each vertex neighborhood to an integer:
$hash_I[u] = \sum_{v \in \Gamma_G(u)} v$.
We then sort the vertices with respect to their hash values and
construct the type-I vertex-classes by eliminating false positives due
to collisions on the hash function.
A similar process is applied to detect type-II vertex classes.
The complexity of this initial construction is
$\mathcal{O}(n \log n + m)$ assuming the number of collisions is small
and hence, false-positive detection cost is negligible.

Maintaining the equivalance classes in case of edge insertions and
deletions is easy: For example, when $uv$ is added to $G$, we first
subtract $u$ and $v$ from their classes and insert them to new
ones~(or leave them as singleton if none of the vertices are now
identical with them). The cost of this maintenance is $\mathcal{O}(n +
m)$.

While updating closeness centralities of the vertices in $V$, we
execute an SSSP at line~\ref{line:source} of
Algorithm~\ref{alg:combined} for at most one vertex from each
class. For the rest of the vertices, we use the same closeness
centrality value. The improvement is straightforward and the
modifications are minor. For brevity, we do not give the
pseudocode.

\subsection{SSSP Hybridization}

The spike-shaped distribution given in Figure~\ref{fig:levels} can also
be exploited for SSSP hybridization. Consider the execution of
Algorithm~\ref{alg:cc}: while executing an SSSP with source $s$, for
each vertex pair $u,v$, $u$ is processed before $v$ if and only if
$d_G(s,u) < d_G(s,v)$. That is, Algorithm~\ref{alg:cc} consecutively
uses the vertices with distance $k$ to find the vertices with distance
$k+1$. Hence, it visits the vertices in a {\em top-down} manner.  SSSP
can also be performed in a a {\em bottom-up} manner. That is to say, after all
distance~(level) $k$ vertices are found, the vertices whose levels are
unknown can be processed to see if they have a neighbor at level
$k$.

Figure~\ref{fig:bfstimes} gives the execution times of bottom-up and
top-down SSSP variants for processing each level. The trend for
top-down resembles the shortest distance distribution in small-world
networks. This is expected since in each level $\ell$, the vertices
that are $\ell$ step far away from $s$ are processed. On the other
hand, for the bottom-up variant, the execution time is decreasing
since the number of unprocessed nodes is decreasing. Following the
idea of Beamer~et~al.~\cite{Beamer12}, we hybridize the SSSPs
throughout the centrality update phase in
Algorithm~\ref{alg:combined}. We simply compare the number of edges
need to be processed for each variant and choose the cheaper one. For
the case presented in Figure~\ref{fig:bfstimes}, the hybrid algorithm
is $3.6$ times faster than the top-down variant.

\begin{figure}[htbp]
\vspace*{-1ex}
\center
\includegraphics[width=0.40\textwidth]{bfstimes.pdf}
\vspace*{-1ex}
\caption{\small Execution times of bottom-up, top-down, and hybrid SSSPs at
  each level for the {\it wiki-Talk} graph. The hybrid version is
  $3.63$ and $4.59$ times faster than the top-down and bottom-up
  versions respectively.
}
\label{fig:bfstimes}
\vspace*{-1ex}
\end{figure}

\section{Related Work}\label{sec:rel}

To the best of our knowledge, there are only two works that deal with
maintaining centrality in dynamic networks. Yet, both are interested
in betweenness centrality. Lee~et~al. proposed the {\bf QUBE}
framework which updates betweenness centrality in case of edge
insertion and deletion within the network~\cite{Lee2012}. {\bf QUBE}
relies on the biconnected component decomposition of the graphs. Upon
an edge insertion or deletion, assuming that the decomposition does not
change, only the centrality values within the updated biconnected
component are recomputed from scratch. If the edge insertion/deletion
affects the decomposition the modified graph is decomposed into its
biconnected components and the centrality values in the affected part
are recomputed. The distribution of the vertices to the biconnected
components is an important criteria for the performance of {\bf
QUBE}. If a large component exists, which is the case for many
real-life networks, one should not expect a significant reduction on
update time. Unfortunately, the performance of {\bf QUBE} is only
reported on small graphs~(less than 100K edges) with very low edge
density. In other words, it only performs significantly well on small
graphs with a tree-like structure having many small biconnected
components.

Green~et~al. proposed a technique to update centrality scores rather
than recomputing them from scratch upon edge insertions~(can be
extended to edge deletions)~\cite{Green2012}. The idea is storing the
whole data structure used by the previous betweenness centrality
update kernel.  This storage is indeed useful for two main reasons: it
avoids a significant amount of recomputation since some of the
centrality values will stay the same. And second, it enables a partial
traversal of the graph even when an update is necessary.  However, as
the authors state, $\mathcal{O}(n^2 + nm)$ values must be kept on the
disk. For the Wikipedia user communication and DBLP
coauthorship networks, which contain
thousands of vertices and millions of edges, the technique by
Green~et~al. requires TeraBytes of memory. The largest graph used
in~\cite{Green2012} has approximately $20K$ vertices and $200K$ edges;
the quadratic storage cost prevents their storage-based techniques to
scale any higher. On the other hand, the memory footprint of our
algorithms are linear and hence they are much more practical.

\section{Experimental Results}\label{sec:exp}

We implemented our algorithms in {\tt C}. The code is compiled with {\tt gcc
v4.6.2} and optimization flags {\tt -O2 -DNDEBUG}. The graphs are kept
in memory in the compressed row storage~(CRS) format. The experiments
are run on a computer with two Intel Xeon E$5520$ CPU clocked at $2.27$GHz
and equipped with $48$GB of main memory. All the experiments are run sequentially.

For the experiments, we used $10$ networks from the UFL Sparse Matrix
Collection\footnote{\url{http://www.cise.ufl.edu/research/sparse/matrices/}} and we also
extracted the coauthor network from current set of DBLP papers.
Properties of the graphs are summarized in
Table~\ref{tab:graph_prop}.
We symmetrized the directed graphs. The graphs are
listed by increasing number of edges and a distinction is made
between small graphs (with less than 500K edges) and the large graphs
(with more than 500K) edges.

\begin{table}
\smaller
\scalebox{0.85}{
 \begin{tabular}{|l|rr|rr|r|}
 \hline
 \multicolumn{3}{|c|}{\bf Graph}&\multicolumn{3}{c|}{{\bf Time} (in sec.)}\\ \hline
   name & {$|V|$} & {$|E|$} & Org. & Best & Speedup\\
 \hline
{\it hep-th} & 8.3K & 15.7K & 1.41 & 0.05 & 29.4 \\
{\it PGPgiantcompo} & 10.6K & 24.3K & 4.96 & 0.04 & 111.2 \\
{\it astro-ph} & 16.7K & 121.2K & 14.56 & 0.36 & 40.5 \\
{\it cond-mat-2005} & 40.4K & 175.6K & 77.90 & 2.87 & 27.2 \\ \hline
\multicolumn{5}{|r|}{\bf geometric mean}&{\bf 43.5}\\\hline
{\it soc-sign-epinions} & 131K & 711K & 778 & 6.25 & 124.5 \\
{\it loc-gowalla} & 196K & 950K & 2,267 & 53.18 & 42.6 \\
{\it web-NotreDame} & 325K & 1,090K & 2,845 & 53.06 & 53.6\\
{\it amazon0601} & 403K & 2,443K & 14,903 & 298 & 50.0 \\
{\it web-Google} & 875K & 4,322K & 65,306 & 824 & 79.2\\
{\it wiki-Talk} & 2,394K & 4,659K & 175,450 & 922 & 190.1 \\
{\it DBLP-coauthor} & 1,236K & 9,081K & 115,919 & 251 & 460.8\\\hline
 \multicolumn{5}{|r|}{\bf geometric mean}&{\bf 99.8}\\\hline
 \end{tabular}
}
\vspace*{-1ex}
\caption{\small The graphs used in the experiments. Column {\em Org.} shows
   the initial closeness computation time of $\textsc{CC}\xspace$ and {\em Best}
   is the best update time we obtain in case of streaming
   data.}
 \label{tab:graph_prop}
\vspace*{-1ex}
\end{table}

\subsection{Handling topology modifications}

To assess the effectiveness of our algorithms, we need to know that when each
edge is inserted to/deleted from the graph. Our datasets from UFL Sparse Matrix
Collection do not have this information. To conduct our experiments on
these datasets, we delete 1,000 edges from a graph chosen randomly in the following
way: A vertex $u \in V$ is selected randomly~(uniformly), and a vertex $v \in \Gamma_G(u)$
is selected randomly~(uniformly). Since we do not want to change the
connectivity in the graph~(having disconnected components can make
our algorithms much faster and it will not be fair to \textsc{CC}\xspace), we discard $uv$
if it is a bridge. If this is not the case we delete it from $G$
and continue. We construct the initial graph by deleting these 1,000
edges. Each edge is then inserted one by one, and
our algorithms are used to recompute the closeness centrality after each
insertion. Beside these random insertion experiments, we also evaluated
our algorithms on a real temporal dataset of the DBLP coauthor
graph\footnote{\url{http://www.informatik.uni-trier.de/~ley/db/}}. In
this graph, there is an edge between two authors if
they published a paper. Publication dates are used as timestamps
of edges. We first constructed the graph for the papers published before
January 1, 2013. Then, we inserted the coauthorship edges of the papers since then.
Although our experiments perform edge insertion, edge
deletion is a very similar process which should give comparable
results.

In addition to \textsc{CC}\xspace, we configure our algorithms in four different ways:
\textsc{CC-B}\xspace only uses biconnected component decomposition (BCD), \textsc{CC-BL}\xspace uses
BCD and filtering with levels, \textsc{CC-BLI}\xspace uses all three work
filtering techniques including identical vertices. And
\textsc{CC-BLIH}\xspace uses all the techniques described in this paper including
SSSP hybridization.

Table~\ref{tab:results} presents the results of the experiments.The
second column, \textsc{CC}\xspace, shows the time to run the full Brandes
algorithm for computing closeness centrality on the original version
of the graph. Columns $3$--$6$ of the table present absolute
runtimes~(in seconds) of the centrality computation algorithms.  The
next four columns, $7$--$10$, give the speedups achieved by each
configuration. For instance, on the average, updating the closeness
values by using \textsc{CC-B}\xspace on {\em PGPgiantcompo} is $11.5$ times faster
than running \textsc{CC}\xspace. Finally the last column gives the overhead of our
algorithms per edge insertion, i.e., the time necessary to detect the
vertices to be updated, and maintain BCD and identical-vertex
classes. Geometric means of these times and speedups are also given to
provide comparison across instances.

\begin{table*}
\center
\smaller
\scalebox{0.90}{
 \begin{tabular}{|l|r|rrrr|rrrr|r|}
 \hline
 &\multicolumn{5}{|c|}{\bf Time~(secs)}&\multicolumn{4}{|c|}{\bf
 Speedups}& \multicolumn{1}{|c|}{\bf Filter}\\
{\bf Graph} & \textsc{CC}\xspace & \textsc{CC-B}\xspace & \textsc{CC-BL}\xspace & \textsc{CC-BLI}\xspace & \textsc{CC-BLIH}\xspace &
 \textsc{CC-B}\xspace & \textsc{CC-BL}\xspace & \textsc{CC-BLI}\xspace & \textsc{CC-BLIH}\xspace & {\bf time~(secs)}\\\hline
{\it hep-th} & 1.413	&	0.317	&	0.057	&	0.053 &	0.048	&	4.5	&	24.8	&	26.6	& 29.4	& 0.001\\
{\it PGPgiantcompo}& 4.960	&	0.431	&	0.059	& 0.055	&	0.045	&	11.5	&	84.1	&	89.9 &	111.2	& 0.001\\
{\it astro-ph} & 14.567	&	9.431	&	0.809	&	0.645 &	0.359	&	1.5	&	18.0	&	22.6	&  40.5	& 0.004\\
{\it cond-mat-2005}& 77.903	&	39.049	&	5.618	& 4.687	&	2.865	&	2.0	&	13.9	&	16.6 &	27.2	& 0.010\\\hline
Geometric mean & 9.444 & 2.663 & 0.352 & 0.306 & 0.217 & 3.5 & 26.8 & 30.7 & 43.5 & 0.003\\\hline
{\it soc-sign-epinions} & 778.870	&	257.410		&	20.603 	&	19.935	&	6.254	&	3.0	&	37.8	&  	39.1		& 124.5	& 0.041\\
{\it loc-gowalla}& 2,267.187		&	1,270.820		&	132.955	&	135.015	&	53.182	&	1.8	&	17.1	&	16.8		& 42.6	&0.063\\
{\it web-NotreDame} & 2,845.367	&	579.821		&	118.861	& 	83.817	&	53.059	&	4.9	&	23.9	&	33.9 		& 53.6	& 0.050\\
{\it amazon0601} & 14,903.080		&	11,953.680	&      	540.092	&	551.867	&	298.095	&	1.2	&      	27.6	&	27.0		& 50.0	& 0.158\\
{\it web-Google} & 65,306.600		&	22,034.460	&      	2,457.660	&	1,701.249	&	824.417	&	3.0	& 	26.6	&	38.4		& 79.2	& 0.267\\
{\it wiki-Talk} & 175,450.720		&	25,701.710	&   	2,513.041 &  	2,123.096	& 	922.828 	&	6.8	&	69.8	& 	82.6		& 190.1	& 0.491\\
{\it DBLP-coauthor} &  115,919.518  & 	18,501.147	&  	288.269	& 	251.557	& 	252.647 	&	6.2	& 	402.1& 	460.8	& 458.8	& 0.530\\\hline
Geometric mean & 13,884.152		&	4,218.031		& 	315.777 	&	273.036 	&	139.170 	&	3.2	& 	43.9	 & 	50.8		& 99.7	& 0.146\\\hline

\end{tabular}
}
\vspace*{-1ex}
\caption{\small Execution times in seconds of all the algorithms and speedups
when compared with the basic closeness centrality algorithm \textsc{CC}\xspace. In
the table \textsc{CC-B}\xspace is the variant which uses only BCDs, \textsc{CC-BL}\xspace uses
BCDs and filtering with levels, \textsc{CC-BLI}\xspace uses all three work
filtering techniques including identical vertices. And
\textsc{CC-BLIH}\xspace uses all the techniques described in this paper including
SSSP hybridization. }
\label{tab:results}
\vspace*{-1ex}
\end{table*}

The times to compute closeness centrality using \textsc{CC}\xspace on the small
graphs range between $1$ to $77$ seconds. On large
graphs, the times range from $13$ minutes to $49$ hours. Clearly,
\textsc{CC}\xspace is not suitable for real-time network analysis and management
based on shortest paths and closeness
centrality. When all the techniques are used~(\textsc{CC-BLIH}\xspace), the time
necessary to update the closeness centrality values of the small
graphs drops below $3$ seconds per edge insertion. The improvements
range from a factor of $27.2$~({\em cond-mat-2005}) to $111.2$~({\em PGPgiantcompo}),
with an average improvement of $43.5$ across small
instances. On large graphs, the update time per insertion drops below
$16$ minutes for all graphs. The improvements
range from a factor of $42.6$~({\em loc-gowalla}) to $458.8$~({\em DBLP-coauthor}),
with an average of $99.7$.  For all
graphs, the time spent filtering the work is below one second which
indicates that the majority of the time is spent for SSSPs. Note that
this part is pleasingly parallel since each SSSP is independent from
each other.

The overall improvement obtained by the proposed
algorithms is very significant. The speedup obtained by using
BCDs~(\textsc{CC-B}\xspace) are $3.5$ and $3.2$ on the average for small and large
graphs, respectively. The graphs {\em PGPgiantcompo}, and
{\em wiki-Talk} benefits the most from BCDs~(with speedups
$11.5$ and $6.8$, respectively). Clearly using the biconnected
component decomposition improves the update performance. However,
filtering by level differences is the most efficient technique: \textsc{CC-BL}\xspace brings
major improvements over \textsc{CC-B}\xspace. For all social
networks, \textsc{CC-BL}\xspace increased the performance when compared with \textsc{CC-B}\xspace,
the speedups range from $4.8$~({\em web-NotreDame}) to
$64$~({\em DBLP-coauthor}). Overall, \textsc{CC-BL}\xspace brings a $7.61$
improvement on small graphs and a $13.44$ improvement on large graphs
over \textsc{CC}\xspace.

For each added edge $uv$, let $X$ be the random variable equal to
$|{d}_G(u,w) - {d}_G(v,w)|$. By using 1,000 $uv$ edges, we computed
the probabilities of the three cases we investigated before and give
them in Fig.~\ref{fig:leveldiffs01}. For each graph in the figure, the
sum of first two columns gives the ratio of the vertices not updated
by \textsc{CC-BL}\xspace. For the networks in the figure, not even $20\%$ of
the vertices require an update~($Pr(X > 1)$). This explains the
speedup achieved by filtering using level differences.
Therefore, level filtering is more useful for the graphs having
characteristics similar to small-world networks.

\begin{figure}[htbp]
\vspace*{-1ex}
\center
\includegraphics[width=0.44\textwidth]{leveldiff.pdf}
\vspace*{-1ex}
\caption{\small The bars show the distribution of random variable $X =
  |{d}_G(u,w) - {d}_G(v,w)|$ into three cases we investigated when
  an edge $uv$ is added.

}
\label{fig:leveldiffs01}
\vspace*{-1ex}
\end{figure}

Filtering with identical vertices is not as useful as the other two
techniques in the work filter. Overall, there is a $1.15$ times
improvement with \textsc{CC-BLI}\xspace on both small and large graphs compared
to \textsc{CC-BL}\xspace. For some graphs, such as {\em web-NotreDame}
and {\em web-Google}, improvements are much
higher~($30\%$ and $31\%$, respectively).

Finally, the hybrid implementation of SSSP also proved to be
useful. \textsc{CC-BLIH}\xspace is faster than \textsc{CC-BLI}\xspace by a factor of $1.42$ on
small graphs and by a factor of $1.96$ on large graphs. Although it
seems to improve the performance for all graphs, in some few cases,
the performance is not improved significantly.
This can be attributed
to incorrect decisions on SSSP variant
to be used. Indeed, we did not
benchmark the architecture
to discover the proper
parameter. \textsc{CC-BLIH}\xspace performs the best on social network graphs with
an improvement ratio of $3.18$~({\em soc-sign-epinions}), $2.54$~({\em
loc-gowalla}), and $2.30$~({\em wiki-Talk}).

All the previous results present the average update time for 1,000
successively added edges. Hence, they do not say anything about the
variance. Figure~\ref{fig:updatedist} shows the runtimes of \textsc{CC-B}\xspace
and \textsc{CC-BLIH}\xspace per edge insertion for {\em web-NotreDame} in a sorted
order. The runtime distribution of \textsc{CC-B}\xspace clearly has multiple
modes. Either the runtime is lower than $100$ milliseconds or it is
around $700$ seconds. We see here the benefit of BCD. According to
the runtime distribution, about $59\%$ of {\em web-NotreDame}'s
vertices are inside small biconnected components. Hence, the time per
edge insertion drops from 2,845 seconds to 700.
Indeed, the largest component only contains $41\%$ of the
vertices and $76\%$ of the edges of the original graph. The decrease
in the size of the components accounts for the gain of performance.

\begin{figure}[htbp]
\vspace*{-1ex}
\center
\includegraphics[width=0.44\textwidth]{updatetimes.pdf}
\vspace*{-1ex}
\caption{\small Sorted list of the runtimes per edge insertion for the first
  $100$ added edges of {\em web-NotreDame}.}
\label{fig:updatedist}
\vspace*{-1ex}
\end{figure}

The impact of level filtering can also be seen on
Figure~\ref{fig:updatedist}. $60\%$ of the edges in the main
biconnected component do not change the closeness values of many
vertices and the updates that are induced by their addition take less
than $1$ second. The remaining edges trigger more expensive updates
upon insertion. Within these $30\%$ expensive edge insertions,
identical vertices and SSSP hybridization provide a significant
improvement~(not shown in the figure).

\paragraph{Better Speedups on Real Temporal Data}

The best speedups are obtained on the DBLP coauthor network, which
uses real temporal data.  Using \textsc{CC-B}\xspace, we reach $6.2$ speedup w.r.t.
\textsc{CC}\xspace, which is bigger than the average speedup on all networks. Main
reason for this behavior is that $10\%$ of the inserted edges are
actually the new vertices joining to the network, i.e., authors with
their first publication, and \textsc{CC-B}\xspace handles these edges quite
fast. Applying \textsc{CC-BL}\xspace gives a $64.8$ speedup over \textsc{CC-B}\xspace, which is
drastically higher than on all other graphs.  Indeed, only $0.7\%$ of
the vertices require to run a SSSP algorithm when an edge is inserted
on the DBLP network. For the synthetic cases, this number is $12\%$.
\textsc{CC-BLI}\xspace provides similar speedups with random insertions and
\textsc{CC-BLIH}\xspace does not provide speedups because of the structure of the graph. Overall,
speedups obtained with real temporal data reaches $460.8$, i.e., $4.6$ times
greater than the average speedup on all graphs. Our algorithms appears
to perform much better on real applications than on synthetic ones.

\subsection{Summary}

All the techniques presented in this paper allow to update closeness
centrality faster than the non-incremental algorithm presented
in~\cite{brandes2001} by a factor of $43.5$ on small graphs and $99.7$
on large ones. Small-world networks such as social networks benefit
very well from the proposed techniques. They tend to have a
biconnected component structure that allow to gain some improvement
using \textsc{CC-B}\xspace. However, they usually have a large biconnected
component and still, most of the gain is derived from exploiting their
spike-shaped distance distribution which brings at least a factor of
$13.4$. Identical vertices typically brings a small amount of
improvement but helps to increase the performance during expensive
updates. Using all the techniques, we achieved to reduce the closeness
centrality update time from $2$ days to $16$ minutes for the graph
with the most vertices in our dataset~({\em wiki-Talk}). And for the
temporal DBLP coauthorship graph, which has the most edges, we reduced
the centrality update time from 1.3 days to 4.2 minutes.

\section{Conclusion}\label{sec:con}

In this paper we propose the first algorithms to achieve fast updates
of exact centrality values on incremental network modification at such
a large scale.  Our techniques exploit the biconnected component decomposition
of these networks, their spike-shaped shortest-distance distributions,
and the existence of nodes with identical neighborhood. In large
networks with more than $500K$ edges, our techniques proved to bring a
$99$ times speedup in average.
With a speedup of 458, the proposed techniques may even allow DBLP to
reflect the impact on centrality of the papers published in quasi
real-time. Our algorithms will serve as a fundamental building block
for the centrality-based network management problem, closeness
centrality computations on dynamic/streaming networks, and their
temporal analysis.

The techniques presented in this paper can directly be extended in two
ways. First, using a statistical sampling to compute an approximation
of closeness centrality only requires a minor adaptation on the SSSP
kernel to compute the contribution of the source vertex to other
vertices instead of its own centrality. Second, the techniques
presented here also apply to betweenness centrality with minor
adaptations.

As a future work, we plan to investigate
local search techniques for the centrality-based network management problem
using our incremental centrality computation algorithms.

\section{Acknowledgments}
This work was supported in parts by the DOE grant DE-FC02-06ER2775 and by
the NSF grants CNS-0643969, OCI-0904809, and OCI-0904802.

\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv


In high school and for a summer during college, I was employed at Pivotrac in Dalhart, Texas. They are a farm sprinkler monitoring business. It was my responsibility to clean, refurbish, and test the old monitoring units that came in and send them back out. This required soldering, multi-meter use, and extreme attention to detail.
During my junior year at Texas Tech, I obtained an internship from Textron Systems (formerly Overwatch Systems), in Austin, Texas. While my time here was brief, I did contribute to the Army DCGS-A program.
Immediately after graduation, I started work at L3 Technologies in Greenville, TX. I primarily work on the Viewpoint Project.
However, I have also worked on other Internal R&D projects, including writing backend Java services for websites, creating web apps using React and other technologies, participating as Scrum Master in the agile process, developing Android applications, and running Microsoft HoloLens demonstrations. For a short period of time I was also a part of the MC-12 project.


Auslec/L&H, hatched in 1886, is a wholesaler focused on the supply of electrical, industrial and safety products. With more than 130 years of experience, the company supports customers from commercial mining, oil, and gas through to industrial, utilities, and facility maintenance, and has 160 stores providing advice, technical and logistical support and e-commerce solutions including Webshop, ERP integration and app technologies.
Since January 2017, Auslec/L&H has been using dotmailer as its email marketing automation provider and already seeing tangible results, according to e-business development manager, Patricia Goncalves.
She told CMO more than 1.7 million emails were delivered in 2017 through the dotmailer platform. But the key was how well the team was able to target customers and tailor the message. Through the dotmailer technology, its companies are now using transactional and behavioural data to design, test and send automated campaigns.
The technology deployment has also helped Auslec significantly increase its customer database to 12,000 contacts. Since introducing more personalised communications, click-to-open rates range from 28 per cent to 35 per cent.
This is vital, Goncalves said given Auslec puts on massive promotions throughout the year, which can last as long as six months.
Goncalves said its former online platform was difficult to work with in terms of creating programs within programs. This led to a lack of transparency and "big picture" vision.
"If we wanted to create a program that was working for a full month, it would take us three days to set up a program," she said. "One of the difficulties was we couldn't see the big picture of the program. When we brought it across to dotmailer, we could see the whole flow, which gives us assurance about where the customer is.
As an example, Goncalves noted a recently launched six-month promotion called 'Bucket List,' aimed at increasing customer engagement on the basis of rewards. Auslec plans to execute this as a six-month campaign along with a series of monthly programs running simultaneously.
The main campaign focuses on delivering messages to customers regarding the rewards they can automatically score during the promotional period. These kick off with a targeted EDM triggered campaign, which directs traffic to landing pages with a countdown to the big launch.
Goncalves said the current campaign aims to engage with Auslec/L&H online and branch customers via a series of daily and monthly campaigns. This includes 24-hour flash sales and conditional giveaways.
Through this longer and more substantial campaign, Goncalves said the intention is to better connect with its growing customer database while building on longer-term relationships. Auslec is also able to get access to real-time data on a customer's status in a particular program.
"With a complete and holistic view of programs, it allows the team to make necessary changes as to maximise the ROI on campaigns," she said, adding a real-time snapshot into a campaign is invaluable for marketers for providing insights into how and when to engage the market.
Digital marketing has had a significant impact particularly on branch managers who were used to using pen and paper and sending customers letters in the mail, Goncalves continued.
"This is very new world to them, but once you show them the bigger picture of the campaign and how it keeps retargeting customers that don't open versus if they do open, and now we've integrated SMS, they can see the bigger picture for our business and can also see the benefits it's having for their customers.
"No longer do they have to filter information about a promotion. Now we are literally making it so every individual email is different to each customer. We can even target some of our regional areas.
The rollout of the technology has also helped the company towards rebranding, both physically and virtually.
"It has changed the scope of our new branding guidelines. We are refurbishing and changing the exterior of our business, so we're rebranding our templates and customers can see that first-hand on our emails," Goncalves said.
Asked the next steps, Goncalves said Auslec is in the process of integrating a new digital platform that will allow it to classify customers including small domestic contractors, small to medium contractors, industrial and commercial customers.
"This means our EDMs will be even more personalised. We haven't reclassified our customers in a long time and databases in our business are just as old as our business is, so we're trying to create new avenues to create fresh databases with accurate classifications," she said.
Updating CRM is another priority, with a view to integrating it with dotmailer, as well as creating a better experience on its e-commerce platform.
While the push to digitally driven marketing might already be familiar territory to many marketers in other sectors, Goncalves said Auslec is on the forefront of the digital movement compared to its industry counterparts.
Auslec/L&H marketing strategist, Rachel Raschilla, said suppliers are now asking the company for insights, feedback, testing and collaboration and cooperation on programs.
"This is an industry that is fairly new to digital. Understandably, our customers are only just moving to online and very, very slowly, so we have the opportunity to build it and be ready for them when they jump across," she said.
Raschilla said the company is also looking at a new strategy within the marketing team to understand customers better.


text:
Q: Decide convergence of the series Using Taylor expansion decide convergence of the series:
$$\sum_{n=1}^{\infty}(e-(1+{{1}\over{n}})^n)^p = \sum_{n=1}^{\infty}a_n$$
I expanded $a_n$ like this
$a_n = (e-(1+{{1}\over{n}})^n)^p = (\sum_{k=0}^{\infty}{{1}\over k!} - \sum_{k=0}^{n}\dbinom{n}{k}{1\over n^k})^p = {1\over n^p}(const.+O({1\over n}))^p$
and then used the ratio test. Is it correct? If so, is there a better approach?
Thank you.

A: Realize that $(1+{{1}\over{n}})^n = \sum_{k=0}^{n}\dbinom{n}{k}{1\over n^k} = {1\over k!}(1 - {1\over n})(1-{2\over n})...(1-{k-1\over n})< \sum_{k=0}^{n}({1\over k!}-{1\over nk!})$
We can expand $e-(1+{{1}\over{n}})^n$ as $\sum_{n=1}^{\infty}{1\over k!}(1 - (1 - {1\over n})(1-{2\over n})...(1-{k-1\over n}))> \sum_{k=0}^{n}{1\over nk!}>{2\over n}$. Therefore, $\sum_{n=1}^{\infty}(e-(1+{{1}\over{n}})^n)^p$ diverges when $\sum_{n=1}^{\infty}({2\over n})^p$ diverges, which is for $p \leq 1$. On the other hand, $e-(1+{{1}\over{n}})^n < (1+{{1}\over{n}})^n-(1+{{1}\over{n}})^{n+1}= {(1+{{1}\over{n}})^n \over n} \leq {e\over n}$. So $\sum_{n=1}^{\infty}(e-(1+{{1}\over{n}})^n)^p$ converges if $\sum_{n=1}^{\infty}({e\over n})^p$ converges, which is for $p>1$.

A: Rewrite the general term as $(e-e^{n\ln(1+1/n)})^p \sim (e-e^{n(\frac{1}{n}-\frac{1}{2n^2}+o(1/n^3))})^p =(e-e^{1-\frac{1}{2n}+o(1/n^2)})^p \sim e^p(1-(1+\frac{1}{2n
}+o(1/n^2)+ o(X))^p\sim e^p\frac{1}{2^pn^p}$
$o(X)$ is the Taylor expansion rest of $e^{n(\frac{1}{n}-\frac{1}{2n^2}+o(1/n^3))})$.
This clearly shows that the series converge for p>1 and diverge otherwise.

redpajama_set_name: RedPajamaStackExchange


text:
\section{Introduction}
\label{intro}

Despite having the fourth largest speaker population in the world, with
200 million native
speakers,\footnote{\url{https://www.visualcapitalist.com/100-most-spoken-languages/}.}
Indonesian is under-represented in NLP.  One reason is the scarcity of
large datasets for different tasks, such as parsing, text classification,
and summarization.  In this paper, we attempt to bridge this gap by
introducing a large-scale Indonesian corpus for text summarization.

Neural models have driven remarkable progress in summarization in recent
years, particularly for abstractive summarization. One of the first
studies was \newcite{rush2015neural}, where the authors proposed an
encoder--decoder model with attention to generate headlines for English
Gigaword documents \cite{graff2003english}.  Subsequent studies
introduced pointer networks \cite{nallapati2016abstractive,see2017get},
summarization with content selection
\cite{hsu2018unified,gehrmann2018bottom}, graph-based attentional models
\cite{tan2017abstractive}, and deep reinforcement learning
\cite{paulus2017a}. More recently, we have seen the widespread adoption
of pre-trained neural language models for summarization, e.g.\ BERT
\cite{liu2019text}, BART \cite{lewis2019bart}, and PEGASUS
\cite{zhang2019pegasus}.

Progress in summarization research has been driven by the availability
of large-scale English datasets, including 320K \textit{CNN/Daily Mail}
document--summary pairs \cite{hermann2015teaching} and 100k \textit{NYT}
articles \cite{sandhaus2008the} which have been widely used in
abstractive summarization research
\cite{see2017get,gehrmann2018bottom,paulus2017a,lewis2019bart,zhang2019pegasus}.
News articles are a natural candidate for summarization datasets, as
they tend to be well-structured and are available in large volumes.
More recently, English summarization datasets in other flavours/domains
have been developed, e.g.\ \textit{XSum} has 226K documents with highly
abstractive summaries \cite{narayan2018don}, BIGPATENT is a
summarization dataset for the legal domain \cite{sharma2019bigpatent},
Reddit TIFU is sourced from social media \cite{kim2019abstractive}, and
\newcite{cohan2018a} proposed using scientific publications from arXiv and
PubMed for abstract summarization.

\begin{figure*}[]
	\centering
	\includegraphics[width=5.7in]{image/liputan6.pdf}
	\caption{Example articles and summaries from Liputan6.  To the
		left is the original document and summary, and to the right is
		an English translation (for illustrative purposes).  We
		additionally highlight sentences that the summary is based
		on (noting that such highlighting is not available in the dataset).}
	\label{fig:example}
\end{figure*}

This paper introduces the first large-scale summarization
dataset for Indonesian, sourced from the \textit{Liputan6.com} online news portal
over a 10-year period. It covers various topics and events that happened
primarily in Indonesia, from October 2000 to October 2010. Below, we
present details of the dataset, propose benchmark extractive and
abstractive summarization methods that leverage both multilingual and
monolingual pre-trained BERT models. We further conduct error analysis
to better understand the limitations of current models over the dataset,
as part of which we reveal not just modelling issues but also problems
with ROUGE.

To summarize, our contributions are: (1) we release a large-scale
Indonesian summarization corpus with over 200K documents, an order of
magnitude larger than the current largest Indonesian summarization
dataset and one of the largest non-English summarization datasets in
existence;\footnote{The data can be accessed at
  \url{https://github.com/fajri91/sum_liputan6}} (2) we present
statistics to show that the summaries in the dataset are reasonably
abstractive, and provide two test partitions, a standard test set and an
extremely abstractive test set; (3) we develop benchmark extractive and
abstractive summarization models based on pre-trained BERT models; and
(4) we conduct error analysis, on the basis of which we share insights
to drive future research on Indonesian text summarization.

\section{Data Construction}
\label{sec:data}

\textit{Liputan6.com} is an online Indonesian news portal which has been
running since August 2000, and provides news across a wide range of
topics including politics, business, sport, technology, health, and
entertainment. According to the Alexa ranking of websites at the time of
writing,\footnote{\url{https://www.alexa.com/topsites}} \textit{Liputan6.com}
is ranked 9th in Indonesia and 112th globally.  The website produces
daily articles along with a short description for its RSS feed.  The
summary is encapsulated in the javascript variable
\texttt{window.kmklabs.article} and the key \texttt{shortDescription},
while the article is in the main body of the associated HTML page. We
harvest this data over a 10-year window --- from October 2000 to October
2010 --- to create a large-scale summarization corpus, comprising
215,827 document--summary pairs. In terms of preprocessing, we remove
formatting and HTML entities (e.g. \texttt{\&quot}, and \texttt{\_\_}),
lowercase all words, and segment sentences based on simple punctuation
heuristics.  We provide example articles and summaries, with English
translations for expository purposes (noting that translations are
not part of the dataset), in \figref{example}.

\begin{table}[t]
	\begin{center}
		\begin{adjustbox}{max width=1\linewidth}
		\begin{tabular}{cr@{\;\;}r@{\;\;}rr@{\;\;}r@{\;\;}r@{\;\;}r}
			\toprule
			\multirow{2}{*}{\bf Variant} & \multicolumn{3}{c}{\bf
				\#Doc} & \multicolumn{4}{c}{\bf \% of Novel $n$-grams}
			\\

			& \bf Train & \bf Dev & \bf Test & \bf 1 & \bf 2 & \bf 3
			& \bf
			4 \\
			\midrule
			Canonical & 193,883 & 10,972 & 10,972 & 16.2 & 52.5 &
			71.8 &
			82.4 \\
			Xtreme & 193,883 & 4,948 & 3,862 & 22.2 & 66.7 &
			87.5 &
			96.6 \\
			\bottomrule
		\end{tabular}
		\end{adjustbox}
	\end{center}
	\caption{Statistics for the canonical and Xtreme variants of our
          data. The percentage of novel \textit{n}-grams is based on the
          combined Dev and Test set.}
	\label{tab:valtest}
\end{table}

As a preliminary analysis of the document--summary pairs over the
10-year period, we binned the pairs into 5 chronologically-ordered
groups containing 20\% of the data each, and computed the proportion of
novel $n$-grams (order 1 to 4) in the summary (relative to the source document).
Based on the results in \figref{abs}, we can see that the proportion of
novel $n$-grams drops over time, implying that the summaries of more
recent articles are less abstractive.  For this reason, we decide to use
the earlier articles (October 2000 to Jan 2002) as the development and
test documents, to create a more challenging dataset.  This setup also
means there is less topic overlap between training and development/test
documents, allowing us to assess whether the summarization models are
able to summarize unseen topics.

\begin{table*}[t]
	\begin{center}
		\begin{adjustbox}{max width=0.85\linewidth}
			\begin{tabular}{cr@{\;}r@{\;}rc@{\;}c@{\;}cc@{\;}c@{\;}c}
				\toprule
				\multirow{2}{*}{\bf Dataset} & \multicolumn{3}{c}{\bf \#Doc}
				& \multicolumn{3}{c}{\bf Article} & \multicolumn{3}{c}{\bf Summary}  \\

				& \bf Train & \bf Dev & \bf Test  & \bf $\mu$(Word)& \bf
				$\mu$(Sent) & \bf \#Vocab & \bf $\mu$(Word) & \bf $\mu$(Sent) & \bf
				\#Vocab \\
				\midrule
				IndoSum & 14,252 & 750 & 3,762 & 347.23 & 18.37 &117K &
				68.09 & 3.47 & 53K \\
				Liputan6 & 193,883 & 10,972 & 10,972 & 232.91 & 12.60 & 311K
				& 30.43 & 2.09  & 100K \\
				\bottomrule
			\end{tabular}
		\end{adjustbox}
	\end{center}
	\caption{\label{tab:datastat} A comparison of IndoSum and Liputan6.
		$\mu$(Word) and $\mu$(Sent) denote the average number of words and
		sentences, respectively.}
\end{table*}

\begin{table}[t]
	\begin{center}
		\begin{adjustbox}{max width=\linewidth}
			\begin{tabular}{cr@{\;\;}r@{\;\;}rr@{\;\;}r@{\;\;}r@{\;\;}r}
				\toprule
				\multirow{2}{*}{\bf Dataset} & \multicolumn{3}{c}{\bf
					\method{Lead-$N$}} & \multicolumn{4}{c}{\bf \% of Novel $n$-grams} \\

				& \bf R1 & \bf R2 & \bf RL & \bf 1 & \bf 2 & \bf 3 & \bf 4 \\
				\midrule
				IndoSum & 65.6 & 58.9 & 64.8 & 3.1 & 10.8 & 16.2 &
				20.3 \\
				Liputan6 & 41.2 & 27.1 & 38.7 & 12.9 & 41.6 & 57.6 &
				66.9\\
				\bottomrule
			\end{tabular}
		\end{adjustbox}
	\end{center}
	\caption{\label{tab:abs} Abstractiveness of the summaries in IndoSum
		and Liputan6.}
\end{table}

\begin{figure}[t]
	\centering
	\includegraphics[width=3.1in]{image/ngram.pdf}
	\caption{Proportion of novel $n$-grams over time in the
		summaries.}
	\label{fig:abs}
\end{figure}

For the training, development and test partitions, we use a splitting
ratio of 90:5:5. In addition to this canonical partitioning of the data,
we provide an ``Xtreme'' variant (inspired by \textit{Xsum};
\newcite{narayan2018don}) whereby we discard development and test
document--summary pairs where the summary has fewer than 90\% novel
$4$-grams (leaving the training data unchanged), creating a smaller,
more challenging data configuration. Summary statistics for the
``canonical'' and ``Xtreme'' variants are given in \tabref{valtest}.

We next present a comparison of Liputan6 (canonical partitioning) and
IndoSum (the current largest Indonesian summarization dataset, as
detailed in \secref{related}; \newcite{kurniawan2018indosum}) in
\tabref{datastat}.  In terms of number of documents, Liputan6 is
approximately 11 times larger than IndoSum (the current largest
Indonesian summarization dataset), although articles and summaries in Liputan6 are slightly shorter.

To understand the abstractiveness of the summaries in the two datasets,
in \tabref{abs} we present ROUGE scores for the simple baseline of using
the first $N$ sentences as an extractive summary (``\method{Lead-$N$}''), and the
percentage of novel $n$-grams in the summary.\footnote{All statistics
	are based on the entire dataset, encompassing the training, dev, and test
	data.}  We use \method{Lead-3}{} and \method{Lead-2}{} for IndoSum and Liputan6
respectively, based on the average number of sentences in the summaries
(\tabref{datastat}).  We see that Liputan6 has consistently lower ROUGE
scores (R1, R2, and RL) for \method{Lead-$N$}; it also has a substantially higher
proportion of novel $n$-grams.  This suggests that the summaries in
Liputan6 are more abstractive than IndoSum.

To create a ground truth for extractive summarization,  we follow
\newcite{cheng2016neural} and \newcite{nallapati2016summarunner}  in
greedily selecting the subset of sentences in the article that maximizes
the ROUGE score based on the reference summary. As a result, each sentence in the
article has a binary label to indicate whether they should be included
as part of an extractive summary. Extractive summaries created this way
will be referred to as ``\method{Oracle}'', to denote the upper bound
performance of an extractive summarization system.

\section{Summarization Models}
\label{model}

We follow \newcite{liu2019text} in building extractive and abstractive
summarization models using BERT as an encoder to produce contextual
representations for the word tokens.  The architecture of both models is
presented in \figref{sum}.
We tokenize words with WordPiece, and append  [CLS] (prefix) and [SEP]
(suffix) tokens to each sentence.  To further distinguish the sentences,
we add even/odd segment embeddings ($T_A/T_B$) based on the order of the
sentence to the word embeddings. For instance, for a document with
sentences [$s_1, s_2, s_3, s_4$], the segment embeddings are
[$T_A,T_B,T_A,T_B$].  Position embeddings ($P$) are also used to denote
the position of each token.  The WordPiece, segment, and position
embeddings are summed together and provided as input to  BERT.

BERT produces a series of contextual representations for the word
tokens, which we feed into a (second) transformer encoder/decoder for
the extractive/abstractive summarization model. We detail the
architecture of these two models in \secref[s]{extractive-model} and
\ref{sec:abstractive-model}. Note that this second transformer is
initialized with random parameters (i.e.\ it is not pre-trained).

For the pre-trained BERT encoder, we use multilingual BERT (mBERT) and
our own IndoBERT \cite{koto2020indolem}.\footnote{The pre-trained mBERT is sourced from:
	\url{https://github.com/google-research/bert}.}  IndoBERT is a
BERT-Base model we trained ourselves using Indonesian documents from
three sources: (1) Indonesian Wikipedia (74M words); (2) news articles
(55M words) from Kompas,\footnote{\url{https://kompas.com}} Tempo
\cite{tala2003the},\footnote{\url{https://koran.tempo.co}} and
Liputan6;\footnote{For Liputan6, we use only the articles from the
	training partition.} and (3) the Indonesian Web Corpus (90M words;
\newcite{medved2019indonesian}).  In total, the training data has 220M
words. We implement IndoBERT using the Huggingface
framework,\footnote{\url{https://huggingface.co/}} and follow the
default configuration of BERT-Base (uncased): hidden size = 768d, hidden
layers = 12, attention heads = 12, and feed-forward = 3,072d.  We train IndoBERT with 31,923 WordPieces
(vocabulary) for 2 million steps.

\begin{figure}[t]
	\centering
	\includegraphics[width=3in]{image/presum.pdf}
	\caption{\label{fig:sum} Architecture of the extractive and
		abstractive summarization models.}
\end{figure}

\subsection{Extractive Model}
\label{sec:extractive-model}

After the document is processed by BERT, we have a contextualized
embedding for every word token in the document. To learn
inter-sentential relationships, we use the [CLS] embeddings ([$x_{S_1},
x_{S_2},.., x_{S_m}$]) to represent the sentences, to which we add
a sentence-level positional embedding ($P$), and feed them to a
transformer encoder (\figref{sum}). An MLP layer with sigmoid activation
is applied to the output of the transformer encoder to predict whether a
sentence should be extracted (i.e.\ $\tilde{y}_S \in \{0,1\}$).
We train the model with binary cross entropy, and update all model
parameters (including BERT) during training.  Note that the parameters
in the transformer encoder and the MLP layer are initialized randomly,
and learned from scratch.

The transformer encoder is configured as follows: layers = 2,
hidden size = 768, feed-forward = 2,048, and heads = 8.
In terms of training hyper-parameters, we train using the Adam optimizer
with learning rate
$lr=2e^{-3}\cdot\text{min}(\text{step}^{-0.5}, \text{step}\cdot\text{warmup}^{-1.5})$
where $\text{warmup}=10,000$. We train for 50,000 steps on 3$\times$V100
16GB GPUs, and perform evaluation on the development set every 2,500
steps. At test time, we select sentences for the extractive summary
according to two conditions: the summary must consist of: (a) at least
two sentences, and (b) at least 15 words. These values were set based on
the average number of sentences and the minimum number of words in a
summary. We also apply trigram blocking to reduce redundancy
\cite{paulus2017a}.
Henceforth, we refer to this model as ``\method{BertExt}''.

\subsection{Abstractive Model}
\label{sec:abstractive-model}

Similar to the extractive model, we have a second transformer to process
the contextualized embeddings from BERT. In this case, we use a
transformer decoder instead (i.e.\ an attention mask is used to prevent the decoder from attending to future time
steps), as we are learning to generate an abstractive summary. But
unlike the extractive model, we use the BERT embeddings for all tokens
as input to the transformer decoder (as we do not need sentence
representations).  We add to these BERT embeddings a second positional
encoding before feeding them to the transformer decoder (\figref{sum}).
The transformer decoder is initialized with random parameters (i.e.\ no
pre-training).

The transformer decoder is configured as follows: layers = 6,
hidden size = 768, feed-forward = 2,048, and heads = 8.
Following \newcite{liu2019text}, we use a different learning rate for
BERT and the decoder when training the model:  $lr$
$=2e^{-3}\cdot\text{min}(\text{step}^{-0.5},\text{step}\cdot20,000^{-1.5})$ and
$0.1\cdot\text{min}(\text{step}^{-0.5},\text{step}\cdot10,000^{-1.5})$ for BERT and
the transformer decoder, respectively.  Both networks are trained with
the Adam optimizer for 200,000 steps on 4$\times$V100 16GB GPUs and
evaluated every 10,000 steps. For summary generation, we use beam width
= 5, trigram blocking, and a length penalty \cite{wu2016google} to generate
at least two sentences and at least 15 words (similar to the extractive model).

Henceforth the abstractive model will be referred to as
``\method{BertAbs}''.  We additionally experiment with a third variant,
``\method{BertExtAbs}'', where we use the weights of the fine-tuned BERT in
\method{BertExt} for the encoder (instead of off-the-shelf BERT
weights).

\section{Experiment and Results}
\label{exp}

\begin{table*}[t]
	\begin{center}
		\begin{adjustbox}{max width=\linewidth}
			\begin{tabular}{ccccccccccc}
				\toprule \multirow{2}{*}{\bf Model} &&
				\multicolumn{4}{c}{\bf Canonical Test Set} && \multicolumn{4}{c}{\bf Xtreme Test Set} \\
				\cmidrule{3-6}
				\cmidrule{8-11}
				&& \bf R1 & \bf R2 & \bf RL &\bf BS && \bf R1 & \bf R2 & \bf RL
				& \bf BS \\
				\midrule
				\method{Lead-1} && 32.67 & 18.50 & 29.40 & 72.62 && 27.27 & 11.56 & 23.60 & 71.19\\
				\method{Lead-2} && 36.68 & 20.23 & 33.71 & 74.58 && 31.10 & 12.78 & 27.63 & 72.98\\
				\method{Lead-3} && 34.49 & 18.84 & 32.06 & 74.31 && 29.54 & 12.05 & 26.68 & 72.78\\
				\method{Oracle} && 51.54 & 30.56 & 47.75 & 79.24 && 43.69 & 18.57 & 38.84 & 76.75\\
				\midrule
				\method{PTGen} && 36.10 & 19.19 & 33.56 & 75.92 && 30.41 & 12.05 & 27.51 & 74.10\\
				\method{PTGen+Cov} && 35.53 & 18.56 & 32.92 & 75.75 && 30.27 & 11.81 & 27.26 & 74.11\\
				\midrule
				\method{BertExt}{} (mBERT)&& 37.51 & 20.15 & 34.57 & 75.22 && 31.83 & 12.63 & 28.37 & 73.62\\
				\method{BertAbs}{} (mBERT) && 39.48 & 21.59 & 36.72 & 77.19 && 33.26 & 13.82 & 30.12 & 75.40 \\
				\method{BertExtAbs}{} (mBERT)&& 39.81 & 21.84 & 37.02 & 77.39 && 33.86 & 14.13 & 30.73 & 75.69 \\
				\midrule
				\method{BertExt}{} (IndoBERT)&& 38.03 & 20.72 & 35.07 & 75.33 && 31.95 & 12.74 & 28.47 & 73.64\\
				\method{BertAbs}{} (IndoBERT) && 40.94 & \bf 23.01 & 37.89 & 77.90 && 34.59 & \bf 15.10 & 31.19 & 75.84\\
				\method{BertExtAbs}{} (IndoBERT)&& \bf 41.08 & 22.85 & \bf 38.01 & \bf 77.93 && \bf 34.84 & 15.03 & \bf 31.40 & \bf 75.99\\
				\bottomrule
			\end{tabular}
		\end{adjustbox}
	\end{center}
	\caption{ROUGE results for the canonical and
		Xtreme test sets. All ROUGE (``R1'', ``R2'', and ``RL'')
                scores have a confidence interval of at most $\pm{0.3}$, as reported by the official ROUGE script. ``BS'' is \textsc{BERScore} computed with \texttt{bert-base-multilingual-cased} (layer 9), as suggested by \citet{zhang2020bertscore}.}
	\label{tab:expresult}
\end{table*}

We use three ROUGE \cite{lin2004rouge} F-1 scores as evaluation metrics:
R1 (unigram overlap), R2 (bigram overlap), and RL (longest common
subsequence overlap). In addition, we also provide \method{BERTScore} (F-1), as
has recently been used for machine translation evaluation \cite{zhang2020bertscore}.\footnote{\url{https://github.com/Tiiiger/bert_score}} We use the development set to select the best
checkpoint during training, and report the evaluation scores for the
canonical and Xtreme test sets in \tabref{expresult}.  For both test
sets, the summarization models are trained using the same training set,
but they are tuned with a different development set (see \secref{data}
for details). In addition to the BERT models, we also include two
pointer-generator models \cite{see2017get}: (1) the base model (\method{PTGen});
and (2) the model with coverage penalty (\method{PTGen+Cov}).\footnote{We use the
	default hyper-parameter configuration recommended by the original
	authors for the pointer-generator models.}

We first look at the baseline \method{Lead-$N$} and \method{Oracle} results.  \method{Lead-2} is
the best \method{Lead-$N$} baseline for Liputan6. This is unsurprising, given that
in \tabref{datastat}, the average summary length was 2 sentences. We
also notice there is a substantial gap between \method{Oracle}{} and \method{Lead-2}:
12--15 points for R1 and 5--7 points for \method{BERTScore}, depending on the test set. This suggests that the
baseline of using the first few sentences as an extractive summary is
ineffective. Comparing the performance between the canonical and Xtreme
test sets, we see a substantial drop in performance for both \method{Lead-$N$} and
\method{Oracle}, highlighting the difficulty of the Xtreme test set due to its
increased abstractiveness.

For the pointer-generator models, we see little improvement when
including the coverage mechanism (\method{PTGen+Cov} vs.\ \method{PTGen}), implying that
there is minimal repetition in the output of \method{PTGen}.  We suspect this is
due to the Liputan6 summaries being relatively short (2 sentences with 30
words on average).  A similar observation is reported by
\newcite{narayan2018don} for \textit{XSum}, where the summaries are
similarly short (a single sentence with 23 words, on average).

Next we look at the BERT models. Overall they perform very well, with
both the mBERT and IndoBERT models outperforming the \method{Lead-$N$} baselines and
\method{PTGen} models by a comfortable margin.  IndoBERT is better than mBERT
(approximately 1 ROUGE point better on average over most metrics),
showing that a monolingually-trained BERT is a more effective
pre-trained model than the multilingual variant. The best performance is
achieved by IndoBERT's \method{BertExtAbs}. In the canonical test set, the
improvement over \method{Lead-2} is $+$4.4 R1, $+$2.62 R2, $+$4.3
R3, and $+$3.4 \method{BERTScore} points. In the Xtreme test set, \method{BertExtAbs} suffers a
substantial drop compared to the canonical test set (6--7 ROUGE and 2 \method{BERTScore} points),
although the performance gap between it and \method{Lead-2} is about the
same.

\section{Error Analysis}
\label{error}

In this section, we analyze errors made by the extractive (\method{BertExt}) and
abstractive (\method{BertExtAbs}) models to better understand their
behaviour. We use the mBERT version of these models in our
analysis.\footnote{The error analysis is based on mBERT rather than
  IndoBERT simply because this was the best-performing model at the time
  the error analysis was performed. While IndoBERT ultimately performed
  slightly better, given that the two models are structurally identical,
  we would expect to see a similar pattern of results.}

\subsection{Error Analysis of Extractive Summaries}

\begin{figure*}[!t]
	\centering
	\subfloat[Distribution of sentence positions for \method{Oracle} and
	\method{BertExt} in the canonical test
	set.]{\includegraphics[width=0.48\textwidth]{image/pos1.pdf}\label{fig:f1}}
	\hfill
	\subfloat[Distribution of sentence positions for \method{Oracle} in
	the training
	set.]{\includegraphics[width=0.48\textwidth]{image/pos2.pdf}\label{fig:f2}}
	\caption{\label{fig:pos} Position of \method{Oracle} and/or Predicted Extractive Summaries}

\end{figure*}

We hypothesized that the disparity between \method{Oracle} and
\method{BertExt} (14.03 point difference for R1 in the canonical test
set) was due to the number of extracted sentences. To test this, when
extracting sentences with \method{BertExt}, we set the total number of
extracted sentences to be the same as the number of sentences in the
\method{Oracle} summary. However, we found minimal benefit using this
approach, suggesting that the disparity is not a result of the number of
extracted sentences.

To investigate this further, we present the frequency of
\textit{sentence positions} that are used in the summary in \method{Oracle} and
\method{BertExt} for the canonical test set in \figref{f1}. We can see that
\method{BertExt} tends to over-select the first two sentences as the summary.
In terms of proportion, 65.47\% of \method{BertExt} summaries involve the first
two sentences. In comparison, only 42.54\% of \method{Oracle} summaries use
sentences in these positions. One may argue that this is because the
training and test data have different distributions under our chronological
partitioning strategy (recall that the test set is sampled from the
earliest articles), but that does not appear to be the case: as
\figref{f2} shows, the distribution of sentence positions in the
training data is very similar to the test data --- 43.14\% of \method{Oracle}
summaries involve the first two sentences.

\subsection{Error Analysis of Abstractive Summaries}

\begin{figure*}[t]
	\centering
	\includegraphics[width=6in]{image/error.pdf}
	\caption{\label{fig:error} Two examples to highlight error categories used in our error analysis.}
\end{figure*}

To perform error analysis for \method{BertExtAbs}, we randomly sample 100
documents with an R1 score $<$0.4 in the canonical test set (which
accounts for nearly 50\% of the test documents). Two native Indonesian
speakers examined these 100 samples to manually assess the quality of
the summaries, and score them on a 3-point ordinal scale: (1)
\textit{bad}; (2) \textit{average}; and (3) \textit{good}. Each
annotator is presented with the source document, the reference summary,
and the summary generated by \method{BertExtAbs}. In addition to the overall
quality evaluation, we also asked the annotators to analyze a number of
(fine-grained) attributes in the summaries:

\begin{itemize}[noitemsep]
	\item \textit{Abbreviations:} the system summary uses abbreviations that
	are different to the reference summary.
	\item \textit{Morphology:} the system summary uses morphological
	variants of the same lemmas contained in the reference summary.
	\item \textit{Synonyms/paraphrasing:} the system summary contains
	paraphrases of the reference summary.
	\item \textit{Lack of coverage:} the system summary lacks coverage of
	certain details that are present in the reference summary.
	\item \textit{Wrong focus:} the system summarizes a different
	aspect/focus of the document to the reference summary.
	\item \textit{Unnecessary details (from document):} the system
	summary includes unimportant but factually correct information.
	\item \textit{Unnecessary details (not from document):} the system
	summary includes unimportant and factually incorrect information
	(hallucinations).
\end{itemize}

\begin{table}[t!]
	\begin{center}
		\begin{adjustbox}{max width=1\linewidth}
			\begin{tabular}{rrrr}
				\toprule
				\bf Category & \bf Bad & \bf Avg. & \bf Good \\
				\midrule
				\#Samples (100) & 32\ensuremath{\phantom{0}} & 8\ensuremath{\phantom{0}} & 60\ensuremath{\phantom{0}}\\
				Abbreviation (\%) & 21.9 & 25.0 & 40.0 \\
				Morphology (\%) & 12.5 & 25.0 & 36.7 \\
				Paraphrasing (\%) & 50.0 & 87.5 & \bf 86.7 \\
				Lack of coverage (\%) & \bf 90.6 & \bf 100.0 & 40.0 \\
				Wrong focus (\%) & 68.8 & 0.00 & 8.3 \\
				Un. details (from doc) (\%) & \bf 90.6 &  75.0 & 75.0 \\
				Un. details (not from doc) (\%) & 18.8 & 12.5 & 5.0 \\
				\bottomrule
			\end{tabular}
		\end{adjustbox}
	\end{center}
	\caption{\label{tab:err} Error analysis for 100 samples with R1
          $<$0.4.}
\end{table}

We present a breakdown of the different error types in \tabref{err}.
Inter-annotator agreement for the overall quality assessment is high
(Pearson's $r =$ 0.69). Disagreements in the quality label (\textit{bad,
  average, good}) are resolved as follows: (1) \{\textit{bad},
\textit{average}\} $\rightarrow$ \textit{bad}; and (2) \{\textit{good},
\textit{average}\} $\rightarrow$ \textit{good}. We only have four
examples with \{\textit{bad}, \textit{good}\} disagreement, which we
resolved through discussion.  Interestingly, more than half (60) of our
samples were found to have \textit{good} summaries.  The primary reasons
why these summaries have low ROUGE scores are paraphrasing (86.7\%),
and the inclusion of additional (but valid) details
(75.0\%). Abbreviations and morphological differences also appear to be
important factors. These results underline a problem with the ROUGE
metric, in that it is unable to detect good summaries that use a
different set of words to the reference summary.  One way forward is to
explore metrics that consider sentence semantics beyond word overlap
such as METEOR \cite{banerjee2005meteor} and
\method{BERTScore},\footnote{Indeed, we suggest that \method{BERTScore} should be used
  as the canonical evaluation metric for the dataset, but leave
  empirical validation of its superiority for Indonesian summarization
  evaluation to future work.}  and question-answering system
based evaluation such as APES \cite{eyal2019question} and QAGS
\cite{wang2020asking}.
Another way is to create more reference summaries (which will help with the
issue of the system summaries including [validly] different details to the single reference).

Looking at the results for \textit{average} summaries (middle column),
\method{BertExtAbs} occasionally fails to capture salient information: 100\% of
the summaries have coverage issues, and 75.0\% contain unnecessary (but valid)
details. They also tend to use paraphrases (87.5\%), which further
impacts on a lower ROUGE score.  Finally, the \textit{bad} system summaries
have similar coverage issues, and also tend to have a very
different focus compared to the reference summary (90.6\%).

In \figref{error} we show two representative examples from
\method{BertExtAbs}. The first example is considered \textit{good} by our
annotators, but due to abbreviations, morphological differences,
paraphrasing, and additional details compared to the reference summary,
the ROUGE score is $<$0.4.  In this example, the gold summary uses the
abbreviation \textit{kepmenakertrans} while \method{BertExtAbs} generates the
full phrase \textit{keputusan menteri tenaga kerja dan transmigrasi}
(which is correct).  The example also uses paraphrases (\textit{invites
	strong criticism} to explain \textit{dissatisfaction}), and there are
morphological differences in words such as \textit{tuntutan} (noun) vs.\
\textit{menuntut} (verb).  The low ROUGE score here highlights the fact
that the bigger issue is with ROUGE itself rather than the summary.

The second example is considered to be \textit{bad}, with the following
issues: lack of coverage, wrong focus, and contains unnecessary details
that are not from the article.  The first sentence \textit{President
	Abdurrahman Wahid was absent} has nothing to do with the original
article, creating a different focus (and confusion) in the overall
summary.

To summarize, coverage, focus, and the inclusion of other details are
the main causes of low quality summaries. Our analysis reveals that
abbreviations and paraphrases are another cause of summaries with low
ROUGE scores, but that is an issue with ROUGE rather than the summaries.
Encouragingly, hallucination (generating details not in the original
document) is not a major issue for these models (notwithstanding that
almost 20\% of \textit{bad} samples contain hallucinations).

\section{Related Datasets}
\label{sec:related}

Previous studies on Indonesian text summarization have largely been
extractive and used small-scale datasets. \newcite{gunawan2017automatic}
developed an unsupervised summarization model over 3K news articles using
heuristics such as sentence length, keyword frequency, and title
features.  In a similar vein, \newcite{najibullah2015indonesian} trained a
naive Bayes model to extract summary sentences in a 100-article
dataset.  \newcite{aris2012text} and \newcite{silvia2014summarizing}
apply genetic algorithms to a summarization dataset with less than 200
articles. These studies do not use ROUGE for evaluation, and the
datasets are not publicly available.

\newcite{koto2016a} released a dataset for chat summarization by manually
annotating chat logs from
\textit{WhatsApp}.\footnote{\url{https://www.whatsapp.com/}.}  However,
this dataset contains only 300 documents. The largest summarization data
to date is \textit{IndoSum} \cite{kurniawan2018indosum}, which has
approximately 19K news articles with manually-written summaries.  Based
on our analysis, however, the summaries of \textit{IndoSum} are highly
extractive.

Beyond Indonesian, there is only a handful of non-English summarization
datasets that are of sufficient size to train modern deep learning
summarization methods over, including: (1) LCSTS \cite{hu2015lcsts}, which contains
2 million Chinese short texts constructed from the Sina Weibo
microblogging website; and (2) ES-News \cite{gonzalez2019summarization},
which comprises 270k Spanish news articles with summaries.  LCSTS
documents are relatively short (less than 140 Chinese characters), while
ES-News is not publicly available.  Our goal is to create a benchmark
corpus for Indonesian text summarization that is both large scale and
publicly available.

\section{Conclusion}
\label{concl}

We release Liputan6, a large-scale summarization corpus for Indonesian.
Our dataset comes with two test sets: a canonical test set and an
``Xtreme'' variant that is more abstractive. We present results for
several benchmark summarization models, in part based on IndoBERT, a new
pre-trained BERT model for Indonesian. We further conducted extensive
error analysis, as part of which we identified a number of issues with
ROUGE-based evaluation for Indonesian.

\section*{Acknowledgments}
We are grateful to the anonymous reviewers for their
helpful feedback and suggestions. In this research, Fajri Koto is
supported by the Australia Awards Scholarship (AAS), funded by the Department of Foreign Affairs and Trade (DFAT), Australia.
This research was undertaken using the LIEF HPC-GPGPU Facility hosted at The University of Melbourne. This facility was established with the assistance of LIEF Grant LE170100200.