Fundamental ideas in network science
Course code: CNSC 6000
Course Status: Mandatory
Background and overall aim of the course:
Networks are ubiquitous. Economic trade, social relationships, terrorist organizations or biochemical reactions – all span networks. Network science has gone through a spectacular development during the last decade. The data deluge due to the information communication revolution enabled to study huge networks like the Internet, the WWW, large social networks, communication (e.g., email and mobile call) networks, ecological and biological networks. It turned out that earlier established models did not work and new paradigms were needed. Surprisingly, universal features of the so called complex networks could be identified in spite of the fact that their range of application covers entirely different systems in economy, sociology, biology or computer science. A truly multidisciplinary endeavor started and has resulted in the new science of complex networks.
In this interdisciplinary course students with different backgrounds can learn about the basic concepts including elements of the theory of graphs, dynamics of and on networks as well as about diverse applications. They will get acquainted with important issues of present day research. Only elementary math prerequisites are assumed.
The society, the economics or the brain are examples of complex systems as opposed to complicated ones like a Swiss watch. What makes the difference? The importance of emergence. Networks: the scaffold of complexity – a holistic approach. What makes a network? Examples from diverse fields.
How does a coffee percolator work and how is this related to networks? Lattices, the simplest networks. Disorder. Percolation, the simplest phase transition. How to characterize the percolation transition? The beauty of fractals. Self-similarity and power laws. Scales and scale freeness.
A little math: some basic notions of graph theory. The old paradigm: Erdös-Rényi (ER) graph and its properties. Percolation transition in the ER model. The non-uniform society and the failure of the ER model. Why to study it?
How many handshakes away are you from Barack Obama? The Milgram experiment and its contemporary version. “Six degrees of separation.” The Small World model. The direct path is not always the shortest.
Scale free networks
Fame and Fortune. Who cites whom in science? The Kevin Bacon game and the Erdös number. The role of hubs and their evolution. Scale freeness and universality. What do the exponents tell us? Exploding moments.
Visualization and measuring
Practical computer tools to visualize networks and to measure most important statistical properties.
The “most random” model with given degree distribution and its properties. General problem of null models. The best map is “on the scale of a mile to the mile” (Lewis Carrol) - different aims of modeling.
Network growth models
The Matthew effect: Rich get richer. Preferential growth. Networks are not static, they result from growth. The Barabási-Albert (BA) model. How hubs make the world small (or even ultra small). How does a newcomer know, who is most popular: Global vs. local growth rules. The problem with clustering and its resolution. Modifications of the BA model.
Not all links are the same! Natural weight measures: Traffic on the link, intensity of relationship. Topological weights. Generalization of the characteristic quantities to weighted networks. Weighted network models.
Local and hierarchical structures
What is “important”? Graphs and subgraphs. Important subgraphs: motifs. Relation to the function of the network. Weighted motifs. Hierarchical structures. Deterministic models.
Quarrel in the karate club. The modular structure of complex networks. Community identification from the topology: Local and global methods. Modularity, resolution limit. Overlapping and hierarchical communities.
Robustness and vulnerability
Random failures and intentional attacks. Terrorist networks. The Achilles heel of scale free networks. Universality classes. Big blackouts: Cascading failures. Network of networks.
The drunkard’s walk. The simple case of lattices. The role of disorder. Random walk in a small world. Relaxation to the steady state. Diffusion and communities.
The dilemma of vaccination. How do epidemics spread? Simple spreading models. The case of the swine flu: prediction with network theory. Sexually transmitted diseases, the sexual web. Vaccination strategies. Innovation spreading, peer pressure.
Links are not permanent. Characterization of temporal networks. The bursty character of human behavior. Models of temporal networks.
The brief history of the Internet. Its hierarchical organization. Self-organization with constrains. The scale free character of the Internet. Models. The WWW as a network. Characterization of directed networks. Modeling the WWW.
Social networks I
Historical remarks. Data collection. What can we learn from small networks? The different types of social networks. Dyadic, triadic connections. Egocentric networks. Capacity limit of the brain: the Dunbar number. Null models.
Social networks II
A new era in social science: the use of electronic footprints. Email, mobile phone, twit records. Digital communities. Natural weights. The importance of weak ties. The gender and age dependence in close relationships.
Transportation networks. Travel habits and environmental consequences. Data collection: GPS, mobile phones, smart cards. Identification of locations. Mobility statistics. Gravity law and radiation model.
The food web and its hierarchical structure, ecological pyramid. Material and energy flow. Types of food webs. Ecological networks. Fragility.
Networks in economy
Trade network. Financial relationships. Cascades and the global economic crisis. Similarity networks and portfolio optimization.
M.E.J. Newman: Networks – An Introduction (Oxford UP, 2010) (Mathematically demanding)
M.O. Jackson: Social and Economic Networks (Princeton UP, 2008)
A. Barrat, M. Barthélemy and A. Vespignani: Dynamical Processes on Complex Networks (Cambridge UP, 2008)
Hanneman, Robert A. and Mark Riddle. 2005. Introduction to social network method, online available:http://faculty.ucr.edu/~hanneman/nettext
The course makes use of Prof. Barabási’s slides (http://barabasilab.neu.edu/courses/phys5116/) and students are encouraged to visit that site.
The pdf files of the lectures will be made available.
The bulk of the course will be provided in lectures.
- Recognize the importance of the network approach in their own fields of studies;
By successfully absolving the course the students will be able to:
- Map out networks from data on complex systems in diverse fields of applications;
- Carry out statistical analysis of complex networks regarding the basic characteristics;
- Measure dynamic properties of processes on networks;
- Attend the more specialized courses for the Network Science Certificate
There will be two assignments. A Wikipedia article in the field of complex networks has to be written. A modeling problem has to be solved. These tasks have to be tackled by the students independently. At the same time they are encouraged to form study groups. The final project should be prepared by pairs of students.
- Assignments (20%)
- Wikipedia article (20%)
- Modeling task (20%)
- Final project (carried out in pairs) (30%)
- Teacher evaluation (10%)