Mixing local and global information for community detection in large networks

Abstract

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.

References in corpus (11)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Finding statistically significant communities in networks
• Hierarchical modularity in human brain functional networks
• Analysis of the structure of complex networks at different resolution levels
• A Novel Measure of Edge Centrality in Social Networks
• Enhancing community detection using a network weighting strategy

Cited by in corpus (17)

• Community detection in networks: Structural communities versus ground truth
• Engineering Parallel Algorithms for Community Detection in Massive Networks
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Community structure: A comparative evaluation of community detection methods
• Big Networks: A Survey
• Community Detection in Complex Networks Using Density-based Clustering Algorithm
• Community detection using boundary nodes in complex networks
• User Popularity-based Packet Scheduling for Congestion Control in Ad-hoc Social Networks
• Community detection using preference networks
• Correlations among Game of Thieves and other centrality measures in complex networks
• Correlation analysis of node and edge centrality measures in artificial complex networks
• Visualizing criminal networks reconstructed from mobile phone records
• Network Community Detection on Metric Space
• The Atlas for the Aspiring Network Scientist
• A new method for community detection in social networks based on message distribution
• ECHO: Encoding Communities via High-order Operators
• SoReC: A Social-Relation Based Centrality Measure in Mobile Social Networks