Improving the performance of algorithms to find communities in networks

Area of Science:

• Network science
• Graph theory
• Data mining

Background:

• Community detection algorithms often lack prior knowledge of network partition structure.
• This lack of information can lead to reduced accuracy and resolution bias in results.

Purpose of the Study:

• To demonstrate how knowing the number of communities enhances standard detection methods.
• To introduce a novel two-step procedure for inferring community number from graph spectra.

Main Methods:

• Utilizing modularity optimization techniques.
• Inferring the number of clusters from the spectra of nonbacktracking and flow matrices.
• Applying the method to benchmark graphs with realistic community structures.

Main Results:

• Standard community detection methods significantly improve in accuracy when the number of clusters is known.
• The proposed method successfully infers the number of clusters in complex graphs.
• The primary limitation identified is the computational overhead associated with spectrum computation.

Conclusions:

• Incorporating prior knowledge of community count substantially boosts network analysis performance.
• Spectral analysis of nonbacktracking and flow matrices offers a viable approach for estimating community numbers.
• Future work may focus on optimizing the computational efficiency of spectrum calculation.