\section{Introduction}

What are cities? In {\it The Death and Life of the Great American Cities},
Jacobs argues that human relations can be seen as a proxy for places within
cities \cite{jacobs1961}. A modern view of cities establishes that they can be
defined by the interactions among several types of networks \cite{batty2013,
west2017}, from infrastructure networks to social networks. In recent years, an
increasing number of studies have been proposed to define cities through
consistent mathematical models \cite{makse1995, makse1998, rozenfeld2008,
rozenfeld2011, rybski2013, murcio2013, hernando2014, frasco2014, arcaute2014,
masucci2015, arcaute2016, fluschnik2016} and to investigate urban indicators at
inter- and intra-city scales, in order to shed some light on problems faced by
decision makers \cite{bettencourt2007, arbesman2009, bettencourt2010a,
bettencourt2010b, gomez-lievano2012, gallos2012a, bettencourt2013, fragkias2013,
oliveira2014, melo2014, louf2014, alves2015, li2015, hanley2016, caminha2017,
operti2017}. Despite the efforts of such studies, to properly defining the
boundaries of urban settlements remains an open problem in the Science of
Cities. A minimum criterion of acceptability for any model of cities seems to be
the one that retrieves a conspicuous scaling law found for United States (US),
United Kingdom (UK), and other countries, known as Zipf's law
\cite{rozenfeld2008, rozenfeld2011, gabaix1999a, gabaix1999b, ioannides2003,
cordoba2008, giesen2010, giesen2011, jiang2011, giesen2012, ioannides2013,
duraton2014, watanabe2015}.

In 1949, Zipf \cite{zipf1949} observed that the frequency of words used in the
English language obeys a natural and robust power law behavior, {\it i.e.} a few
words are used many times, while many words are used just a few times. Zipf's
law can be represented generically by the following relation between the size
$S$ of objects from a given set and its rank $R$:
\begin{equation}\label{eq1}
R \propto S^{-\zeta},
\end{equation}

\noindent
where $\zeta=1$ is Zipf's exponent. The size of objects is, in the original
context, the frequency of used words. On the other hand, if such objects are
cities, then the sizes stand for the population of each city, taking into
account Zipf's law and reflecting the fact that there are more small towns than
metropolises in the world. We emphasize that it is not straightforward that the
Zipf's law, despite its robustness, should hold independently of the city
definition, since other scaling relations are not, such as the allometric
exponents for CO$_2$ emissions and light pollution \cite{oliveira2014,
operti2017}. Many other man-made and natural phenomena also exhibit the same
persistent result, {\it e.g.} earthquakes and incomes \cite{sornette1996,
okuyama1999}.

Here, we propose a worldwide model to define urban settlements beyond their
usual administrative boundaries through a bottom-up approach that takes into
account cultural, political, and geographical biases naturally embedded in the
population distribution of continental areas. After all, it is not surprising
that two regions, {\it e.g.} one in western Europe and another one in eastern
Asia, spatially contiguous in population or in commuting level have different
cultural, political or geographical characteristics. Thus, it is also not
surprising that such issues yield different stages of the same mechanics of
growth. The main goal of our model is to be successful in defining cities even
in large regions. Our conjecture is straightforward: there are hierarchical
mechanisms, similar to those present in previous studies of cities in the UK
\cite{arcaute2016} and brain networks \cite{gallos2012b}, behind the growth and
innovation of urban settlements. These mechanisms are ruled by a combination of
general measures, such as the population and the area of each city, and
intrinsic factors which are specific to each region, {\it e.g.} topographical
heterogeneity, political and economic issues, and cultural customs and
traditions. In other words, if political turmoil or economic recession plagues a
metropolis for a long time, all of its satellites are affected too, {\it i.e.}
the entire region ruled by the metropolis will be negatively impacted.

\section{The models}

\subsection{City Clustering Algorithm (CCA)}

