Academics

EECS 444/544: Analysis of Societal Networks

Instructor: Professor Vijay Subramanian

Course description

Networks are everywhere. We encounter a variety of networks of different sizes and forms on a daily basis: societal networks such as the network of retweets of a certain hashtag on Twitter or the friends network on Facebook; technological networks such as the Internet with the telecommunication network of computers, the links between webpages, the groupings of users generated by recommendation systems for predictions or the network of users on BitTorrent downloading a specific file; and economic networks such as trade networks or supply-chain networks. Some of these networks emerge naturally such as many societal networks, while others are planned such as the public transportation or road network. We depend on the efficient functioning of these networks to transact many of our activities. This course serves as an introduction to the broad class of networks described above: how these networks are connected, how they form, how processes and transactions take place on them, and how Facebook Friends Network Food Contamination Spread Network between Countries Sample Network of Brain Regions London Underground Network they are being transformed and interconnected in the modern world. Students will learn how to develop and apply mathematical models and tools from graph theory, linear algebra, probability and game theory in order to analyze network processes such as how opinions and fads spread on networks, how sponsored advertisements are developed, how web content is displayed, how recommendation systems work, etc.

Textbooks(s)

Networks, Crowds, and Markets: Reasoning About a Highly Connected World, Jon Kleinberg and David Easley (Cambridge University Press, 2010)

A .pdf copy of the textbook is freely available online on the author Jon Kleinberg’s website. 

We may also use material from the following books: 

• Networks: An Introduction, M. E. J. Newman, Oxford University Press, 2010 
• Social and Economic Networks, Matthew O. Jackson, Princeton University Press, 2010 

Additionally, we may use research articles and papers as further reading material. These will be posted on the course website and/or distributed in class.

Syllabus

Graph Theory and Social Networks, Game Theory (sponsored ad auctions), Markets and Strategic
Interaction on Networks (graphical games), Information Networks and the World-Wide Web (centrality,
PageRank, HITS, matching markets), Network Dynamics: Population Models (information cascades),
Network Dynamics: Structural Models (epidemics, cascades).

Super set of material to be covered is:

• Graph Theory & Social Networks
  Topics covered: Basic graph theory, structure & properties
  (Chapters 2, 3, 4 of textbook)
• Graph generation
  Topics covered: Erdos-Renyi random graphs, Preferential attachment
  (Chapter 18 of textbook)
• Game Theory
  Topics covered: Basics, Auctions, Sponsored-search ad-auctions, Equilibria
  (Chapters 6, 9, 15 of textbook)
• Information Networks & the World-Wide Web
  Topics covered: Network centrality, PageRank, HITS, matching markets
  (Chapters 14, 10 of textbook)
• Network Dynamics: Population Models
  Topics covered: Information cascades
  (Chapter 16 of textbook)
• Network Dynamics: Structural Models
  Topics covered: Epidemics, Cascades
  (Chapters 19, 21 of textbook)

Prerequisites 

Most necessary mathematical tools will be developed as a part of the course. However, students are assumed to have some mathematical sophistication (some familiarity with proofs, basic understanding of probability, some exposure to linear algebra and graph theory, etc.). EECS 444: EECS 301, MATH 425 or STATS 425, C or better for prerequisites EECS 544: EECS 301, MATH 425 or STATS 425, or Graduate Standing and C or better for prerequisites 

EECS 203 and EECS 453/551 would be useful but not required.