Computing Communities in Large Networks Using Random Walks
From MaRDI portal
Publication:5301388
Abstract: Dense subgraphs of sparse graphs (communities), which appear in most real-world complex networks, play an important role in many contexts. Computing them however is generally expensive. We propose here a measure of similarities between vertices based on random walks which has several important advantages: it captures well the community structure in a network, it can be computed efficiently, it works at various scales, and it can be used in an agglomerative algorithm to compute efficiently the community structure of a network. We propose such an algorithm which runs in time O(mn^2) and space O(n^2) in the worst case, and in time O(n^2log n) and space O(n^2) in most real-world cases (n and m are respectively the number of vertices and edges in the input graph). Experimental evaluation shows that our algorithm surpasses previously proposed ones concerning the quality of the obtained community structures and that it stands among the best ones concerning the running time. This is very promising because our algorithm can be improved in several ways, which we sketch at the end of the paper.
Recommendations
Cited in
(76)- Complex systems: features, similarity and connectivity
- An integrative dynamical perspective for graph theory and the analysis of complex networks
- Community detection in networks via a spectral heuristic based on the clustering coefficient
- An analysis of shipping agreements: the cooperative container network
- On community structure validation in real networks
- Two sample tests for high-dimensional autocovariances
- Complex networks as a unified framework for descriptive analysis and predictive modeling in climate science
- EAMCD: an efficient algorithm based on minimum coupling distance for community identification in complex networks
- Gravitational community detection by predicting diameter
- A DC Programming Approach for Finding Communities in Networks
- Network community detection on metric space
- Top-\(k\) overlapping densest subgraphs
- Random walks and diffusion on networks
- Impact of the Soai-autocatalysis on natural sciences
- Estimating large covariance matrix with network topology for high-dimensional biomedical data
- Ant colony optimization based on random walk for community detection in complex networks
- Dense community detection in multi-valued attributed networks
- The interconnectedness of the economic content in the speeches of the US presidents
- Finding network communities using random walkers with improved accuracy
- Synwalk: community detection via random walk modelling
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Modeling latent topics in social media using dynamic exploratory graph analysis: the case of the right-wing and left-wing trolls in the 2016 US elections
- Big networks: a survey
- An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification
- Inference with non-probability samples and survey data integration: a science mapping study
- Blind subgrouping of task-based fMRI
- Fast approximation for computing the fractional arboricity and extraction of communities of a graph
- Bayesian degree-corrected stochastic blockmodels for community detection
- Comparison of algorithms in graph partitioning
- Analysis of node2vec random walks on networks
- Structure Detection in Mixed-Integer Programs
- A multidimensional and multimembership clustering method for social networks and its application in customer relationship management
- scientific article; zbMATH DE number 6982944 (Why is no real title available?)
- Traveling salesman problems with PageRank distance on complex networks reveal community structure
- Detection of structurally homogeneous subsets in graphs
- Modeling acquaintance networks based on balance theory
- Detection of core-periphery structure in networks using spectral methods and geodesic paths
- A bag-of-paths framework for network data analysis
- Random walk with restart: fast solutions and applications
- Fuzzy random walkers with second order bounds: an asymmetric analysis
- Bounded Arboricity to Determine the Local Structure of Sparse Graphs
- Community identification algorithm using relative edge density measure
- The interplay between population stability and food-web topology predicts the occurrence of motifs in complex food-webs
- Clustering via the modified Petford-Welsh algorithm
- Post-processing hierarchical community structures: quality improvements and multi-scale view
- Robustness of community structure to node removal
- Adapting infomap to absorbing random walks using absorption-scaled graphs
- On the reliable and efficient numerical integration of the Kuramoto model and related dynamical systems on graphs
- Personalized PageRank clustering: a graph clustering algorithm based on random walks
- Communities, Random Walks, and Social Sybil Defense
- Revealing the community structure of urban bus networks: a multi-view graph learning approach
- Length of clustering algorithms based on random walks with an application to neuroscience
- Modularity maximization to design contiguous policy zones for pandemic response
- Centrality based community discovery
- A link-based similarity for improving community detection based on label propagation algorithm
- Stationary subspace analysis of nonstationary covariance processes: eigenstructure description and testing
- Weighted stochastic block model
- Clustering and community detection in directed networks: a survey
- An improved spectral clustering community detection algorithm based on probability matrix
- Sparse Matrix Graphical Models
- A classification for community discovery methods in complex networks
- Fast unfolding of communities in large networks
- Modeling community structure and topics in dynamic text networks
- A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
- An effective and scalable overlapping community detection approach: integrating social identity model and game theory
- Network refinement: denoising complex networks for better community detection
- Complex networks for community detection of basketball players
- Clustering large attributed information networks: an efficient incremental computing approach
- Probability distributions for Markov chain based quantum walks
- Two local dissimilarity measures for weighted graphs with application to protein interaction networks
- Discovering subjectively interesting multigraph patterns
- Community extraction in multilayer networks with heterogeneous community structure
- Clustering as a dual problem to colouring
- A graph clustering algorithm based on a clustering coefficient for weighted graphs
- Generalization of clustering agreements and distances for overlapping clusters and network communities
- Graph clustering based on modularity variation estimations
This page was built for publication: Computing Communities in Large Networks Using Random Walks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5301388)
