A FastMap-based framework for efficiently computing top-K projected centrality

Ang Li, Peter Stuckey, Sven Koenig, T. K.Satish Kumar

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.

Original languageEnglish
Title of host publicationMachine Learning, Optimization, and Data Science
Subtitle of host publication9th International Conference, LOD 2023 Grasmere, UK, September 22–26, 2023 Revised Selected Papers, Part I
EditorsGiuseppe Nicosia, Varun Ojha, Emanuele La Malfa, Gabriele La Malfa, Panos M. Pardalos, Renato Umeton
Place of PublicationCham Switzerland
PublisherSpringer
Pages158-173
Number of pages16
ISBN (Electronic)9783031539695
ISBN (Print)9783031539688
DOIs
Publication statusPublished - 2024
EventInternational Conference on Machine Learning, Optimization, and Data Science 2023 - Grasmere, United Kingdom
Duration: 22 Sept 202326 Sept 2023
Conference number: 9th
https://link.springer.com/book/10.1007/978-3-031-53969-5 (Proceedings)
https://lod2023.icas.cc/ (Website)

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume14505
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Machine Learning, Optimization, and Data Science 2023
Abbreviated titleLOD 2023
Country/TerritoryUnited Kingdom
CityGrasmere
Period22/09/2326/09/23
Internet address

Keywords

  • FastMap
  • Graph Embedding
  • Projected Centrality

Cite this