Página 1 dos resultados de 79 itens digitais encontrados em 0.006 segundos

Statistical analysis and modeling of optical transport networks; Análise estatística e modelação de redes óticas de transporte

Routray, Sudhir Kumar
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Tese de Doutorado
ENG
Relevância na Pesquisa
66.59%
Statistical analysis and modeling of networks is now an integral part of network science and engineering. In case of optical transport networks (OTNs), it can be used for the planning and dimensioning when the complete information is not available or is difficult to process. The core networks around the world today are almost optical and they form the backbone of the Internet. Therefore, the statistical characteristics of these networks must be studied to understand their nature and to estimate their parameters. In science and technology, network analysis and modeling are used for several purposes such as the analysis of their stability, reliability and long term evolution. Knowledge of the statistical models helps in the estimation of several critical parameters of the networks. The work presented in this thesis is focused on the analysis and modeling of link lengths and shortest path lengths in OTNs. The parameters used in the models presented in this thesis can be estimated from the very basic information of the networks such as the coverage area and the number of nodes, both of which can be found from the node locations. These models can be applied to estimate key parameters of the networks. In this thesis, we have shown that the link lengths of the OTNs follow general extreme value distribution. The parameters of the proposed distribution can be estimated from the average link lengths of the networks. We develop expressions for the average link lengths of OTNs which can be estimated with an average error of just 11%. We apply the developed model to estimate link length dependent parameters in OTNs. We show that the shortest path lengths of the OTNs follow Johnson SB distribution. We estimate the parameters of the developed model from the convex area and the number of nodes of the network. We also apply this model to estimate several shortest path-dependent parameters in OTNs.; A análise estatística e modelação de redes é atualmente uma parte integrante da ciência e engenharia de redes. No caso das redes óticas de transporte (OTN)...

Local-Based Semantic Navigation on a Networked Representation of Information

Capitán, José A.; Borge-Holthoefer, Javier; Gómez, Sergio; Martinez-Romo, Juan; Araujo, Lourdes; Cuesta, José A.; Arenas, Alex
Fonte: Public Library of Science Publicador: Public Library of Science
Tipo: Artigo de Revista Científica
Publicado em 24/08/2012 EN
Relevância na Pesquisa
36.18%
The size and complexity of actual networked systems hinders the access to a global knowledge of their structure. This fact pushes the problem of navigation to suboptimal solutions, one of them being the extraction of a coherent map of the topology on which navigation takes place. In this paper, we present a Markov chain based algorithm to tag networked terms according only to their topological features. The resulting tagging is used to compute similarity between terms, providing a map of the networked information. This map supports local-based navigation techniques driven by similarity. We compare the efficiency of the resulting paths according to their length compared to that of the shortest path. Additionally we claim that the path steps towards the destination are semantically coherent. To illustrate the algorithm performance we provide some results from the Simple English Wikipedia, which amounts to several thousand of pages. The simplest greedy strategy yields over an 80% of average success rate. Furthermore, the resulting content-coherent paths most often have a cost between one- and threefold compared to shortest-path lengths.

Spreading and shortest paths in systems with sparse long-range connections

Moukarzel, Cristian F.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/05/1999
Relevância na Pesquisa
46.5%
Spreading according to simple rules (e.g. of fire or diseases), and shortest-path distances are studied on d-dimensional systems with a small density p per site of long-range connections (``Small-World'' lattices). The volume V(t) covered by the spreading quantity on an infinite system is exactly calculated in all dimensions. We find that V(t) grows initially as t^d/d for t<< t^* = (2p \Gamma_d (d-1)!)^{-1/d} and later exponentially for $t>>t^*$, generalizing a previous result in one dimension. Using the properties of V(t), the average shortest-path distance \ell(r) can be calculated as a function of Euclidean distance r. It is found that \ell(r) = r for rr_c. The characteristic length r_c, which governs the behavior of shortest-path lengths, diverges with system size for all p>0. Therefore the mean separation s \sim p^{-1/d} between shortcut-ends is not a relevant internal length-scale for shortest-path lengths. We notice however that the globally averaged shortest-path length, divided by L, is a function of L/s only.; Comment: 4 pages, 1 eps fig. Uses psfig

Pair Connectedness and Shortest Path Scaling in Critical Percolation

Grassberger, P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/06/1999
Relevância na Pesquisa
56.13%
We present high statistics data on the distribution of shortest path lengths between two near-by points on the same cluster at the percolation threshold. Our data are based on a new and very efficient algorithm. For $d=2$ they clearly disprove a recent conjecture by M. Porto et al., Phys. Rev. {\bf E 58}, R5205 (1998). Our data also provide upper bounds on the probability that two near-by points are on different infinite clusters.; Comment: 7 pages, including 4 postscript figures

Shortest paths on systems with power-law distributed long-range connections

Moukarzel, Cristian F.; de Menezes, Marcio Argollo
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/01/2002
Relevância na Pesquisa
46.35%
We discuss shortest-path lengths $\ell(r)$ on periodic rings of size L supplemented with an average of pL randomly located long-range links whose lengths are distributed according to $P_l \sim l^{-\xpn}$. Using rescaling arguments and numerical simulation on systems of up to $10^7$ sites, we show that a characteristic length $\xi$ exists such that $\ell(r) \sim r$ for $r<\xi$ but $\ell(r) \sim r^{\theta_s(\xpn)}$ for $r>>\xi$. For small p we find that the shortest-path length satisfies the scaling relation $\ell(r,\xpn,p)/\xi = f(\xpn,r/\xi)$. Three regions with different asymptotic behaviors are found, respectively: a) $\xpn>2$ where $\theta_s=1$, b) $1<\xpn<2$ where $0<\theta_s(\xpn)<1/2$ and, c) $\xpn<1$ where $\ell(r)$ behaves logarithmically, i.e. $\theta_s=0$. The characteristic length $\xi$ is of the form $\xi \sim p^{-\nu}$ with $\nu=1/(2-\xpn)$ in region b), but depends on L as well in region c). A directed model of shortest-paths is solved and compared with numerical results.; Comment: 10 pages, 10 figures, revtex4. Submitted to PRE

Scaling limits for shortest path lengths along the edges of stationary tessellations - Supplementary material

Voss, Florian; Gloaguen, Catherine; Schmidt, Volker
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/12/2009
Relevância na Pesquisa
56.32%
We consider spatial stochastic models, which can be applied e.g. to telecommunication networks with two hierarchy levels. In particular, we consider two Cox processes concentrated on the edge set of a random tessellation, where the points can describe the locations of low-level and high-level network components, respectively, and the edge set the underlying infrastructure of the network, like road systems, railways, etc. Furthermore, each low-level component is marked with the shortest path along the edge set to the nearest high-level component. We investigate the typical shortest path length of the resulting marked point process, which is an important characteristic e.g. in performance analysis and planning of telecommunication networks. In particular, we show that its distribution converges to simple parametric limit distributions if a certain scaling factor converges to zero and infinity, respectively. This can be used to approximate the density of the typical shortest path length by analytical formulae.

An Estimation of the Shortest and Largest Average Path Length in Graphs of Given Density

Gulyás, László; Horváth, Gábor; Cséri, Tamás; Kampis, George
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/01/2011
Relevância na Pesquisa
36.26%
Many real world networks (graphs) are observed to be 'small worlds', i.e., the average path length among nodes is small. On the other hand, it is somewhat unclear what other average path length values networks can produce. In particular, it is not known what the maximum and the minimum average path length values are. In this paper we provide a lower estimation for the shortest average path length (l) values in connected networks, and the largest possible average path length values in networks with given size and density. To the latter end, we construct a special family of graphs and calculate their average path lengths. We also demonstrate the correctness of our estimation by simulations.

Degree distribution of shortest path trees and bias of network sampling algorithms

