This research introduces a framework based on stationary measures derived from random walk processes for comparing substructures within and across complex networks. It includes a Stationary Distribution Distance (SDD) for node neighborhoods, a Hitting Time Similarity (HTS) for global structural alignment, and a hierarchical aggregation scheme. The method is both computationally efficient and theoretically grounded.
Key findings
Introduces Stationary Distribution Distance (SDD) for comparing node neighborhoods.
Proposes Hitting Time Similarity (HTS) for capturing global structural alignment.
Develops a hierarchical aggregation scheme combining local and global information.
Establishes theoretical connections to spectral graph theory.
Demonstrates scalability to networks with millions of edges.
Limitations & open questions
The framework's performance on highly dynamic or evolving networks is yet to be tested.
The sensitivity of the measures to noise in real-world data requires further investigation.