Critical phenomena in complex networks - Cornell University

Networks Igor Segota Statistical physics presentation Introduction Network / graph = set of nodes connected 1 by edges (lines) 2

The edges can be either undirected or directed (with arrows) 3 5 Random network = have N nodes and M edges placed between random pairs 4 - simplest mathematical model The mathematical theory of networks

6 originates from 1950s [Erdos, Renyi] In the last 20 years abundance of data about real networks: Internet, citation networks, social networks Biological networks, e.g. protein interaction networks, etc. Introduction Network / graph = set of nodes connected 1

by edges (lines) 2 The edges can be either undirected or directed (with arrows) 3 5 Random network = have N nodes and M edges placed between random pairs 4

- simplest mathematical model The mathematical theory of networks 6 originates from 1950s [Erdos, Renyi] In the last 20 years abundance of data about real networks: Internet, citation networks, social networks Biological networks, e.g. protein interaction networks, etc. Statistical measures

How to systematically analyze a network? Define: Degree: number of neighbors of each node i: qi 3 Average degree: [over all nodes] Degree distribution probability that a randomly chosen node has exactly q neighbors: P(q)

1 2 5 4 6 Is there a notion of path or distance on a network? Path length, or node-to-node distance:

How many links we need to pass through to travel between two nodes ? Characterizes the compactness of a network Scale-free networks If we look at the real world networks, e.g.: a) WWW, b) movie actors, c,d) citation networks, phone calls, metabolic networks, etc.. They arent random the degree distribution follows a power law:

P(q) = A q- with 2 3 They do not arise by chance! Examples: WWW, publications, citations Can we get an intuitive feeling for the network shape, given some statistical measure?

Network comparison NP-complete problems on networks NP-complete problem Problem such that no solution that scales as a polynomial with system size is known. Directed Hamiltonian Path problem Find a sequence of one-way edges going through each

3 node only once. DNA computation: 1 2 4 5 6

NP-complete problems on networks NP-complete problem Problem such that no solution that scales as a polynomial with system size is known. Directed Hamiltonian Path problem Find a sequence of one-way edges going through each 3

node only once. DNA computation: 1 = TATCGGATCGGTATATCCGA 1 2 4 5

6 2 = GCTATTCGAGCTTAAAGCTA What about the edges ? [Aldeman; 1994.]

NP-complete problems on networks CATATAGGCT CGATAAGCGA TATCGGATCGGTATATCCGA GCTATTCGAGCTTAAAGCTA 1 2

For each pair of nodes, construct a corresponding edge Due to directionality of DNA, edge orientation is preserved and 1->2 is not equal to 2->1 Idea: generate all possible combinations of all possible lengths then filter out the wrong ones NP-complete problems on networks Generate

Keep 1 6 12354546 12354546 1235456

1235456 1246 1246 Keep those containing all 1,2,3,4,5,6

Keep len=6 1 2 23 124546

124546 124546 4 3 5

31235 1231 123546 4546 123546 123546

123546 6 Emergent phenomena on networks Critical phenomena: an abrupt emergence of a giant connected cluster [simulation] Analogous to the effect in percolation theory (in fact it is exactly the same effect)

p=0.1 p=0.2 p=0.3 p=0.4

p=0.45 p=0.47 p=0.49 p=0.5 p=0.51

0.53 0.55 p=0.6 p=0.7

p=0.8 p=0.9 Network percolation experiments Living neural networks [Breskin et. al., 2006] Nodes = cells, edges = cell extensions + transmitting molecules Rat brain neurons grown in a dish, everyone gets connected Put a chemical that reduces the probability of neuron firing

(disables edge) [effectively adjusts the ]