A FastMap-based algorithm for block modeling. (English) Zbl 1502.68258
Schaus, Pierre (ed.), Integration of constraint programming, artificial intelligence, and operations research. 19th international conference, CPAIOR 2022, Los Angeles, CA, USA, June 20–23, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13292, 232-248 (2022).
Summary: 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.
For the entire collection see [Zbl 1493.68024].
For the entire collection see [Zbl 1493.68024].
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 91D30 | Social networks; opinion dynamics |
References:
| [1] | Abbe, E., Community detection and stochastic block models: recent developments, J. Mach. Learn. Res., 18, 6446-6531 (2017) · Zbl 1403.62110 |
| [2] | Antonopoulos, C.G.: Dynamic range in the C. elegans brain network. Chaos: Interdisc. J. Nonlinear Sci. 26(1), 013102 (2016) |
| [3] | Chan, J., Liu, W., Kan, A., Leckie, C., Bailey, J., Ramamohanarao, K.: Discovering latent blockmodels in sparse and noisy graphs using non-negative matrix factorisation. In: Proceedings of the ACM International Conference on Information & Knowledge Management (2013) |
| [4] | Cohen, L., Uras, T., Jahangiri, S., Arunasalam, A., Koenig, S., Kumar, T.K.S.: The FastMap algorithm for shortest path computations. In: Proceedings of the International Joint Conference on Artificial Intelligence (2018) |
| [5] | Davis, T.: USAir97 (2014). https://www.cise.ufl.edu/research/sparse/matrices/Pajek/USAir97 |
| [6] | Faloutsos, C., Lin, K.I.: FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (1995) |
| [7] | Fredman, ML; Tarjan, RE, Fibonacci heaps and their uses in improved network optimization algorithms, J. ACM (JACM), 34, 596-615 (1987) · Zbl 1412.68048 · doi:10.1145/28869.28874 |
| [8] | Girvan, M.; Newman, ME, Community structure in social and biological networks, Natl. Acad. Sci., 99, 7821-7826 (2002) · Zbl 1032.91716 · doi:10.1073/pnas.122653799 |
| [9] | Gopalakrishnan, S., Cohen, L., Koenig, S., Kumar, T.K.S.: Embedding directed graphs in potential fields using FastMap-D. In: Proceedings of the International Symposium on Combinatorial Search (2020) |
| [10] | Hagberg, A., Swart, P., Chult, D.S.: Exploring network structure, dynamics, and function using NetworkX. Technical report, Los Alamos National Lab, Los Alamos, NM (United States) (2008) |
| [11] | Lee, J.; Gross, SP; Lee, J., Improved network community structure improves function prediction, Sci. Rep., 3, 1-9 (2013) |
| [12] | Li, J., Felner, A., Koenig, S., Kumar, T.K.S.: Using FastMap to solve graph problems in a Euclidean space. In: Proceedings of the International Conference on Automated Planning and Scheduling (2019) |
| [13] | Lin, S.; Hu, Q.; Wang, G.; Yu, PS; Cao, T.; Lim, E-P; Zhou, Z-H; Ho, T-B; Cheung, D.; Motoda, H., Understanding community effects on information diffusion, Advances in Knowledge Discovery and Data Mining, 82-95 (2015), Cham: Springer, Cham · doi:10.1007/978-3-319-18038-0_7 |
| [14] | Mattenet, A.; Davidson, I.; Nijssen, S.; Schaus, P., Generic constraint-based block modeling using constraint programming, J. Artif. Intell. Res., 70, 597-630 (2021) · Zbl 1512.68311 · doi:10.1613/jair.1.12280 |
| [15] | Murphy, KP, Machine Learning: A probabilistic perspective (2012), Cambridge: The MIT Press, Cambridge · Zbl 1295.68003 |
| [16] | Newman, M.E.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006) |
| [17] | Peixoto, T.P.: Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models. Phys. Rev. E 89(1), 012804 (2014) |
| [18] | Perozzi, B., Al-Rfou, R., Skiena, S.: DeepWalk: online learning of social representations. In: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2014) |
| [19] | Ramteke, R., et al.: Improving single and multi-view blockmodelling by algebraic simplification. In: Proceedings of the International Joint Conference on Neural Networks (IJCNN) (2020) |
| [20] | Ye, F., Chen, C., Zheng, Z.: Deep autoencoder-like nonnegative matrix factorization for community detection. In: Proceedings of the ACM International Conference on Information and Knowledge Management (2018) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
