P De Meo, E Ferrara, G Fiumara, and A Provetti.
Journal of Computer and Systems Sciences 80(1):72-87 (2014).
Useful links: PDF | Journal page | Arxiv | CONCLUDE code.
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 but still 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.
Testing on diverse benchmark datasets shows good results, both in times and quality of the clustering; that is the case for synthetic networks with well-defined clusters as well as for real-world network instances.