Thèses sur le sujet « Small world graph »

Les possibilités d'intégration sont de plus en plus importantes et le nombre de transistors disponibles sur un composant n'est plus aussi critique que dans le passé. Cependant les structures de traitement du type monoprocesseur ne bénéficient plus de cette augmentation de ressources et on voit apparaître des composants du type MP Soc (multiprocessors on Chip) qui intègre plusieurs coeurs de processeur sur une même puce. Le problème consiste donc à faire passer à l'échelle des architectures systèmes du type MIMD (Multiple Instruction stream Multiple Data stream). Si on considère des coeurs de processeur complexe alors le problème reste actuellement assez maîtrisable car leur nombre reste limité (2 voit 4 processeurs). Par contre l'utilisation de noeuds de traitement de plus petite taille autorise l'intégration de dizaines voire de centaines de processeurs sur un même circuit. Les besoins en puissance de calcul ne se satisfont plus des limites rencontrées sur des processeurs complexes. La généralisation des composants du type MPSoC qui intègrent un nombre toujours plus important de processeurs sur une puce. Cependant, interconnecter un grand nombre de processeurs sur une puce est un délicat. Essentiellement, les structures adaptées aux contraintes de la puce sont trop peu générales, et les schémas de l’interconnexion plus globale engendrent des coûts de fabrication trop élevés. Ce problème se décompose en deux sous problèmes intimement liés qui sont la recherche d'une topologie permettant d'atteindre un niveau de connectivité acceptable et le coût matériel de sa réalisation. C'est dans ce dernier cas qui s'inscrit le contexte scientifique de ce mémoire. Les concepteurs se basent sur des différentes architectures pour réaliser des puces. Les architectures à mémoire partagée où il y a une saturation d’accès mémoire avec un grand nombre de PEs (Processeurs Élémentaires) comme par exemple TILERA Corporation. Les architectures à mémoire distribué où il se manifeste le problème des programmes fortement communicants. Ce type d'architecture est structuré autour d'un Noc (Network-on-Chip). De nombreuses études ont déjà été réalisées sur la problématique des architectures et de leurs réalisations avec pour motivations de trouver une manière élégante de supporter des Pes qui est de plus en plus nombreux et rapide en limitant le nombre de fils et pour obtenir des réseaux réguliers où le coût et le temps de développement du layout sont très court. Pour cette raison, nous sommes à la recherche d'une nouvelle plate-forme homogène avec des multicoeurs réguliers et massivement parallèles. C'est dans ce dernier cas qui s'inscrit le contexte industriel de ce mémoire de thèse. Pour des raisons techniques, il faut rendre les circuits homogènes, réguliers et denses parce que le coût et le temps de développement du layout d'un circuit non régulier sont très longs. Pour cette raison, il faut s'appuyer sur des architectures massivement parallèles. Les processeurs doivent communiquer entre eux, ils sont donc connectés via un réseau qui implémente une topologie. Pour une topologie donnée, on dispose de métriques grossières telles que le nombre de noeuds (le nombre de sommets dans un graphe donné), le degré (le nombre de liens entrants et sortants pour chaque sommet dans ce graphe donné) et le diamètre (la distance maximale entre deux noeuds ou sommets quelconques dans le graphe). Dans ce cas, comme on veut un circuit régulier, où les CPUs sont organisés en grille 2D pour les techniques actuels et éventuellement 3D pour les futurs techniques alors il faut obtenir le coût silicium pour mapper la topologie choisie sur cette grille. Le passage de la topologie (mapping) à la réalisation sera qualifié de placement-routage" physique (le terme "placement" veut dire de placer les sommets de ce graphe donné sur une grille 2D et le terme "routage" veut dire de faire communiquer ces sommets entre eux)
Graphs with a minimum diameter have applications in the design of building-block switching systems, communication networks, and distributed computer systems. Several methods of constructing directed graphs with a small diameter are proposed. First, the dissertation presents as background several (delta, D) graphs including the Hypercube and de Bruijn. It shows the major disadvantages when implementing these topologies in practice for large scale. To achieve our goal, we propose a regular graph called Small World Heuristic (SWH) suitable for large parallel computers. This graph has a maximum degree ! and a small diameter D, while maintaining an acceptable level of connectivity. We show that this heuristic can connect on short distance thousands of nodes as little as 4 links per node. ̕Finally, we present a new integrated placement and routing algorithm to implement this heuristic on 2D VLSI

It has been observed that real-world random networks like the WWW, Internet, social networks, citation networks, etc., organize themselves into closely-knit groups that are locally dense and globally sparse. These closely-knit groups are termed communities. Nodes within a community are similar in some aspect. For example in a WWW network, communities might consist of web pages that share similar contents. Mining these communities facilitates better understanding of their evolution and topology, and is of great theoretical and commercial significance. Community related research has focused on two main problems: community discovery and community identification. Community discovery is the problem of extracting all the communities in a given network, whereas community identification is the problem of identifying the community, to which, a given set of nodes belong. We make a comparative study of various existing community-discovery algorithms. We then propose a new algorithm based on bibliographic metrics, which addresses the drawbacks in existing approaches. Bibliographic metrics are used to study similarities between publications in a citation network. Our algorithm classifies nodes in the network based on the similarity of their neighborhoods. One of the drawbacks of the current community-discovery algorithms is their computational complexity. These algorithms do not scale up to the enormous size of the real-world networks. We propose a hash-table-based technique that helps us compute the bibliometric similarity between nodes in O(m ?) time. Here m is the number of edges in the graph and ?, the largest degree. Next, we investigate different centrality metrics. Centrality metrics are used to portray the importance of a node in the network. We propose an algorithm that utilizes centrality metrics of the nodes to compute the importance of the edges in the network. Removal of the edges in ascending order of their importance breaks the network into components, each of which represent a community. We compare the performance of the algorithm on synthetic networks with a known community structure using several centrality metrics. Performance was measured as the percentage of nodes that were correctly classified. As an illustration, we model the ucf.edu domain as a web graph and analyze the changes in its properties like densification power law, edge density, degree distribution, diameter, etc., over a five-year period. Our results show super-linear growth in the number of edges with time. We observe (and explain) that despite the increase in average degree of the nodes, the edge density decreases with time.
Ph.D.
School of Electrical Engineering and Computer Science
Engineering and Computer Science
Computer Science

The main subject of the thesis is concerned with interacting particle systems, which are classes of spatio-temporal stochastic processes describing the evolution of particles in interaction with each other. The particles move on a finite or infinite discrete space and on each element of this space the state of the configuration is integer valued. Configurations of particles evolve in continuous time according to a Markov process. Here the space is either the infinite deterministic d-dimensional lattice or a random graph given by the finite d-dimensional torus with random matchings. In Part I we investigate the stochastic order in a particle system with multiple births, deaths and jumps on the d-dimensional lattice: stochastic order is a key tool to understand the ergodic properties of a system. We give applications on biological models of spread of epidemics and metapopulation dynamics systems. In Part II we analyse the coalescing random walk in a class of finite random graphs modeling social networks, the small world graphs. We derive the law of the meeting time of two random walks on small world graphs and we use this result to understand the role of random connections in meeting time of random walks and to investigate the behavior of coalescing random walks.

Made available in DSpace on 2015-03-03T15:15:30Z (GMT). No. of bitstreams: 1 GerdivaneFD_DISSERT.pdf: 2461999 bytes, checksum: afd653d46e87e83d8b0144e8086a3d19 (MD5) Previous issue date: 2014-02-21
Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior
In this work a study of social networks based on analysis of family names is presented. A basic approach to the mathematical formalism of graphs is developed and then main theoretical models for complex networks are presented aiming to support the analysis of surnames networks models. These, in turn, are worked so as to be drawn leading quantities, such as aggregation coefficient, minimum average path length and connectivity distribution. Based on these quantities, it can be stated that surnames networks are an example of complex network, showing important features such as preferential attachment and small-world character
Neste trabalho ? apresentado um estudo das redes sociais baseado na an?lise dos nomes de fam?lias. Faz-se uma abordagem b?sica do formalismo matem?tico dos grafos e em seguida apresenta-se os principais modelos te?ricos para as Redes Complexas com o objetivo de fundamentar a an?lise das redes dos sobrenomes. Estas, por sua vez, s?o trabalhadas de modo a serem extra?das as principais grandezas, tais como coe ciente de agrega??o, menor caminho m?dio e distribui??o de conectividades. Com base nestas grandezas, pode-se a rmar que as redes de sobrenomes s?o um exemplo de rede complexa, exibindo caracter?sticas importantes como liga??o preferencial e o car?ter de mundo pequeno.

