Preferential attachment networks with power law degree sequence undergo a phase transition when the power law exponent τ changes. For τ > 3 typical distances in the network are logarithmic in the size of the network and for 2 < τ < 3 they are doubly logarithmic. In this thesis, we identify the correct scaling constant for τ ∈ (2, 3) and discover a surprising dichotomy between preferential attachment networks and networks without preferential attachment. This contradicts previous conjectures of universality. Moreover, using a model recently introduced by Dereich and Mörters, we study the critical behaviour at τ = 3, and establish novel results for the scale of the typical distances under lower order perturbations of the attachment function.

This thesis studies the characteristics of the network structure extracted from the public KTH web. The network structure was extracted with a crawler and consisted of 671,013 nodes and 23,515,683 links. The system is studied by applying statistical concepts from network science such as degree distribution and average path to reveal the characteristics of the network. The aim of the statistical analysis is to explore the robustness of the network and to answer if the network is scale-free. The thesis will examine the results from the study and compare the results to previous similar research. The results indicate that there might have been a change in regards to the network structure of websites since the last major research was done on the subject, likely caused by changes in web design. However, the results still indicate characteristics typical for a scale-free network. Due to irregularities in the crawler results may be slightly unreliable. / Detta kandidatexamensarbete undersöker de egenskaper i nätverksstrukturen för det allmänna KTH nätet. Denna struktur extraherades med en spindel och bestod av 671,013 noder och 23,515,583 länkar. Systemet studerades genom att applicera statistiska koncept från nätverksteori såsom gradfördelning och genomsnittlig väg för att visa nätverkets egenskaper. Målet med den statistiska undersökningen är utforska nätverkets robusthet och besvara frågan om nätverket är så kallad scale-free. Studien jämför även resultaten med resultat från tidigare studier med liknande undersökningar.   Resultaten indikerar att det kan ha blivit en förändring i avseende på nätverkets struktur sedan den tidigare omfattande studien genomfördes, förmodligen orsakat av ändringar i webdesign. Trots det så indikerar resultaten att nätverket fortfarande har egenskaper typiska för ett scale-free nätverk. På grund av oregelbundenhet i spindeln så kan resultaten vara smått opålitliga.

<p>Individual proteins, and small collections of proteins, have been extensively studied for at least two hundred years. Today, more than 350 genomes have been completely sequenced and the proteomes of these genomes have been at least partially mapped. The inventory of protein coding genes is the first step toward understanding the cellular machinery. Recent studies have generated a comprehensive data set for the physical interactions between the proteins of <i>Saccharomyces cerevisiae</i>, in addition to some less extensive proteome interaction maps of higher eukaryotes. Hence, it is now becoming feasible to investigate important questions regarding the evolution of protein-protein networks. For instance, what is the evolutionary relationship between proteins that interact, directly or indirectly? Do interacting proteins co-evolve? Are they often derived from each other? In order to perform such proteome-wide investigations, a top-down view is necessary. This is provided by network (or graph) theory.</p><p>The proteins of the cell may be viewed as a community of individual molecules which together form a society of proteins (nodes), a network, where the proteins have various kinds of relationships (edges) to each other. There are several different types of protein networks, for instance the two networks studied here, namely metabolic networks and protein-protein interaction networks. The metabolic network is a representation of metabolism, which is defined as the sum of the reactions that take place inside the cell. These reactions often occur through the catalytic activity of enzymes, representing the nodes, connected to each other through substrate/product edges. The indirect interactions of metabolic enzymes are clearly different in nature from the direct physical interactions, which are fundamental to most biological processes, which constitute the edges in protein-protein interaction networks.</p><p>This thesis describes three investigations into the evolution of metabolic and protein-protein interaction networks. We present a comparative study of the importance of retrograde evolution, the scenario that pathways assemble backward compared to the direction of the pathway, and patchwork evolution, where enzymes evolve from a broad to narrow substrate specificity. Shifting focus toward network topology, a suggested mechanism for the evolution of biological networks, preferential attachment, is investigated in the context of metabolism. Early in the investigation of biological networks it seemed clear that the networks often display a particular, 'scale-free', topology. This topology is characterized by many nodes with few interaction partners and a few nodes (hubs) with a large number of interaction partners. While the second paper describes the evidence for preferential attachment in metabolic networks, the final paper describes the characteristics of the hubs in the physical interaction network of <i>S. cerevisiae</i>.</p>

Barabási-Albert random graph models are a class of evolving random graphs that are frequently used to model social networks with scale-free degree distributions. It has been shown that Barabási-Albert random graph models have asymptotic scale-free degree distributions as the size of the graph tends to infinity. Real world networks, however, have finite size so it is important to know how close the degree distribution of a Barabási-Albert random graph of a given size is to its asymptotic distribution. Stein’s method is chosen as one main method for obtaining explicit bounds for the distance between distributions. We derive a new version of Stein’s method for a class of scale-free distributions and apply the method to a Barabási-Albert random graph. We compare the evolution of a sequence of Barabási-Albert random graphs with continuous time stochastic processes motivated by Yule’s model for evolution. Through a coupling of the models we bound the total variation distance between their degree distributions. Using these bounds, we extend degree distribution bounds that we find for specific models within the scheme to find bounds for every member of the scheme. We apply the Azuma-Hoeffding inequality and Chernoff bounds to find bounds between the degree sequences of the random graph models and the given scale-free distribution. These bounds prove that the degree sequences converge completely (and therefore also converge almost surely) to our scale-free distribution. We discuss the relationship between the random graph processes and the Chinese restaurant process. Aided by the construction of an inhomogeneous Markov chain, we apply our results for the degree distribution in a Barabási-Albert random graph to a particular statistic of the Chinese restaurant process. Finally, we explore how our methods can be adapted and extended to other evolving random graph processes. We study a Bernoulli evolving random graph process, for which we bound the distance between its degree distribution and a geometric distribution and we bound the distance between the number of triangles in the graph and a normal distribution.

Many processes and systems in nature and society can be characterized as large numbers of discrete elements that are (usually non-uniformly) interrelated. These networks were long thought to be random, but in the late 1990s, Barabási and Albert found that an underlying structure did in fact exist in many natural and technological networks that are now referred to as scale free. Since then, researchers have gained a much deeper understanding of this particular form of complexity, largely by combining graph theory, statistical physics, and advances in computing technology. This dissertation focuses on out-of-equilibrium dynamic processes as they unfold on these complex networks. Diffusion in networks of non-interacting nodes is shown to be temporally complex, while equilibrium is represented by a stable state with Poissonian fluctuations. Scale free networks achieve equilibrium very quickly compared to regular networks, and the most efficient are those with the lowest inverse power law exponent. Temporally complex diffusion also occurs in networks with interacting nodes under a cooperative decision-making model. At a critical value of the cooperation parameter, the most efficient scale free network achieves consensus almost as quickly as the equivalent all-to-all network. This finding suggests that the ubiquity of scale free networks in nature is due to Zipf's principle of least effort. It also suggests that an efficient scale free network structure may be optimal for real networks that require high connectivity but are hampered by high link costs.

Respondent-driven sampling (RDS) is very useful in collecting data from individuals in hidden populations, where a sampling frame does not exist. It starts with researchers choosing initial respondents from a group which may be involved in taboo or illegal activities, after which they recruit other peers who belong to the same group. Analysis results in unbiased estimates of population proportions though with strong assumptions about the underlying social network and RDS recruitment process. These assumptions bear little resemblance to reality, and thus compromise the estimation of any means, population proportions or variances inferred from studies. The topology of the contact network, denoted by the number of links each person has, provides insight into the processes of infectious disease spread. The overall objective of the thesis is to identify the topology of an injection drug use network, and critically review the methods developed to produce estimates. The topology of people who inject drugs (PWID) collected by RDS in Ottawa, 2006 was compared with a Poisson distribution, an exponential distribution, a power-law distribution, and a lognormal distribution. The contact distribution was then evaluated against a small-world network characterized by high clustering and low average distances between individuals. Last a systematic review of the methods used to produce RDS mean and variance estimates was conducted. The Poisson distribution, a type of random distribution, was not an appropriate fit for PWID network. However, the PWID network can be classified as a small world network organised with many connections and short distances between people. Prevention of transmission in such networks should be focussed on the most active people (clustered individuals and hubs) as intervention with any others is less effective. The systematic review contained 32 articles which included the development and evaluation of 12 RDS mean and 6 variance estimators. Overall, the majority of estimators perform roughly the same, with the exception of RDSIEGO which outperformed the 6 other RDS mean estimators. The Tree bootstrap variance estimate does not rely on modelling RDS as a first order Markov (FOM) process, which seems to be the main limitation of the other existing estimators. The lack of FOM as an assumption and the flexible application of this variance estimator to any RDS point estimate make the Tree bootstrapping estimator a more efficient choice.

The study of complex networks presented a huge development in last decades. In this dissertation we want to analyze the epidemic spread in scale-free networks through the Susceptible - Infected - Susceptible (SIS) model. We review the fundamental concepts to describe complex networks and the classical epidemiological models. We implement an algorithm that produces a scale-free network and explore the Quenched Mean-Field (QMF) dynamics in a scale-free network. Moreover, we simulate a change on the topology of the network according to the states of the nodes, and it generates a positive epidemic threshold. We show analytically that the fraction of infected vertices follows a power-law distribution in the vicinity of this critical point / O estudo de redes complexas tem se desenvolvido muito nos últimos anos. Nesta dissertação queremos analisar o processo de propagação de epidemia em redes livres de escala através do modelo Suscetível - Infectado - Suscetível (SIS). Apresentamos uma revisão de redes e as principais características dos modelos epidemiológicos clássicos. Implementamos um algoritmo que produz uma rede livre de escala dado um expoente e exploramos a dinâmica do modelo Quenched Mean-Field (QMF) inserido em uma rede livre de escala. Além disso, foi simulada uma possível alteração na topologia da rede, devido aos estados dos vértices infectados, que gerou um limiar epidêmico positivo no modelo e a probabilidade de vértices infectados seguiu uma lei de potência na vizinhança desse ponto crítico

The study of complex networks presented a huge development in last decades. In this dissertation we want to analyze the epidemic spread in scale-free networks through the Susceptible - Infected - Susceptible (SIS) model. We review the fundamental concepts to describe complex networks and the classical epidemiological models. We implement an algorithm that produces a scale-free network and explore the Quenched Mean-Field (QMF) dynamics in a scale-free network. Moreover, we simulate a change on the topology of the network according to the states of the nodes, and it generates a positive epidemic threshold. We show analytically that the fraction of infected vertices follows a power-law distribution in the vicinity of this critical point / O estudo de redes complexas tem se desenvolvido muito nos últimos anos. Nesta dissertação queremos analisar o processo de propagação de epidemia em redes livres de escala através do modelo Suscetível - Infectado - Suscetível (SIS). Apresentamos uma revisão de redes e as principais características dos modelos epidemiológicos clássicos. Implementamos um algoritmo que produz uma rede livre de escala dado um expoente e exploramos a dinâmica do modelo Quenched Mean-Field (QMF) inserido em uma rede livre de escala. Além disso, foi simulada uma possível alteração na topologia da rede, devido aos estados dos vértices infectados, que gerou um limiar epidêmico positivo no modelo e a probabilidade de vértices infectados seguiu uma lei de potência na vizinhança desse ponto crítico

Individual proteins, and small collections of proteins, have been extensively studied for at least two hundred years. Today, more than 350 genomes have been completely sequenced and the proteomes of these genomes have been at least partially mapped. The inventory of protein coding genes is the first step toward understanding the cellular machinery. Recent studies have generated a comprehensive data set for the physical interactions between the proteins of Saccharomyces cerevisiae, in addition to some less extensive proteome interaction maps of higher eukaryotes. Hence, it is now becoming feasible to investigate important questions regarding the evolution of protein-protein networks. For instance, what is the evolutionary relationship between proteins that interact, directly or indirectly? Do interacting proteins co-evolve? Are they often derived from each other? In order to perform such proteome-wide investigations, a top-down view is necessary. This is provided by network (or graph) theory. The proteins of the cell may be viewed as a community of individual molecules which together form a society of proteins (nodes), a network, where the proteins have various kinds of relationships (edges) to each other. There are several different types of protein networks, for instance the two networks studied here, namely metabolic networks and protein-protein interaction networks. The metabolic network is a representation of metabolism, which is defined as the sum of the reactions that take place inside the cell. These reactions often occur through the catalytic activity of enzymes, representing the nodes, connected to each other through substrate/product edges. The indirect interactions of metabolic enzymes are clearly different in nature from the direct physical interactions, which are fundamental to most biological processes, which constitute the edges in protein-protein interaction networks. This thesis describes three investigations into the evolution of metabolic and protein-protein interaction networks. We present a comparative study of the importance of retrograde evolution, the scenario that pathways assemble backward compared to the direction of the pathway, and patchwork evolution, where enzymes evolve from a broad to narrow substrate specificity. Shifting focus toward network topology, a suggested mechanism for the evolution of biological networks, preferential attachment, is investigated in the context of metabolism. Early in the investigation of biological networks it seemed clear that the networks often display a particular, 'scale-free', topology. This topology is characterized by many nodes with few interaction partners and a few nodes (hubs) with a large number of interaction partners. While the second paper describes the evidence for preferential attachment in metabolic networks, the final paper describes the characteristics of the hubs in the physical interaction network of S. cerevisiae.

Wealth distribution is an important issue in Economics, especially wealth inequality. There are no absolutely perfect solutions to this issue long times ago. Despite we are in 21 century, the situation are getting worse and hard to resolve. We focus on developing an agent simulation model based on Evolutionary game and Scale-free network. From this model, we observed some phenomena in wealth distribution by changing the network structure. And we experiments 5 strategies to increase the connectivity of agents in network, which increasing the edges to fully-connected network or increasing the edges between two different groups. After these experiments, we find that the increasing of connectivity in the network is positive to the agents¡¦ wealth accumulation which means we build more relationship with the other people is benefit to our wealth accumulation. Furthermore, we divide the agents in the simulation to three groups: the poor, the middle class and the rich. In the group simulation, we find that increasing the connectivity inside the poor group is the best way to decrease the Gini coefficient and wealth inequality.