In 2008, Rozenfeld {\it et al.} \cite{rozenfeld2008} proposed a model to define
cities beyond their usual administrative boundaries using a notion of spatial
continuity of urban settlements, called the City Clustering Algorithm (CCA)
\cite{rozenfeld2008, rozenfeld2011, rybski2013, oliveira2014, frasco2014,
fluschnik2016, caminha2017, operti2017}. The CCA is defined for discrete or
continuous landscapes \cite{rozenfeld2011} by two parameters: a population
density threshold $D^*$ and a distance threshold $\ell$. These parameters
describe the populated areas and the commuting distance between areas,
respectively. Here, we adopt the following strategy to improve the discrete CCA
performance: (i) Supposing a regular rectangular lattice $L_x \times L_y$ of
sites where the population density of the $k$-th site is $D_k$, we perform an
initial agglomeration by $D^*$ to identify all clusters. If $D_k>D^*$, then the
$k$-th site is populated and we aggregate it with its populated nearest
neighbors. Otherwise, the $k$-th site is unpopulated. (ii) For each populated
cluster, we define its {\it shell sites}, {\it i.e.} sites in the interface
between populated and unpopulated areas. (iii) Lastly, we perform a final
agglomeration by $\ell$, taking into account only the shell sites. If
$d_{ij}<\ell$, where $d_{ij}$ is the distance between the $i$-th and $j$-th
shell sites, and if they belong to different clusters, then the $i$-th and
$j$-th sites belong to the same CCA cluster, even with spatial discontinuity.
Otherwise, they indeed belong to different CCA clusters. This simple strategy
improves the algorithm's computational performance because the number of shell
sites is proportional to $L$, where $L=L_x \approx L_y$ is a linear measure of
the lattice.

\subsection{City Local Clustering Algorithm (CLCA)}

We propose a worldwide model based on the CCA, called the City Local Clustering
Algorithm (CLCA), not only to define cities beyond their usual administrative
boundaries, but also to take into account the intrinsic cultural, political and
geographical biases associated with most societies and reflected in their
particular growing dynamics. The traditional CCA, with fixed $\ell$ and $D^*$,
when applied to a large population density map, can introduce biases defining a
lot of clusters in some regions, while in others just a few. We present the CLCA
with the aim of defining cities even in large regions in order to overcome such
CCA weakness. Hence, it is possible that other models, such as the models based
on street networks proposed by Masucci {\it et al.} \cite{masucci2015} and
Arcaute {\it et al.} \cite{arcaute2016}, carry the same CCA burden and that
local adaptations are necessary for their applications into large regions.

The main idea of ​​our model is to analyze the change of the CCA clusters
through the variation of $D^*$ under the perspective of different regions.
First, we define a regular rectangular lattice $L_x \times L_y$ of sites, where
the population density of the $k$-th site is $D_k$. We sort all the sites in a
list according to the population density, in descending order. Therefore, the
site with the greatest population density is the first entry in this list, which
we call the first {\it reference site}. The reference site can be considered as
the current core of the analyzed region. Second, we apply the CCA to the
lattice, keeping a fixed value of $\ell$, for a range of $D^*$ decreasing from a
maximum value $D^{(max)}$ to a minimum value $D^{(min)}$ with a decrement
$\delta$. During the decreasing of $D^*$, clusters are formed and they spread
out to all regions of the lattice. Eventually, the cluster that contains the
reference site (from now on the {\it reference cluster}), together with one or
more of the other clusters, will merge from $D^{(i)}$ to $D^{(i+1)}$, where
$D^{(i+1)} = D^{(i)}-\delta$. In order to accept or deny the merging of these
clusters, we introduce three conditions:

\begin{enumerate}[(i)]
\item If the area $A_r(D^{(i)})$ of the reference cluster $r$, {\it i.e.} the
cluster that contains the $r$-th reference site at $D^{(i)}$, obeys
\begin{equation}\label{eq2}
A_r(D^{(i)}) < A^*,
\end{equation}

\noindent
then the reference cluster $r$ always merges with other clusters, because it is
still considered very small. In this context, the area $A^*$ can be understood
as the minimal area of a metropolis.

\item If the difference between the areas of the reference cluster $r$ at
$D^{(i+1)}$ and $D^{(i)}$ obeys
\begin{equation}\label{eq3}
A_r(D^{(i+1)})-A_r(D^{(i)}) > H^* A_r(D^{(i)}),
\end{equation}

\noindent
then the reference cluster $r$ has grown without merging (Fig.\ref{clca}a) or
there is a merging of at least two large clusters (Fig.\ref{clca}b). In the last
case, we emphasize that if there are more than two clusters involved in the
merging process, the reference cluster $r$ may not be one of the largest. As the
first case is not desirable, we can avoid it by reducing the value of $\delta$
and keeping the value of $H^*$ relatively high. The parameter $H^*$ can be
understood as the percentage of the area of the reference cluster $r$ at
$D^{(i)}$. If the second case happens, we consider the entire region inside of
the reference cluster $r$ at $D^{(i+1)}$, but the clusters of this region (which
we call the {\it usual clusters}) are defined by those at $D^{(i)}$. The usual
clusters are the CCA clusters at the imminence of the merging process between
$D^{(i)}$ and $D^{(i+1)}$. This includes the reference cluster $r$ itself and
one or more of the other clusters before the merging (Fig.\ref{clca}b).
Furthermore, all of the sites of the reference cluster $r$ at $D^{(i+1)}$ are
removed from the initial list of reference sites. This condition is necessary
because we should not merge two large metropolises.

\item In condition (ii), when a reference cluster $r$ is merging with another
cluster that covers one or more regions already defined by previous reference
clusters at different values of $D^*$, there is a strong likelihood of the
emergence of a {\it forbidden region} within that cluster. In this case, we
force the region already defined by the largest value of $D^*$ to grow to the
limits of the forbidden region (Fig.\ref{clca}c). The forbidden regions are the
complementary areas of the reference clusters already defined within the usual
clusters. As a consequence of this procedure, some CCA clusters that were hidden
after the analysis of the previous reference cluster arise in this forbidden
region. We justify this condition by the idea that a metropolis rules the growth
of its satellites, since it plays a fundamental role in their socioeconomic
relations.
\end{enumerate}

\noindent
We apply the same procedure to the second reference cluster, to the third
reference cluster, and so on. Finally, we also define the {\it isolated
clusters} with the minimum value of $D^*$ for all the cases accepted in
condition (ii). In order to make our model clearer, we chose the descending
order to sort the population density for one reason: To favor the merging
process of the high density clusters that rose from the decreasing of the $D^*$.
In practice, we run our revised discrete CCA just once for the entire range of
input parameters and store all of the outputs in order to improve the
performance of the model. The apparent simplicity of this task hides a RAM
memory management problem of storing all of the outputs in a medium-performance
computer. We overcome such a barrier through the {\it zram module}
\cite{zram2017}, available in the newest linux kernels. The zram module creates
blocks which compress and store information dynamically in the RAM memory
itself, at the cost of processing time.

\section{The dataset}

We use the {\it Global Rural-Urban Mapping Project} (GRUMPv1) \cite{grump2011},
available from the {\it Socioeconomic Data and Applications Center} (SEDAC) at
Columbia University, to apply the CLCA to a single global dataset. The GRUMPv1
dataset is composed of georeferenced rectangular population grids for 232
countries around the world in the year 2000 (Fig. \ref{grumpv1}). Such a dataset
is a compilation of gridded census and satellite data for the populations of
urban and rural areas. These data are provided at a high resolution of
$30\;\text{arc-seconds}$, equivalent to $30/3600\;\text{degrees}$ or a grid of
$0.926\;km \times 0.926\;km$ at the Equator. We note that despite of the
heterogeneous population distributions that built the GRUMPv1, its overall
resolution is tolerable to the CLCA, since we can identify well-defined clusters
around all continents in the raw data.

We calculate the area of ​​each site by the composition of two spherical
triangles \cite{snyder1987}. The area of a spherical triangle with edges $a$,
$b$ and $c$ is given by
\begin{equation}\label{eq4}
A=4 R_e^2 \tan^{-1}\left[\tan\left(\frac{s}{2}\right)\tan\left(\frac{s_a}{2}\right)\tan\left(\frac{s_b}{2}\right)\tan\left(\frac{s_c}{2}\right)\right]^{1/2},
\end{equation}

\noindent
where $s=(a/R_e+b/R_e+c/R_e)/2$, $s_a=s-a/R_e$, $s_b=s-b/R_e$, and
$s_c=s-c/R_e$. In this formalism, $R_e=6,378.137\;km$ is the Earth's radius and
the edge lengths are calculated by the great circle (geodesic) distance between
two points $i$ and $j$ on the Earth's surface:
\begin{equation}\label{eq5}
d_{ij}=R_e\cos^{-1}[\sin(\phi_i) \sin(\phi_j)+\cos(\phi_i)\cos(\phi_j)\cos(\lambda_j-\lambda_i)].
\end{equation}

\noindent
The values of $\lambda_i$ ($\lambda_j$) and $\phi_i$ ($\phi_j)$, measured in
radians, are the longitude and latitude, respectively, of the point $i$ ($j$).
Thus, we are able to define the population density for each site of the lattice,
since its population and area are known.

We also pre-process the GRUMPv1 dataset, dividing all countries and continents
--- and even the entire world --- into large regions which we call {\it clusters
of regions}, to apply our model in a feasible computational time using
medium-performance computers. These regions are defined by the CCA with lower
and upper bound parameters $D^*=50\;\text{people}/km^2$ and $\ell=10\;km$,
respectively. We believe that such large clusters can hold the socioeconomic and
cultural relations among different urban settlements of a territory. Fig.
\ref{us_east}a shows the largest clusters of regions in the US; as we can see,
all of the Eastern US is considered a single cluster.

\section{Results}

