La science moderne des graphes est apparue ces dernières années comme un domaine d'intérêt et a apporté des progrès significatifs à notre connaissance des réseaux. Jusqu'à récemment, les algorithmes d'exploration de données existants étaient destinés à des données structurées / relationnelles, alors que de nombreux ensembles de données nécessitent une représentation graphique, comme les réseaux sociaux, les réseaux générés par des données textuelles, les structures protéiques 3D ou encore les composés chimiques. Il est donc crucial de pouvoir extraire des informations pertinantes à partir de ce type de données et, pour ce faire, les méthodes d'extraction et d'analyse des graphiques ont été prouvées essentielles.L'objectif de cette thèse est d'étudier les problèmes dans le domaine de la fouille de graphes axés en particulier sur la conception de nouveaux algorithmes et d'outils liés à la diffusion d'informations et plus spécifiquement sur la façon de localiser des entités influentes dans des réseaux réels. Cette tâche est cruciale dans de nombreuses applications telles que la diffusion de l'information, les contrôles épidémiologiques et le marketing viral.Dans la première partie de la thèse, nous avons étudié les processus de diffusion dans les réseaux sociaux ciblant la recherche de caractéristiques topologiques classant les entités du réseau en fonction de leurs capacités influentes. Nous nous sommes spécifiquement concentrés sur la décomposition K-truss qui est une extension de la décomposition k-core. On a montré que les noeuds qui appartiennent au sous-graphe induit par le maximal K-truss présenteront de meilleurs proprietés de propagation par rapport aux critères de référence. De tels épandeurs ont la capacité non seulement d'influencer une plus grande partie du réseau au cours des premières étapes d'un processus d'étalement, mais aussi de contaminer une plus grande partie des noeuds.Dans la deuxième partie de la thèse, nous nous sommes concentrés sur l'identification d'un groupe de noeuds qui, en agissant ensemble, maximisent le nombre attendu de nœuds influencés à la fin du processus de propagation, formellement appelé Influence Maximization (IM). Le problème IM étant NP-hard, il existe des algorithmes efficaces garantissant l’approximation de ses solutions. Comme ces garanties proposent une approximation gloutonne qui est coûteuse en termes de temps de calcul, nous avons proposé l'algorithme MATI qui réussit à localiser le groupe d'utilisateurs qui maximise l'influence, tout en étant évolutif. L'algorithme profite des chemins possibles créés dans le voisinage de chaque nœud et précalcule l'influence potentielle de chaque nœud permettant ainsi de produire des résultats concurrentiels, comparés à ceux des algorithmes classiques.Finallement, nous étudions le point de vue de la confidentialité quant au partage de ces bons indicateurs d’influence dans un réseau social. Nous nous sommes concentrés sur la conception d'un algorithme efficace, correct, sécurisé et de protection de la vie privée, qui résout le problème du calcul de la métrique k-core qui mesure l'influence de chaque noeud du réseau. Nous avons spécifiquement adopté une approche de décentralisation dans laquelle le réseau social est considéré comme un système Peer-to-peer (P2P). L'algorithme est construit de telle sorte qu'il ne devrait pas être possible pour un nœud de reconstituer partiellement ou entièrement le graphe en utilisant les informations obtiennues lors de son exécution. Notre contribution est un algorithme incrémental qui résout efficacement le problème de maintenance de core en P2P tout en limitant le nombre de messages échangés et les calculs. Nous fournissons également une étude de sécurité et de confidentialité de la solution concernant la désanonymisation des réseaux, nous montrons ainsi la rélation avec les strategies d’attaque précédemment definies tout en discutant les contres-mesures adaptés. / Modern science of graphs has emerged the last few years as a field of interest and has been bringing significant advances to our knowledge about networks. Until recently the existing data mining algorithms were destined for structured/relational data while many datasets exist that require graph representation such as social networks, networks generated by textual data, 3D protein structures and chemical compounds. It has become therefore of crucial importance to be able to extract meaningful information from that kind of data and towards this end graph mining and analysis methods have been proven essential. The goal of this thesis is to study problems in the area of graph mining focusing especially on designing new algorithms and tools related to information spreading and specifically on how to locate influential entities in real-world networks. This task is crucial in many applications such as information diffusion, epidemic control and viral marketing. In the first part of the thesis, we have studied spreading processes in social networks focusing on finding topological characteristics that rank entities in the network based on their influential capabilities. We have specifically focused on the K-truss decomposition which is an extension of the core decomposition of the graph. Extensive experimental analysis showed that the nodes that belong to the maximal K-truss subgraph show a better spreading behavior when compared to baseline criteria. Such spreaders can influence a greater part of the network during the first steps of a spreading process but also the total fraction of the influenced nodes at the end of the epidemic is greater. We have also observed that node members of such dense subgraphs are those achieving the optimal spreading in the network.In the second part of the thesis, we focused on identifying a group of nodes that by acting all together maximize the expected number of influenced nodes at the end of the spreading process, formally called Influence Maximization (IM). The IM problem is actually NP-hard though there exist approximation guarantees for efficient algorithms that can solve the problem while obtaining a solution within the 63% of optimal classes of models. As those guarantees propose a greedy approximation which is computationally expensive especially for large graphs, we proposed the MATI algorithm which succeeds in locating the group of users that maximize the influence while also being scalable. The algorithm takes advantage the possible paths created in each node’s neighborhood to precalculate each node’s potential influence and produces competitive results in quality compared to those of baseline algorithms such as the Greedy, LDAG and SimPath. In the last part of the thesis, we study the privacy point of view of sharing such metrics that are good influential indicators in a social network. We have focused on designing an algorithm that addresses the problem of computing through an efficient, correct, secure, and privacy-preserving algorithm the k-core metric which measures the influence of each node of the network. We have specifically adopted a decentralization approach where the social network is considered as a Peer-to-peer (P2P) system. The algorithm is built based on the constraint that it should not be possible for a node to reconstruct partially or entirely the graph using the information they obtain during its execution. While a distributed algorithm that computes the nodes’ coreness is already proposed, dynamic networks are not taken into account. Our main contribution is an incremental algorithm that efficiently solves the core maintenance problem in P2P while limiting the number of messages exchanged and computations. We provide a security and privacy analysis of the solution regarding network de-anonimization and show how it relates to previously defined attacks models and discuss countermeasures.

The problem of efficient parallelization of 2D Ising spin systems requires realistic algorithmic design and implementation based on an understanding of issues from computer science and statistical physics. In this work, we not only consider fundamental parallel computing issues but also ensure that the major constraints and criteria of 2D Ising spin systems are incorporated into our study. This realism in both parallel computation and statistical physics has rarely been reflected in previous research for this problem. In this thesis,we designed and implemented a variety of parallel algorithms for both sweep spin selection and random spin selection. We analyzed our parallel algorithms on a portable and general parallel machine model, namely the LogP model. We were able to obtain rigorous theoretical run-times on LogP for all the parallel algorithms. Moreover, a guiding equation was derived for choosing data layouts (blocked vs. stripped) for sweep spin selection. In regards to random spin selection, we were able to develop parallel algorithms with efficient communication schemes. We analyzed randomness of our schemes using statistical methods and provided comparisons between the different schemes. Furthermore, algorithms were implemented and performance data gathered and analyzed in order to determine further design issues and validate theoretical analysis. / Master of Science

Le givrage a été identifié comme un danger important dès le début de l'aéronautique.L'accrétion de givre sur les ailes d'avion, due à la présence de gouttelettes surfonduesdans les nuages, cause parmi d'autres conséquences néfastes une dégradation des performancesaérodynamiques pouvant conduire au décrochage. C'est pourquoi les avionneursdéveloppent depuis longtemps des systèmes de protection. Comme les essais en vols ou ensoufflerie sont souvent complexes à mettre en oeuvre et onéreux, la simulation numériqueest devenue un outil efficace et complémentaire pour dimensionner ces systèmes.Cette thèse s'inscrit dans le contexte de la modélisation de l'accrétion de givre, duruissellement et des systèmes de protection thermique. Elle s'articule en sept chapitres.Après avoir présenté les enjeux et contexte, on introduit une approche tricouche permettantde modéliser l'accrétion de givre et le ruissellement de manière instationnaire. Les troischapitres suivants traitent des méthodes de discrétisation de ce modèle ainsi que de soncouplage avec un modèle du système de protection thermique. Les deux derniers sontconsacrés à la présentation des résultats de simulations numériques montrant l'intérêt del'approche développée et la faisabilité de simulations complètes de phénomènes d'accrétionde givre sur une paroi chauffée ou non. / Icing has been identified as a serious issue since the start of aeronautics. Ice accretion onwings, due to supercooled droplets inside clouds, leads to severe degradation of aerodynamicperformances, among other undesirable effects. Therefore, aircraft manufacturers have sincea long time developed ice protection systems. As flight tests or wind tunnel experimentsare often complicated to implement and expensive, numerical modeling is an effective andcomplementary tool to design those systems. This thesis concerns the modeling of ice accretion, runback and thermal ice protectionsystems. It consists of seven chapters. The first one is dedicated to the presentation of theconcerns and the context. Then a three layer approach allowing to model in an unsteadyway ice accretion and runback is presented. Following three chapters deal with this modeldiscretization as well as a method to couple it with a thermal ice protection system model.Two last chapters are dedicated to numerical simulations showing the sake of the approachand the feasibility of a whole simulation of ice accretion on a heated or unheated surface.

