Large-scale networks are becoming more prevalent, with applications in healthcare systems, financial networks, social networks, and traffic systems. The detection of normal and abnormal behaviors (signals) in these systems presents a challenging problem. State-of-the-art approaches such as principal component analysis and graph signal processing address this problem using signal projections onto a space determined by an eigendecomposition or singular value decomposition. When a graph is directed, however, applying methods based on the graph Laplacian or singular value decomposition causes information from unidirectional edges to be lost. Here we present a novel formulation and graph signal processing framework that addresses this issue and that is well suited for application to extremely large, directed, sparse networks. In this thesis, we develop and demonstrate a graph Fourier transform for which the spectral components are the Jordan subspaces of the adjacency matrix. In addition to admitting a generalized Parseval’s identity, this transform yields graph equivalence classes that can simplify the computation of the graph Fourier transform over certain networks. Exploration of these equivalence classes provides the intuition for an inexact graph Fourier transform method that dramatically reduces computation time over real-world networks with nontrivial Jordan subspaces. We apply our inexact method to four years of New York City taxi trajectories (61 GB after preprocessing) over the NYC road network (6,400 nodes, 14,000 directed edges). We discuss optimization strategies that reduce the computation time of taxi trajectories from raw data by orders of magnitude: from 3,000 days to less than one day. Our method yields a fine-grained analysis that pinpoints the same locations as the original method while reducing computation time and decreasing energy dispersal among spectral components. This capability to rapidly reduce raw traffic data to meaningful features has important ramifications for city planning and emergency vehicle routing.

Thesis (Ph. D.)--School of Electrical and Computer Engineering, Georgia Institute of Technology, 2004. Directed by Douglas M. Blough. / Includes bibliographical references (leaves 62-63).

Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά: 1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδοχικές κορυφές και ακμές, μια απαίτηση όλων των αλγορίθμων γραφημάτων). 2. Ευκινησία (Agility): ικανότητα να αλλάξει και να ρυθμίσει εξαρχής την εσωτερική της διάταξη με σκοπό να βελτιώσει την τοπικότητα των αναφορών των στοιχείων, σύμφωνα με έναν δεδομένο αλγόριθμο. 3. Δυναμικότητα (Dynamicity): ικανότητα να ενθέσει ή να διαγράψει αποδοτικά κορυφές και ακμές. Όλες οι προηγούμενες γνωστές δομές γραφημάτων δεν υποστήριζαν τουλάχιστον ένα από τα προηγούμενα χαρακτηριστικά ή/και δεν μπορούσαν να εφαρμοστούν σε δυναμικά δίκτυα μεταφορών ευρείας κλίμακας. Σε αυτή τη διπλωματική εργασία, παρουσιάζεται η πρακτικότητα της νέας δομής γραφημάτων εκτελώντας μια εκτενή πειραματική μελέτη για δρομολόγηση συντομότερων διαδρομών σε Ευρωπαϊκά οδικά δίκτυα ευρείας κλίμακας με μερικές δεκάδες εκατομμύρια κορυφές και ακμές. Χρησιμοποιώντας κλασικούς αλγόριθμους εύρεσης συντομότερων διαδρομών, επιτυγχάνονται εύκολα χρόνοι ερωτημάτων από μια αρχική κορυφή σε μια τελική κορυφή της τάξης των milliseconds, ενώ η νέα δομή γραφημάτων μας μπορεί να ενημερωθεί σε μόλις μερικά microseconds μετά από μια ένθεση ή διαγραφή μιας κορυφής ή ακμής. / We present a new graph data structure specifically suited for large scale transportation networks in dynamic scenario. Our graph data structure provides tree unique characteristics, namely compactness, agility and dynamicity. All previous data structures were lacking support in at least one of the aforementioned characteristics. We demonstrate the practicality of the new graph data structure by conducting experiments on large scale European road networks, achieving query times of classical routing algorithms in the order of milliseconds and update times in the order of a few microseconds.

No description available.

No description available.

No description available.

The objective of the research is to study optimal routing policy (ORP) problems and to develop an optimal adaptive routing algorithm practical for large-scale Stochastic Time-Dependent (STD) real-life networks, where a traveler could revise the route choice based upon en route information. The routing problems studied can be viewed as counterparts of shortest path problems in deterministic networks. A routing policy is defined as a decision rule that specifies what node to take next at each decision node based on realized link travel times and the current time. The existing routing policy algorithm is for explorative purpose and can only be applied to hypothetical simplified network. In this research, important changes have been made to make it practical in a large-scale real-life network. Important changes in the new algorithm include piece-wise linear travel time representation, turn-based, label-correcting, criterion of stochastic links, and dynamic blocked links. Complete dependency perfect online information (CDPI) variant is then studied in a real-life network (Pioneer Valley, Massachusetts). Link travel times are modeled as random variables with time-dependent distributions which are obtained by running Dynamic Traffic Assignment (DTA) using data provided by Pioneer Valley Planning Commission (PVPC). A comprehensive explanation of the changes by comparing the two algorithms and an in-depth discussion of the parameters that affects the runtime of the new algorithm is given. Computational tests on the runtime changing with different parameters are then carried out and the summary of its effectiveness are presented. To further and fully understand the applicability and efficiency, this algorithm is then tested in another large-scale network, Stockholm in Sweden, and in small random networks. This research is also a good starting point to investigate strategic route choice models and strategic route choice behavior in a real-life network. The major tasks are to acquire data, generate time-adaptive routing policies, and estimate the runtime of the algorithm by changing the parameters in two large-scale real-life networks, and to test the algorithm in small random networks. The research contributes to the knowledge base of ORP problems in stochastic time-dependent (STD) networks by developing an algorithm practical for large-scale networks that considers complete time-wise and link-wise stochastic dependency.

L'activité neuronale partagée entre les différentes régions cérébrales permet d'estimer les patrons d'activation fonctionnelle à l'échelle de réseaux distribués, même en l'absence de paradigme. Constamment rapportés dans la population saine, les réseaux fonctionnels au repos (RSNs) peuvent être utilisés comme objet d'étude pour comprendre la contribution du développement sensoriel atypique sur la communication globale inter-réseau. À ce jour, peu d'études ont exploré l'organisation cérébrale au repos dans le contexte de la surdité. Pourtant, de multiples évidences soutiennent l'importance des entrées sensorielles en début de vie dans la consolidation de l'architecture fonctionnelle du cerveau. L'étude présentée dans ce mémoire a été développée et conceptualisée pour rendre compte de la relation entre la privation sensorielle et l'activité cérébrale spontanée entre les RSNs. À cette fin, 17 personnes avec une surdité congénitale de degré sévère à profond et 18 personnes entendantes non signeurs ont été recrutées et ont effectué 10 minutes d'enregistrement par imagerie magnétique fonctionnelle (IRMf) à l'état de repos. Les estimations de connectivité fonctionnelle de 17 RSNs extraites par une méthode de parcellisation fonctionnelle du cerveau ont été comparées entre les groupes. Le couplage entre les réseaux d'attention dorsale (DAN) et d'attention ventrale (VAN) était significativement plus élevé chez les participants qui présentent une surdité. Ces deux systèmes sont impliqués dans les tâches attentionnelles descendantes (« top-down ») et ascendantes (« bottom-up »), respectivement. Les résultats démontrent une réorganisation du cerveau au sein des réseaux associatifs et proposent une preuve potentielle des substrats neuronaux qui sous-tendraient les performances attentionnelles supérieures des personnes avec une surdité. / Neural activity shared between different brain regions allows estimation of functional activation patterns at the scale of distributed networks, even in the absence of a paradigm. Consistently reported in the healthy population, resting-state functional networks (RSNs) can be studied to understand the contribution of atypical sensory development on global inter-network communication. To date, few studies have explored brain organization at rest in the context of deafness. Yet, numerous evidence supports the importance of early sensory input in the consolidation of the brain's functional architecture. The study presented in this thesis was developed and conceptualized to report on the relationship between sensory deprivation and spontaneous brain activity between RSNs. To this end, 17 individuals with severe to profound congenital hearing loss and 18 non-signer hearing individuals were recruited and performed 10 minutes of functional magnetic imaging (fMRI) recording at rest. Functional connectivity estimates of 17 RSNs extracted by a functional brain parcellation method were compared between groups. The coupling between dorsal attention (DAN) and ventral attention (VAN) networks was significantly higher in deaf participants. These two systems are involved in topdown and bottom-up attentional tasks, respectively. The results demonstrate brain plasticity within associative networks and offer potential evidence of neural substrates that may underlie superior attentional performances observed in individuals with deafness.

No description available.

Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans plusieurs espaces métriques spécifiques, et, en particulier, ceux générés par certains de ces outils, comme Vivaldi et Sequoia. / During this Ph.D we introduced Bin Covering under Distance Constraint (BCCD in French) and Bin Packing under Distance Constraint (BPCD in French). Those two problems find their applications in the context of large scale networks, like Internet. We studied those problems in general metric spaces, and proved that using resource augmentation is mandatory. Resource augmentation allows to build algorithms working on solutions with less constraints than the optimal solution to which it is compared to. We found interesting approximations algorithms using this relaxation, and proved the necessity of this resource augmentation. However many tools are used to embed large networks we are interested in in specific metric spaces. Thus we studied those problems in different specific metric spaces, in particular those generated by the use of Vivaldi and Sequoia, two of those tools.