Possiamo sentire la forma di un grafo? Un grafo può farci sentire la forma dei dati?

Naldi, Giovanni

Matematica, cultura e società, Série 1, Tome 5 (2020) no. 2, pp. 111-134.

Riassunto (VO)

Sistemi composti da elementi discreti che presentano interazioni binarie appaiono in vari ambiti scientifici e tecnologici. La struttura matematica naturale per studiare e rappresentare tali sistemi è quella di grafo in cui gli elementi sono detti vertici (nodi) mentre le interazioni lati (o archi). Di interesse sono anche i modelli che rappresentano processi dinamici su un grafo e in cui si associa ad ogni lato e/o vertice equazioni o operatori differenziali. In tal caso, per capire il comportamento dell'intero sistema è importante comprendere sia la dinamica dei singoli elementi sia la struttura sottostante. In questo articolo (diviso in due parti) considereremo due problemi particolari: il primo consiste nella ricostruzione della topologia di un grafo (sia nel caso statico sia nel caso dinamico); il secondo riguarda la possibilità di estrarre informazioni su un insieme di dati partendo dalle proprietà di un grafo che li rappresenti.

Abstract

Systems composed of discrete elements that present binary interactions appear in various scientific and technological areas. The natural mathematical structure for studying, and representing, these systems is that of a graph in which the elements are called vertices (nodes) while the interactions/edges/arcs. We are also interested in models that represent dynamic processes on a graph and in which differential equations or operators are associated with each edge and/or vertex . To understand the behavior of the wholesystem, it is important to understand both the dynamics of the individual elements and the underlyingstructure. In this article (divided into two parts) we will consider two particular problems: the first oneconsists in the reconstruction of the topology of a graph (both in the static and in the dynamic case); thesecond concerns the possibility of extracting information on a data set starting from the properties of a graph that represents them.

Bibliographie

[1] G. Aletti, D. Lonardoni, G. Naldi, T. Nieus, From dynamics to links: a sparse reconstruction of the topology of a neural network, Commun. Appl. Ind. Math., Vol. 10 N. 2 2019, 2-11 | DOI | MR | Zbl

[2] M. Benzi, E. Estrada, C. Klymko, Ranking Hubs and Authorities Using Matrix Functions, Linear Algebra and its Applications, 438 2013, 2447- 2474. | DOI | MR | Zbl

[3] G. Berkolaiko, P. Kuchment Introduction to Quantum Graphs, AMS Mathematical Surveys and Monographs. Providence RI, 2013. | DOI | MR | Zbl

[4] N.L. Biggs, E.K. Lloyd, R.J. Wilson Graph Theory 1736-1936. Oxford University Press, New York, 1998. | MR

[5] P. Blanchard, D. Volchenkov Random Walks and Diffusions on Graphs and Databases - An Introduction. Springer-Verlag Berlin Heidelberg, 2011. | DOI | MR | Zbl

[6] F. Cavarretta, G. Naldi, Mathematical study of a nonlinear neuron model with active dendrites, AIMS Mathematics 4 (3), 831-846. | DOI | MR

[7] Fan R. K. Chung Spectral Graph Theory. AMS CBMS Regional Conference Series in Mathematics Vol. 92, 1997. | MR