To show the relevance of our model, we apply the CLCA to the GRUMPv1 dataset at
three different geographic levels: countries, continents and the entire world.
For each case, we consider only a single set of CLCA parameters. We justify our
choices with the following assumptions: (i) $D^{(min)}=100\;\text{people}/km^2$,
a value slightly greater than the lower bound CCA parameter
($D^*=50\;\text{people}/km^2$) used to define the regions of clusters; (ii)
$D^{(max)}=1000\;\text{people}/km^2$, a loosened value of $D^{(max)}=\infty$;
(iii) $\delta=10\;\text{people}/km^2$, a small enough value to avoid the
reference clusters growing without merging; (iv) $\ell=3\;km$, the critical
distance threshold, already extensively analyzed by previous CCA studies
\cite{rozenfeld2008, rozenfeld2011, oliveira2014}; (v) $A^*=50\;km^2$, the
minimum area of a metropolis, as it is required that $A^*$ be reasonably greater
than the minimum unit of area from the dataset and smaller than a metropolis'
area; and (vi) $H^*=0.05$, a large enough value to favor the merging of clusters
which are similar in size. The Fig. \ref{us_east}b shows the CLCA cities defined
by the single set of CLCA parameters. For other regions, see the Supplementary
Information (SI).

We study the population distribution using the Maximum Likelihood Estimator
(MLE) proposed by Clauset {\it et al.} \cite{clauset2009}. Their approach
combines maximum-likelihood fitting methods with goodness-of-fit tests based on
Kolmogorov-Smirnov (KS) statistic. The Fig. \ref{g_countries_panel} shows the
log-log behavior of the Cumulative Distribution Function (CDF) for the
population of the CLCA cities, considering only the countries with the highest
number of CLCA cities for each continent (for other countries, see the SI). The
$Pr(\mathcal{P} \geq P)$ represents the probability that a random population
$\mathcal{P}$ takes on a value greater or equal to the population $P$. In all
CDF plots, we also show the maximum likelihood power-law fit, as well as, the
value of the exponent $\zeta=\alpha-1$, where $\alpha$ is the MLE exponent, and
the value of $P_{min}$, the lower bound of the MLE.

In Fig. \ref{g_countries_hist}, we show a normalized histogram, with frequency
$F$, of the $\zeta$ exponents for all countries ( 145 out of 232) with at least
10 CLCA cities in the region covered by the maximum likelihood power-law fit.
The mean value of the $\zeta$ exponents is $\bar{\zeta}=0.98$, with variance
$\sigma^2=0.09$. The dashed red line stands for the normal distribution
$\mathcal{N}(\bar{\zeta},\sigma^2)$. In spite of the $\zeta$ exponent
heterogeneity illustrated by Fig. \ref{g_countries_hist}, Zipf's law holds for
most countries around the globe. We emphasize that such results corroborate with
previous studies performed for one country or a small number of countries
\cite{rozenfeld2008, rozenfeld2011, gabaix1999a, gabaix1999b, ioannides2003,
cordoba2008, giesen2010, giesen2011, jiang2011, giesen2012, ioannides2013,
duraton2014, watanabe2015}. In special, the Fig. \ref{g_countries_hist} also
endorses an astute meta-analysis performed by Cottineau \cite{cottineau2017}.
Cottineau provided a comparison among the Zipf's law exponents found in 86
studies. Our results strongly corroborate those presented in such study, except
that our exponents are ranged between 0 and 2.

Furthermore, we challenge the robustness of our model at higher geographic
levels: continents and the entire world. We performed the same analyses and find
that our results persist on both scales, {\it i.e.} the CLCA cities follows
Zipf's law for continents and the entire world, as illustrated in Figs.
\ref{g_continents_panel} and \ref{g_world}.

We summarize our results in a set of 7 tables: Tables \ref{t_countries_af},
\ref{t_countries_as}, \ref{t_countries_eu}, \ref{t_countries_na} ,
\ref{t_countries_oc}, and \ref{t_countries_sa}, for countries from Africa; Asia;
Europe; North America; Oceania; and South America, respectively. Table
\ref{t_continents_world} contains similar information for all continents and the
entire world. In all cases, we show the name of the considered region (country,
continent or globe), the ISO 3166-1 alpha-3 code associated (only for
countries), the number of cities obtained by the CLCA and those covered by the
MLE, the lower bound $P_{min}$, and the Zipf's exponent $\zeta$.

