Compressing regularized dynamics improves link prediction with the map equation in sparse networks

Area of Science:

• Network science
• Data mining
• Computational social science

Background:

• Link prediction is crucial for understanding network dynamics in various fields.
• Community structure analysis is a key technique for effective link prediction.
• Standard MapSim, based on the map equation, struggles with sparse networks due to complete observation assumptions.

Purpose of the Study:

• To enhance link prediction in sparse networks by addressing limitations of the standard map equation.
• To introduce regularization methods to improve community detection and mitigate fragmentation in incomplete network data.

Main Methods:

• Incorporation of a global regularization method using Bayesian estimates of transition rates.
• Implementation of three local regularization methods to complement the global approach.
• Evaluation of regularized MapSim against standard MapSim and state-of-the-art embedding methods on real-world sparse networks.

Main Results:

• Regularized MapSim significantly outperforms standard MapSim and embedding methods on highly sparse networks.
• The proposed methods effectively compensate for incomplete observations and reduce spurious community fragmentation.
• The global regularization approach demonstrates superior community detection and link prediction performance across various network densities.

Conclusions:

• Regularization techniques substantially improve the robustness and accuracy of link prediction in sparse networks.
• The global regularization method offers a principled, efficient, and hyperparameter-free solution for network analysis.
• This work provides a more reliable tool for predicting future interactions in complex systems with incomplete data.