Topologically biased random walk and community finding in networks

Area of Science:

• Network Science
• Quantum Mechanics
• Computational Physics

Background:

• Random walks are fundamental tools for analyzing network structures.
• Understanding network topology is crucial for various applications, including community detection.
• Existing random walk methods may not fully capture complex network properties.

Purpose of the Study:

• To develop a novel approach for biased random walks in undirected networks.
• To investigate the behavior of these walks using an analogy with quantum mechanics perturbation theory.
• To analyze the relationship between bias parameters and network exploration characteristics.

Main Methods:

• Formulating a one-parameter family of topology biases for random walks.
• Employing a formal analogy with quantum mechanical perturbation theory.
• Utilizing parametric equations of motion to study walk dynamics.
• Analyzing the spectral gap and the second eigenvalue of the transition matrix.

Main Results:

• Demonstrated a method to bias random walks based on network topology.
• Established an analogy with quantum mechanics to understand biased random walk features.
• Showcased how parameter variations influence random walk behavior.
• Quantified the spectral gap's relation to relaxation rates and network structure.

Conclusions:

• The proposed topology biased random walks offer a new perspective on network exploration.
• The quantum mechanics analogy provides a powerful framework for analysis.
• This approach facilitates the development of ad hoc algorithms for complex network and community discovery.