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

Abstract This study presents a novel algorithm, , 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 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 $$\Gamma$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Γ</mml:mi> </mml:math> maximum similarity matching, 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 , named _, which employs innovative computational strategies to improve efficiency, particularly in dynamic environments. Experimental validations on several real-world datasets demonstrate that and _ 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.