Statistical Mechanics of Monomer-Dimer Models on Complete and Erdös-Rényi Graphs

Nella tesi sono trattate due famiglie di modelli meccanico statistici su vari grafi: i modelli di spin ferromagnetici (o di Ising) e i modelli di monomero-dimero. Il primo capitolo è dedicato principalmente allo studio del lavoro di Dembo e Montanari, in cui viene risolto il modello di Ising su grafi aleatori. Nel secondo capitolo vengono studiati i modelli di monomero-dimero, a partire dal lavoro di Heilemann e Lieb,con l'intento di dare contributi nuovi alla teoria. I principali temi trattati sono disuguaglianze di correlazione, soluzioni esatte su alcuni grafi ad albero e sul grafo completo, la concentrazione dell'energia libera intorno al proprio valor medio sul grafo aleatorio diluito di Erdös-Rényi.

Definizione di un sistema di raccomandazione basato su reti commerciali

Nel contesto economico odierno i sistemi di raccomandazione rappresentano uno strumento utile al fine di aumentare le vendite con pubblicità e promozioni su misura per ciascun utente. Tali strumenti trovano numerose applicazioni nei siti di e-commerce, si pensi ad Amazon o a MovieLens. Esistono diverse tipologie di sistemi di raccomandazione, che si differenziano principalmente per il modo con cui sono prodotte le raccomandazioni per gli utenti. In questa tesi se ne vuole definire una nuova tipologia, che superi la restrizione del vincolo ad un sito a ad una società, fornendo agli utenti raccomandazioni di prodotti acquistabili in negozi reali e il più possibile accessibili, nel senso geografico del termine. Si e inoltre astratto il concetto di raccomandazione, passando da un insieme omogeneo di oggetti ad un insieme eterogeneo di entità ottenibili attraverso lo svolgimento di attività. Con queste premesse il sistema da definire dovrà raccomandare non più solo entità, ma entità e shop presso i quali sono disponibili per le persone.

Analisi combinatoria dei parchi d'attrazioni

Da oltre mezzo secolo i parchi di divertimento sono strutture complesse e altamente organizzate, entro cui si muovono migliaia di persone quotidianamente; in cui l'elettrificazione, la manutenzione, la sicurezza (sia come safety sia come security) non possono essere lasciate all'improvvisazione. Fra i diversi modelli matematici con cui è possibile rappresentare un parco di divertimenti i grafi si adattano bene a rappresentare l'organizzazione "geografica" delle attrazioni e dei sentieri che le collegano. Fortunatamente la teoria dei grafi si presta anche molto bene all'impostazione e risoluzione dei problemi di ottimizzazione, fornendo quindi uno strumento privilegiato per miglioramenti strutturali nella direzione sia del risparmio economico, sia della fruizione ottimale delle strutture. In questa tesi ho analizzato un aspetto particolare dei grafi associati a quattro parchi d'attrazione: le distanze reciproche tra attrazioni e in particolare la collocazione dei "centri", cioè di vertici del grafo per cui la massima distanza da altri vertici sia minima. I calcoli sono stati eseguiti adattando un'implementazione esistente in Matlab dell'algoritmo di Dijkstra, utilizzando in ingresso le matrici di adiacenza dei grafi. Dopo un capitolo dedicato ai richiami essenziali di teoria dei grafi, il capitolo due traccia una breve storia dei parchi d'attrazione concentrandosi sui quattro che sono l'oggetto di questo studio. Il terzo capitolo, fulcro teorico della tesi, descrive la sperimentazione riportata nel capitolo quattro.

Sviluppo di tecniche di Speckle tracking per la correzione del movimento in ecografia epatica perfusionale

