• English
  • Deutsch
  • Log In
    Password Login
    Research Outputs
    Fundings & 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
November 6, 2022
Conference Paper
Title

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  
Mainwork
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-  
Conference
International Conference on Discovery Science 2022  
International Conference on Algorithmic Learning Theory 2022  
DOI
10.1007/978-3-031-18840-4_34
Language
English
Fraunhofer-Institut für Intelligente Analyse- und Informationssysteme IAIS  
Keyword(s)
  • Convex cores

  • Geodesic closure

  • Outerplanar graphs

  • Cookie settings
  • Imprint
  • Privacy policy
  • Api
  • Contact
© 2024