No description available.

Networks (or graphs) are an effective abstraction for representing many real-world complex systems. Analyzing various structural properties of and dynamics on such networks reveal valuable insights about the behavior of such systems. In today's data-rich world, we are deluged by the massive amount of heterogeneous data from various sources, such as the web, infrastructure, and online social media. Analyzing this huge amount of data may take a prohibitively long time and even may not fit into the main memory of a single processing unit, thus motivating the necessity of efficient parallel algorithms in various high-performance computing (HPC) platforms. In this dissertation, we present distributed and shared memory parallel algorithms for some important network analytic problems. First, we present distributed memory parallel algorithms for switching edges in a network. Edge switch is an operation on a network, where two edges are selected randomly, and one of their end vertices are swapped with each other. This operation is repeated either a given number of times or until a specified criterion is satisfied. It has diverse real-world applications such as in generating simple random networks with a given degree sequence and in modeling and studying various dynamic networks. One of the steps in our edge switch algorithm requires generating multinomial random variables in parallel. We also present the first non-trivial parallel algorithm for generating multinomial random variables. Next, we present efficient algorithms for assortative edge switch in a labeled network. Assuming each vertex has a label, an assortative edge switch operation imposes an extra constraint, i.e., two edges are randomly selected and one of their end vertices are swapped with each other if the labels of the end vertices of the edges remain the same as before. It can be used to study the effect of the network structural properties on dynamics over a network. Although the problem of assortative edge switch seems to be similar to that of (regular) edge switch, the constraint on the vertex labels in assortative edge switch leads to a new difficulty, which needs to be addressed by an entirely new algorithmic approach. We first present a novel sequential algorithm for assortative edge switch; then we present an efficient distributed memory parallel algorithm based on our sequential algorithm. Finally, we present efficient shared memory parallel algorithms for generating random networks with exact given degree sequence using a direct graph construction method, which involves computing a candidate list for creating an edge incident on a vertex using the Erdos-Gallai characterization and then randomly creating the edges from the candidates. / Ph. D.

Socially coupled systems are comprised of inter-dependent social, organizational, economic, infrastructure and physical networks. Today's urban regions serve as an excellent example of such systems. People and institutions confront the implications of the increasing scale of information becoming available due to a combination of advances in pervasive computing, data acquisition systems as well as high performance computing. Integrated modeling and decision making environments are necessary to support planning, analysis and counter factual experiments to study these complex systems. Here, we describe SIMFRASTRUCTURE -- a computational infrastructure that supports high performance computing oriented decision and analytics environments to study socially coupled systems. Simfrastructure provides a middleware with multiplexing mechanism by which modeling environments with simple and intuitive user-interfaces can be plugged in as front-end systems, and high-end computing resources -- such as clusters, grids and clouds -- can be plugged in as back-end systems for execution. This makes several key aspects of simulation systems such as the computational complexity, data management and resource management and allocation completely transparent to the users. The decoupling of user interfaces, data repository and computational resources from simulation execution allows users to run simulations and access the results asynchronously and enables them to add new datasets and simulation models dynamically.  Simfrastructure enables implementation of a simple yet powerful modeling environment with built-in analytics-as-aservice platform, which provides seamless access to high end computational resources, through an intuitive interface for studying socially coupled systems. We illustrate the applicability of Simfrastructure in the context of an integrated modeling environment to study public health epidemiology and network science. / Master of Science

The advances in social media and social computing technologies have dramatically changed the way through which people interact, organize, and collaborate. The use of social media also makes the large-scale data revealing human behavior accessible to researchers and practitioners. The analysis and modeling of social networks formed from relatively stable online communities have been extensively studied. The research on the structural and dynamical patterns of large-scale crowds motivated by accomplishing common goals, named the cyber movement organizations (CMO) or cyber-enabled social movement organizations (CeSMO), however, is still limited to anecdotal case studies. This research is one of the first steps towards the understanding of the CMO/CeSMO based on real data collected from online social media.The focus of my research is on the study of an important type of CMO/CeSMO, the crowd-powered search behavior (also known as human flesh search, HFS), in which a large number of Web users voluntarily gathered together to find out the truth of an event or the information of a person that could not be identified by one single person or simple online searches. In this research, I have collected a comprehensive data-set of HFS. I first introduce the phenomenon of HFS and reviewed the study of online social groups/communities. Then, I present the empirical studies of both individual HFS episodes and aggregated HFS communities, and unveiled their unique topological properties. Based on the empirical findings, I propose two models to simulate evolution and topology of individual HFS networks. I conclude the dissertation with discussions of future research of CMO/CeSMO.

Orientador: Prof. Dr. Fabrício Olivetti de França / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2017. / Um dos tópicos estudados em Ciência das Redes é o de detecção de comunidades, que são sub-redes com características que se destacam dentro de seu conjunto. Diversos algoritmos de detecção de comunidades foram criados, se diferenciando na natureza da comunidade estimada. Esta dissertação tem como objetivo principal analisar diferentes algoritmos de detecção de comunidades da literatura para criação de um modelo de escolha de algoritmos de detecção de comunidade a partir das características da rede. Para isso, três hipóteses. Foram testadas: i) os melhores algoritmos de detecção de comunidade se complementam em relação à redes em que obtém seu melhor desempenho; ii) o desempenho de cada algoritmo de detecção de comunidade esta ligada diretamente _a propriedade da rede. iii) uma vez que as propriedades da rede são mensuradas, é possível fazer uma escolha dos melhores algoritmos de detecção de comunidade para essa rede. Para a primeira hipótese foram testados sete algoritmos do estado da arte e avaliados seus desempenhos individuais sobre redes artifiais, em termos da métrica de Informação Mutua Normalizada (NMI). Veríamos a existência de um conjunto de algoritmos que obtiveram o maior NMI para determinados tipos de redes e nenhum outro algoritmo obteve esse mesmo valor, concluindo que a escolha adequada do algoritmo de acordo com as características da rede é importante. Para a segunda hipótese foram testados modelos de regressão com o objetivo de verificar a possibilidade de estimar o desempenho de cada algoritmo baseado nas caracteristicas da rede. Verifcamos que a maioria dos modelos foram superiores aos da base de referencia utilizados, principalmente ao remover as redes infectaveis. Para a terceira hipótese foram testados algoritmos de classicação com o objetivo de escolher um ou mais algoritmos de acordo com a características da rede. Verificamos que o desempenho dos modelos obtidos pelos algoritmos foram superiores aos da base de referencia, com algumas ressalvas. / One of the topics studied in Network Science is the community detection, that are subnetworks with features that stand out as a whole. Many algorithms were developed for the detection of communities, difering in the nature of the estimated community. This dissertation has as its main objective, the analysis of diferent community detection algorithms from the literature to create models to help choosing the best algorithms given the features from the network. For this purpose, three hypotheses were tested: i) whether the best algorithms for detecting communities complement each other in relation to the networks in which they obtain better performance; ii) whether the performance of each community detection algorithm is directly associated with the network property, and iii) once the network properties are measured, whether it is possible to choose the best community detection algorithms for this network. For the first hypothesis, seven stateof- the-art algorithms were tested and their individual performances in articial networks were evaluated in terms of the NMI metric. We verifed the existence of a set of algorithms that obtained the highest NMI for certain types of networks and no other algorithm obtained that same value, concluding that the proper choice of the algorithm according to the network features is important. For the second hypothesis, regression models were tested to verify the possibility of estimate the performance of each algorithm based on the features of the network. We verifed that most of the models were superior to the baseline used, mainly in the removal of infeasible networks. For the third hypothesis, the classifcation algorithms were tested to choose one or more algorithms according to the network features. We veried that the performance of the models obtained by the algorithms was higher than those of the baseline, with some caveats.

<div>Complex systems are often characterized by a large collection of components interacting in nontrivial ways. Self-organization among these individual components often leads to emergence of a macroscopic structure that is neither completely regular nor completely random. In order to understand what we observe at a macroscopic scale, conceptual, mathematical, and computational tools are required for modeling and analyzing these interactions. A principled approach to understand these complex systems (and the processes that give rise to them) is to formulate generative models and infer their parameters from given data that is typically stored in the form of networks (or graphs). The increasing availability of network data from a wide variety of sources, such as the Internet, online social networks, collaboration networks, biological networks, etc., has fueled the rapid development of network science. </div><div><br></div><div>A variety of generative models have been designed to synthesize networks having specific properties (such as power law degree distributions, small-worldness, etc.), but the structural richness of real-world network data calls for researchers to posit new models that are capable of keeping pace with the empirical observations about the topological properties of real networks. The mechanistic approach to modeling networks aims to identify putative mechanisms that can explain the dependence, diversity, and heterogeneity in the interactions responsible for creating the topology of an observed network. A successful mechanistic model can highlight the principles by which a network is organized and potentially uncover the mechanisms by which it grows and develops. While it is difficult to intuit appropriate mechanisms for network formation, machine learning and evolutionary algorithms can be used to automatically infer appropriate network generation mechanisms from the observed network structure.</div><div><br></div><div>Building on these philosophical foundations and a series of (not new) observations based on first principles, we extrapolate an action-based framework that creates a compact probabilistic model for synthesizing real-world networks. Our action-based perspective assumes that the generative process is composed of two main components: (1) a set of actions that expresses link formation potential using different strategies capturing the collective behavior of nodes, and (2) an algorithmic environment that provides opportunities for nodes to create links. Optimization and machine learning methods are used to learn an appropriate low-dimensional action-based representation for an observed network in the form of a row stochastic matrix, which can subsequently be used for simulating the system at various scales. We also show that in addition to being practically relevant, the proposed model is relatively exchangeable up to relabeling of the node-types. </div><div><br></div><div>Such a model can facilitate handling many of the challenges of understanding real data, including accounting for noise and missing values, and connecting theory with data by providing interpretable results. To demonstrate the practicality of the action-based model, we decided to utilize the model within domain-specific contexts. We used the model as a centralized approach for designing resilient supply chain networks while incorporating appropriate constraints, a rare feature of most network models. Similarly, a new variant of the action-based model was used for understanding the relationship between the structural organization of human brains and the cognitive ability of subjects. Finally, our analysis of the ability of state-of-the-art network models to replicate the expected topological variations in network populations highlighted the need for rethinking the way we evaluate the goodness-of-fit of new and existing network models, thus exposing significant gaps in the literature.</div>

<p>It was only in the last decade that Magnetic Resonance Imaging (MRI) technologies have achieved high-quality levels that enabled comprehensive assessments of individual human brain structure and functions. One of the most important advancements put forth by Thomas Yeo and colleagues in 2011 was the intrinsic functional connectivity MRI (fcMRI) networks which are highly reproducible and feature consistently across different individual brains. This dissertation aims to unravel different characteristics of human brain fcMRI networks, separately through network morphospace and collectively through stochastic block models.</p><p><br></p><p>The quantification of human brain functional (re-)configurations across varying cognitive demands remains an unresolved topic. Such functional reconfigurations are rather subtle at the whole-brain level. Hence, we propose a mesoscopic framework focused on functional networks (FNs) or communities to quantify functional (re-)configurations. To do so, we introduce a 2D network morphospace that relies on two novel mesoscopic metrics, Trapping Efficiency (TE) and Exit Entropy (EE). We use this framework to quantify the Network Configural Breadth across different tasks. Network configural breadth is shown to significantly predict behavioral measures, such as episodic memory, verbal episodic memory, fluid intelligence and general intelligence.</p><p><br></p><p>To properly estimate and assess whole-brain functional connectomes (FCs) is among one of the most challenging tasks in computational neuroscience. Among the steps in constructing large-scale brain networks, thresholding of statistically spurious edge(s) in FCs is the most critical. State-of-the-art thresholding methods are largely ad hoc. Meanwhile, a dominant proportion of the brain connectomics research relies heavily on using a priori set of highly-reproducible human brain functional sub-circuits (functional networks (FNs)) without properly considering whether a given FN is information-theoretically relevant with respect to a given FC. Leveraging recent theoretical developments in Stochastic block model (SBM), we first formally defined and subsequently quantified the level of information-theoretical prominence of a priori set of FNs across different subjects and fMRI task conditions for any given input FC. The main contribution of this work is to provide an automated thresholding method of individuals’ FCs based on prior knowledge of human brain functional sub-circuitry.</p>

Urban development planning efforts are challenged to enhance coevolving spatial and socioeconomic systems that exist and interact at multiple scales. While network and simulation sciences have created new tools and theories suitable for urban studies, models of development are not yet suitable for local and regional development planning. A case study of the City of Roanoke, Virginia, grounded network development theories of scaling, engagement, and collective perception function, as well as network forms. By advancing urban development network theory, frameworks for urban simulation like agent-based models take more coherent shape. This in turn better positions decision-making and planning practitioners to adapt, transform, or renew local network-oriented development systems, and conceptualize a framework for computational urban development planning for regions and localities. / Ph. D.

<p dir="ltr">Our research revolves around the evolving landscape of Open-Source Software (OSS) supply chains, emphasizing their critical role in contemporary software development while investigating the escalating security concerns associated with their integration. As OSS continues to shape the software ecosystem, our research acknowledges the paradigm shift in the software supply chain, highlighting its complexity and the associated security challenges. Focusing on Debian packages, we employ advanced network science methods to comprehensively assess the structural dynamics and vulnerabilities within the OSS supply chain. The study is motivated by the imperative to understand, model, and mitigate security risks from interconnected software components.</p><p dir="ltr">Our research questions delve into 1) identifying high-risk packages 2) comparing risk profiles between source and build stages and 3) predicting future vulnerabilities. Data collection involves collecting source code repositories, build-info information, and vulnerability data of Debian packages. Leveraging a multifaceted methodology, we perform the following things: graph construction, subsampling, metrics creation, explorative data analysis, and statistical investigations on the Debian package network. This statistical approach integrates the Wilcoxon test, Chi-Square test, and advanced network dynamics modeling with machine learning, to explore evolving trends and correlations between different stages of the OSS supply chain.</p><p dir="ltr">Our goals include providing actionable insights for industry practitioners, policymakers, and developers to enhance risk management in the OSS supply chain. The expected outcomes encompass an enriched understanding of vulnerability propagation, the identification of high-risk packages, and the comparison of network-based risk metrics against traditional software engineering measures. Ultimately, our research contributes to the ongoing discourse on securing open-source ecosystems, offering practical strategies for risk mitigation and fostering a safer and more resilient OSS supply chain.</p>

Sistemas Complexos são característicos por possuir uma rede interna representando o relacionamento estrutural entre seus elementos e uma forma natural de interpretar essa interação é através de um grafo. Neste trabalho, o sistema de transporte público urbano de São Paulo é reinterpretado de forma acoplada (ônibus e metrô juntos) como uma rede complexa, abstraindo detalhes operacionais e focando na conectividade. Pelo grafo empiricamente gerado, é feita uma caraterização estatística nas métricas de redes complexas, onde diferentes valores de raio de distância são usados para agrupar pontos e estações próximas que antes se apresentavam desconectados. Esse agrupamento pode ser interpretado como uma ferramenta de política pública, representando a disposição do usuário em se locomover ao ponto mais próximo para acessar o transporte. O processo mostrou que aumentar essa disposição gera grande redução na distância e número de passos entre ônibus, trens e linhas de metrô para atingir todos os destinos da rede. É utilizado um modelo exploratório que testa a robustez da rede aleatoriamente, deterministicamente e probabilisticamente tendo como alvo pontos e linhas. De acordo com os raios de agrupamento, definido como disposição, diferentes valores de fragmentação foram obtidos diante dos ataques simulados. Esses resultados suportam duas principais características observadas na literatura de redes deste tipo: possuem um elevado grau de robustez à falhas aleatórias, mas são vulneráveis a ataques tendo como alvo nós ou links importantes / Complex systems are characteristic by having an internal network representing the structural relationship between its elements and a natural way to interpret this interaction is through a graph. In this work, the urban public transport system of São Paulo is reinterpreted as a coupled (bus and subway) complex network, bypassing operational details and focusing on connectivity. Using the empirically generated graph, a statistical characterisation is made by network metrics where different radius values are used to group nearby stops and stations that were disconnected before. That can be interpreted as a public policy tool, representing the user\'s willingness to get around the nearest point to access transportation. This process has shown that increasing this willingness generates great reduction in the distance and in the number of jumps between buses, trains and subways lines to achieve all the network destinations. An exploratory model is used to test the robustness of the network by randomly, deterministically and preferentially targeting the stops and service lines. According to the grouping radius, aka willingness, different fragmentation values were obtained under attack simulations. These findings support two main characteristics observed in such networks literature: they have a high degree of robustness to random failures, but are vulnerable to targeted attacks