Critical phenomena in complex networks - Cornell University

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 ]

Recently Viewed Presentations

  • Introduction to CUDA Programming

    Introduction to CUDA Programming

    Introduction to CUDA Programming. Architecture Overview. Andreas Moshovos. Winter 2009. ... no bus arbitration. Packet switches messages form virtual channel. ... (SFU) 1 Double-FP Unit (DPU) Multi-threaded instruction dispatch.
  • Company Name

    Company Name

    , mutually supportive but sparking energy and creativity in alternation between support ("comping") and solo performance. Jazz is a minimalist, "resource poor" environment where solo performance stands on its own. Mistakes . are areoften disguised and incorporated as . the...
  • Cs423/523 - Ewu

    Cs423/523 - Ewu

    Lecture 4 - Hackers and Attackers Reading: Chapters 3, 7, 16 CSCD 303 Essential Computer Security Winter 2014 * Cybercrime Credit Card Theft - Numbers!! 2005 - More than 40 million credit card numbers belonging to U.S. consumers were accessed...
  • Amartya Sen: The Capabilities Approach Sundeep Sahay Amartya

    Amartya Sen: The Capabilities Approach Sundeep Sahay Amartya

    (Protecting this capability means protecting institutions that constitute and nourish such forms of affiliation, and also protecting the freedom of assembly and political speech.) Having the social bases of self-respect and non-humiliation; being able to be treated as a dignified...
  • Using the Ideal Gas Law and Previously Learned Concepts

    Using the Ideal Gas Law and Previously Learned Concepts

    Using the Ideal Gas Law and Previously Learned Concepts A gas that is 80.0% carbon and 20.0% hydrogen has a density of 1.339 g/L at STP. Use this info. to calculate its Molecular Weight in g/mol Empirical Formula Molecular Formula...
  • Internal EMS Auditing at Naval Installations Navy EMS

    Internal EMS Auditing at Naval Installations Navy EMS

    Cost savings - give examples Improved relations with regulators - give examples Documentation of processes - reduced impact of personnel turnover Acknowledge personnel for achievements Report EMS successes within and outside of the organization 30 April 2003 Internal EMS Auditing...
  • Theme Journals - Mrs. Terry

    Theme Journals - Mrs. Terry

    A theme is the main idea, or message, of an essay, paragraph, or a book. The message may be about life, society, or human nature. Themes. often explore timeless and universal ideas and may be implied rather than stated. A...
  • "Disability and Development - Disability Inclusion and ...

    "Disability and Development - Disability Inclusion and ...

    "DISABILITY AND DEVELOPMENT - DISABILITY INCLUSION AND ACCESSIBLE URBAN DEVELOPMENT" Lefhoko Kesamang . Senior Social Welfare Officer. African Union Commission