Computing Communities in Large Networks Using Random Walks
From MaRDI portal
Publication:5301388
DOI10.7155/JGAA.00124zbMATH Open1161.68694DBLPjournals/jgaa/PonsL06arXivcond-mat/0412368OpenAlexW2033590892WikidataQ62072911 ScholiaQ62072911MaRDI QIDQ5301388FDOQ5301388
Authors: Pascal Pons, Matthieu Latapy 
Publication date: 19 January 2009
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/cond-mat/0412368
Recommendations
Cited In (76)
- Complex systems: features, similarity and connectivity
- Community detection in networks via a spectral heuristic based on the clustering coefficient
- Complex networks as a unified framework for descriptive analysis and predictive modeling in climate science
- On community structure validation in real networks
- An analysis of shipping agreements: the cooperative container network
- Two sample tests for high-dimensional autocovariances
- 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
- Dense community detection in multi-valued attributed networks
- The interconnectedness of the economic content in the speeches of the US presidents
- 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
- Analysis of node2vec random walks on networks
- Structure Detection in Mixed-Integer Programs
- Comparison of algorithms in graph partitioning
- Fast approximation for computing the fractional arboricity and extraction of communities of a graph
- Bayesian degree-corrected stochastic blockmodels for community detection
- Title not available (Why is that?)
- Detection of core-periphery structure in networks using spectral methods and geodesic paths
- A multidimensional and multimembership clustering method for social networks and its application in customer relationship management
- Traveling salesman problems with PageRank distance on complex networks reveal community structure
- A bag-of-paths framework for network data analysis
- Detection of structurally homogeneous subsets in graphs
- Modeling acquaintance networks based on balance theory
- Fuzzy random walkers with second order bounds: an asymmetric analysis
- Random walk with restart: fast solutions and applications
- Bounded Arboricity to Determine the Local Structure of Sparse Graphs
- Clustering via the modified Petford-Welsh algorithm
- The interplay between population stability and food-web topology predicts the occurrence of motifs in complex food-webs
- Post-processing hierarchical community structures: quality improvements and multi-scale view
- Robustness of community structure to node removal
- Communities, Random Walks, and Social Sybil Defense
- Personalized PageRank clustering: a graph clustering algorithm based on random walks
- Modularity maximization to design contiguous policy zones for pandemic response
- 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
- Probability distributions for Markov chain based quantum walks
- Clustering large attributed information networks: an efficient incremental computing approach
- 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
- Generalization of clustering agreements and distances for overlapping clusters and network communities
- Graph clustering based on modularity variation estimations
- An integrative dynamical perspective for graph theory and the analysis of complex networks
- EAMCD: an efficient algorithm based on minimum coupling distance for community identification in complex networks
- Gravitational community detection by predicting diameter
- Ant colony optimization based on random walk for community detection in complex networks
- Finding network communities using random walkers with improved accuracy
- Inference with non-probability samples and survey data integration: a science mapping study
- Blind subgrouping of task-based fMRI
- Community identification algorithm using relative edge density measure
- 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
- Revealing the community structure of urban bus networks: a multi-view graph learning approach
- Centrality based community discovery
- Length of clustering algorithms based on random walks with an application to neuroscience
- Complex networks for community detection of basketball players
- Network refinement: denoising complex networks for better community detection
- A graph clustering algorithm based on a clustering coefficient for weighted graphs
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)
