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 recently. 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.
This is an interdisciplinary course and students with different backgrounds are expected to register for it. The aim is to get acquainted with the basic concepts of network science including elements of the theory of graphs, dynamics of and on networks as well as with applications from biology, sociology, economics and other fields. Mostly elementary math prerequisites are assumed, the tools needed will constitute part of the course.
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.
Networks may be coupled: network of networks. Multi-layer networks and their characterization. Multiplex networks: different link types. Effect on the community structure.
Love and hate: Links with different signs. The notion of structural balance and weak balance theory. Dynamics leading to structural balance.
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)
A.-L. Barabási: Network Science (Cambridge UP, 2016)
J. P. Scott: Social Network Analysis: A Handbook (Sage Publications, 2004)
A. Barrat, M. Barthélemy and A. Vespignani: Dynamical Processes on Complex Networks (Cambridge UP, 2008)
D. Easley and J. Kleinberg: Networks, Crowds and Markets (Cambridge UP, 2010)
The pdf files of the lectures will be made available.
The bulk of the course will be provided in lectures. There will be discussions of the tasks
and the final projects will be presented by the students in a seminar form.
The course has an e-learning site where materials about the lectures, homework, etc.
are posted. It also serves for communication.
By successfully absolving the course the students will be able to:
- Recognize the importance of the network approach in their own fields of studies;
- 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 in Network Science.
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 individually (for Network Science PhD students) or by pairs of students (in other programs). There will be homework tasks.
- Assignments (Assignment 1: 10%, Assignment 2: 20%)
- Wikipedia article (20%)
- Final project (carried out individually (for CNS students) or in pairs (for others)) (40%)
- Teacher evaluation (mostly based on homework) (10%)