Community Detection Using Restrained Random-Walk Similarity.

Area of Science:

• Graph theory
• Network analysis
• Data mining

Background:

• Community detection is crucial for understanding complex networks.
• Existing methods face challenges in accuracy and scalability.
• Random walk-based approaches show promise but require refinement.

Purpose of the Study:

• To propose a novel restrained random-walk similarity method for graph community detection.
• To enhance the accuracy of community structure identification in networks.
• To address limitations of existing random walk techniques.

Main Methods:

• Utilizing finite-length random walks starting from vertices.
• Defining community membership based on similarity of visited vertex sets.
• Implementing two key constraints: excluding abnormal walks and restraining walk length.
• Abnormal walks are identified and excluded based on low visit frequency.
• Walks are terminated upon repeated visits to already passed vertices.

Main Results:

• The proposed method demonstrates superior accuracy in community detection compared to previous techniques.
• Experiments on real-world networks validate the effectiveness of the restrained random-walk approach.
• The method successfully identifies underlying community structures in complex graphs.

Conclusions:

• The restrained random-walk similarity method is an effective technique for graph community detection.
• The constraints applied to random walks improve the reliability and accuracy of results.
• This method offers a significant advancement in network analysis for identifying community structures.