A degree-constrained subgraph construction (DCS) problem aims to find an optimal spanning subgraph (w.r.t an objective function) subject to certain degree constraints on the vertices. DCS generalizes many combinatorial optimization problems such as Matchings and Edge Covers and has many practical and real-world applications. This thesis focuses on DCS problems where there are only upper and lower bounds on the degrees, known as b-matching and b-edge cover problems, respectively. We explore linear and submodular functions as the objective functions of the subgraph construction.<br><br>The contributions of this thesis involve both the design of new approximation algorithms for these DCS problems, and also their applications to real-world contexts.<br>We designed, developed, and implemented several approximation algorithms for DCS problems. Although some of these problems can be solved exactly in polynomial time, often these algorithms are expensive, tedious to implement, and have little to no concurrency. On the contrary, many of the approximation algorithms developed here run in nearly linear time, are simple to implement, and are concurrent. Using the local dominance framework, we developed the first parallel algorithm submodular b-matching. For weighted b-edge cover, we improved the classic Greedy algorithm using the lazy evaluation technique. We also propose and analyze several approximation algorithms using the primal-dual linear programming framework and reductions to matching. We evaluate the practical performance of these algorithms through extensive experimental results.<br><br>The second contribution of the thesis is to utilize the novel algorithms in real-world applications. We employ submodular b-matching to generate a balanced task assignment for processors to build Fock matrices in the NWChemEx quantum chemistry software. Our load-balanced assignment results in a four-fold speedup per iteration of the Fock matrix computation and scales to 14,000 cores of the Summit supercomputer at Oak Ridge National Laboratory. Using approximate b-edge cover, we propose the first shared-memory and distributed-memory parallel algorithms for the adaptive anonymity problem. Minimum weighted b-edge cover and maximum weight b-matching are shown to be applicable to constructing graphs from datasets for machine learning tasks. We provide a mathematical optimization framework connecting the graph construction problem to the DCS problem.

No description available.

[pt] De grande importância para pesquisa científica, o software científico se mostra, por vezes, desafiador no que se refere ao design de interfaces com o usuário. Por outro lado, a gamificação se oferece como potencial solução em questões de experiência com o usuário e interatividade. Nesta tese, desenvolvemos um método para a gamificação de software científico voltado para processos de design colaborativo, orientado por um modelo baseado em jogo, informado por aspectos de uso e desenvolvimento deste tipo de software e, também, por aspectos similares ao jogo na prática científica. / [en] Vastly important to scientific research, scientific software is often challenging regarding the design of its user interfaces. On the other hand, gamification is seen as a potential solution in matters of user experience and interactivity. In this thesis, we develop a method for the gamification of scientific software aimed at collaborative design processes, guided by a game-based model, informed by aspects of use and development of that type of software and, also by game-like aspects of scientific practice.

In this report, we study how finite differences can be used to simulate acoustic wave propagation originating from a point source in the ocean using the Helmholtz equation. How to model sediment layers and the vast size of the ocean is studied in particular. The finite differences are implemented with summation by parts operators with boundary conditions enforced with simultaneous approximation terms and projection. The numerical solver is combined with the WaveHoltz method to improve the performance. Sediment layers are handled with interface conditions and the domain is artificially expanded using absorbing layers. The absorbing layer is implemented with an alternative approach to the super-grid method where the domain expansion is accomplished by altering the wave speed rather than with coordinate transformations. To isolate these issues, other parameters such as variations in the ocean floor are neglected. With this simplification, cylindrical coordinates are used and the angular variation is assumed to be zero. This reduces the problem to a quasi-three-dimensional system. We study how the parameters of the alternative absorbing layer approach affect its quality. The numerical solver is verified on several test cases and appears to work according to theory. Finally, a semi-realistic simulation is carried out and the solution seems correct in this setting.

zweimal im Jahr erscheinende Zeitschrift über aktuelle Themen der TU Chemnitz, ergänzt von Sonderheft(en)

zweimal im Jahr erscheinende Zeitschrift über aktuelle Themen der TU Chemnitz, ergänzt von Sonderheft(en)