The aim of the thesis is to define the dependency of the classification of patients affected by neurodegenerative diseases on the choice of the parcellation atlas. Part of this thesis is the application of the functional connectivity analysis and the calculation of graph metrics according to the method published by Olaf Sporns and Mikail Rubinov [1] on fMRI data measured at CEITEC MU. The application is preceded by the theoretical research of parcellation atlases for brain segmentation from fMRI frames and the research of mathematical methods for classification as well as classifiers of neurodegenerative diseases. The first chapters of the thesis brings a theoretical basis of knowledge from the field of magnetic and functional magnetic resonance imaging. The physical principles of the method, the conditions and the course of acquisition of image data are defined. The third chapter summarizes the graph metrics used in the diploma thesis for analyzing and classifying graphs. The paper presents a brief overview of the brain segmentation methods, with the focuse on the atlas-based segmentation. After a theoretical research of functional connectivity methods and mathematical classification methods, the findings were used for segmentation, calculation of graph metrics and for classification of fMRI images obtained from 96 subjects into the one of two classes using Binary classifications by support vector machines and linear discriminatory analysis. The data classified in this study was measured on patiens with Parkinson’s disease (PD), Alzheimer’s disease (AD), Mild cognitive impairment (MCI), a combination of PD and MCI and subjects belonging to the control group of healthy individuals. For pre-processing and analysis, the MATLAB environment, the SPM12 toolbox and The Brain Connectivity Toolbox were used.

Real-world large-scale complex networks such as the Internet, social networks and biological networks have increasingly attracted the interest of researchers from many areas. Accurate modelling of the statistical regularities of these large-scale networks is critical to understand their global evolving structures and local dynamical patterns. Traditionally, the Erdos and Renyi random graph model has helped the investigation of various homogeneous networks. During the past decade, a special computational methodology has emerged to study complex networks, the outcome of which is identified by two models: the Watts and Strogatz small-world model and the Barabasi-Albert scale-free model. At the core of the complex network modelling process is the extraction of characteristics of real-world networks. I have developed computer simulation algorithms for study of the properties of current theoretical models as well as for the measurement of two real-world complex networks, which lead to the isolation of three complex network modelling essentials. The main contribution of the thesis is the introduction and study of a new General Two-Stage growth model (GTS Model), which aims to describe and analyze many common-featured real-world complex networks. The tools we use to create the model and later perform many measurements on it consist of computer simulations, numerical analysis and mathematical derivations. In particular, two major cases of this GTS model have been studied. One is named the U-P model, which employs a new functional form of the network growth rule: a linear combination of preferential attachment and uniform attachment. The degree distribution of the model is first studied by computer simulation, while the exact solution is also obtained analytically. Two other important properties of complex networks: the characteristic path length and the clustering coefficient are also extensively investigated, obtaining either analytically derived solutions or numerical results by computer simulations. Furthermore, I demonstrate that the hub-hub interaction behaves in effect as the link between a network's topology and resilience property. The other is called the Hybrid model, which incorporates two stages of growth and studies the transition behaviour between the Erdos and Renyi random graph model and the Barabasi-Albert scale-free model. The Hybrid model is measured by extensive numerical simulations focusing on its degree distribution, characteristic path length and clustering coefficient. Although either of the two cases serves as a new approach to modelling real-world large-scale complex networks, perhaps more importantly, the general two-stage model provides a new theoretical framework for complex network modelling, which can be extended in many ways besides the two studied in this thesis.

Modelos e teorias científicas surgem da necessidade do homem entender melhor o funcionamento do mundo em que vive. Constantemente, novos modelos e técnicas são criados com esse objetivo. Uma dessas teorias recentemente desenvolvida é a da Criticalidade Auto-Organizada. No Capítulo 2 desta tese, apresentamos uma breve introdução a Criticalidade Auto-Organizada. Tendo a criticalidade auto-organizada como pano de fundo, no Capítulo 3, estudamos a dinâmica Bak-Sneppen (e diversas variantes) e a comparamos com alguns algoritmos de otimização. Apresentamos no Capítulo 4, uma revisão histórica e conceitual das redes complexas. Revisamos alguns importantes modelos tais como: Erdös-Rényi, Watts-Strogatz, de configuração e Barabási-Albert. No Capítulo 5, estudamos o modelo Barabási-Albert não-linear. Para este modelo, obtivemos uma expressão analítica para a distribuição de conectividades P(k), válida para amplo espectro do espaço de parâmetros. Propusemos também uma forma analítica para o coeficiente de agrupamento, que foi corroborada por nossas simulações numéricas. Verificamos que a rede Barabási-Albert não-linear pode ser assortativa ou desassortativa e que, somente no caso da rede Barabási-Albert linear, ela é não assortativa. No Capítulo 6, utilizando dados coletados do CD-ROM da revista Placar, construímos uma rede bastante peculiar -- a rede do futebol brasileiro. Primeiramente analisamos a rede bipartida formada por jogadores e clubes. Verificamos que a probabilidade de que um jogador tenha participado de M partidas decai exponencialmente com M, ao passo que a probabilidade de que um jogador tenha marcado G gols segue uma lei de potência. A partir da rede bipartida, construímos a rede unipartida de jogadores, que batizamos de rede de jogadores do futebol brasileiro. Nessa rede, determinamos várias grandezas: o comprimento médio do menor caminho e os coeficientes de agrupamento e de assortatividade. A rede de jogadores de futebol brasileiro nos permitiu analisar a evolução temporal dessas grandezas, uma oportunidade rara em se tratando de redes reais.
Models and scientific theories arise from the necessity of the human being to better understand how the world works. Driven by this purpose new models and techniques have been created. For instance, one of these theories recently developed is the Self-Organized Criticality, which is shortly introduced in the Chapter 2 of this thesis. In the framework of the Self-Organized Criticality theory, we investigate the standard Bak-Sneppen dynamics as well some variants of it and compare them with optimization algorithms (Chapter 3). We present a historical and conceptual review of complex networks in the Chapter 4. Some important models like: Erdös-Rényi, Watts-Strogatz, configuration model and Barabási-Albert are revised. In the Chapter 5, we analyze the nonlinear Barabási-Albert model. For this model, we got an analytical expression for the connectivity distribution P(k), which is valid for a wide range of the space parameters. We also proposed an exact analytical expression for the clustering coefficient which corroborates very well with our numerical simulations. The nonlinear Barabási-Albert network can be assortative or disassortative and only in the particular case of the linear Barabási-Albert model, the network is no assortative. In the Chapter 6, we used collected data from a CD-ROM released by the magazine Placar and constructed a very peculiar network -- the Brazilian soccer network. First, we analyzed the bipartite network formed by players and clubs. We find out that the probability of a footballer has played M matches decays exponentially with M, whereas the probability of a footballer to score G gols follows a power-law. From the bipartite network, we built the unipartite Brazilian soccer players network. For this network, we determined several important quantities: the average shortest path length, the clustering coefficient and the assortative coefficient. We were also able to analise the time evolution of these quantities -- which represents a very rare opportunity in the study of real networks.