[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Introduzione agli algoritmi e strutture dati. McGraw-Hill Education, 2010.

[9] D. M. Cvetković, P. Rowlinson, S. Simić, An Introduction to the Theory of Graph Spectra, London Mathematical Society, Cambridge University Press, 2010. | MR | Zbl

[10] E.R. Van Dam, W.H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 2003, 241-272. | DOI | MR | Zbl

[11] E.R. Van Dam, W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Mathematics 309 2009, 576-586. | DOI | MR | Zbl

[12] R. Diestel, Graph Theory. Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173, 2016.

[13] E. Estrada, N. Hatano, M. Benzi, The Physics of Communicability in Complex Networks, Physics Reports, 514 2012, 89-119. | DOI | MR

[14] L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii academiae scientiarum Petropolitanae 8, 1741, 128-140.

[15] R. Ghrist Elementary Applied Topology, ed. 1.0, Createspace, 2014. | Zbl

[16] C. Gordon, D. Webb, S. Wolpert, Isospectral plane domains and surfaces via Riemannian orbifolds, Invent. Math., Vol. 110 n. 1, 1992, 1-22 | fulltext EuDML | DOI | MR | Zbl

[17] L. J. Grady, J. R. Polimeni Discrete Calculus, Applied Analysis on Graphs for Computational Science, Springer-Verlag London, 2010. | DOI | MR

[18] B. Gutkin, U. Smilansky, Can one hear the shape of a graph?, J. Phys. A: Math. Gen. Vol. 34 2001, 6061. | DOI | MR | Zbl

[19] K. M. Hall, An r-dimensional quadratic placement algorithm. Management Science, 17 1970, 219-229. | Zbl

[20] V. Isakov Inverse problems for partial differential equations. Springer-Verlag, New York, 1998. | DOI | MR | Zbl

[21] V. Y. Ivrii, Second term of the spectral asymptotic expansion of the Laplace-Beltrami operator on manifolds with boundary. Funct. Anal. Appl., 14(2) (1980), 98-106. | MR | Zbl

[22] V. Ivrii, Accurate spectral asymptotics for elliptic operators that act in vector bundles. Funct. Anal. Appl., 16(2) (1982), 101-108. | MR

[23] M. Kac, Can one hear the shape of a drum?, Amer. Math. Monthly 73 (1966), 1-23. | DOI | MR | Zbl

[24] M. Kneser, Lineare Relationen Zwischen quadratischer Formen, Math. Ann., 168 (1967), 31-39. | fulltext EuDML | DOI | MR | Zbl

[25] P. Kurasov, M. Nowaczyk, Inverse Spectral Problem for Quantum Graphs, J. Phys. A: Math. Gen. Vol. 38 2005, 4901-15. | DOI | MR | Zbl

[26] M. London, M. Husser, Dendritic computation. Annu. Rev. Neurosci. Vol. 28 2005, 503-532.

[27] J. Milnor, Eigenvalues of the Laplace operator of certain manifold, Proc. Nat. Acad. Sci. U.S.A., 51 (1964), 542. | DOI | MR | Zbl

[28] O. Ore I Grafi e le loro applicazioni. Zanichelli, Bologna, 1979. | MR

[29] A. Pleijel, Propriétés asymptotiques des fonctions fondamentales du probléme des vibrations dans un corps élastique, Arkiv f. Mat. Astron. o. Fysik, 26 (1939), 1-9. | MR | Zbl

[30] D. A. Spielman, Graphs, vectors, and matrices, Bull. Amer. Math. Soc. (N.S.), Vol. 54 n. 1, 2017, 45-61. | DOI | MR | Zbl

[31] T. Sunada, Riemannian coverings and isospectral manifolds, Ann. of Math. (2), Vol. 121 n. 1, 1985, 169-186. | DOI | MR | Zbl

[32] W. T. Tutte, How to draw a graph, Proc. London Math. Soc. (3) 13 1963, 743-767. | DOI | MR | Zbl

[33] Marie-France Vignéras, Varietés riemanniennes isospectrales et non isometriques, Ann. of Math., 91 (1980), 21-32. | Zbl

[34] H. Weyl, Über die asymptotische verteilung der Eigenwerte, Gott Nach. (1911), 110-117. | fulltext EuDML | Zbl

[35] H. Weyl, Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller differentialgleichungen, Math. Ann., 71 (1912), 441-479. | fulltext EuDML | DOI | MR | Zbl

[36] S. Zelditch, Spectral determination of analytic bi-axisymmetric plane domains, Geom. Funct. Anal., Vol. 10 n.3, 2000, 628-677. | DOI | MR | Zbl

[37] S. Zelditch, Eigenfunctions of the Laplacian on a Riemannian manifold. CBMS Regional Conference Series in Mathematics, Vol. 125, AMS, Providence, 2017. | MR | Zbl