O avanço das pesquisas em redes complexas proporcionou desenvolvimentos significativos para a compreensão de sistemas complexos. Uma rede complexa é modelada matematicamente por meio de um grafo, onde cada vértice representa uma unidade dinâmica e suas interações são simbolizadas por um conjunto de arestas. Para se determinar propriedades estruturais desse sistema, caminhadas aleatórias tem-se mostrado muito úteis pois dependem apenas de informações locais (vértices vizinhos). Entre elas, destaca-se o passeio auto-excludente (SAW) que possui a restrição de não visitar um vértice que já foi alcançado, ou seja, apresenta memória do caminho percorrido. Por este motivo o SAW tem apresentado melhores resultados do que caminhantes sem restrição, na exploração da rede. Entretanto, por não se tratar de um processo Markoviano ele apresenta grande complexidade analítica, tornando indispensável o uso de simulações computacionais para melhor compreensão de sua dinâmica em diferentes topologias. Mesmo com as dificuldades analíticas, o SAW se tornou uma ferramenta promissora na identificação de estruturas de comunidades. Apesar de sua importância, detecção de comunidades permanece um problema em aberto devido à alta complexidade computacional associada ao problema de optimização, além da falta de uma definição formal do significado de comunidade. Neste trabalho, propomos um método de detecção de comunidades baseado em SAW para extrair uma estrutura de comunidades da rede otimizando o parâmetro modularidade. Combinamos características extraídas desta dinâmica com a análise de componentes principais para posteriormente classificar os vértices em grupos por meio da clusterização hierárquica aglomerativa. Para avaliar a performance deste novo algoritmo, comparamos os resultados com outras quatro técnicas populares: Girvan-Newman, Fastgreedy, Walktrap e Infomap, aplicados em dois tipos de redes sintéticas e nove redes reais diversificadas e bem conhecidas. Para os benchmarks, esta nova técnica produziu resultados satisfatórios em diferentes combinações de parâmetros, como tamanho de rede, distribuição de grau e número de comunidades. Já para as redes reais, obtivemos valores de modularidade superior aos métodos tradicionais, indicando uma distribuição de grupos mais adequada à realidade. Feito isso, generalizamos o algoritmo para redes ponderadas e digrafos, além de incorporar metadados à estrutura topológica a fim de melhorar a classificação em grupos. / The progress in complex networks research has provided significant understanding of complex systems. A complex network is mathematically modeled by a graph, where each vertex represents a dynamic unit and its interactions are symbolized by groups of edges. To determine the system structural properties, random walks have shown to be a useful tool since they depend only on local information (neighboring vertices). Among them, the selfavoiding walk (SAW) stands out for not visiting vertices that have already been reached, meaning it can record the path that has been travelled. For this reason, SAW has shown better results when compared to non-restricted walkers network exploration methods. However, as SAW is not a Markovian process, it has a great analytical complexity and needs computational simulations to improve its dynamics in different topologies. Even with the analytical complexity, SAW has become a promising tool to identify the community structure. Despite its significance, detecting communities remains an unsolved problem due to its high computational complexity associated to optimization issues and the lack of a formal definition of communities. In this work, we propose a method to identify communities based on SAW to extract community structure of a network through optimization of the modularity score. Combining technical features of this dynamic with principal components analyses, we classify the vertices in groups by using hierarchical agglomerative clustering. To evaluate the performance of this new algorithm, we compare the results with four other popular techniques: Girvan-Newman, Fastgreedy, Walktrap and Infomap, applying the algorithm in two types of synthetic networks and nine different and well known real ones. For the benchmarks, this new technique shows satisfactory results for different combination of parameters as network size, degree distribution and number of communities. As for real networks, our data shows better modularity values when compared to traditional methods, indicating a group distribution most suitable to reality. Furthermore, the algorithm was adapted for general weighted networks and digraphs in addition to metadata incorporated to topological structure, in order to improve the results of groups classifications.

We study the large deviation behaviour of simple random walks in dimension three or more in this thesis. The first part of the thesis concerns the number of lattice sites visited by the random walk. We call this the range of the random walk. We derive a large deviation principle for the probability that the range of simple random walk deviates from its mean. Our result describes the behaviour for deviation below the typical value. This is a result analogous to that obtained by van den Berg, Bolthausen, and den Hollander for the volume of the Wiener sausage. In the second part of the thesis, we are interested in the number of lattice sites visited by two independent simple random walks starting at the origin. We call this the intersection of ranges. We derive a large deviation principle for the probability that the intersection of ranges by time n exceeds a multiple of n. This is also an analogous result of the intersection volume of two independent Wiener sausages.

This paper investigates whether the inherent non-stationarity of macroeconomic time series is entirely due to a random walk or also to non-linear components. Applying the numerical tools of the analysis of dynamical systems to long time series for the US, we reject the hypothesis that these series are generated solely by a linear stochastic process. Contrary to the Real Business Cycle theory that attributes the irregular behavior of the system to exogenous random factors, we maintain that the fluctuations in the time series we examined cannot be explained only by means of external shocks plugged into linear autoregressive models. A dynamical and non-linear explanation may be useful for the double aim of describing and forecasting more accurately the evolution of the system. Linear growth models that find empirical verification on linear econometric analysis, are therefore seriously called in question. Conversely non-linear dynamical models may enable us to achieve a more complete information about economic phenomena from the same data sets used in the empirical analysis which are in support of Real Business Cycle Theory. We conclude that Real Business Cycle theory and more in general the unit root autoregressive models are an inadequate device for a satisfactory understanding of economic time series. A theoretical approach grounded on non-linear metric methods, may however allow to identify non-linear structures that endogenously generate fluctuations in macroeconomic time series. (authors' abstract) / Series: Working Papers Series "Growth and Employment in Europe: Sustainability and Competitiveness"

Existing methods to utilize capacity-heterogeneity in a P2P system either rely on constructing special overlays with capacity-proportional node degree or use topology adaptation to match a node's capacity with that of its neighbors. In existing P2P networks, which are often characterized by diverse node capacities and high churn, these methods may require large node degree or continuous topology adaptation, potentially making them infeasible due to their high overhead. In this thesis, we propose an unstructured P2P system that attempts to address these issues. We first prove that the overall throughput of search queries in a heterogeneous network is maximized if and only if traffic load through each node is proportional to its capacity. Our proposed system achieves this traffic distribution by biasing search walks using the Metropolis-Hastings algorithm, without requiring any special underlying topology. We then define two saturation metrics for measuring the performance of overlay networks: one for quantifying their ability to support random walks and the second for measuring their potential to handle the overhead caused by churn. Using simulations, we finally compare our proposed method with Gia, an existing system which uses topology adaptation, and find that the former performs better under all studied conditions, both saturation metrics, and such end-to-end parameters as query success rate, latency, and query-hits for various file replication schemes.

Online Social Networks (OSNs) such as Facebook, Twitter, and YouTube are among the most popular sites on the Internet. Billions of users are connected through these sites, building strong and effective communities to share views and ideas, and make recommendations nowadays. Therefore, by choosing an appropriate user-base from billions of people is required to analyze the structure and key characteristics of the large social graphs to improve current systems and to design new applications. For this reason, node sampling technique plays an important role to study large-scale social networks. As a basic requirement, the sampled nodes and their links should possess similar statistical features of the original network, otherwise the conclusion drawn from the sampled network may not be appropriate for the entire population. Hence, good sampling strategies are key to many online social network applications. For instance, before introducing a new product or adding new feature(s) of a product to the online social network community, that specific new product or the additional feature has to be exposed to only a small set of users, who are carefully chosen to represent the complete set of users. As such, different random walk-based sampling techniques have been introduced to produce samples of nodes that not only are internally well-connected but also capture the statistical features of the whole network. Traditionally, walk-based techniques do not have the restriction on the number of times that a node can be re-visited while sampling. This may lead to an inefficient sampling method, because the walk may be "stuck" at a small number of high-degree nodes without being able to reach out to the rest of the nodes. A random walk, even after a large number of hops, may not be able to obtain a sampled network that captures the statistical features of the entire network. In this thesis, we propose two walk-based sampling techniques to address the above problem, called K-Avoiding Random Walk (KARW) and Neighborhood-Avoiding Random Walk (NARW). With KARW, the number of times that a node can be re-visited is constrained within a given number K. With NARW, the random walk works in a "jump" fashion, since the walk starts outside of the N-hop neighborhood from the current node chosen randomly. By avoiding the current nodes neighboring area of level-N, NARW is expected to reach out the other nodes within the entire network quickly. We apply these techniques to construct multiple independent subgraphs from a social graph, consisting of 63K users with around a million connections between users collected from a Facebook dataset. By simulating our proposed strategies, we collect performance metrics and compare the results with the current state-of-the-art sampling techniques (Uniform Random Sampling, Random Walk, and Metropolis Hastings Random Walk). We also calculate some of the key statistical features (i.e., degree distribution, betweenness centrality, closeness centrality, modularity, and clustering coefficient) of the sampled graphs to get an idea about the network structures that essentially represent the original social graph. / Graduate / 0984 / shahed.anwar@gmail.com

No description available.

No description available.

No description available.

Thesis (M.Sc.)--University of Adelaide, Dept. of Applied Mathematics, 2001. / "November 2001." Bibliography: leaves 128-130.

Thesis (Ph. D.)--University of Washington, 2002. / Vita. Includes bibliographical references (leaves 106-114).