Ces dix dernières années, l'étude des réseaux petits-mondes a montré une grande stabilité de certaines métriques issues de la théorie des graphes formels. Elle porte sur l'analyse de réseaux traduisant des activités de l'homme : réseaux d'échanges téléphoniques, de connexions aériennes, de navigation sur le Web, de structure des lexiques linguistiques, mais également de réseaux de diffusion des épidémies ou de réseaux de relations sociales. En revanche, peu d'études ont porté sur l'analyse de la dynamique de ces graphes et leur évolution au cours du temps. C'est cette approche que nous développons dans ce document. Nous nous intéressons ici à des graphes obtenus à partir de comptes rendus professionnels de travailleurs sociaux. Ces graphes modélisent les cooccurrences des mots au sein des phrases. Notre analyse porte sur un lexique professionnel et sur l'évolution de son usage sur une période de près de 40 ans. Après avoir constitué notre matériel à partir des textes écrits (environ 1500 pages dactylographiées), ce corpus d'étude a été quantifié, vérifié, homogénéisé et traité orthographiquement sur un mode semi-automatique. Puis ce corpus normalisé a donné lieu à la constitution d'un graphe global pour la période complète, et d'une quarantaine de graphes pour chacune des sous-périodes étudiées. C'est sur ceux-ci que porte l'analyse de la dynamique d'évolution de graphe issu d'un lexique professionnel. Au final, notre travail permet de pointer le paradoxe existant, entre d'une part la contrainte d'écriture liée à un objet qui ne change que très peu dans la nature de sa mission (le travail d'un éducateur de rue) et d'autre part la permissivité du langage oral qui ne cesse d'évoluer (le langage professionnel). Par ailleurs notre approche propose une certaine automatisation pour dégager l'essentiel d'un "dire professionnel" dans un corpus de comptes rendus.

碩士
國立交通大學
資訊科學與工程研究所
99
Along with the development of internet, many novel network services appear. Rise of the social network service changes our traditional social structure, and people can easily communicate with their old friends or even make new friends on it. The famous “Small World Theory” describes that there are only six people between any two people in the world, but researchers still can’t prove this theory completely until now. Nowadays, our world is getting smaller because of these social networks, and we have some new ideas about the “Small World Theory”. We carry out the experiment on Facebook to collect lots of users’ social data, and then use graph database to conduct further analysis. We want to re-verify the “Small World Theory” and also extend this theory. We focus on the degree of separation and control the size of the dataset. The experimental result shows our dataset is “Four Degrees of Separation”, and this conclusion can be extended to whole world by further experiment.

碩士
國立交通大學
工業工程與管理系所
103
Analysis of large and complex network graphs has been an important issue. Small-world network is a special type of those complex network graphs. The structure of this type of graphs cannot be effectively recognized by conventional graph drawing algorithms, such that it is difficult to identify and analyze the network. To solve this problem, this paper proposes a visualization approach, which utilizes centrality to remove some links between nodes, then uses a plane graph drawing method to lay out the reduced subgraph without any edge crossing, then applies a force-directed graph drawing method based on node-edge repulsion to improve the layout, finally adds back the remaining links. On experimental analysis, our results can not only analyze the same information with previous methods, but successfully gain more useful information. It lets us have a better understanding for the relationship between nodes and search out some messages that were never found before. Application of this approach to semiconductor wafer fabrication example is demonstrated.

