# Presentation: 253739

## Physics of Complex Networks

- Dylan Walker
- Stony Brook University

## Outline

- Overview of Network Properties

- Random Network Models

- Networks in the Real World

- Ranking Citation Networks

- Small World Networks

- Power Laws

- Diffusion on Directed Networks

- Motivations

## Motivations

- Why study complex networks?
- Connectivity of systems is important
- Evolution of complex systems Network Growth
- Physical Processes on Networks
- Why is it physics?
- Follows statistical mechanics:
- Processes on a lattice  Processes on Network
- Criticality
- Common problems: e.g., Community detection reduces to Ising-type problems

## What can we study?

- Connectivity of networks
- Function from topology (e.g., in bio systems)
- Relational similarity (community detection)
- Ranking from topology
- Evolution of networks
- Growth
- Robustness (random, targeted node removal)
- Optimization
- Processes on networks
- Diffusion, dynamical exchange
- Epidemiology on a fixed interaction network
- Games on networks

## Networks in the world

- Skitter AS-level Map of the Internet (CAIDA: http://caida.org)

**Notes:**
This is a map of the internet created by the CAIDA skitter project.  Each node is an autonomous system (a collection of IP’s into a system with a coherent routing policy).  Coloring of nodes is related to degree connectivity.

## Networks in the world

- SARS – Epidemic outbreak [Singapore Feb 25-Apr. 30, 2003]
- (Borgatti 2003)

- Disease spread by a few “superspreaders”

- Great example of relevance of connectivity

**Notes:**
These are reported cases of SARS in Singapore during 1 month in 2003.  This network picture of the epidemic is particularly revealing:  it shows us that the disease is spread by a few key players  “Superspreaders”.  Without these superspreaders, the outbreak would not reach epidemic proportions. This is a great example of the implications of connectivity.

## Networks in the world

- _Effect of Node Removal_
- Red = lethal
- Green = non-lethal
- Orange = slow-growth
- Yellow = unknown

- Protein-Protein Interactions in S. Cerevisiae
- (Jeong 2001)

**Notes:**
This is a protein-protein interaction network for Yeast.  The nodes are proteins and edges represent an interaction. The coloring of the nodes represents the phenotype effect of removing the protein from the network.  To a large extent, biologists formerly classified proteins on their individual functions (catalysts, signaling, etc.).  The lethality coding here should make it clear that the role a protein plays from a network standpoint cannot be ignored.    

## Network Properties

- Directed graphs  kin , kout

- _Degree_ (k) ~ # edges attached to a node

- _Degree distribution_: Pk

- Adjacency Matrix:

- _Diameter_: Largest geodesic path between any node pair in the network

- _Geodesic Path_: Shortest path between a pair of nodes

## Network Properties

- A node is in a component if it can “be reached” by any other node in the component.

- Strong Component – a large *dominant* component

- Clustering:

- Component:

- Are your neighbors more likely to be connected?

- Infinite Component – percolation

**Notes:**
The clustering is roughly the answer to the question: how connected are your neighbors.  There are a few popular clustering metrics.  This one is defined here is basically the number of actual triangles over the possible number.  Other metrics extend this to a local property (e.g., C  C_i  for the ith node) where the triples must be centered on that node.  A single coefficient of clustering is then obtained by taking an average of the C_i ‘s. 

## Network Properties 

- Network Properties

- _Degree Correlations:_

- _Betweenness centrality_:

- Internet AS-level degree correlations
- (Maslov, arXiv:cond-mat/0205379)

- Betweenness of a given node is related to the number of shortest paths between all pairs of nodes that pass through it.

- i

- s

- t

## Community Structure

- High School Friendship Network (Moody)

- Dense interconnections *within* communities.
- Sparse connections *between* communities.

- Problem: Detect community structure

- Community structure related to:
-       - context in information networks
-       - function in biological networks
-       - social implications (homophily, etc.)

**Notes:**
Community structure is another important property of networks.  A community is defined as a group of nodes that are densely connected to each other but sparsely connected to the outside world.  Communities in information networks may indicate common information.  In biological networks (such as protein interaction networks) communities may indicate that the nodes (proteins) act together to accomplish a particular function.  In social networks, such as the one shown below, communities may be interpreted more literally as groups of people with stronger social ties.  Detections of communities is an important problem in network science.  

## Random Graphs

- Poisson Random Graphs (Erdos & Renyi)
- 	N nodes, connect each pair of nodes with probability p
- Phase transition (critical conn. probability pc):
- 	   many small components        Single giant component

- Degree dist. given by:

- Graph structure (stochastic) depends only on p

**Notes:**
-Degree Dist:
The degree dist. is given by the following relation.  This is easy to see; the first piece is the number of ways to attach the endpoint of k edges that all emanate from a particular node (this should really be N-1, but N is large).  The second piece is the probability that there are exactly k edges.  If we look at the limit where N becomes large (fixed k) this becomes the Poisson distribution (hence the name).  Btw, z here is just the average degree.
-Phase Transition: 
The realization of a phase transition as you pass a critical probability can be seen in the topology of the graph.  One way to look at this is in terms of the size distribution of connected components.  A P approaches P_c , the average component size increases;  A single giant component emerges.

## Random Graph – Phase Transition

- Average component size vs. Giant component size:

- Average component size:

- 2nd order phase transition at z = 1

**Notes:**
-Average component size vs. Giant component size
You can calculate the fraction of the graph taken up by the giant component.  This result follows from the fact that if a node is not in the giant component then neither is its neighbor.  Since S is a size, it must be positive definite; so for z<1  S=0.  For z >1 there is a non-zero solution.  
The average component size (excluding the giant component) can also be calculated.  This can be done via the theory of generating functions.  The results are shown here.  Below is an iterated graphical plot of the two quantities.  

## Random Graphs – Properties

- _Diameter_:

- The number of nodes a distance L away from a node is approximately:

- If we expand this to include all the nodes in the graph, we get the approximate diameter:

- _Clustering_:

- In a random graph, the probability that two neighbors of a node are connected is just the independent probability, p:

- <k>

**Notes:**
The diameter of a random graph can be approximated with the following reasoning.  If we assume all nodes have degree <k>, then the number of nodes included in a distance L from a given node is given by this eq.
If we wish include all the nodes in the graph, this gives us the approximate diameter.  (Of course if p is small, this approximation breaks down because we run into many nodes that with k=0 or 1)
-Clustering: since each connection is independent, the clustering in a random graph is just given by the conn. probability, p.

## Where Random Graphs Fail

- Most real world networks do not have Poisson degree distributions.

- Poisson Random Graph is not a very good model of real networks...

- Clustering of real networks is vastly different:

- The local topology of real world networks is not reproduced in random graphs.

- Motifs:

| Network | C | CR | Ref |
| --- | --- | --- | --- |
| WWW | 0.1078 | 0.00023 | Adamic (1999) |
| Internet AS | 0.3 | 0.001 | Pastor-Satorras (2001) |
| SPIRES coauthor | 0.726 | 0.003 | Newman (2001) |
| C. Elegans | 0.28 | 0.05 | Watts,Strogatz (1998) |

**Notes:**
The Poisson random graph is often not a very good model for real world networks.  For one thing, many real world networks have vastly different properties: degree distribution, clustering, topology and loop structure.  
Moreover, it is not even a good null model for many real world networks.  Of course, the random graph is really not meant to model real world networks.  There are many models out there that better reproduce real world network features... this is still a direction of current research.  How

## Random Graphs – Further Work

- _Configuration Model_:

- _Randomizing a network_:

- Often times we measure some property of a network that has grown stochastically. What result should we expect by random chance?

- Edge swapping conserves degree distribution

- 1) Attach stubs (ends of edges) to nodes to insist the desired degree distribution.

- Still cannot reproduce the high clustering seen in real networks.

- This creates every possible topology w/ equal probability.

- 2) Connect pairs of stubs at random.

- _Exponential Random Graph Models_:

- Boltzmann-like ensemble:

**Notes:**
The configuration model is another random graph model that can generate a desired degree distribution.  It works like this:  Take N sample from the desired degree distribution to create a net with N nodes. Each sample is the number of stubs attached to a node.  Now attach the stubs together randomly.  This will create every possible topology with equal probability.  However this model is still incapable of reproducing the high clustering seen in many real-world networks.  (btw, these random graphs also exhibit a percolation phase transition)
-Exponential Random Graph Models
This is a method to generate graphs from an ensemble weighted according to any general set of measurables you wish.  A graph with some set of properties appears with probability specified by the equation here.  This approach however is not very practical (notice the sum over all graph in the denominator) from a standpoint of computability.  
-Randomizing a network

## Small World Experiment

- Stanley Milgram’s Small World Experiment (1967)

- Sent 60 letters to  Witchita, KS

- Intended target: Cambridge, MA

- Messages passed by known acquaintance only.

- Average completed chain length ~ 6

- 6 Degrees of Separation

## The Watts-Strogatz Model

- Tuning between on ordered lattice and a random graph

- 1) Start with ordered ring: Each node wired to k neighbors

- 2) Rewire each edge with prob. p

## The Watts-Strogatz Model - Properties

- However, the Degree Distribution is not very similar to real-world networks

- Typical path length drops quickly to achieve the small-world effect

- High clustering is achieved for a range of p values.

## Scale Free Networks

- So what underlying mechanism is responsible for the power law distribution if any?

- There is something special about power law distributions...

- One particularly ubiquitous degree distribution form is the power law:

| Network | Size |  |  | Ref |
| --- | --- | --- | --- | --- |
| www | 2x108 | 2.1 | 2.71 | Broder (2000) |
| E. Coli (metabolic) | 778 | 2.2 | 2.2 | Jeong (2000) |
| Movie actors | 2.12x105 | 2.3 | 2.3 | (Barabasi 1999) |
| Word co-occurence | 4.62x105 | 2.7 | 2.7 | (Cancho 2001) |

- Not to mention non-network power law distributions ...

- city populations, earthquake magnitudes, word frequency, book sales, solar flare intensity,...

## Power Laws and Scale-Free behavior 

- Scale-free Criteria:

- Differentiating above wrt. a and considering the cases  x=1, a=1 yields:

- with the solution:

- Power law distributions are the only functions that satisfy the Scale Free Criteria

- On to Network growth models that yield power laws...

## Preferential Attachment Model

- Attach new node to existing
- graph with probability:

- 2/24

- 2/24

- 1/24

- 3/24

- 1/24

- 4/24

- 3/24

- 1/24

- 2/24

- 2/24

- 1/24

- 2/24

- ?

- ?

- ?

**Rich get Richer**

## Preferential Attachment Model

- _Continuum theory_

- The nodes grow:

- The edges:

- The degree of a given
- node is governed by:

- because:

- So in general:

- We want to calculate the degree distribution based on this continuum model using two
- facts:

- Master eq.

**Notes:**
We can examine this preferential attachment model in continuous time.  Let the number of nodes increase linearly with time.  When we add a node, we’ll attach it to “m” other nodes.  Then the evolution of the degree of some node (i) is given by the equation.  If we examine the denominator, we realize that summing over the degree of all existing nodes is just another way to count the number of edges.  This leads to the general result that the degree grows with the root of time (where the t_i is just the node’s time of birth).  [There is actually a step function here that I’m ignoring, since a node has zero degree before it’s born.]
The result is that in the limit of large time, the degree distribution of this model follows a power law.  You can arrive at this result using other approaches (e.g., the master equation approach).

## Extensions and Other Models...

- Other models that yield Power Laws:

- There are many....

- Variations of Preferential Attachment Model:

- Optimization/ evolution based on process on network

| Model | constraints | Ref |
| --- | --- | --- |
|  |  | Barabasi, Albert (1999) |
|  | no scaling for | Krapivsky, Redner (2000) |
|  |  | Bianconi, Barabasi (2000) |

- What about networks for which preferential attachment mechanism makes no sense?

- Vertex copying models

- Reproduction/mutation of nodes

- Future Work:

## Self Organized Criticality

- A brief aside:

- We do observe phase transitions and critical phenomenon in network growth models that are stochastic.

- Generally, power law distributions are associated with a divergence of scale in a system.

- Divergence occurs at the critical point

- If this is a general origin of power law distributions, something must drive the system towards criticality:

- _Percolation Forest Fire Model_

- Trees appear at random positions at
- a const. rate

- Lightening strikes initiate forest fires that burn connected components

- Burning of components will not affect most forest until component percolates

- Forest is driven towards point where components just  begin to percolate

## Processes on a Network - Diffusion

- Random Surfer Model:

- What about getting stuck in loops?

- a takes care of that

- Let’s count the surfer’s that pass through each point:

## Ranking Citation Networks

- _What are citation networks?_

- _How do we currently rank papers?_

- But ki(t) is monotonically increasing with time.

- New papers do not compete with old papers on even ground

- All citations are treated as equally important...

- But shouldn’t citations from “**stronger**” papers matter more?

## Ranking Citation Networks – Google Inspiration

- The Google Pagerank algorithm accounts for strength (popularity) of papers in a self consistent way... via diffusion:

- The PageRank eq.:

- This should look familiar—it’s just the diffusion I showed you before.

- We can adapt the PageRank algorithm to rank citation networks... **CiteRank**

- Surfer population is likely to be high

- A strong website gets many links

- Prob. to follow link is proportional to
- population

## Ranking Citation Networks – Aging

- The random researcher is slightly _different_ than the random surfer...

- He doesn’t start researching from just any random paper...

- He prefers (like you) to begin with a recent publication:

- Why do this?

- Random surfers on a network with a time arrow will all flow towards the old edge of the network. This is due to the **aging** of the network.

- In the CiteRank algorithm, the initial distribution of random researchers is biased exponentially:

## Ranking Citation Network – Optimal Parameters

- What is the meaning of the PageRank or CiteRank number?

- While we use it to rank papers, the CiteRank number is a prediction of traffic.

- The best ranking is the one for which:

- Unfortunately, traffic data for citation networks is not readily available.

- CiteRank model of traffic has two parameters:

- i.e., predicted traffic is maximally correlated with actual traffic.

- Number of *recently** *accrued* *citations

- Provided we have the publication dates of papers, we can time-resolve the citation network.... And rewind

## CiteRank on Two Real Networks

- ArXiv: High Energy Physics Theory (hep-th):
- 	A snapshot of the high energy physics theory area of arxiv.org from April 2003 (citations ranging from 1992-2003)
- 	2800 papers ; 350,000 citations
- 	no form of peer review
- Physical Review (physrev):
- 	Citation data from all Physical Review journals (citations ranging from 1913-2005)
- 	380,000 papers ; 3,100,000 citations

## Linear Correlation of Ti with Dki

- Linear Correlation of Ti with Dki

- physrev

**Notes:**
So here are the results of that correlation for the physrev network.  The correlation is shown as contours over the parameter plane.  The features are pretty similar for the hep-th network (which I’ll show you in a moment). There’s a fairly sharp peak in the correlation here that is localized around a particular value of alpha.  It’s a little wider over tau_d.  The maximal correlation is achieved for alpha=0.5, tau_d=2.6 yrs.  In case you are interested, the value of the maximum correlation coeff=0.6543.

## Linear Correlation of Ti with Dki

- Linear Correlation of Ti with Dki

- hep-th

- rank corr.

**Notes:**
Here’s the same thing for the hep-th network. You’ll notice that the time scale of tau_d is in days here.  We just don’t have nearly as much data here as we did in the physrev case. But if you compare the regions on a similar scale, you see that the features of the correlation plot are remarkably similar.  Keep in mind that these two citation networks are, in fact, very different.  Physrev data is from peer-reviewed publications acquired over a hundred year period.  Hep-th is made up of electronically submitted preprint articles with no associated form of peer-review. 
Here the alpha=0.48  tau_d=363 days.  In case you’re interested the maximal correlation coeff=0.7275 .  

## CiteRank: Remarks

- Good agreement in estimation of a over networks:
- On average, the typical researcher follows citation chain of length ~ 2
- Future explorations
- Precise relation between Dki and Tireal
- Sampling of actual traffic

## Conclusion

- Overview of Network Properties

- Random Network Models

- Networks in the Real World

- Ranking Citation Networks

- Small World Networks

- Power Laws

- Diffusion on Directed Networks

## Questions?

## References

- M.E.J. Newman, S.H Strogatz, D.J. Watts *Random Graphs with arbitrary degree distributions and their applications*, Phys. Rev. E 64 026118, arXiv:cond-mat/0007235

- A. Barabasi, R. Albert *Statistical Mechanics of Complex Networks*, Rev. Mod. Phys 74, 47 (2002) arXiv:cond-mat/01006096

- M.E.J. Newman, *The Structure and Function of Complex Networks*, SIAM Review 45, 167-256 (2003), arXiv:cond-mat/0303516

- M.E.J. Newman, *Power Laws, Pareto distributions and Zipf’s Law*, Contemp. Phys 46 323-351 (2005), arXiv:cond-mat/0412004

- S. Itzkovitz, et. al., *Subgraphs in Random Networks*, Phys. Rev. E 68, 026127 (2003), arXiv:cond-mat/0302375

- I. Simonsen, K Eriksen, S. Maslov, K. Sneppen, *Diffusion on Complex Networks: A way to probe their large scale topological structure*, Elsevier Science (2003), arXiv:cond-mat/0312476

- I. Simonsen, K Eriksen, S. Maslov, K. Sneppen, *Diffusion on Complex Networks: A way to probe their large scale topological structure*, Elsevier Science (2003), arXiv:cond-mat/0312476

- S. Maslov, K. Sneppen, A. Zaliznyak, *Pattern Detection in Complex Networks: Correlation Profile of the Internet*, arXiv:cond-mat/0205379

## Rank Correlation of Ti with Dki

- Rank Correlation of Ti with Dki

- physrev

**Notes:**
In case you’re interested, the maximal correlation coeff=0.6436

## Rank Correlation of Ti with Dki

- Rank Correlation of Ti with Dki

- hep-th

- Return to Linear Corr.

**Notes:**
In case you’re interested, the maximal correlation coeff=0.5978 .

## Extra Slide – Power Laws & Scale Free Behavior

- Scale-free Criteria:

- Set x=1:

- Differentiate the eq. wrt. a:

- Now set a=1 in the above relation:

- 1)

- 2)

- 3)

- or

- Return to Power Laws & Scale Free Behavior

## Extra Slide – Giant component Fraction

- u ~ prob. node is not in giant component
- S ~ fraction of nodes in giant component

- If node is not in giant component, then neither are its neighbors:

- This eq. is transcendental... can calculate the solution iteratively.

- Fraction of nodes in giant component:

- Notice: this depends crucially on degree dist.

- Return to Phase Transition

**Notes:**
Here we use the fact that if a node is not in the giant component, then neither are its neighbors.  In the sum, the first term is the probability the node has k neighbors times the probability that all these k neighbors are not in the giant component.  We insert the degree dist. here of the Poisson random graph.  Notice that if this were some other graph with a different degree dist., the giant component fraction would scale differently.
The result we get, after transforming to S, is a transcendental relation that  can be solved iteratively.

## Extra Slide – Generating Functions

- The nth power of the generating fn. is the dist. of the sum of n indep. realizations:

- For some discrete dist. pk define:

- Can also define a generating fn. for the excess degree:

- Prob. dist. that there are k other edges besides the one you followed in

- or

- What about how many edges leaving a node other than the one we came in on?

## Extra Slide – Average Component Size (1)

- H1(x) ~ gen. function for dist. of the sizes of components 	reached from one end of a randomly chosen edge

- Consistency insists that:

-  (x qk) ~ prob. that a node reached from randomly
-               chosen edge has k *other* edges

- This says that if original node has component size dist. according to H1 , then it must be the same as the dist. of the sum of its neighbor’s components.

## Extra Slide – Average Component Size (2)

- In practice, this is not always possible.

- Generating fn. for the dist. of s by starting from a randomly chosen edge

- Generating fn. for the dist. of s by starting from a randomly chosen node

- Want to relate:

- So, ideally, if we know the fn.’s G0 and G1 , we can calculate H1 and then H0

- then:

- The extra normalization factor
- Comes from the fact that we define H to exclude the giant component (which breaks the automatic normalization of the gen. fn.)

## Extra Slide – Average Component Size (3)

- Return to phase transition

- For the Poisson random graph:

## Extra Slide –Pref. Attachment Master Eq. Approach

- Based on the idea that nodes do not lose links or disappear.

- Prob. that a node born at time ti has degree k at time t+1

- Prob. a new node pref. attaches to a  node with degree k-1

- Prob. a new node does not pref. attach to a  node with degree k

- The above becomes:

- Return to Pref. Attachment

## Extra Slide – Community Structure + Potts model

- Imagine a spin sitting at every node of a network.

- Connections between nodes with the same spin state are rewarded

- Lack of connection between nodes with same spin state is punished

- Return to Community Structure

## Extra Slide – Zipf’s Law & k-estimations

- Cumulative dist.:

- Advantage: no need to bin the data to plot this

- Normalization:

- Moments:

- and generally:

- Largest value:

- For n samples drawn from p(x)

## Extra Slide - Power Law Distributions in the World

- M.E.J. Newman, *Power Laws, Pareto distributions and Zipf’s Law*, Contemp. Phys 46 323-351 (2005)

- Return to scale free

## END

## Slide 51

## Motivations

- Why study complex networks?
- Connectivity of systems is important
- Robustness: resilience of a network to node removal
- Biology: topology related to function
- Epidemiology: Epidemic “threshold” transmission probability
- Why is it physics?
- Follows statistical mechanics:
- Processes on a lattice  Processes on Network
- Criticality
- Common problems: e.g., Community detection reduces to Ising-type problems

## Random Garbage

## Outline

- Networks in the world
- Random Graphs
- Properties of networks
- Degree distribution ~ Pk ~
- Clustering coefficient ~ C
- Degree Correlations ~ assortativity
- Show Maslov’s picture
- Community Structure
- Example of clearly visible community structure
- Models of Growth
- Preferential Attachment Model
- Watts-Strogatz Model
- Scale Free Networks
- Connection to power law (see Newman’s Zipf Law Review p.11)
- Self Organized Criticality
- Search on networks
- Random walks on networks -> Google algorithm
- CiteRank Algorithm