Topologically biased random walk with application for community finding in networks

Abstract

We present a new approach of topology biased random walks for undirected networks. We focus on a one parameter family of biases and by using a formal analogy with perturbation theory in quantum mechanics we investigate the features of biased random walks. This analogy is extended through the use of parametric equations of motion (PEM) to study the features of random walks {\em vs.} parameter values. Furthermore, we show an analysis of the spectral gap maximum associated to the value of the second eigenvalue of the transition matrix related to the relaxation rate to the stationary state. Applications of these studies allow {\em ad hoc} algorithms for the exploration of complex networks and their communities.

8 pages, 7 figures

References in corpus (16)

• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Community detection in graphs
• Epidemic spreading in scale-free networks
• Synchronization in complex networks
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Community detection algorithms: a comparative analysis
• Detecting Network Communities: a new systematic and efficient algorithm
• Detecting communities in large networks
• Preferential attachment in the growth of social networks: the case of Wikipedia
• Wikipedias: Collaborative web-based encyclopedias as complex networks
• Entropy Rate of Diffusion Processes on Complex Networks
• Localization of maximal entropy random walk
• Backbone of complex networks of corporations: The flow of control
• Assortative model for social networks

Cited by in corpus (25)

• A network analysis of countries' export flows: firm grounds for the building blocks of the economy
• A spectrum of routing strategies for brain networks
• Maximal-entropy random walks in complex networks with limited information
• Characteristic times of biased random walks on complex networks
• Flow graphs: interweaving dynamics and structure
• Efficient exploration of multiplex networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• In a World That Counts: Clustering and Detecting Fake Social Engagement at Scale
• Maximal entropy random walk in community finding
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• RobustECD: Enhancement of Network Structure for Robust Community Detection
• Enhancing community detection by local structural information
• Networks with arbitrary edge multiplicities
• Reactive random walkers on complex networks
• Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees
• Maximal-entropy random walk unifies centrality measures
• The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes
• Biased random walkers and extreme events on the edges of complex networks
• Generalized Markov stability of network communities
• Random Surfers on a Web Encyclopedia
• Synthetic sequence generator for recommender systems - memory biased random walk on sequence multilayer network
• The Atlas for the Aspiring Network Scientist
• Rapid Bayesian Inference of Global Network Statistics Using Random Walks
• Degree-penalized contact processes
• Tuning Ranking in Co-occurrence Networks with General Biased Exchange-based Diffusion on Hyper-bag-graphs