Lecture #27: Network Dynamics

Lecture is about network dynamics, briefly, analysis of the changes that occur

in the network in time. These changes include appearance and disappearance of nodes,

links and also some aggregate metrics of the network. In addition to the analysis

of the known changes, network dynamics deals with predictions about future changes

in the network, like formation and dropping of new edges.

First study mentioned in the class was "Empirical Analysis of an Evolving Social Network".

Paper analyzes a university e-mail network. Ties are weighted with the number of messages

within the last 60 days between the pairs. One major result is that, individuals sharing at

least one class are 3-times more likely to start emailing each other if they have an email contact

in common. Probability significantly increases as number of ties or shared classes increase.

Next part was about the Team Assembly Mechanisms and Evolution of Affiliation Network

Related to Social Network. Examples studies in this field are Broadway Musical Industry and

Collaboration Networks in different sciences. Interesting findings can be summarized as follows;

If your friends join, so will you.

Cliquish communities grow more slowly.

Second part of the lecture was about the results of the affects described in the first.

As the nodes and links change over time, how does the degree distribution,

clustering coefficient and average shortest path change. Graph Densification is analyzed

for physics citations, patent citations, autonomous systems and affiliation networks.

A mathematical model is given. The main result is that number of edges are growing faster

than nodes, so average degree is increasing. Similar studies are carried out for the

diameter change.

In the final part, possible explanation of densification, community structure and difficulty of cross linking, and forest fire model is discussed.

Lecture #26: Percolation and Network Resilience

This lecture’s topic was percolation and network resilience. We want to answer the questions of if a given fraction of nodes or edges are removed from a network , how large the connected components are or what the average distance between nodes in the components is. While removing nodes or edges we should consider some points. In bond percolation each edge is removed with probability (1-p). Causing the most damage to the network with the removal of the fewest edges is targeted attack. Usually edges with high betweenness are the targets to make the most damage to network.
Percolation threshold in an Erdos-Renyi graph is the point at which the giant component emerges.
Another fact about the resilience is scale-free networks are resilient with respect to random attacks. However they are not resilient against targeted attacks. Removal of successfully chosen a small number of nodes may cause many more nodes (their neighbors) to be disconnected to the network.
In power grid structural networks each node has a load and a capacity that says how much load it can tolerate. When a node is removed from the network its load is distributed to the remaining nodes. If the load of a node exceeds its capacity then the node fails. Hence we can conclude that network resilience depends on topology of the network.

Colloquium: Epidemic Spreading in Social Networks by Dr Kitsak/December 2nd 2010

The colloquium topic was information diffusion in networks. Dr. Kitsak mentioned about diseases that spread very fast and killed lots of people in the past and recent years also. The most important point here is to understand how information (or disease) spreads based on network structure and what strategies can be applied to overcome the diseases very fast.There are many things that can influence the spread of information within a network. The three main factors in diffusion are network structure (degree distribution, clustering, connected components, etc.), strength of ties (frequency of communication and strength of influence), and spreading agents. A strong tie can be defined by frequent contact, affinity, or having many mutual contacts.

Dr. Kitsak also mentioned three key models for infection. These are SI, SIS and SIR. SIR stands for Susceptible -> Infected -> Removed/Recovered. Each node in the network can be classified by one of these terms in the SIR model. If a node is susceptible, then it can be infected. An infected node is self-explanatory. A removed node means it was infected and removed from the network. Or, a node can recover and build a natural immunity. The SI model is simply Susceptible -> Infected. The definitions remain the same, but a node is unable to recover and therefore remains infected. The SIS model is Susceptible ->Infected -> Susceptible. One of the important network structure that disease can be spread is worldwide airport network. Dr. Kitsak also mentioned about network immunization. One vaccine strategy may be instead of vaccinating all people vaccinate a threshold part so the community can be divided into clusters and virus can't jump to clusters. Dr. Kitsak also told that our community is scale free network.

So who are the most influential spreader in the network?K-shell is the most robust spreading efficiency indicator. So if we want a disease spread quickly we should find different K-shells at different places in the world.As a conclusion Dr. Kitsak pointed out these factors:

1-Almost no epidemic threshold in Scale-Free Networks.
2- Efficient Immunization Strategy: Immunize at least critical fraction fc of nodes so that only isolated clusters of susceptible individuals remain.
3- Immunization strategy is not reciprocal to spreading strategy.
4-Influential spreaders (not necessarily hubs) occupy the innermost k-cores.

Metric computations tools

I have uploaded two tools to computer basic network metric under Course Content. These are useful if you have very large networks that Pajek can not process.

One of the tools is just for betweenness centrality and the other includes a set of metrics and also draws results of some.