Abstract
A. Li, P. Stuckey, S. Koenig and S. Kumar. A FastMap-Based Framework for Efficiently Computing Top-K Projected Centrality. In International Conference on Machine Learning, Optimization, and Data Science (LOD) 2023 - Part 1, G. Nicosia, V. Ojha, E. La Malfa, G. La Malfa, P. M. Pardalos and R. Umeton (editor), volume 14505 of 158-173. Springer, 2024.Abstract: In graph theory and network analysis, various measures of centrality are used to characterize the importance of vertices in a graph. Although different measures of centrality have been invented to suit the nature and requirements of different underlying problem domains, their application is restricted to explicit graphs. In this paper, we first define implicit graphs that involve auxiliary vertices in addition to the pertinent vertices. We then generalize the various measures of centrality on explicit graphs to corresponding measures of projected centrality on implicit graphs. We also propose a unifying framework for approximately, but very efficiently computing the top-K pertinent vertices in implicit graphs for various measures of projected centrality. Our framework is based on FastMap, a graph embedding algorithm that embeds a given undirected graph into a Euclidean space in near-linear time such that the pairwise Euclidean distances between vertices approximate a desired graph-based distance function between them. Using FastMap's ability to facilitate geometric interpretations and analytical procedures in Euclidean space, we show that the top-K vertices for many popularly used measures of centrality - and their generalizations to projected centrality - can be computed very efficiently in our framework.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.