Cluster analysis of local convergent sequences of structures1. Issue 4 (26th April 2017)

• Record Type: Journal Article
• Authors: Nešetřil, Jaroslav; de Mendez, Patrice Ossona
• Is Part Of: Random structures & algorithms. Volume 51:Issue 4(2017)
• Page Start: 674
• Page End: 728
• Publication Date: 2017-04-26
• Subjects: graph and relational structure -- graph limits -- structural limits -- radon measures -- stone space -- model theory -- first‐order logic -- measurable graph; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20719
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: The cluster analysis of very large objects is an important problem, which spans several theoretical as well as applied branches of mathematics and computer science. Here we suggest a novel approach: under assumption of local convergence of a sequence of finite structures we derive an asymptotic clustering. This is achieved by a blend of analytic and geometric techniques, and particularly by a new interpretation of the authors' representation theorem for limits of local convergent sequences, which serves as a guidance for the whole process. Our study may be seen as an effort to describe connectivity structure at the limit (without having a defined explicit limit structure) and to pull this connectivity structure back to the finite structures in the sequence in a continuous way. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 674–728, 2017