Introduction to Network Science
Student/Faculty's Expectations on Teaching and Learning
Instructor:
John C.S. Lui
This is an introductory course on "Network Science",
in particular, it is about the theories, algorithms as well
as system issues for large scale networks
such as online social networks, Internet, geodistributed data center networks (DCNs).
In this course, we cover fundamental principles
and theories for such large scale networks.
Furthermore, how one can use these basic analytical tools
and algorithms to understand the structures and dynamic of such networks.
Note that this course is "conceptual"
in nature. Students need to spend the time to attend the lectures ,
read the book(s) or papers,
do the assignments and finish the project so
to understand and keep pace with the class.
Teaching Assistants
Textbook:
Course Grades:
 Homework: 20%
 Project: 30%;
 Examination: 50%
(note: you need to get at least 25% in the final exam to pass the course)
Policy: Late homework or programming assignments will NOT be
considered.
FINAL EXAMINATION : Date April 21, 7:00 pm to 9:00 pm, 2016. YIA Room 401 !!!!!!
Final Examination :
Please note that the final examination is NOT an openbook exam. You are allowed to
bring in one piece of A4 paper (or 2pages) of ``cheat sheet'' . Topics to be covered
in the final exam are:
 Various centrality measures
 Components, funning effect, degree distributions
 Power law and scalefree networks
 Clustering coefficeint
 Assorting mixing
 Graph partitioning
 Community detection
 Modularity maximization
 Random Graphs
 Concept of Information Maximization
Tentative Outline for the Course:
 Introduction to Large Scale Networks
 Measures and Metrics, Centrality measures
on degree, eigenvector, Katz, pagerank, betweenness, closeness,..etc
 The Largescale Structure of Networks, e.g.,
components, funning effect, degree distributions, power law and
scalefree networks, clustering coefficeint, assorting mixing
 Basic Concepts of Algorithms, e.g.,
useful data structures, time and space complexity
 Fundamental Network Algorithms, e.g.,
algorithms to determine degree distributions, clustering coefficients,
BFS, variants of shortest path, maxflow mincut
 Matrix Algorithms and Graph Partitioning, e.g.,
dominant eigenvector, graph partitioning, community detection, modularity maximization
 Random Graphs, e.g., degree and edges distributions, clustering
coefficient, giant and small components, path length
 Random Graphs with General Degree Distributions
 Networks Formation, e.g, network formation algorithms
 Percolation and Network Resilience, e.g., nodes vs. bonds percoloation, network robustness
 Epidemics on Networks, e.g., influence models, network stability and information spreading
 Dynamic Systems on Networks
 Network Search
 Network Advertisement
 Network Search and Exploration
 Gametheoretic Analysis of Online Social Networks
 Data Center Networks (DCNs)
 Data Plane vs. Control Plane in networks
 Software Defined Networks (SDNs)
 more to be added later....
Lecture Notes: (Password Protected)

Administrative matter

Introduction to Network Science

Introduction to Technological Networks

Introduction to Social Networks

Introduction to Networks of Information

Mathematics of Networks

Performance Measures and Metrics

Largescale Structure of Networks

Fundamental Network Algorithms

Matrix Algorithms and Graph Partitioning

Random Networks

Random Networks with General Degree Distributions

Theory of Network Formation

Network Models of Smallworld and Exponential Random Graphs (*****)

Percolation and Network Resilience (*****)

Epidemics on Networks (*****)

Dynamical Systems on Networks (*****)

Network Search (*****)

Introduction to Theory of Submodularity

Calculation of Group Closeness Centrality

Analyzing Competitive Influence Maximization Problems with Partial Information

Boosting Information Spread: An Algorithmic Approach
Homework (Password Protected)
Submission: Please submit your homework in class

Homework 1
(Deadline: Feb 18, 2016. 7:00 pm, in the lecture period)
Solution to Homework 1

Homework 2
(Deadline: March 10 , 2016. 7:00 pm, in the lecture period)
Solution to Homework 2
Project (Password Protected)
Submission: Please submit your programming project by May 3rd, 2016.

Programming Project
(Graph Data for 964 nodes and 3,000 undirected edges)
References: