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

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

Fonte: Universidade de Aveiro
Publicador: Universidade de Aveiro

Tipo: Tese de Doutorado

ENG

Relevância na Pesquisa

66.59%

#Engenharia electrotécnica#Redes de comunicação óptica#Análise estatística#Optical transport networks#statistical analysis#statistical modeling#link lengths#link length related parameters#shortest path lengths

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)...

Link permanente para citações:

## Local-Based Semantic Navigation on a Networked Representation of Information

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.

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 21/05/1999

Relevância na Pesquisa

46.5%

#Condensed Matter - Disordered Systems and Neural Networks#Condensed Matter - Soft Condensed Matter#Condensed Matter - Statistical Mechanics

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

Link permanente para citações:

## Pair Connectedness and Shortest Path Scaling in Critical Percolation

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

Link permanente para citações:

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

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

Link permanente para citações:

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

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.

Link permanente para citações:

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

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.

Link permanente para citações:

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

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]...

Link permanente para citações:

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

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

Link permanente para citações:

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

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.

Link permanente para citações:

## Maximum Entropy Models of Shortest Path and Outbreak Distributions in Networks

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.

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 03/06/2010

Relevância na Pesquisa

36.23%

#Physics - Physics and Society#Condensed Matter - Statistical Mechanics#Computer Science - Networking and Internet Architecture

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

Link permanente para citações:

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

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

Link permanente para citações:

## Faster Shortest Paths in Dense Distance Graphs, with Applications

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...

Link permanente para citações:

## Average path length for Sierpinski pentagon

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...

Link permanente para citações:

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

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.

Link permanente para citações:

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

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

Link permanente para citações:

## A New Notion of Path Length in the Plane

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...

Link permanente para citações:

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

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

Link permanente para citações:

## The Complexity of Rerouting Shortest Paths

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.)

Link permanente para citações: