Metric-Based Classification of Graph Vertices
Daniel Jaewoo Kim, John Pugmire · Digital WPI · 2019
In their 2013 paper, Cao et. al introduce the diffusion state distance (DSD) metric on graphs for use in the vertex labeling problem on protein-protein interaction networks. We generalize their classification approach, which uses weighted k-nearest neighbors voting, to work with any graph metric. We analyze the performance of this approach on graphs resembling real-world networks using shortest-path distance, DSD, and resistance distance. To this end, we propose novel simulation models to generate labeled scale-free and small-world networks, and perform label prediction experiments on the simulated graphs as well as real-world networks. We conclude that the DSDbased prediction algorithm exhibits more robust community awareness than the ones using the other metrics.