Network theory - fundementals I.

Network theory - fundementals I.

- 9 mins

Networks

Complex system : composed of interconnected parts that as a whole exhibit one or more properties not obvious from the properties of the individul parts

Graphs and networks


Graph : vertices, edges, directed or not, weighted or not

Network : nodes, links, flows, epidemics, growth, rewiring, etc.

The next step from graphs to networks is complex systems which we model with networks!

Graph types

Sotring it on computer can be done in an adjecency matrix (not memory efficient) or in an adjecency list (linked list).

For undirected graphs A is symmetric. Multiplying a position vector with A gives the neighbors of that point.

Sparseness

A network is sparse in the limit if the number of links .

A networks is dense in the limit if the number of links .

In the dense case the average connections per node goes to infinity. ().

Most real networks are sparse. Therefore the probability of two nodes being linked is negligible, goes to 0 in the limit.

Basics of networks

Pathology

Algorithms

PageRank

The importance of a node is affected by the number of in-neighbors and the importance of the in-neighbors.

Assume an iteraive process, each node distributes its PageRank evenly at each timestep between its neighbors.

Total PageRank of the system is therefore conserved since it is only being redistributed at each timestep. For simplicity one should scale it to 1.

If we intruduce dampening with probability :

Components

A component is an undirected network that corresponds to a maximal set of nodes in which a path exists between any pair of nodes.

Most networks contain a giant component.

A giant component in a network is a subsystem which relative size remains finite in the limit.

Can be generalized to the directed case:

Advacned network characteristics

Scale-free networks

A network is scale-free if the tail of its degree distribution decays as a power-law, where is the node degree decay exponent:

It is called scale free because scaling functions are defined as:

and power laws are scaling.

Wealth densitiy is a scaling probability density ( ), this is called the Pareto-distribution.

Also there is no typical degree in scale-free networks as a result of being scaling.

Normalizing the scale-free degree distribution:

Therefore is:

As a result:

Scale-freeness implies large hubs in the network.

In physics being scale-free usually occurs at phase transitions at critical points and often suggests divergence. The moments of p(k) are divergent for a scale-free system when .

Most real world networks are scale-free and their node degree decay factor () is below 3 thus is divergent in the limit, therefore the standard deviation is divergent as well!

If is in the range the system behaves ultra-small world and the scale-free property is relevant.

Let denote the conditional probability of finding a node with degree from a node with degree . From the definition of conditional probability:

Where it is easier to count all the nodes denoted with and then dividing by the nodes that all have degrees .

If we divide (the matrix of number of links between degree , node pairs) with the total number of links in the networks beging we can get which obviously sums to one for both degrees:

The meaning of is the probability of finding a node on the end of a link with degree . This is obviously proportional to the number of links from nodes with degree :

For a neutral network we expect which after the normalization of and translates to therefore any significant deviance from this value indicates degree correlations in a networks.

In practice preparing is difficult and computationally expensive so average nearest neighbor degree is calculated instead:

In terms of , .

In case of a neutral network and therefore:

We should remeber that is the normalized which is therefore:

Calculating this parameter is takes variables in memory and less steps than calculating . We can now calculate the covariance of :

Substituting the joint probability in the above equation:

After simplification:

We can simply check this formula by remembering that in a neutral network the probabilities in the parantheses cancel out and there is no co-variance between degrees.

The Pearson-correlation is defined as the co-variance of the parameters diveded by their variances. The variance of and is:

The Pearson-correlation is therefore:

If the network is neutral, if it is disassortative otherwise assortative.

@Regards, Alex

Alex Olar

Alex Olar

Christian, foodie, physicist, tech enthusiast

comments powered by Disqus
rss facebook twitter github gitlab youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora quora