Analisi di grafi su architetture a memoria distribuita

Questo lavoro di tesi tratta il tema delle reti complesse, mostrando i principali modelli di rete complessa quali: il modello Random, il modello Small-World ed il modello Scale-free; si introdurranno alcune metriche usate per descrivere le reti complesse quali la Degree centrality, la Closeness centrality e la Betweenness centrality; si descriveranno i problemi da tenere in considerazione durante la definizione e l’implementazione di algoritmi su grafi; i modelli di calcolo su cui progettare gli algoritmi per risolvere i problemi su grafi; un’analisi prestazionale degli algoritmi proposti per calcolare i valori di Beweenness centrality su grafi di medio-grandi dimensioni. Parte di questo lavoro di tesi è consistito nello sviluppo di LANA, LArge-scale Network Analyzer, un software che permette il calcolo e l’analisi di varie metriche di centralità su grafo.

Large-scale Network Analysis on Distributed Architectures

Questa dissertazione esamina le sfide e i limiti che gli algoritmi di analisi di grafi incontrano in architetture distribuite costituite da personal computer. In particolare, analizza il comportamento dell'algoritmo del PageRank così come implementato in una popolare libreria C++ di analisi di grafi distribuiti, la Parallel Boost Graph Library (Parallel BGL). I risultati qui presentati mostrano che il modello di programmazione parallela Bulk Synchronous Parallel è inadatto all'implementazione efficiente del PageRank su cluster costituiti da personal computer. L'implementazione analizzata ha infatti evidenziato una scalabilità negativa, il tempo di esecuzione dell'algoritmo aumenta linearmente in funzione del numero di processori. Questi risultati sono stati ottenuti lanciando l'algoritmo del PageRank della Parallel BGL su un cluster di 43 PC dual-core con 2GB di RAM l'uno, usando diversi grafi scelti in modo da facilitare l'identificazione delle variabili che influenzano la scalabilità. Grafi rappresentanti modelli diversi hanno dato risultati differenti, mostrando che c'è una relazione tra il coefficiente di clustering e l'inclinazione della retta che rappresenta il tempo in funzione del numero di processori. Ad esempio, i grafi Erdős–Rényi, aventi un basso coefficiente di clustering, hanno rappresentato il caso peggiore nei test del PageRank, mentre i grafi Small-World, aventi un alto coefficiente di clustering, hanno rappresentato il caso migliore. Anche le dimensioni del grafo hanno mostrato un'influenza sul tempo di esecuzione particolarmente interessante. Infatti, si è mostrato che la relazione tra il numero di nodi e il numero di archi determina il tempo totale.

Disseminazioni in reti peer-to-peer attraverso algoritmi di gossip a due fasi

Gli algoritmi di gossip sono utilizzati per la disseminazione di messaggi in una rete peer-to-peer. La tesi tratta lo sviluppo, l'implementazione e l'analisi di quattro nuovi algoritmi di gossip "a due fasi". Gli algoritmi sono stati sviluppati e testati con il simulatore LUNES per poi essere analizzati in vari confronti con gli algoritmi classici dell'ambito, ovvero Fixed Probability e Conditional Broadcast. Le prove sono state effettuate su varie tipologie di grafi, ovvero Random, Scale-free, Small-world e K-Regular.

Functional brain network efficiency predicts intelligence

The neuronal causes of individual differences in mental abilities such as intelligence are complex and profoundly important. Understanding these abilities has the potential to facilitate their enhancement. The purpose of this study was to identify the functional brain network characteristics and their relation to psychometric intelligence. In particular, we examined whether the functional network exhibits efficient small-world network attributes (high clustering and short path length) and whether these small-world network parameters are associated with intellectual performance. High-density resting state electroencephalography (EEG) was recorded in 74 healthy subjects to analyze graph-theoretical functional network characteristics at an intracortical level. Ravens advanced progressive matrices were used to assess intelligence. We found that the clustering coefficient and path length of the functional network are strongly related to intelligence. Thus, the more intelligent the subjects are the more the functional brain network resembles a small-world network. We further identified the parietal cortex as a main hub of this resting state network as indicated by increased degree centrality that is associated with higher intelligence. Taken together, this is the first study that substantiates the neural efficiency hypothesis as well as the Parieto-Frontal Integration Theory (P-FIT) of intelligence in the context of functional brain network characteristics. These theories are currently the most established intelligence theories in neuroscience. Our findings revealed robust evidence of an efficiently organized resting state functional brain network for highly productive cognitions.

Editorial

In fact, much of the attraction of network theory initially stemmed from the fact that many networks seem to exhibit some sort of universality, as most of them belong to one of three classes: random, scale-free and small-world networks. Structural properties have been shown to translate into different important properties of a given system, including efficiency, speed of information processing, vulnerability to various forms of stress, and robustness. For example, scale-free and random topologies were shown to be...

Using three-dimensional microfluidic networks for solving computationally hard problems

This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.

Estudo sistêmico da geração de conhecimento no IPEN

Com o escopo de fornecer subsídios para compreender como o processo de colaboração científica ocorre e se desenvolve em uma instituição de pesquisas, particularmente o IPEN, o trabalho utilizou duas abordagens metodológicas. A primeira utilizou a técnica de análise de redes sociais (ARS) para mapear as redes de colaboração científica em P&D do IPEN. Os dados utilizados na ARS foram extraídos da base de dados digitais de publicações técnico-científicas do IPEN, com o auxílio de um programa computacional, e basearam-se em coautoria compreendendo o período de 2001 a 2010. Esses dados foram agrupados em intervalos consecutivos de dois anos gerando cinco redes bienais. Essa primeira abordagem revelou várias características estruturais relacionadas às redes de colaboração, destacando-se os autores mais proeminentes, distribuição dos componentes, densidade, boundary spanners e aspectos relacionados à distância e agrupamento para definir um estado de redes mundo pequeno (small world). A segunda utilizou o método dos mínimos quadrados parciais, uma variante da técnica de modelagem por equações estruturais, para avaliar e testar um modelo conceitual, apoiado em fatores pessoais, sociais, culturais e circunstanciais, para identificar aqueles que melhor explicam a propensão de um autor do IPEN em estabelecer vínculos de colaboração em ambientes de P&D. A partir do modelo consolidado, avaliou-se o quanto ele explica a posição estrutural que um autor ocupa na rede com base em indicadores de ARS. Nesta segunda parte, os dados foram coletados por meio de uma pesquisa de levantamento com a utilização de um questionário. Os resultados mostraram que o modelo explica aproximadamente 41% da propensão de um autor do IPEN em colaborar com outros autores e em relação à posição estrutural de um autor na rede o poder de explicação variou entre 3% e 3,6%. Outros resultados mostraram que a colaboração entre autores do IPEN tem uma correlação positiva com intensidade moderada com a produtividade, da mesma forma que, os autores mais centrais na rede tendem a ampliar a sua visibilidade. Por fim, vários outros indicadores estatísticos bibliométricos referentes à rede de colaboração em P&D do IPEN foram determinados e revelados, como, a média de autores por publicação, média de publicações por autores do IPEN, total de publicações, total de autores e não autores do IPEN, entre outros. Com isso, esse trabalho fornece uma contribuição teórica e empírica aos estudos relacionados à colaboração científica e ao processo de transferência e preservação de conhecimento, assim como, vários subsídios que contribuem para o contexto de tomada de decisão em ambientes de P&D.

Tomaso's fortune /

Short stories.

Network topology and the evolution of dynamics in an artificial genetic regulatory network model created by whole genome duplication and divergence

Topological measures of large-scale complex networks are applied to a specific artificial regulatory network model created through a whole genome duplication and divergence mechanism. This class of networks share topological features with natural transcriptional regulatory networks. Specifically, these networks display scale-free and small-world topology and possess subgraph distributions similar to those of natural networks. Thus, the topologies inherent in natural networks may be in part due to their method of creation rather than being exclusively shaped by subsequent evolution under selection. The evolvability of the dynamics of these networks is also examined by evolving networks in simulation to obtain three simple types of output dynamics. The networks obtained from this process show a wide variety of topologies and numbers of genes indicating that it is relatively easy to evolve these classes of dynamics in this model. (c) 2006 Elsevier Ireland Ltd. All rights reserved.

Network construction and graph theoretical analysis of functional language networks in pediatric epilepsy

This dissertation introduces a new approach for assessing the effects of pediatric epilepsy on the language connectome. Two novel data-driven network construction approaches are presented. These methods rely on connecting different brain regions using either extent or intensity of language related activations as identified by independent component analysis of fMRI data. An auditory description decision task (ADDT) paradigm was used to activate the language network for 29 patients and 30 controls recruited from three major pediatric hospitals. Empirical evaluations illustrated that pediatric epilepsy can cause, or is associated with, a network efficiency reduction. Patients showed a propensity to inefficiently employ the whole brain network to perform the ADDT language task; on the contrary, controls seemed to efficiently use smaller segregated network components to achieve the same task. To explain the causes of the decreased efficiency, graph theoretical analysis was carried out. The analysis revealed no substantial global network feature differences between the patient and control groups. It also showed that for both subject groups the language network exhibited small-world characteristics; however, the patient's extent of activation network showed a tendency towards more random networks. It was also shown that the intensity of activation network displayed ipsilateral hub reorganization on the local level. The left hemispheric hubs displayed greater centrality values for patients, whereas the right hemispheric hubs displayed greater centrality values for controls. This hub hemispheric disparity was not correlated with a right atypical language laterality found in six patients. Finally it was shown that a multi-level unsupervised clustering scheme based on self-organizing maps, a type of artificial neural network, and k-means was able to fairly and blindly separate the subjects into their respective patient or control groups. The clustering was initiated using the local nodal centrality measurements only. Compared to the extent of activation network, the intensity of activation network clustering demonstrated better precision. This outcome supports the assertion that the local centrality differences presented by the intensity of activation network can be associated with focal epilepsy.^

