Subject: Re: Path length Distribution in MANET

From: "J. Noel Chiappa" <[email-masked]>
Date: Mon, 5 Jun 2000 13:42:15 -0400

> From: "Charles E. Perkins" <[email-masked]>

    >>> 1) random graphs ... e.g., there exists a link between two nodes with
    >>> fixed probability p)

    >> when the number n of node get large (with p fixed) pair of nodes are at
    >> distance 1 with probability p, and distance 2 with probability 1-p.
    >> Other distance probabilities tend to zero (exponentially fast in n).
    >> Interesting things occurs when p=O(1/n) or p=O(1/sqrt(n)).
 
    > This seems like an impossible result, unless there is more to the
    > problem statement. For instance, if p==0, then surely P(distance==2)
    > == 0. If p==0.00000001, then P(distance=2) is not much larger than 0.
 
No, I think it might be correct - note the phrase "when N gets large". Even
if you have a low probability of connection to any given node, if there are a
very large set of nodes to chose from as an intermediate, the chance of at
least one two-hop path existing is pretty good.

Well, let's work it out. For a graph of N nodes, the probability of a direct
connection between nodes i and j is p. Now, considering two-hop paths, there
are N-2 potential intermediate nodes k (i.e. all the nodes in the graph,
except i and j). For any node k, the probability of a two-hop path through
that node is p^2, so the chance of a path through k not existing is 1-p^2,
and the probability that there is no k which is connected to both i and
j is (1-p^2)^(N-2). (And the probability that there is at least one would
be 1-that, of course...)

I've forgotten the math I'd need to take the limit of that as N goes to
infinity, but I'll bet the answer is just plain 0 (anything less than 1
multiplied by itself enough times gets vanishingly small). So, the chance that
a one-hop path does exist must be 1-0 == 1 (somewhat better than the stated
1-p, which makes no sense anyway - why would the probability go down as the
probabilty of a link goes up).

    > Besides, this problem statement places no geometric constraint. The two
    > nodes that are farthest apart are equally probable to have a link as
    > the two nodes closest together.

It's worse than that. By saying that the probabilty p of a link existing
between i and j is a fixed p, regardless of N, you're saying that the degree
D (i.e. number of connections) of any given node goes up at the same rate as
the network grows. This is extremely unlikely, physically; much better would
be a model with constant D.

I don't seem to recall much work on such graphs in my graph theory books on
random graphs, though (sigh). I do seem to recall a paper by Yakov on memory
requirements for BGP which indicated that the average path length in a graph
of degree D, as the graph grew, was O(ln(N)); and IIRC he had a cite to a
paper showing that.

	Noel

---

From: [email-masked]
Date: Fri, 09 Jun 2000 19:12:52 +0200

>be a model with constant D.

The problem with such models is that it is difficult to guarrantee that the
graph is connected, it may break in several isolated islands.

Philippe