FaRS: A Performance-Driven Approach to Role Similarity in Graphs

Abstract

This study presents a novel algorithm, FaRS, for single-source role similarity search, designed to capture nuanced topological features within graphs more effectively than existing methods. Traditional role-based similarity algorithms like RoleSim are proficient at identifying automorphic equivalences but often fail to distinguish nodes with structural differences despite their automorphic similarities. By incorporating a technique that utilizes the top maximum similarity matching, FaRS enhances the fidelity of role similarity evaluations by considering a broader range of adjacency relationships. This approach not only ensures the accurate identification of automorphic and structural equivalences but also adheres to key mathematical properties such as uniqueness, symmetry, boundedness, and triangular inequality. We also introduce an accelerated variant of FaRS, named Opt_FaRS, which employs innovative computational strategies to improve efficiency, particularly in dynamic environments. Experimental validations on several real-world datasets demonstrate that FaRS and Opt_FaRS outperform standard benchmarks in both accuracy and computational speed, offering substantial improvements for applications in diverse domains like social network analysis and complex network management. This work contributes significant theoretical and practical advancements to the field of graph-based similarity search, laying a foundation for future explorations into dynamic graph analytics.