 # Network Model Estimation Based on Linearity of Expectation and Randomization

Subject Computer Science Data Structures and Algorithms

## Question

A number of peer-to-peer systems on the internet are based on overlay networks.
Rather than using the physical internet as the network on which to perform computation, these systems run protocols by which nodes choose collections of virtual “neighbors” so as to define a higher-level graph whose structure may bear little or no relation to the underlying physical network.
Such an overlay network is then used for sharing data and services, and it can be extremely flexible compared with a physical network, which is hard to modify in real time to adapt to changing conditions.
Peer-to-peer networks tend to grow through the arrival of new participants who join by linking into the existing structure.
This growth process has an intrinsic effect on the characteristics of the overall network.
Recently, people have investigated simple abstract models for network growth that might provide insight into the way such processes behave in real networks at a qualitative level.
Here is a simple example of such a model:
The system begins with a single node v1.
Nodes then join one at a time; as each node joins, it executes a protocol whereby it forms a directed link to a single other node chosen uniformly at random from those already in the system.
More concretely, if the system already contains nodes v1, v2, . . . , vk−1 and node vk wishes to join, it randomly selects one of v1, v2, . . . , vk−1 and links to that node.
Suppose we run this process until we have a system consisting of nodes v1, v2, . . . , vn; the random process described above will produce a directed network in which each node other than v1 has exactly one outgoing edge.
On the other hand, a node may have multiple incoming links, or none at all.
The incoming links to a node vj reflect all the other nodes whose access into the system is via vj ; so if vj has many incoming links, this can place a large load on it.
Then to keep the system load-balanced, we would like all nodes to have a roughly comparable number of incoming links.
That is unlikely to happen, however, since nodes that join earlier in the process are likely to have more incoming links than nodes that join later.
Let us try to quantify this imbalance as follows:
(a) Given the random process described above, what is the expected number of incoming links to node vj in the resulting network? Give an exact formula in terms of n and j, and also try to express this quantity asymptotically using Θ notation.
(b) Part (a) makes precise a sense in which the nodes that arrive early carry an “unfair” share of the connections in the network.
Another way to quantify the imbalance is to observe that, in a run of this random process, we expect many nodes to end up with no incoming links.
Give a formula for the expected number of nodes with no incoming links in a network grown randomly according to this model.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

1. a) If we consider Incoming(j) the amount of incoming links for the node vj, then we have the following relation that relates this amount to the number of incoming links between the node vj and the remaining nodes (vj+1, vj+2,….vn):
Incoming(j)=Incoming(j,j+1)+Incoming(j,j+2)…..+Incoming(j,n-1)+Incoming(j,n).
It is straightforward that for any k=j+1,n we have Incoming(j,k)=1 when vk connects to vj and Incoming(j,k)=0 when vk doesn’t connect to vj (as per problem statement).
Also per problem hypothesis, because vj randomly uniform chooses a single node among the set {v1,v2,….,vj-1} to connect => expected probability for Incoming(j,k)=1/(k-1) for any k>j....

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

Computer Science - Algorithm Assignment \$25.00
Algorithm
Computer Science
Dynamic Programming
Longest Increasing Subsequence
Array
Trees and Hashing Code Related Questions. Hashcode C++ Implementation \$33.00
Tree
Hash
C++
BST
Binary
Search
Node
AVL
Code
Table
Collision
Key
Balanced
Structure
Data
Value
Property
Computer
Science
Two Dynamic Programming Algorithms: Rod Cutting & Minimum Number of Coins Change \$18.00
Dynamic
Programming
Algorithm
Complexity
Recurrence
Rod
Cut
Coin
Change
Amount
Integer
Denomination
Pseudocode
Maximum
DP
Sale
Unit
Piece
Price
Table
Bottom-up
Example
Analysis
Base
Case
Algorithm Analysis, Correctness and Sorted Linked List Algorithm \$10.00
Algorithm
List
Loop
Invariant
Worst
Case
Analysis
Complexity
Correctness
Ascending
Initialization
Maintenance
Termination
Arrays, Linked Lists, Queue and Stack Data Structures in C++ \$40.00
Algorithm
Array
List
Queue
Stack
Data
Structure
C++
Singly
Doubly
Prototype
Template
Function
Computer
Science
Live Chats