Network Analysis I

Question 1

Describe the Erdös Rényi Model

Answer 1

We have a set of nodes

and a connection probability p.

For each node pair, we use p to decide if there should be a connection or not.

for p = 0.5 (a coin flip)

we may get something simmilar to the figure

Question 2

Can we calculate the number of nodes in a large Erdös Rényi Model?

Answer 2

Yes! using the formula explained in the figure we are actually able to do so, by knowing the number of nodes and the connection probability.

Question 3

What is a node degree?

Answer 3

Degree of a node i: number of edges adjacent to i (for directed graph can also distinguisth in-degree and out-degree). Degree distribution: distribution of degrees of all nodes in a network.

Question 4

What is the power law?

Answer 4

In many real networks there is a linear relationship between the logarithms of the degree d, and its relative frequency f (d).

This applies to word appearances (for example. is, is (no pun intended) a more used word than elephant).

See figure for distribution

Question 5

Why is the power law interesting here?

Answer 5

If we want to add a new node to the network, we can expect it to be added to one of the nodes with many attachments unless we introduce prefential attachments

Question 6

What is the idea of prefential attachments?

Answer 6

The change of assigning a new node to another existing node is propertional to the degree of the existing node. The rules for this can however be a bit ambigous

Question 7

How do we resolve the ambiguities in the informal preferential attachment model?

Answer 7

The Linearized Chord Diagram model resolves the ambiguities in the informal preferential attachment model.

Basis: adding a new node by preferential attachment in the m = 1 (m is the amount of edges) case is easy and non-ambiguous.

For a full explanation of the LCD algorithm:

1. Generate a random matching of the nodes.

https://gyazo.com/27918d2fb1209e071d98baab41988e89

2.

https://gyazo.com/d80dec9a29169e9dcb1113c63903793e

3.

https://gyazo.com/6952b1856431ee9c66a4cbce9e070de6

4.

https://gyazo.com/82706a42899e0e7eadc11afe21a28d42

5.

https://gyazo.com/d5d5a6cda0943421eaec3bf5bd378171

6.

https://gyazo.com/9e5950d807e79be41b9b968ae5a0b632

7. last

https://gyazo.com/41da2278e2966b02471d0d5b4993885d

Question 8

What effect did the LCD have on the protein-protein network?

Answer 8

A more straight logaritmic line. Meaning it is better in terms of degree distribution

Question 9

How do we measure the amount of clustering

Answer 9

For a node v in G we use two things:

1. τ3(v) : (tau) number of length-2 paths with v in the middle
   * this does not need to be a triangle*
2. τ△ : number of triangles containing v

This will give us a clustering coefficient

example - see figure

Question 10

What how do we use exponential random graphs?

Answer 10

We can use it since there are a lot of attributes to a network. We can use these attributes and assign parameters (scores) which can be used to calculate the probability of this to happen, though this requires the normalization constant (paritition function) to be found which is very difficult.

An example is the use of open and closed triangles as attributes

As seen in the figure: