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
(82)- Traveling salesman problems with PageRank distance on complex networks reveal community structure
- Fuzzy random walkers with second order bounds: an asymmetric analysis
- Estimating large covariance matrix with network topology for high-dimensional biomedical data
- The interplay between population stability and food-web topology predicts the occurrence of motifs in complex food-webs
- Personalized PageRank clustering: a graph clustering algorithm based on random walks
- Random walks and diffusion on networks
- Generalization of clustering agreements and distances for overlapping clusters and network communities
- Graph clustering based on modularity variation estimations
- Network community detection on metric space
- Top-\(k\) overlapping densest subgraphs
- Dense community detection in multi-valued attributed networks
- Clustering large attributed information networks: an efficient incremental computing approach
- Big networks: a survey
- Weighted stochastic block model
- A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis
- Synwalk: community detection via random walk modelling
- Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator
- Clustering as a dual problem to colouring
- 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
- On community structure validation in real networks
- Modularity maximization to design contiguous policy zones for pandemic response
- A bag-of-paths framework for network data analysis
- Discovering subjectively interesting multigraph patterns
- Stationary subspace analysis of nonstationary covariance processes: eigenstructure description and testing
- The interconnectedness of the economic content in the speeches of the US presidents
- Modeling community structure and topics in dynamic text networks
- Length of clustering algorithms based on random walks with an application to neuroscience
- A link-based similarity for improving community detection based on label propagation algorithm
- A graph clustering algorithm based on a clustering coefficient for weighted graphs
- An effective and scalable overlapping community detection approach: integrating social identity model and game theory
- Network refinement: denoising complex networks for better community detection
- Impact of the Soai-autocatalysis on natural sciences
- An analysis of shipping agreements: the cooperative container network
- Community identification algorithm using relative edge density measure
- 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
- Clustering via the modified Petford-Welsh algorithm
- Robustness of community structure to node removal
- Bounded Arboricity to Determine the Local Structure of Sparse Graphs
- Community detection in networks via a spectral heuristic based on the clustering coefficient
- An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification
- scientific article; zbMATH DE number 6982944 (Why is no real title available?)
- Detection of core-periphery structure in networks using spectral methods and geodesic paths
- Probability distributions for Markov chain based quantum walks
- A multidimensional and multimembership clustering method for social networks and its application in customer relationship management
- Community extraction in multilayer networks with heterogeneous community structure
- Sparse Matrix Graphical Models
- Ant colony optimization based on random walk for community detection in complex networks
- Finding network communities using random walkers with improved accuracy
- Complex networks as a unified framework for descriptive analysis and predictive modeling in climate science
- A classification for community discovery methods in complex networks
- Communities, Random Walks, and Social Sybil Defense
- On the reliable and efficient numerical integration of the Kuramoto model and related dynamical systems on graphs
- Gravitational community detection by predicting diameter
- Structure Detection in Mixed-Integer Programs
- Clustering and community detection in directed networks: a survey
- Analysis of node2vec random walks on networks
- Fast unfolding of communities in large networks
- A DC Programming Approach for Finding Communities in Networks
- Centrality based community discovery
- Complex networks for community detection of basketball players
- EAMCD: an efficient algorithm based on minimum coupling distance for community identification in complex networks
- Inference with non-probability samples and survey data integration: a science mapping study
- Blind subgrouping of task-based fMRI
- Post-processing hierarchical community structures: quality improvements and multi-scale view
- An integrative dynamical perspective for graph theory and the analysis of complex networks
- Adapting infomap to absorbing random walks using absorption-scaled graphs
- Revealing the community structure of urban bus networks: a multi-view graph learning approach
- Entropic detection of chromatic community structures
- A Dirichlet stochastic block model for composition-weighted networks
- An improvement on the Louvain algorithm using random walks
- A maximal-clique-based set-covering approach to overlapping community detection
- Defensive alliances in signed networks
- Overlapping community detection algorithms using modularity and the cosine
- Detection of structurally homogeneous subsets in graphs
- Modeling acquaintance networks based on balance theory
- An improved spectral clustering community detection algorithm based on probability matrix
- Complex systems: features, similarity and connectivity
- Two sample tests for high-dimensional autocovariances
- Random walk with restart: fast solutions and applications
- Two local dissimilarity measures for weighted graphs with application to protein interaction networks
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)
