Clustering Contextual Neural Gas: A New Approach for Spatial Planning and Analysis Tasks - Computational Approaches for Urban Environments - page 79

Since its introduction, numerous extensions and variants of the CHL algorithm
have been proposed. For example, De Silva and Carlsson ( 2004 )presenteda
generalization of CHL which produces a simplicial complex instead of a graph.
An alternative to CHL was presented by Aupetit ( 2005 ). In this approach, each edge
and vertex of the Delaunay triangulation is the basis of a generative model so that
the triangulation generates a mixture of Gaussian density functions; the likelihood
of the set of model parameters is maximized using the expectation-maximization
algorithm.

4.2.3 Multilevel Modularity Optimization

The multilevel modularity optimization algorithm (MLMO; Blondel et al. 2008 )
is a heuristic method which seeks to find a clustering of a graph with maximum
modularity. Modularity is a quality measure that evaluates the density of connec-
tions inside a cluster as compared with the connection between different clusters
(Newman and Girvan 2004 ). Because optimizing modularity is a problem that is
computationally hard (Brandes et al. 2008 ), heuristic algorithms are inevitable for
practical applications.
The MLMO algorithm consists of two phases: Initially, each vertex of a graph is
assigned to a single cluster. Then, in the first phase, each vertex is assigned to the
cluster of the neighboring vertex which yields the largest increase of modularity, as
long as it is positive. In the second phase, the original graph is replaced by a newly
built graph whose vertices are the clusters found during the first phase. Connections
between the new graphs' vertices exist if there is at least one connection between
vertices of the corresponding clusters in the original graph. The two phases are
iteratively repeated until there are no more changes to the graph and a maximum of
modularity is reached.
The MLMO algorithm is computationally efficient and scales very well, because
the number of clusters dramatically reduces with each pass. In particular, computer
simulations on large graphs indicated that its complexity is linear on typical and
sparse data (Blondel et al. 2008 ). A limitation of most modularity optimizing
clustering algorithms is that they fail to detect small clusters in very large graphs
(Fortunato and Barthelemy 2006 ). However, the MLMO algorithm seems to be
unaffected by this limitation because of its multilevel nature (Blondel et al. 2008 ).
In fact, it has been shown by Fortunato ( 2010 ) and Lancichinetti and Fortunato
( 2009 ) that the quality of the MLMO's results is superior to that of many other
graph clustering algorithms.

4.3 Workflow

The proposed method consists of three major steps that are typically executed in
sequential order: