Projects per year
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 language | English |
---|---|
Title of host publication | Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 19th International Conference, CPAIOR 2022 Los Angeles, CA, USA, June 20–23, 2022 Proceedings |
Editors | Pierre Schaus |
Place of Publication | Cham Switzerland |
Publisher | Springer |
Pages | 232-248 |
Number of pages | 17 |
ISBN (Electronic) | 9783031080111 |
ISBN (Print) | 9783031080104 |
DOIs | |
Publication status | Published - 2022 |
Event | International 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 2022 → 23 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
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 13292 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 2022 |
---|---|
Abbreviated title | CPAIOR 2022 |
Country/Territory | United States of America |
City | Los Angeles |
Period | 20/06/22 → 23/06/22 |
Internet address |
Keywords
- Community Detection and Block Modeling
- FastMap
- Graph Embeddings
Projects
- 1 Active
-
ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)
Smith-Miles, K., Stuckey, P., Taylor, P. G., Ernst, A., Aickelin, U., Garcia De La Banda Garcia, M., Pearce, A., Wallace, M., Bondell, H., Hyndman, R., Alpcan, T., Thomas, D. A., Anjomshoa, H., Kirley, M. G., Tack, G., Costa, A., Fackrell, M., Zhang, L., Glazebrook, K., Branke, J., O'Sullivan, B., O'Shea, N., Cheah, A., Meehan, A., Wetenhall, P., Bowly, D., Bridge, J., Faka, S., Mareels, I., Coleman, R. A., Crook, J., Liebman, A. & Aleti, A.
Equans Services Australia Pty Limited
23/09/21 → 23/09/26
Project: Research