• English
  • Deutsch
  • Log In
    Password Login
    or
  • Research Outputs
  • Projects
  • Researchers
  • Institutes
  • Statistics
Repository logo
Fraunhofer-Gesellschaft
  1. Home
  2. Fraunhofer-Gesellschaft
  3. Konferenzschrift
  4. A Fast Heuristic for Computing Geodesic Closures in Large Networks
 
  • Details
  • Full
Options
06 November 2022
Conference Paper
Titel

A Fast Heuristic for Computing Geodesic Closures in Large Networks

Abstract
Motivated by the increasing interest in applications of graph geodesic convexity in machine learning and data mining, we present a heuristic for approximating the geodesic convex hull of node sets in large networks. It generates a small set of (almost) maximal outerplanar spanning subgraphs for the input graph, computes the geodesic closure in each of these graphs, and regards a node as an element of the convex hull if it belongs to the closed sets for at least a user specified number of outerplanar graphs. Our heuristic algorithm runs in time linear in the number of edges of the input graph, i.e., it is faster with one order of magnitude than the standard algorithm computing the closure exactly. Its performance is evaluated empirically by approximating convexity based core-periphery decomposition of networks. Our experimental results with large real-world networks show that for most networks, the proposed heuristic was able to produce close approximations significantly faster than the standard algorithm computing the exact convex hulls. For example, while our algorithm calculated an approximate core-periphery decomposition in 5 h or less for networks with more than 20 million edges, the standard algorithm did not terminate within 50 days.
Author(s)
Seiffarth, Florian
Universität Bonn
Horvath, Tamas
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS
Wrobel, Stefan
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS
Hauptwerk
Discovery Science. 25th International Conference, DS 2022. Proceedings
Project(s)
Lamarr-Institute for Machine Learning and Artificial Intelligence
Funder
Bundesministerium für Bildung und Forschung -BMBF-
Konferenz
International Conference on Discovery Science 2022
International Conference on Algorithmic Learning Theory 2022
Thumbnail Image
DOI
10.1007/978-3-031-18840-4_34
Language
English
google-scholar
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS
Tags
  • Convex cores

  • Geodesic closure

  • Outerplanar graphs

  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Send Feedback
© 2022