This paper emphasizes some intriguing links between neural computation on graphical domains and social networks, like those used in nowadays search engines to score the page authority. It is pointed out that the introduction of web domains creates a unified mathematical framework for these computational schemes. It is shown that one of the major limitations of currently used connectionist models, namely their scarce ability to capture the topological features of patterns, can be effectively faced by computing the node rank according to social-based computation, like Google's PageRank. The main contribution of the paper is the introduction of a novel graph spectral notion, which can be naturally used for the graph isomorphism problem. In particular, a class of graphs is introduced for which the problem is proven to be polynomial. It is also pointed out that the derived spectral representations can be nicely combined with learning, thus opening the doors to many applications typically faced within the framework of neural computation.

Diligenti, M., Gori, M., Maggini, M. (2004). Neural computation, social networks, and topological spectra. THEORETICAL COMPUTER SCIENCE, 320(1), 71-87 [10.1016/j.tcs.2004.03.044].

Neural computation, social networks, and topological spectra

DILIGENTI, MICHELANGELO;GORI, MARCO;MAGGINI, MARCO
2004-01-01

Abstract

This paper emphasizes some intriguing links between neural computation on graphical domains and social networks, like those used in nowadays search engines to score the page authority. It is pointed out that the introduction of web domains creates a unified mathematical framework for these computational schemes. It is shown that one of the major limitations of currently used connectionist models, namely their scarce ability to capture the topological features of patterns, can be effectively faced by computing the node rank according to social-based computation, like Google's PageRank. The main contribution of the paper is the introduction of a novel graph spectral notion, which can be naturally used for the graph isomorphism problem. In particular, a class of graphs is introduced for which the problem is proven to be polynomial. It is also pointed out that the derived spectral representations can be nicely combined with learning, thus opening the doors to many applications typically faced within the framework of neural computation.
2004
Diligenti, M., Gori, M., Maggini, M. (2004). Neural computation, social networks, and topological spectra. THEORETICAL COMPUTER SCIENCE, 320(1), 71-87 [10.1016/j.tcs.2004.03.044].
File in questo prodotto:
File Dimensione Formato  
TCS04.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 418.26 kB
Formato Adobe PDF
418.26 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/29732
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo