Many real life complex networks consists of a tremendous amount of nodes and edges which make them difficult to extract and analyze. This thesis aims to examine what network prop- erties that can be deduced when considering small samples of a complex network and how well they correspond to the characteristics of the complete network. This is of importance as sampling will most likely be the de facto method when analyzing complex networks in the future. The study examine the scale-free property, the small-world property and the com- munity structure of the network spanned by the KTH domain. The method consisted of gathering data about the network through sampling it in a breadth-first manner using a web crawler. The samples was then compared with respect to each property. The results was that good approximations of the scale-free property could be made from small samples of the KTH network. However, no good approximation could be made about the small-world property using the sampling technique. Good approximations about a node’s community affiliation could be observed. However, general conclusions of the com- plete network’s community structures could not be made. To summarize, the result indi- cate that small samples can be used to approximate some properties of the complete KTH network. However, to determine if the result is true for the general case more research is necessary. / Komplexa nätverk i vår omvärld består av ett stort antal hörn och kanter vilket gör dem svå- ra att extrahera och analysera. Denna rapport undersöker vilka nätverksegenskaper som kan härledas vid undersökningen av små stickprov av ett nätverk och hur bra dessa representerar egenskaperna hos det fullständiga nätverket. Detta är av betydelse eftersom användandet av små stickprov kommer troligtvis att vara standarden vid undersökningar av nätverk i framtiden. Denna studie undersökte scale-free egenskapen, small-world egenskapen och community strukturen för nätverket som omfattas av KTH domaänen. Metoden innefattade att samla in data om nätverket genom stickprov baserat på en bredden-först sökning. Detta realiserades genom att använda en sökrobot. Sedan jämfördes de olika stickproven med avseende på de olika nätverksegenskaperna. Resultetat visade att nätverkets scale-free egenskap kunde approximaeras med små stickprov. Däremot var det inte möjligt att approximera nätverkets small-world egenskap genom användet av den givna stickprovsmetoden. Goda approximationer observerades för att avgöra ett hörns community tillhörighet men den allmäna community strukturen kunde inte approximeras. Sammanfattningsvis visade resultatet att stickprov kan användas för att approximera vissa egenskaper hos det fullständiga KTH nätverket men att mer forskning krävs för att avgöra om resultaten kan generaliseras.

No description available.

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

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. / Network analysis has become a popular topic in many disciplines including social sciences, epidemiology, biology, and business as it provides valuable insights about many real-world systems represented as networks. The recent advancement of science and technology has resulted in a massive growth of such networks, and mining and processing such massive networks poses significant challenges, which can be addressed by various high-performance computing (HPC) platforms. In this dissertation, we present parallel algorithms for a few network analytic problems using HPC platforms. Random networks are widely used for modeling many complex real-world systems such as the Internet, biological, social, and infrastructure networks. Most prior work on generating random graphs involves sequential algorithms, and they can be broadly categorized in two classes: (i) edge switching and (ii) stub-matching. We present parallel algorithms for generating random graphs using both the edge switching and stub-matching methods. Our parallel algorithms for switching edges can generate random networks with billions of edges in a few minutes with 1024 processors. We have studied several load balancing methods to equally distribute workload among the processors to achieve the best performance. The parallel algorithm for generating random graphs using the stub-matching method also shows good speedup for medium-sized networks. We believe the proposed parallel algorithms will prove useful in analyzing and mining of emerging networks.

学位プログラム名: 京都大学大学院思修館 / 京都大学 / 新制・課程博士 / 博士(総合学術) / 甲第25457号 / 総総博第33号 / 新制||総総||6(附属図書館) / 京都大学大学院総合生存学館総合生存学専攻 / (主査)准教授 水本 憲治, 教授 齋藤 敬, 教授 今中 雄一 / 学位規則第4条第1項該当 / Doctor of Philosophy / Kyoto University / DFAM

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.