In this dissertation we set out to study a simplified model of activation flow in artificial neural networks with geometrical embedding. The model provides a mathematical description of abstract neural activation transfer in terms, which bear resemblances to multi-value Boltzmann-like evolution. The activation-preserving constraint mimics a critical regime of the dynamics and, along with accounting for geometrical location of the neurons, makes the system more feasible for modelling of real-world networks. We focus on scale invariance or scale-freeness and small-world phenomena in the said networks. Our results clearly confirm presence of both features at the functional level of the activity-flow graph. We show that the degree distribution preserves a power-law shape with the exponent value approximately equal to -2. In addition, we present our results concerning characteristic path length in the said graphs, which grows roughly logarithmically with the size of the network, while the clustering coefficient turns out to be relatively high. Taken together, the clustering and path length ratios are surprisingly high, and thus confirm large both local and global efficiency of the network. Finally, we compare the properties of activation-flow model to those reported in neurobiological analyses of brain networks recorded with functional magnetic resonance imagining (fMRI). There is a strong agreement between the shape and exponent value of degree distribution also the clustering and characteristic path lengths are comparable in both the model and medical data.
Celem niniejszej rozprawy jest analiza uproszczonego modelu przepływu aktywności w sztucznych sieciach neuronowych zanurzonych w przestrzeni geometrycznej. Przedstawiony model dostarcza matematycznego opisu transferu aktywności w terminach zbliżonych do wielowartościowych maszyn Boltzmanna. Wymóg zachowania stałej sumarycznej aktywności odzwierciedla krytyczność dynamiki i wraz z uwzględnieniem wpływu lokalizacji geometrycznej neuronów sprawia, że system jest bardziej adekwatny do modelowania rzeczywistych sieci. Badania koncentrują się na bezskalowości oraz fenomenie małego świata w wyżej wymienionych sieciach. Uzyskane rezultaty potwierdzają obecność obu własności w omawianych grafach. Pokażemy, że rozkład stopni wejściowych wierzchołków zachowuje się jak funkcja potęgowa z wykładnikiem równym -2. Ponadto prezentujemy wyniki dotyczące charakterystycznej długości ścieżki, który rośnie logarytmicznie wraz z wielkością systemu, podczas gdy współczynnik klasteryzacji okazuje się dość duży. W konsekwencji stosunek klasteryzacji do długości ścieżek jest zaskakująco wysoki, co jest dystynktywną własnością sieci małego świata. Wreszcie, dokonujemy porównania cech omawianego modelu przepływu aktywności z neuro-biologicznymi rezultatami, przedstawionymi w badaniach grafów mózgowych z danych uzyskanych z funkcjonalnego obrazowania z wykorzystaniem rezonansu magnetycznego (fMRI). Wskazujemy silną odpowiedniość pomiędzy kształtem i wartością wykładnika rozkładu stopni, zaś klasteryzacja i charakterystyczna długość ścieżki są porównywalne w modelu i danych medycznych.

Big data has become an increasingly important topic in recent years, with new sources of data comes the need to be aware of the trade-off it requires, necessitating great care in both choice and implementation of algorithms, as well as how to adapt existing algorithms to handle this new setting. At the same time, the interpretability and understanding of a small to medium number of features is still key in many areas where understanding the data is paramount. In this thesis we show how we can tackle both these issues with the aid of self-organizing algorithms. Two objectives were achieved: Firstly, we created an anomaly detection system with emphasis on feature interpretability and show its results on real-world mobile network data provided by Nokia. Secondly, we propose and implement modifications to the growing neural gas algorithm, an algorithm that has seen uses in fields such as anomaly detection, 3D reconstruction and data compression. This modification is done using approximate nearest neighbor techniques with the purpose of creating an algorithm that is capable of efficiently trading accuracy for execution time and making growing neural gas usable in high-dimensional settings and with a larger model size.
Big Data é um tópico de cada vez mais importância, com esta nova fonte de dados é necessário ter em mente os compromissos necessários para a utilizar, requerendo grande cuidado na escolha de algoritmo e implementação, bem como as mudanças necessárias para adaptar algoritmos existentes. Ao mesmo tempo, a interpretação de um número médio de variáveis continua a ser chave em diversas áreas. Nesta tese mostramos como resolver ambos estes problemas sob a lente de algoritmos intitulados "self-organizing". Dois objetivos são cumpridos: A criação de um sistema de deteção de anomalias com ênfase em interpretabilidade e os seus resultados quando aplicado a dados de uma rede móvel, disponibilizados pela Nokia. Propomos e implementamos também modificações ao algoritmo de "Growing Neural Gas", um algoritmo com uso em deteção de anomalias, reconstrução 3D e compressão de dados. Esta modificação é feita usando técnicas de "Approximate Nearest Neighbours", criando um algoritmo capaz de balancear a precisão do modelo desejado com o tempo de execução, estas mudanças fazem com que "Growing Neural Gas" seja usável em cenários com um número grande de variáveis e capaz de produzir modelos de maior dimensão em tempo útil.
Mestrado em Engenharia de Computadores e Telemática