L'ecografia con mezzo di contrasto è una tecnica non invasiva che consente di visualizzare la micro e la macrocircolazione grazie all'utilizzo di microbolle gassose che si distribuiscono in tutto il sistema cardiovascolare. Le informazioni emodinamiche e perfusionali ricavabili dalle immagini eco con contrasto possono essere utilizzate per costruire un modello a grafo dell'albero vascolare epatico. L'analisi della connettività del grafo rappresenta una strategia molto promettente che potrebbe consentire di sostituire la misurazione del gradiente pressorio venoso del fegato, che richiede cateterismo, determinando un notevole miglioramento nella gestione dei pazienti cirrotici. La presente tesi si occupa della correzione dei movimenti del fegato, che deve essere realizzata prima di costruire il grafo per garantire un'accuratezza adeguata. Per correggere i movimenti è proposta una tecnica di Speckle tracking, testata sia in vitro su sequenze eco sintetiche, sia in vivo su sequenze reali fornite dal Policlinico Sant'Orsola.

Dbms basati sui grafi: Analisi e prototipazione di neo4j.

L’obiettivo di questa tesi è quello di mettere a confronto due mondi: quello dei DBMS relazionali e quello dei DBMS a grafo, con lo scopo di comprendere meglio quest'ultimo. Perciò, sono state scelte le due tecnologie che meglio rappresentano i loro mondi: Oracle per gli RDBMS e Neo4j per i Graph DBMS. I due DBMS sono stati sottoposti ad una serie di interrogazioni atte a testare le performance al variare di determinati fattori, come la selettività, il numero di join che Oracle effettua, etc. I test svolti si collocano nell'ambito business intelligence e in particolare in quello dell’analisi OLAP.

Estrazione e annotazione di una rete citazionale da articoli scientifici

Lavoro svolto per la creazione di una rete citazionale a partire da articoli scientifici codificati in XML JATS. Viene effettuata un'introduzione sul semantic publishing, le ontologie di riferimento e i principali dataset su pubblicazioni scientifiche. Infine viene presentato il prototipo CiNeX che si occupa di estrarre da un dataset in XML JATS un grafo RDF utilizzando l'ontologia SPAR.

Circolazioni e omologia dei grafi

In questa tesi verrà trattato il problema di introdurre una teoria omologica sui grafi. Si vedranno i grafi come un 1-complessi simpliciali, e dunque l'idea sarà di applicare le conoscenze che si hanno di una teoria omologica generale ad un oggetto specifico, che è appunto il grafo.

Laplace operator on finite graphs and a network diffusion model for the progression of the Alzheimer disease

Nella tesi viene descritto il Network Diffusion Model, ovvero il modello di A. Ray, A. Kuceyeski, M. Weiner inerente i meccanismi di progressione della demenza senile. In tale modello si approssima l'encefalo sano con una rete cerebrale (ovvero un grafo pesato), si identifica un generale fattore di malattia e se ne analizza la propagazione che avviene secondo meccanismi analoghi a quelli di un'infezione da prioni. La progressione del fattore di malattia e le conseguenze macroscopiche di tale processo(tra cui principalmente l'atrofia corticale) vengono, poi, descritte mediante approccio matematico. I risultati teoretici vengono confrontati con quanto osservato sperimentalmente in pazienti affetti da demenza senile. Nella tesi, inoltre, si fornisce una panoramica sui recenti studi inerenti i processi neurodegenerativi e si costruisce il contesto matematico di riferimento del modello preso in esame. Si presenta una panoramica sui grafi finiti, si introduce l'operatore di Laplace sui grafi e si forniscono stime dall'alto e dal basso per gli autovalori. Al fine di costruire una cornice matematica completa si analizza la relazione tra caso discreto e continuo: viene descritto l'operatore di Laplace-Beltrami sulle varietà riemanniane compatte e vengono fornite stime dall'alto per gli autovalori dell'operatore di Laplace-Beltrami associato a tali varietà a partire dalle stime dall'alto per gli autovalori del laplaciano sui grafi finiti.

Graph-based analysis of brain resting-state fMRI data in nocturnal frontal lobe epileptic patients

Il lavoro che ho sviluppato presso l'unità di RM funzionale del Policlinico S.Orsola-Malpighi, DIBINEM, è incentrato sull'analisi dati di resting state - functional Magnetic Resonance Imaging (rs-fMRI) mediante l'utilizzo della graph theory, con lo scopo di valutare eventuali differenze in termini di connettività cerebrale funzionale tra un campione di pazienti affetti da Nocturnal Frontal Lobe Epilepsy (NFLE) ed uno di controlli sani. L'epilessia frontale notturna è una peculiare forma di epilessia caratterizzata da crisi che si verificano quasi esclusivamente durante il sonno notturno. Queste sono contraddistinte da comportamenti motori, prevalentemente distonici, spesso complessi, e talora a semiologia bizzarra. L'fMRI è una metodica di neuroimaging avanzata che permette di misurare indirettamente l'attività neuronale. Tutti i soggetti sono stati studiati in condizioni di resting-state, ossia di veglia rilassata. In particolare mi sono occupato di analizzare i dati fMRI con un approccio innovativo in campo clinico-neurologico, rappresentato dalla graph theory. I grafi sono definiti come strutture matematiche costituite da nodi e links, che trovano applicazione in molti campi di studio per la modellizzazione di strutture di diverso tipo. La costruzione di un grafo cerebrale per ogni partecipante allo studio ha rappresentato la parte centrale di questo lavoro. L'obiettivo è stato quello di definire le connessioni funzionali tra le diverse aree del cervello mediante l'utilizzo di un network. Il processo di modellizzazione ha permesso di valutare i grafi neurali mediante il calcolo di parametri topologici che ne caratterizzano struttura ed organizzazione. Le misure calcolate in questa analisi preliminare non hanno evidenziato differenze nelle proprietà globali tra i grafi dei pazienti e quelli dei controlli. Alterazioni locali sono state invece riscontrate nei pazienti, rispetto ai controlli, in aree della sostanza grigia profonda, del sistema limbico e delle regioni frontali, le quali rientrano tra quelle ipotizzate essere coinvolte nella fisiopatologia di questa peculiare forma di epilessia.

Entropia, contenuto informativo e network linguistici: applicazioni al manoscritto di Voynich

La tesi si propone di investigare, mediante un approccio puramente quantitativo, il contenuto informativo e la morfologia della lingua del manoscritto di Voynich (VMS), noto per essere redatto in un alfabeto sconosciuto e tuttora non decodificato. Per prima cosa, a partire dal concetto di entropia, sviluppato nel contesto della teoria della informazione, si costruisce una misura del contenuto informativo di un testo (misura di Montemurro-Zanette); quindi, si presentano diversi esperimenti in cui viene misurata l'informazione di testi sottoposti a trasformazioni linguistiche di vario genere(lemmatizzazione, traduzione, eccetera). In particolare, l'applicazione al VMS di questa misura unita ad altre tecniche, ci permette di indagare la struttura tematica del manoscritto e le relazioni tra i suoi contenuti, verificando che esiste una continuità semantica tra pagine consecutive appartenenti a una stessa sezione. La grande quantità di hapax nel manoscritto ci porta poi a considerazioni di tipo morfologico: suggerisce infatti che la lingua del manoscritto sia particolarmente flessiva. La ricerca, in particolare, di sequenze di hapax consecutivi, ci porta a identificare -verosimilmente- alcuni nomi propri. Proprio per approfondire la morfologia della lingua si costruisce infine un grafo linguistico basato sostanzialmente sulla distanza di Hamming; confrontando la topologia di questi grafi per alcune lingue e per la lingua del VMS si osserva che quest'ultimo si distingue per maggiore densità e connessione. Traendo le conclusioni, i forti indizi a favore della presenza di un contenuto informativo nel testo confermano l'ipotesi che questo sia scritto in una vera lingua. Tuttavia, data la notevole semplicità delle regole di costruzione morfologiche, a nostro parere non sembra assimilabile ad una lingua naturale conosciuta, ma piuttosto ad una artificiale, creata appositamente per questo testo.

Dimensione di un insieme parzialmente ordinato

Con questo lavoro si studia l'argomento della dimensione di un insieme parzialmente ordinato P, introdotta nel 1941 da Dushnik e Miller, tramite diagrammi di Hasse, in modo da avere una visione geometrica di un concetto algebrico. Il Teorema di Szpilrajn permette di linearizzare un qualsiasi insieme parzialmente ordinato P: questo anticipa la definizione di dimensione, siccome tutte le linearizzazioni sono realizzatori: le loro coppie comuni sono presenti anche in P. La dimensione viene definita come il minimo numero cardinale m di realizzatori per P. Vengono rivisti alcuni dei risultati già pubblicati da M. Barnabei, F. Bonetti e R. Pirastu e ripresi da M. Silimbani nella sua Tesi di Dottorato: ci si concentra sulla dimensione 2 in cui può essere definito un etichettamento doppio, che si può utilizzare per avere un algoritmo poco costoso atto a sapere se un insieme parzialmente ordinato ha dimensione 2 : esso pone le basi per una corrispondenza biunivoca tra un insieme parzialmente ordinato di cardinalità n dotato di un etichettamento doppio e l'insieme delle permutazioni su n elementi. Infine viene spiegato un altro modo per scoprire se un insieme parzialmente ordinato P ha dimensione al massimo 2 servendosi del solo diagramma di Hasse: ciò succede se e solo se il grafo di inconfrontabilità di P ammette un orientamento transitivo.

Grafi aleatori - il modello di Erdos-Rényi

Dopo aver dato una definizione formale per il modello di Erdos-Rényi, si dimostra che in un grafo ER il grado dei nodi (misura della connessione) risulta essere una variabile aleatoria con distribuzione binomiale, mentre il clustering (misura della densità di archi a livello locale) tende a zero. Successivamente si determinano le funzioni soglia per alcune proprietà monotone particolarmente significative, consentendo così di descrivere diverse configurazioni possibili per un grafo ER al variare dei suoi parametri. Infine, si mostra come si possano utilizzare i grafi ER per modellizzare la diffusione di una malattia infettiva all’interno di una popolazione numerosa.

Procesamiento y almacenamiento distribuido de imágenes basados en grafos: Aplicación para recuperación de información en imágenes muy grandes

El almacenamiento y tratamiento de señales digitales es un campo muy importante de la informática. Dichas señales contienen información valiosa que ha de ser extrada y transformada para poder ser utilizada. En la presente tesis doctoral se han creado métodos para almacenar, procesar y recuperar información de las regiones contenidas en una imagen, en especial en imágenes de gran tamaño. Como base del trabajo se ha diseñado una estructura de datos de tipo grafo para poder almacenar todas las regiones contenidas en una imagen. En esta estructura de datos se pueden guardar tanto los descriptores de bajo nivel de las regiones como las relaciones estructurales entre las distintas regiones de la imagen. En los sistemas de almacenamiento de imágenes es una práctica habitual distribuir las imágenes para mejorar el rendimiento. Más allá de este tipo de distribución, una característica distintiva y novedosa de la estructura de datos creada en la presente investigación es que puede funcionar de forma distribuida de manera que una imagen grande puede ser dividida en varias subimagenes, y dichas sub-imágenes pueden ser almacenadas de forma separada en varios servidores. También se han adaptado algunos métodos y algoritmos pertenecientes a la Morfología Matemática para trabajar directamente sobre la estructura de datos distribuida. De esta manera, se pueden procesar todas las sub-imágenes de una misma imagen sin necesidad de reconstruir la imagen inicial. Finalmente, haciendo uso de la estructura de datos y de los métodos desarrollados se ha creado un prototipo de sistema multi-agente capaz de almacenar y procesar imágenes grandes. Este prototipo permite realizar consultas para recuperar información perteneciente a regiones de una imagen almacenada en el sistema sin necesidad de volver a ser procesada. En la experimentación realizada, resumida en los resultados presentados, se muestra que la división y distribución de una imagen en varias sub-imágenes reduce los tiempos de almacenamiento, procesamiento y recuperación de la información.

Probabilistic mapping with mobile robots in structured environments

La mayor parte de los entornos diseñados por el hombre presentan características geométricas específicas. En ellos es frecuente encontrar formas poligonales, rectangulares, circulares . . . con una serie de relaciones típicas entre distintos elementos del entorno. Introducir este tipo de conocimiento en el proceso de construcción de mapas de un robot móvil puede mejorar notablemente la calidad y la precisión de los mapas resultantes. También puede hacerlos más útiles de cara a un razonamiento de más alto nivel. Cuando la construcción de mapas se formula en un marco probabilístico Bayesiano, una especificación completa del problema requiere considerar cierta información a priori sobre el tipo de entorno. El conocimiento previo puede aplicarse de varias maneras, en esta tesis se presentan dos marcos diferentes: uno basado en el uso de primitivas geométricas y otro que emplea un método de representación cercano al espacio de las medidas brutas. Un enfoque basado en características geométricas supone implícitamente imponer un cierto modelo a priori para el entorno. En este sentido, el desarrollo de una solución al problema SLAM mediante la optimización de un grafo de características geométricas constituye un primer paso hacia nuevos métodos de construcción de mapas en entornos estructurados. En el primero de los dos marcos propuestos, el sistema deduce la información a priori a aplicar en cada caso en base a una extensa colección de posibles modelos geométricos genéricos, siguiendo un método de Maximización de la Esperanza para hallar la estructura y el mapa más probables. La representación de la estructura del entorno se basa en un enfoque jerárquico, con diferentes niveles de abstracción para los distintos elementos geométricos que puedan describirlo. Se llevaron a cabo diversos experimentos para mostrar la versatilidad y el buen funcionamiento del método propuesto. En el segundo marco, el usuario puede definir diferentes modelos de estructura para el entorno mediante grupos de restricciones y energías locales entre puntos vecinos de un conjunto de datos del mismo. El grupo de restricciones que se aplica a cada grupo de puntos depende de la topología, que es inferida por el propio sistema. De este modo, se pueden incorporar nuevos modelos genéricos de estructura para el entorno con gran flexibilidad y facilidad. Se realizaron distintos experimentos para demostrar la flexibilidad y los buenos resultados del enfoque propuesto. Abstract Most human designed environments present specific geometrical characteristics. In them, it is easy to find polygonal, rectangular and circular shapes, with a series of typical relations between different elements of the environment. Introducing this kind of knowledge in the mapping process of mobile robots can notably improve the quality and accuracy of the resulting maps. It can also make them more suitable for higher level reasoning applications. When mapping is formulated in a Bayesian probabilistic framework, a complete specification of the problem requires considering a prior for the environment. The prior over the structure of the environment can be applied in several ways; this dissertation presents two different frameworks, one using a feature based approach and another one employing a dense representation close to the measurements space. A feature based approach implicitly imposes a prior for the environment. In this sense, feature based graph SLAM was a first step towards a new mapping solution for structured scenarios. In the first framework, the prior is inferred by the system from a wide collection of feature based priors, following an Expectation-Maximization approach to obtain the most probable structure and the most probable map. The representation of the structure of the environment is based on a hierarchical model with different levels of abstraction for the geometrical elements describing it. Various experiments were conducted to show the versatility and the good performance of the proposed method. In the second framework, different priors can be defined by the user as sets of local constraints and energies for consecutive points in a range scan from a given environment. The set of constraints applied to each group of points depends on the topology, which is inferred by the system. This way, flexible and generic priors can be incorporated very easily. Several tests were carried out to demonstrate the flexibility and the good results of the proposed approach.

Metodología para la generación automática de entornos virtuales en simuladores de conducción terrestre

Está Tesis refleja los trabajos de investigación que tienen como resultado el desarrollo de una metodología cuyo objetivo es la automatización optimizada en la generación de grandes entornos virtuales destinados a simulaciones de conducción terrestre guiada, es decir, sobre trayectorias predefinidas, bajo PC. En ella se aborda el ciclo completo de generación de un entorno virtual, aportando soluciones optimizadas en cada una de las fases. Para definir estas soluciones, se ha llevado a cabo un estudio en profundidad de las características y requisitos exigidos a este tipo de representaciones virtuales así como de las posibles vías resolutivas, concluyéndose con el establecimiento de tres fases constructivas. La primera fase es la del análisis perceptivo visual. La presente Tesis, tras sintetizar las características que definen a este tipo de entornos así como sus condiciones perceptivas, propone una metodología constructiva que saca el máximo partido de las mismas de una manera hasta ahora no considerada: la creación del entorno mediante el ensamblaje y repetición (instanciación) de un número finito de patrones repetitivos o módulos. Son múltiples las ventajas aportadas por este sistema modular de instanciación: disminución de las labores de modelado, reducción drástica de la memoria de almacenamiento requerida y de los tiempos de carga, facilitación de las tareas de creación y edición de los escenarios. La segunda fase es la generación geométrica y topológica del entorno. El elevado volumen y heterogeneidad de la información a manejar hace necesario el desarrollo de métodos que automaticen el procesamiento de la misma. La presente Tesis desarrolla un sistema consistente en varios criterios de organización, corrección y almacenamiento de la información de partida. Dicho sistema permite por un lado la construcción fácilmente escalable y editable de entornos que cumplan las normativas circulatorias vigentes y por otro lado garantiza un óptimo flujo de la información entre los diversos subsistemas integrantes de la simulación. Flujo que ha sido plasmado en la elaboración de diversos protocolos de comunicación. La tercera fase es la del posicionamiento 3D de la base de datos visual, su jerarquización y optimización escénica. En esta fase, la presente Tesis ha desarrollado una serie de Algoritmos de Posicionamiento modular que garantizan el correcto acoplamiento de los módulos a lo largo de una serie de líneas directrices. Dichas líneas son creadas a partir de la definición de las trayectorias circulatorias, lo que ha permitido a su vez, la definición por parte de esta Tesis de un sistema de niveles de detalle discretos pseudo-variantes con el punto de vista, que permite optimizar la carga geométrica del escenario, mediante la definición en tiempo de precarga de los posibles niveles de detalle de cada módulo en función de su distancia transversal a la trayectoria. Por otro lado, con el fin de potenciar las ventajas de este sistema de instanciación esta Tesis propone el empleo de una serie de shaders que deforman los módulos en tiempo real, lo que permite disminuir el número de módulos necesarios en tiempo de precarga y aumenta la versatilidad constructiva y realismo de los escenarios. Finalmente, esta Tesis organiza todo el escenario en un grafo de la escena (scene graph) que busca minimizar el recorrido del mismo con el fin de maximizar las velocidades de refresco y facilitar las labores de edición de los escenarios. En este punto, la construcción modular del entorno es fundamental para alcanzar dichos objetivos. Todos los planteamientos teóricos expuestos en esta Tesis se han materializado en las correspondientes aplicaciones informáticas que se han validado como herramientas de desarrollo en la creación de grandes entornos virtuales de simuladores actualmente en funcionamiento, como los de Metro de Madrid de las series 7000, 8000, 3000, 9000 y Citadis y en otros experimentales donde también se han implementado los criterios y resultados perceptivos que optimizan estos simuladores.