A FastMap-based algorithm for block modeling

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

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

5 Citations (Scopus)

Abstract

Block modeling algorithms are used to discover important latent structures in graphs. They are the graph equivalent of clustering algorithms. However, existing block modeling algorithms work directly on the given graphs, making them computationally expensive and less effective on large complex graphs. In this paper, we propose a FastMap-based algorithm for block modeling on single-view undirected graphs. FastMap 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. In the first phase, our FastMap-based block modeling (FMBM) algorithm uses FastMap with a probabilistically-amplified shortest-path distance function between vertices. In the second phase, it uses Gaussian Mixture Models (GMMs) for identifying clusters (blocks) in the resulting Euclidean space. FMBM outperforms other state-of-the-art methods on many benchmark and synthetic instances, both in efficiency and solution quality. It also enables a perspicuous visualization of clusters (blocks) in the graphs, not provided by other methods.

Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022 Los Angeles, CA, USA, June 20–23, 2022 Proceedings
EditorsPierre Schaus
Place of PublicationCham Switzerland
PublisherSpringer
Pages232-248
Number of pages17
ISBN (Electronic)9783031080111
ISBN (Print)9783031080104
DOIs
Publication statusPublished - 2022
EventInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2022 - Los Angeles, United States of America
Duration: 20 Jun 202223 Jun 2022
Conference number: 19th
https://link.springer.com/book/10.1007/978-3-031-08011-1 (Proceedings)
https://sites.google.com/usc.edu/cpaior-2022 (Website)

Publication series

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

Conference

ConferenceInternational Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2022
Abbreviated titleCPAIOR 2022
Country/TerritoryUnited States of America
CityLos Angeles
Period20/06/2223/06/22
Internet address

Keywords

  • Community Detection and Block Modeling
  • FastMap
  • Graph Embeddings

Cite this