Local Algorithms for Estimating Effective Resistance
Pan Peng, Daniel Lopatta, Yuichi Yoshida, Gramoz Goranci
Abstract
Effective resistance is an important metric that measures the similarity of two vertices in a graph. It has found applications in graph clustering, recommendation systems and network reliability, among others. In spite of the importance of the effective resistances, we still lack efficient algorithms to exactly compute or approximate them on massive graphs.
Topics & Concepts
Computer scienceCluster analysisReliability (semiconductor)Metric (unit)GraphSimilarity (geometry)Clustering coefficientAlgorithmTheoretical computer scienceMachine learningArtificial intelligenceEconomicsOperations managementPower (physics)Image (mathematics)Quantum mechanicsPhysicsComplex Network Analysis TechniquesGraph theory and applicationsAdvanced Graph Neural Networks