Spectral clustering with epidemic diffusion.

Area of Science:

• Graph theory
• Network analysis
• Computational mathematics

Background:

• Spectral clustering commonly partitions graphs using graph Laplacian eigenvalues/eigenvectors.
• Graph Laplacian is closely associated with random walks on graphs.
• Existing methods may struggle with dense intercommunity linking, obscuring community structure.

Purpose of the Study:

• To propose a novel spectral partitioning method leveraging epidemic diffusion properties.
• To introduce the replicator operator as an alternative to the graph Laplacian for spectral clustering.
• To evaluate the effectiveness of the replicator-based method against traditional spectral clustering.

Main Methods:

• Developed a spectral partitioning method based on epidemic diffusion dynamics.
• Utilized the replicator operator, equivalent to a reweighted graph Laplacian.
• Reweighted graph edges using eigenvector centralities of incident nodes.
• Partitioned nodes using the ratio of the replicator's second to first eigenvector components.

Main Results:

• The replicator operator reweights edges, prioritizing connections between central nodes.
• Demonstrated the replicator's equivalence to the symmetric normalized Laplacian of a reweighted graph.
• Compared performance against traditional spectral clustering on synthetic graphs.
• Showcased superior community detection for dense, clique-like structures.

Conclusions:

• Epidemic diffusion offers a powerful alternative for spectral graph partitioning.
• The replicator-based method effectively identifies communities obscured by dense linking.
• This approach enhances the discovery of modular structures in complex networks.