Bhamidi, Shankar; Goodman, Jesse; van der Hofstad, Remco; Komjáthy, Júlia
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.37%
In this article, we explicitly derive the limiting degree distribution of the shortest path tree from a single source on various random network models with edge weights. We determine the asymptotics of the degree distribution for large degrees of this tree and compare it to the degree distribution of the original graph. We perform this analysis for the complete graph with edge weights that are powers of exponential random variables (weak disorder in the stochastic mean-field model of distance), as well as on the configuration model with edge-weights drawn according to any continuous distribution. In the latter, the focus is on settings where the degrees obey a power law, and we show that the shortest path tree again obeys a power law with the same degree power-law exponent. We also consider random $r$-regular graphs for large $r$, and show that the degree distribution of the shortest path tree is closely related to the shortest path tree for the stochastic mean-field model of distance. We use our results to shed light on an empirically observed bias in network sampling methods. This is part of a general program initiated in previous works by Bhamidi, van der Hofstad and Hooghiemstra [Ann. Appl. Probab. 20 (2010) 1907-1965], [Combin. Probab. Comput. 20 (2011) 683-707]...

A Note on the Unsolvability of the Weighted Region Shortest Path Problem

De Carufel, Jean-Lou; Grimm, Carsten; Maheshwari, Anil; Owen, Megan; Smid, Michiel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/05/2013
Relevância na Pesquisa
46.28%
Let S be a subdivision of the plane into polygonal regions, where each region has an associated positive weight. The weighted region shortest path problem is to determine a shortest path in S between two points s, t in R^2, where the distances are measured according to the weighted Euclidean metric-the length of a path is defined to be the weighted sum of (Euclidean) lengths of the sub-paths within each region. We show that this problem cannot be solved in the Algebraic Computation Model over the Rational Numbers (ACMQ). In the ACMQ, one can compute exactly any number that can be obtained from the rationals Q by applying a finite number of operations from +, -, \times, \div, \sqrt[k]{}, for any integer k >= 2. Our proof uses Galois theory and is based on Bajaj's technique.; Comment: 6 pages, 1 figure

A linear time algorithm for the next-to-shortest path problem on undirected graphs with nonnegative edge lengths

Wu, Bang Ye; Guo, Jun-Lin; Wang, Yue-Li
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/03/2012
Relevância na Pesquisa
46.39%
For two vertices $s$ and $t$ in a graph $G=(V,E)$, the next-to-shortest path is an $st$-path which length is minimum amongst all $st$-paths strictly longer than the shortest path length. In this paper we show that, when the graph is undirected and all edge lengths are nonnegative, the problem can be solved in linear time if the distances from $s$ and $t$ to all other vertices are given. This result generalizes the previous work (DOI 10.1007/s00453-011-9601-7) to allowing zero-length edges.

Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks

Bauckhage, Christian; Kersting, Kristian; Hadiji, Fabian
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 17/01/2015
Relevância na Pesquisa
46.28%
Properties of networks are often characterized in terms of features such as node degree distributions, average path lengths, diameters, or clustering coefficients. Here, we study shortest path length distributions. On the one hand, average as well as maximum distances can be determined therefrom; on the other hand, they are closely related to the dynamics of network spreading processes. Because of the combinatorial nature of networks, we apply maximum entropy arguments to derive a general, physically plausible model. In particular, we establish the generalized Gamma distribution as a continuous characterization of shortest path length histograms of networks or arbitrary topology. Experimental evaluations corroborate our theoretical results.

Optimization of transport protocols with path-length constraints in complex networks

Ramasco, Jose J.; de la Lama, Marta S.; Lopez, Eduardo; Boettcher, Stefan
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/06/2010
Relevância na Pesquisa
36.23%
We propose a protocol optimization technique that is applicable to both weighted or unweighted graphs. Our aim is to explore by how much a small variation around the Shortest Path or Optimal Path protocols can enhance protocol performance. Such an optimization strategy can be necessary because even though some protocols can achieve very high traffic tolerance levels, this is commonly done by enlarging the path-lengths, which may jeopardize scalability. We use ideas borrowed from Extremal Optimization to guide our algorithm, which proves to be an effective technique. Our method exploits the degeneracy of the paths or their close-weight alternatives, which significantly improves the scalability of the protocols in comparison to Shortest Paths or Optimal Paths protocols, keeping at the same time almost intact the length or weight of the paths. This characteristic ensures that the optimized routing protocols are composed of paths that are quick to traverse, avoiding negative effects in data communication due to path-length increases that can become specially relevant when information losses are present.; Comment: 8 pages, 8 figures

