  The problem of clustering large complex networks plays a key role in several
scientific fields ranging from Biology to Sociology and Computer Science. Many
approaches to clustering complex networks are based on the idea of maximizing a
network modularity function. Some of these approaches can be classified as
global because they exploit knowledge about the whole network topology to find
clusters. Other approaches, instead, can be interpreted as local because they
require only a partial knowledge of the network topology, e.g., the neighbors
of a vertex. Global approaches are able to achieve high values of modularity
but they do not scale well on large networks and, therefore, they cannot be
applied to analyze on-line social networks like Facebook or YouTube. In
contrast, local approaches are fast and scale up to large, real-life networks,
at the cost of poorer results than those achieved by local methods. In this
article we propose a glocal method to maximizing modularity, i.e., our method
uses information at the global level, yet its scalability on large networks is
comparable to that of local methods. The proposed method is called COmplex
Network CLUster DEtection (or, shortly, CONCLUDE.) It works in two stages: in
the first stage it uses an information-propagation model, based on random and
non-backtracking walks of finite length, to compute the importance of each edge
in keeping the network connected (called edge centrality.) Then, edge
centrality is used to map network vertices onto points of an Euclidean space
and to compute distances between all pairs of connected vertices. In the second
stage, CONCLUDE uses the distances computed in the first stage to partition the
network into clusters. CONCLUDE is computationally efficient since in the
average case its cost is roughly linear in the number of edges of the network.