It is remarkable that the top CLCA city, with a population of 63,585,039 people,
is composed of three large urban settlements (Alexandria, Cairo, and Luxor)
connected by several small ones. Figs. \ref{cairo}a, \ref{cairo}b, and
\ref{cairo}c show the largest cluster of regions in Egypt for the GRUMPv1
dataset; CLCA cities; and night-time lights from the National Aeronautics and
Space Administration (NASA) \cite{nasa2016}, respectively. We believe the main
reason for this finding has been present in the Northeast of Africa since before
the beginning of ancient civilization --- namely, the Nile river. Actually, it
is well known that almost the entire Egypt population lives in a strip along the
Nile river, in the Nile delta, and in the Suez canal on 4\% of the total country
area ($~10^6\;km^2$), where there are arable lands to produce food
\cite{gehad2003}. The river and delta regions are composed by some large cities
and a lot of small villages, making them extremely dense. Therefore, our results
raise the hypothesis that the cities and villages across the Nile can be seen as
a kind of ``megacity'', despite spatially non-contiguous, due to the
socioeconomic relation, reflected on the high commuting levels, among close
subregions.

The Table \ref{t_world} shows the top 25 CLCA cities in the entire world by
population, and their associated areas. After the top CLCA city,
Alexandria-Cairo-Luxor, we emphasize that the 13 next-largest CLCA cities are in
Asia. Indeed, we can see that the shape of the tail end of the entire world
population distribution (in Fig. \ref{g_world}) is roughly ruled by the greater
CLCA city in Africa and several CLCA cities in Asia. 

These facts are not in line with what was recently reported by the {\bf United Nations (UN)} \cite{un2016}, {\it e.g.} the largest CLCA city, Alexandria-Cairo-Luxor, is just the 9th largest city according to the UN, and the largest UN city, Tokyo, is just the 4th largest according to our analyses.

\section{Conclusions}

We propose a model to define urban settlements through a bottom-up approach
beyond their usual administrative boundaries, and moreover to account for the
intrinsic cultural, political, and geographical biases associated with most
societies and reflected in their particular growing dynamics. We claim that such
a property qualifies our model to be applied worldwide, without any regional
restrictions. We also propose an alternative strategy to improve the
computational performance of the discrete CCA. We emphasize that the CCA can
still be used to define cities; however, it depends upon a different tuning of
its parameters for each large region without direct socioeconomic and political
relations. Furthermore, we show that the definition of cities proposed by our
approach is robust and holds to one of the most famous results in Social
Science, Zipf's law, not only for previously studied countries, {\it e.g.} the
US, the UK, or China, but for all countries (145 from 232 provided by GRUMPv1)
around the world. We also find that Zipf's law emerges at different geographic
levels, such as continents and the entire world. Another highlight of our study
is the fact that our model is applied upon one single dataset to define all
cities. Furthermore, we find that the most populated cities are not the major
players in the global economy (such as New York City, London, or Tokyo). The
largest CLCA city, with a population of 63,585,039 people, is an agglomeration
of several small cities close to each other which connects three large cities:
Alexandria, Cairo, and Luxor. Finally, after the top CLCA city of
Alexandria-Cairo-Luxor, we find that the next-largest 13 CLCA cities are in
Asia. These facts are not in full agreement with a recent UN report
\cite{un2016}. According to our results, the largest CLCA city,
Alexandria-Cairo-Luxor, is just the 9th largest city according to the UN, while
the largest UN city, Tokyo, is just the 4th largest according to our analyses.


\section{Data Accessibility}
The dataset supporting this article are available at
\url{http://sedac.ciesin.columbia.edu/data/collection/grump-v1}. More
specifically, the reader can click on ``Data sets'' and, after that, on
``Population Count Grid, v1 (1990,1995,2000)''. We also provide the codes for
the proposed model that are available at
\url{https://doi.org/10.5061/dryad.968nq8n}.

\section{Competing Interests}
We have no competing interests.

\section{Author's Contributions}
EAO performed the data analysis, the algorithm of the proposed model, and the
statistical analysis. He also participated in the design of the study and
drafted the manuscript. VF carried out the funding acquisition and helped draft
the manuscript. JSA participated in the design of the study, carried out the
funding acquisition, and helped draft the manuscript. HAM conceived, designed,
and coordinated the research, as well as, carried out the funding acquisition
and helped draft the manuscript. All authors approved the manuscript.

\section{Acknowledgements}
We thank the Global Rural-Urban Mapping Project (GRUMPv1) team for the dataset
provided. Furthermore, we would like to thank X. Gabaix for helpful comments and
discussions.

\section{Funding}
We gratefully acknowledge funding by CNPq, CAPES, FUNCAP, NSF, and ARL
Cooperative Agreement Number W911NF-09-2-0053 (the ARL Network Science CTA).

