Degree Distribution (degree + distribution)

Distribution by Scientific Domains


Selected Abstracts


An analytic model for the behavior of arbitrary peer-to-peer networks

EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS, Issue 6 2004
Rüdiger Schollmeier
We present an analytic approach to better understand and design peer-to-peer (P2P) networks, which are becoming increasingly important, as they contribute an amount of traffic often dominating the total traffic in the internet even today. We start from a graph theoretical approach for infinite random networks and enhance that to include the effects of a finite network. Our approach is valid for an arbitrary degree distribution in the network and thus avoids the need for extensive simulation, which would otherwise be required to evaluate the performance of a specific P2P protocol. Our analytic approach can thus be used for improved tailoring of P2P communication as well as to minimize the often excessive signaling traffic. Copyright © 2004 AEI [source]


Topology and Dependency Tests in Spatial and Network Autoregressive Models

GEOGRAPHICAL ANALYSIS, Issue 2 2009
Steven Farber
Social network analysis has been identified as a promising direction for further applications of spatial statistical and econometric models. The type of network analysis envisioned is formally identical to the analysis of geographical systems, in that both involve the measurement of dependence between observations connected by edges that constitute a system. An important item, which has not been investigated in this context, is the potential relationship between the topology properties of networks (or network descriptions of geographical systems) and the properties of spatial models and tests. The objective of this article is to investigate, within a simulation setting, the ability of spatial dependency tests to identify a spatial/network autoregressive model when two network topology measures, namely degree distribution and clustering, are controlled. Drawing on a large data set of synthetically controlled social networks, the impact of network topology on dependency tests is investigated under a hierarchy of topology factors, sample size, and autocorrelation strength. In addition, topology factors are related to known properties of empirical systems. El análisis de redes sociales ha sido y es una dirección prometedora en el avance de las aplicaciones de modelos econométricos y de estadística espacial. El tipo de análisis de redes que proponemos es idéntico al análisis de sistemas geográficos, ya que ambos miden la dependencia entre observaciones conectadas que conforman un sistema. Un punto importante que no ha sido investigado en este contexto es la potencial relación entre las propiedades topológicas de redes (o descripción de redes de sistemas geográficos) y las propiedades de los modelos y pruebas (tests) espaciales. El objetivo de este artículo es investigar (dentro del marco de simulaciones Monte Carlo), la capacidad que poseen las pruebas de dependencia espacial para identificar un modelo autorregresivo espacial/de redes, en los casos en los que dos medidas topológicas de redes (grado de distribución y transitividad) son controlados. Haciendo uso de una base de datos de redes sociales controladas sintéticamente, este artículo evalúa el impacto de la topología de redes en las pruebas de dependencia espacial. Dicho impacto es evaluado con respecto a variaciones en los factores topológicos, el tamaño de muestra, y los niveles de autocorrelación espacial. Adicionalmente, los factores topológicos son relacionados a propiedades conocidas de varios sistemas empíricos. [source]


Network of sexual contacts and sexually transmitted HIV infection in Burkina Faso

JOURNAL OF MEDICAL VIROLOGY, Issue 6 2006
Vito Latora
Abstract Two thirds of the people who have been infected by human immunodeficiency virus (HIV) in the world live in Sub-Saharan African countries. The results of a study measuring the degree distribution of the network of sexual contacts in Burkina Faso are described. Such a network is responsible for the spread of sexually transmitted diseases, and in particular of HIV. It has been found that the number of different sexual partners reported by males is a power law distribution with an exponent ,,=,2.9 (0.1). This is consistent with the degree distribution of scale-free networks. On the other hand, the females can be divided into two groups: the prostitutes with an average of 400 different partners per year, and females with a stable partner, having a rapidly decreasing degree distribution. Such a result may have important implications on the control of sexually transmitted diseases and in particular of HIV. Since scale-free networks have no epidemic threshold, a campaign based on prevention and anti-viral treatment of few highly connected nodes can be more successful than any policy based on enlarged but random distribution of the available anti-viral treatments. J. Med. Virol. 78:724,729, 2006. © 2006 Wiley-Liss, Inc. [source]


USING NETWORK ANALYSIS TO CHARACTERIZE FOREST STRUCTURE

NATURAL RESOURCE MODELING, Issue 2 2008
MICHAEL M. FULLER
Abstract Network analysis quantifies different structural properties of systems of interrelated parts using a single analytical framework. Many ecological phenomena have network-like properties, such as the trophic relationships of food webs, geographic structure of metapopulations, and species interactions in communities. Therefore, our ability to understand and manage such systems may benefit from the use of network-analysis techniques. But network analysis has not been applied extensively to ecological problems, and its suitability for ecological studies is uncertain. Here, we investigate the ability of network analysis to detect spatial patterns of species association in a tropical forest. We use three common graph-theoretic measures of network structure to quantify the effect of understory tree size on the spatial association of understory species with trees in the canopy: the node degree distribution (NDD), characteristic path length (CPL), and clustering coefficient (CC). We compute the NDD, CPL, and CC for each of seven size classes of understory trees. For significance testing, we compare the observed values to frequency distributions of each statistic computed from randomized data. We find that the ability of network analysis to distinguish observed patterns from those representing randomized data strongly depends on which aspects of structure are investigated. Analysis of NDD finds no significant difference between random and observed networks. However, analysis of CPL and CC detected nonrandom patterns in three and one of the seven size classes, respectively. Network analysis is a very flexible approach that holds promise for ecological studies, but more research is needed to better understand its advantages and limitations. [source]


Random trees and general branching processes

RANDOM STRUCTURES AND ALGORITHMS, Issue 2 2007
Anna Rudas
Abstract We consider a tree that grows randomly in time. Each time a new vertex appears, it chooses exactly one of the existing vertices and attaches to it. The probability that the new vertex chooses vertex x is proportional to w(deg(x)), a weight function of the actual degree of x. The weight function w : , , ,+ is the parameter of the model. In 4 and 11 the authors derive the asymptotic degree distribution for a model that is equivalent to the special case, when the weight function is linear. The proof therein strongly relies on the linear choice of w. Using well-established results from the theory of general branching processes we give the asymptotical degree distribution for a wide range of weight functions. Moreover, we provide the asymptotic distribution of the tree itself as seen from a randomly selected vertex. The latter approach gives greater insight to the limiting structure of the tree. Our proof is robust and we believe that the method may be used to answer several other questions related to the model. It relies on the fact that considering the evolution of the random tree in continuous time, the process may be viewed as a general branching process, this way classical results can be applied. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007 [source]


The phase transition in inhomogeneous random graphs

RANDOM STRUCTURES AND ALGORITHMS, Issue 1 2007
Béla Bollobás
Abstract The "classical" random graph models, in particular G(n,p), are "homogeneous," in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power-law degree distributions. Thus there has been a lot of recent interest in defining and studying "inhomogeneous" random graph models. One of the most studied properties of these new models is their "robustness", or, equivalently, the "phase transition" as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is "what it should be"), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is "stable": for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3,122, 2007 [source]