Measuring the Diversity and the Integration of Film Production in Mercosur: A Social Network Analysis

Based on an original and comprehensive database of all feature fiction films produced in Mercosur between 2004 and 2012, the paper analyses whether the Mercosur film industry has evolved towards an integrated and culturally more diverse market. It provides a summary of policy opportunities in terms of integration and diversity, emphasizing the limiter role played by regional policies. It then shows that although the Mercosur film industry remains rather disintegrated, it tends to become more integrated and culturally more diverse. From a methodological point of view, the combination of Social Network Analysis and the Stirling Model opens up interesting research tracks to analyse creative industries in terms of their market integration and their cultural diversity.

Intervention for organizational innovation: a case study

This article is intended to report an intervention in a SME of the IT sector, aiming at an organizational change process towards a greater proactivity of employees. The presentation of the case includes the diagnosis, intervention, and the beginning of the implementation of innovation projects, based on an adapted model of third generation large-group organizational change methods. In addition to the steps followed, small-world analysis techniques were used, with the intention of determining the existing communication networks; also, a content analysis of collected success stories was made, in order to suggest strong points for a future organizational culture. The results clarified the desirable characteristics of an intervention method with large groups, adapted to Portuguese companies, and effective in organizational innovation project design. The analysis of the success stories helped to determine the strengths of an orientation for the future, while the use of measures of small-world networks allowed us to analyze the existing informal organization. Although this study does not include the completion of the projects, due to difficulties in the company, it can provide a solid basis for application in future interventions.

Network Construction and Graph Theoretical Analysis of Functional Language Networks in Pediatric Epilepsy

This dissertation introduces a new approach for assessing the effects of pediatric epilepsy on the language connectome. Two novel data-driven network construction approaches are presented. These methods rely on connecting different brain regions using either extent or intensity of language related activations as identified by independent component analysis of fMRI data. An auditory description decision task (ADDT) paradigm was used to activate the language network for 29 patients and 30 controls recruited from three major pediatric hospitals. Empirical evaluations illustrated that pediatric epilepsy can cause, or is associated with, a network efficiency reduction. Patients showed a propensity to inefficiently employ the whole brain network to perform the ADDT language task; on the contrary, controls seemed to efficiently use smaller segregated network components to achieve the same task. To explain the causes of the decreased efficiency, graph theoretical analysis was carried out. The analysis revealed no substantial global network feature differences between the patient and control groups. It also showed that for both subject groups the language network exhibited small-world characteristics; however, the patient’s extent of activation network showed a tendency towards more random networks. It was also shown that the intensity of activation network displayed ipsilateral hub reorganization on the local level. The left hemispheric hubs displayed greater centrality values for patients, whereas the right hemispheric hubs displayed greater centrality values for controls. This hub hemispheric disparity was not correlated with a right atypical language laterality found in six patients. Finally it was shown that a multi-level unsupervised clustering scheme based on self-organizing maps, a type of artificial neural network, and k-means was able to fairly and blindly separate the subjects into their respective patient or control groups. The clustering was initiated using the local nodal centrality measurements only. Compared to the extent of activation network, the intensity of activation network clustering demonstrated better precision. This outcome supports the assertion that the local centrality differences presented by the intensity of activation network can be associated with focal epilepsy.

Spatial and Functional Organization of Pig Trade in Different European Production Systems: Implications for Disease Prevention and Control

Understanding the complexity of live pig trade organization is a key factor to predict and control major infectious diseases, such as classical swine fever (CSF) or African swine fever (ASF). Whereas the organization of pig trade has been described in several European countries with indoor commercial production systems, little information is available on this organization in other systems, such as outdoor or small-scale systems. The objective of this study was to describe and compare the spatial and functional organization of live pig trade in different European countries and different production systems. Data on premise characteristics and pig movements between premises were collected during 2011 from Bulgaria, France, Italy, and Spain, which swine industry is representative of most of the production systems in Europe (i.e., commercial vs. small-scale and outdoor vs. indoor). Trade communities were identified in each country using the Walktrap algorithm. Several descriptive and network metrics were generated at country and community levels. Pig trade organization showed heterogeneous spatial and functional organization. Trade communities mostly composed of indoor commercial premises were identified in western France, northern Italy, northern Spain, and north-western Bulgaria. They covered large distances, overlapped in space, demonstrated both scale-free and small-world properties, with a role of trade operators and multipliers as key premises. Trade communities involving outdoor commercial premises were identified in western Spain, south-western and central France. They were more spatially clustered, demonstrated scale-free properties, with multipliers as key premises. Small-scale communities involved the majority of premises in Bulgaria and in central and Southern Italy. They were spatially clustered and had scale-free properties, with key premises usually being commercial production premises. These results indicate that a disease might spread very differently according to the production system and that key premises could be targeted to more cost-effectively control diseases. This study provides useful epidemiological information and parameters that could be used to design risk-based surveillance strategies or to more accurately model the risk of introduction or spread of devastating swine diseases, such as ASF, CSF, or foot-and-mouth disease.