AIT

1. Bootstrapping less comfortable

2. High traffic with delay and zigzag routes

3. Overlay topology not optimal

4. No not found message possible

1. Dynamic hierarchical layer with hub based network using superpeers (degree>>20) (the backbone network) and leafnodes (degree<7)

2. Leafnode-to-Superpeer // Request → superpeer

3. Superpeer-to-Superpeer // Request → superpeerS

Same as FRM

1. Asymmetric load on side of superpeers

2. Overlay topology not optimal // Hub structure contradicts physical network

3. High traffic with delay and zigzag routes

4. No not found message possible

1. Set of vertices and edges as graph, vectors, matrix

2. Clustering coefficient C(v) = 2*e(v)/deg(v)*(deg(v)-1) with e(v) number of edges between neighbors

3. Distance d(v,w) is minimal path length of all paths

4. Random graphs

Add randomly edges between n vertices // stochastic process

Erdös-Renyi (1960) and Gilbert

1. Choose g_nm out of G_nm the set of graphs with n vertices and m edges

2. Theorems // with high probability

[First] Node degree > O(log n) → big connected component of size O(n)

[Second] Graph connected → diameter in O(log n)

1. Choose g_np out of G_n the set of graphs with n vertices and a probability p

2. Add an edge (v,w) with p

3. Theorems // with high probability

[First] C(v) is asymptotically equal to p

[Second] p > ln(n)/n → g_np connected

1. Technical, 2. social and 3. biological

1. P2P

2. Internet

3. WWW

4. Power distribution

5. Train system

6. Web of streets

1. Friendship

2. Acquaintance

3. Relationships

4. Memberships

5. Collaborations

1. Food chain

2. Neural nets

1. Deliver letter from random person A to specific B

2. Only be given to an acquaintance // constraint

3. Result shows on average via 6 mediators

4. But small experiment with only 50 persons and 5% successfully delivered letters

1. Know close people more than far people

2. Mortality does not influence structures (Reliability)

3. Growth of people does not affect structures (Scalability)

4. Use small world characteristics for P2P

1. Vertex v has position Pos(v)\in \{x_1,…,x_d} (Coordinates) and x_i(v) (position in dimension d)

2. Query is given to closer neighbor v minimizing Sum_i|x_i(v)-x_i(t)| // Manhattan Distance

3. Add randomly edges between vertices v and w with p=d(v,w)^(-alpha) to empty 2D grid

4. Theorems

[First] alpha=d → shortcuts are found // Otherwise to many or to little shortcuts

[Second] Shortcut length in O(log n)

1. Local routing

2. Greedy

3. Metric for distance needed

High C(v) → high L // not for real-world networks (RW)

1. L is similar

2. C is greater

1. L is smaller

2. C is greater // SW have dense local structure

3. Similar diameter

4. Constant vertex degree

5. SW can not be explained by RG neither by GL

1. Average degree <k> is 6

2. Number of vertices N is 10^9

3. Probability of degree 500 is 10^-99

4. Number of vertices with degree 500 is 10^-90

1. Probability of degree 500 is 10^-6

2. Number of vertices with degree 500 is 10^3

3. L is 19

4. gamma is -2,4

1. Degree distribution is power-law distributed // general with gamma between -4 and -2

2. Probability of connection to k vertices P(k)=k^-gamma with gamma between -3 and -2

3. Many small degree vertices

4. High degree vertices (so-called hubs) more probable than in normal distributions

1. Collaboration of scientists

2. Relationship between woman and men in sweden

1. Large and complex networks follow power-law relationship and are scale-free

2. Network grows over time at any time step (discrete time modeling)

3. Edge generation for new vertices is not random but follows the principle “the rich get richer”

Scale-free networks SF are robust against random failures but sensitive against attacks

RG neither robust against random failure nor sensitive against attacks

1. Watts-Strogatz

2. Barabasi-Albert

3. Copying model by Kumar, Raghavan et al. (2000)

1. Influenced by C(v) and average path length L of real-world networks

2. Build a ring of n vertices and add edges to k clockwise neighbors

3. Label each edge with a number between 0 and 1

4. If label is smaller than p change target vertex

1. Model is regular

2. C(v)→3/4 for large k

3. Diameter in O(n)

1. C(v) stays high and drops rapidly

2. L drops rapidly and stays low // Shortcuts

1. Model is regular random

2. Low C(v)

3. Diameter in O(log n)

1. Start with network of 10 vertices and 20 randomly distributed edges

2. Every time step add new vertex x with m edges with target drawn by the preferential attachment (deg(v)/Sum_w deg(w))

1. Every time step copy one vertex with all edges adding edge from copy to original

2. Redirect randomly edges with small probability

3. Probability to get new edges is proportional to current degree