Fractal Behavior of the Shortest Path Between Two Lines in Percolation Systems

Paul, Gerald; Havlin, Shlomo; Stanley, H. Eugene
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/03/2002
Relevância na Pesquisa
46.13%
Using Monte-Carlo simulations, we determine the scaling form for the probability distribution of the shortest path, $\ell$, between two lines in a 3-dimensional percolation system at criticality; the two lines can have arbitrary positions, orientations and lengths. We find that the probability distributions can exhibit up to four distinct power law regimes (separated by cross-over regimes) with exponents depending on the relative orientations of the lines. We explain this rich fractal behavior with scaling arguments.; Comment: Figures are low resolution and are best viewed when printed

Faster Shortest Paths in Dense Distance Graphs, with Applications

Mozes, Shay; Nussbaum, Yahav; Weimann, Oren
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/04/2014
Relevância na Pesquisa
36.34%
We show how to combine two techniques for efficiently computing shortest paths in directed planar graphs. The first is the linear-time shortest-path algorithm of Henzinger, Klein, Subramanian, and Rao [STOC'94]. The second is Fakcharoenphol and Rao's algorithm [FOCS'01] for emulating Dijkstra's algorithm on the dense distance graph (DDG). A DDG is defined for a decomposition of a planar graph $G$ into regions of at most $r$ vertices each, for some parameter $r < n$. The vertex set of the DDG is the set of $\Theta(n/\sqrt r)$ vertices of $G$ that belong to more than one region (boundary vertices). The DDG has $\Theta(n)$ arcs, such that distances in the DDG are equal to the distances in $G$. Fakcharoenphol and Rao's implementation of Dijkstra's algorithm on the DDG (nicknamed FR-Dijkstra) runs in $O(n\log(n) r^{-1/2} \log r)$ time, and is a key component in many state-of-the-art planar graph algorithms for shortest paths, minimum cuts, and maximum flows. By combining these two techniques we remove the $\log n$ dependency in the running time of the shortest-path algorithm, making it $O(n r^{-1/2} \log^2r)$. This work is part of a research agenda that aims to develop new techniques that would lead to faster, possibly linear-time, algorithms for problems such as minimum-cut...

Average path length for Sierpinski pentagon

Peng, Junhao; Xu, Guoai
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.08%
In this paper,we investigate diameter and average path length(APL) of Sierpinski pentagon based on its recursive construction and self-similar structure.We find that the diameter of Sierpinski pentagon is just the shortest path lengths between two nodes of generation 0. Deriving and solving the linear homogenous recurrence relation the diameter satisfies, we obtain rigorous solution for the diameter. We also obtain approximate solution for APL of Sierpinski pentagon, both diameter and APL grow approximately as a power-law function of network order $N(t)$, with the exponent equals $\frac{\ln(1+\sqrt{3})}{\ln(5)}$. Although the solution for APL is approximate,it is trusted because we have calculated all items of APL accurately except for the compensation($\Delta_{t}$) of total distances between non-adjacent branches($\Lambda_t^{1,3}$), which is obtained approximately by least-squares curve fitting. The compensation($\Delta_{t}$) is only a small part of total distances between non-adjacent branches($\Lambda_t^{1,3}$) and has little effect on APL. Further more,using the data obtained by iteration to test the fitting results, we find the relative error for $\Delta_{t}$ is less than $10^{-7}$, hence the approximate solution for average path length is almost accurate.; Comment: 12pages...

Fractal Structure of Shortest Interaction Paths in Native Proteins and Determination of Residues on a Given Shortest Path

Erman, Burak
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.45%
Fractal structure of shortest paths depends strongly on interresidue interaction cutoff distance. The dimensionality of shortest paths is calculated as a function of interaction cutoff distance. Shortest paths are self similar with a fractal dimension of 1.12 when calculated with step lengths larger than 6.8 {\AA}. Paths are multifractal below 6.8 {\AA}. The number of steps to traverse a shortest path is a discontinuous function of cutoff size at short cutoff values, showing abrupt decreases to smaller values as cutoff distance increases. As information progresses along the direction of a shortest path a large set of residues are affected because they are interacting neighbors to the residues of the shortest path. Thus, several residues are involved diffusively in information transport which may be identified with the present model. An algorithm is introduced to determine the residues of a given shortest path. The shortest path residues are the highly visited residues during information transport. These paths are shown to lie on the high entropy landscape of the protein where entropy is taken to increase with abundance of visits to nodes during signal transport.

A simpler and more efficient algorithm for the next-to-shortest path problem

Wu, Bang Ye
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 03/05/2011
Relevância na Pesquisa
46.39%
Given an undirected graph $G=(V,E)$ with positive edge lengths and two vertices $s$ and $t$, the next-to-shortest path problem is to find an $st$-path which length is minimum amongst all $st$-paths strictly longer than the shortest path length. In this paper we show that the problem can be solved in linear time if the distances from $s$ and $t$ to all other vertices are given. Particularly our new algorithm runs in $O(|V|\log |V|+|E|)$ time for general graphs, which improves the previous result of $O(|V|^2)$ time for sparse graphs, and takes only linear time for unweighted graphs, planar graphs, and graphs with positive integer edge lengths.; Comment: Partial result appeared in COCOA2010

A New Notion of Path Length in the Plane

Hoehn, L. C.; Oversteegen, L. G.; Tymchatyn, E. D.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 25/01/2013
Relevância na Pesquisa
36.26%
A path in the plane is a continuous function $\gamma$ from the unit interval into the plane. The Euclidean length of a path in the plane, when defined, has the following properties: it is invariant under isometries of the plane, it is monotone with respect to subpaths, and for any two points in the plane the path mapping homeomorphically onto the straight line segment joining them is the unique, nowhere constant path (up to homeomorphism) of minimal length connecting them. However, the Euclidean length does not behave well with respect to limits -- even when a sequence of paths $\gamma_i$ converges uniformly to a path $\gamma$ it is not necessarily true that their lengths converge. Moreover, for many paths the Euclidean length is not defined (i.e.\ not finite). In this paper we introduce an alternative notion of length of a path, $\length$, which has the above three properties, and is such that the length of any path is defined and finite. This enables one to compare the efficiency (shortness) of two paths between a given pair of points, even if their Euclidean lengths are infinite. In addition, if a sequence of paths $\gamma_i$ converges uniformly to a path $\gamma$, them $\lim \length(\gamma_i) = \length(\gamma)$. Moreover, this notion of length is defined for any map $\gamma$ from a locally connected continuum into the plane. We apply this notion of length to obtain a characterization of those families of paths which can be reparameterized to be equicontinuous. We also prove the existence of a unique shortest path in the closure of a given homotopy class of paths in an arbitrary plane domain...

Analytical results for the distribution of shortest path lengths in random networks

Katzav, Eytan; Nitzan, Mor; ben-Avraham, Daniel; Krapivsky, P. L.; Kühn, Reimer; Ross, Nathan; Biham, Ofer
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
66.42%
We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-R\'enyi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as $N^{\alpha}$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance $d=\lfloor 1/\alpha \rfloor$ from each other. The distribution of shortest path lengths between nodes of degree $m$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of $m$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.; Comment: 12 pages, 4 figures, accepted to EPL

The Complexity of Rerouting Shortest Paths

Bonsma, Paul
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.19%
The Shortest Path Reconfiguration problem has as input a graph G (with unit edge lengths) with vertices s and t, and two shortest st-paths P and Q. The question is whether there exists a sequence of shortest st-paths that starts with P and ends with Q, such that subsequent paths differ in only one vertex. This is called a rerouting sequence. This problem is shown to be PSPACE-complete. For claw-free graphs and chordal graphs, it is shown that the problem can be solved in polynomial time, and that shortest rerouting sequences have linear length. For these classes, it is also shown that deciding whether a rerouting sequence exists between all pairs of shortest st-paths can be done in polynomial time. Finally, a polynomial time algorithm for counting the number of isolated paths is given.; Comment: The results on claw-free graphs, chordal graphs and isolated paths have been added in version 2 (april 2012). Version 1 (September 2010) only contained the PSPACE-hardness result. (Version 2 has been submitted.)