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, we will learn various algorithms,
mathematical principles, and software platforms
for large scale networks analysis.
In here, the networks can be both physical or logical networks.
Logical networks include
online social networks (e.g., Facebook, WeChat, Twitters, ...etc),
Internet, Skype P2P networks,
geodistributed data center networks (DCNs),
or cities which have mass amount of InternetofThings (IoTs)
devices.
Phyiscal networks include power plant networks, biological networks,..etc.
In this course, we cover fundamental principles
and algorithms for such large scale network analysis.
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 especially important since companies
like Tencent, Alibaba and Huawei are looking for engineers
to carry out large scale network analysis on their services/networks.
Teaching Assistants
 Mr. XYZ Office hour:
Office, HSH Eng Bldg, Room 120, TBD.
Textbook:
Course Grades:
 Homework: 25%
 Project: 25%;
 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 December XX, X:XX pm to Y:YY pm, 2018. ZZZ Room XXX !!!!!!
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
 ... more
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: Sept, XX, 2018. 7:00 pm, in the lecture period)
Solution to Homework 1

More to come ....
Project (Password Protected)
Submission: Please submit your programming project by Dec XX, 2018.

Programming Project
(Graph Data for 964 nodes and 3,000 undirected edges)
Reference books:
Reference papers:
 R. Albert and AL. Barabasi.
Statistical mechanics of complex networks.
Rev. Mod. Phys, Vol. 74, p 4797, 2002
 M. E. J. Newman.
The Structure and Function of Complex Networks.
SIAM Review, Vol. 45, p 167256, 2003
 S. Boccaletti et al.
Complex networks: Structure and dynamics.
Phys. Reports, Vol. 424, p 175308, 2006
 S. N. Dorogovtsev and J. F. F. Mendes.
Evolution of Networks.
Adv. Phys. Vol. 51, N 4, p 10791187
Related software:
 Computation engines:
Python,
Jupyter.
 Python libraries:
 Visualization:
 Open Graph Visualization platform:
Gephi.
 yEd Graph Editor
yEd.
 Graph Visualization Software:
Graphviz.
READING MATERIALS:
 Introduction to network science:
 AlbertLaszlo Barabasi and Eric Bonabeau.
Scale
Free Networks. Scientific American, p 5059, 2003
 Mark Newman.
The physics of networks. Physics Today,2008

Stanley Milgram. The SmallWorld Problem. Psychology
Today, Vol 1, No 1, pp 6167, 1967
 J. Travers and S. Milgram.
An Experimental Study of the Small World
Problem. Sociometry, vol 32, No 4, pp 425433, 1969
 Mark Granovetter. The strengtth of weak
ties , American Journal of Sociology, 78(6):13601380, 1973.

J. Leskovec and E. Horvitz. PlanetaryScale Views on a Large InstantMessaging Network.
Proceedigs WWW 2008

L. Backstrom, P. Boldi, M. Rosa, J. Ugander, S. Vigna.
Four Degrees of Separation.
WebSci '12 Procs. 4th ACM Web Science Conference,
pp 3342, 2012
 Power Laws:

M. E. J. Newman.
Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46(5), 323351, 2005
 A. Clauset, C.R. Shalizi, M.E.J. Newman.
Powerlaw distributions in empirical data. SIAM Review 51(4), 661703, 2009

M. Mitzenmacher.
A brief history of generative models for power law and lognormal
distributions. Internet Mathematics, vol 1, No. 2, pp. 226251, 2004.

M.L. Goldstein, S.A. Morris, and G.G. Yen. Problems with fitting to
the powerlaw distribution , Eur. Phys. J. B 41, pp 255258, 2004.

Chapter 18. Power Laws and
RichGetRicher Phenomena. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected
World".
 Random Graphs:
 P. Erdos and A. Renyi.
On random graphs I. Publ. Math. Debrecen, 1959.
 P. Erdos and A. Renyi.
On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960.
 Chapter 12. Random graphs. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Small World and Dynamical Grwoth Models:
 Duncan J. Watts and Steven H. Strogatz.
Collective dynamics of ``smallworld'' networks.
. Nature 393:44042, 1998.
 AL Barabasi and R. Albert.
Emergence of Scaling in Random Networks. Science, 286, 1999.
 Chapter 14. Models of network formation. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.

Chapter 20. The SmallWorld
Phenomenon. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected
World".
 Centrality Measures:
 Linton C. Freeman.
Centrality in Social Networks. Conceptual Clarification.
Social Networks, Vol 1, pp 215239, 1978
 Phillip Bonacich.
Power and Centrality: A Family of Measures. American journal of sociology, Vol.92, pp 11701182, 1987.
 Leo Katz
A new status index derived from sociometric analysis . Psychometrika, 19, 3943, 1953.
 Phillip Bonacich, Paulette Lloyd,
Eigenvectorlike measures of centrality for asymmetric relations .
Social Networks 23, 191201, 2001
 Chapter 7. Measures and metrics. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Chapter 5. Centrality and Prestige. S. Wasserman
and K. Faust.
"Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
 Link Analysis:
 Sergey Brin, Larry Page.
The Anatomy of a LargeScale Hypertextual Web Search Engine,
,1998.

John M. Kleinberg.
Authoritative Sources in a Hyperlinked Environment. Proc. 9th ACMSIAM Symposium on Discrete Algorithms, 1998.

Andrei Broder et all.
Graph structure in the Web. Procs of the 9th international World Wide Web conference,
2000

Amy N. Langville and Carl D. Meyer,
A Survey of Eigenvector Methods of Web Information Retrieval. 2004

David F. Gleich.
PageRank beyond the Web arXiv:1407.5107, 2014
 Chapter 7. Measures and metrics. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.

Chapter 14. Link Analysis
and Web Search. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected
World".
 Structural Equivalence:

White, D., Reitz, K.P. Measuring role distance: structural, regular and relational
equivalence. Technical report, University of California, Irvine, 1985

S. Borgatti, M. Everett. The class of all regular equivalences: algebraic structure
and computations. Social Networks, v 11, p6568, 1989

E. A. Leicht, P.Holme, and M. E. J. Newman. Vertex similarity in networks. Phys. Rev. E 73, 026120, 200

G. Jeh and J. Widom. SimRank: A Measure of StructuralContext Similarity.
Proceedings of the eighth ACM SIGKDD , p 538543. ACM Press, 2002

M. McPherson, L. SmithLovin, and
J. Cook. Birds of a Feather: Homophily in Social Networks, Annu. Rev. Sociol, 27:41544, 2001.
 M. Newman.
Mixing patterns in
networks. Phys. Rev. E, Vol. 67, p 026126, 2003

M. D. Conover, J. Ratkiewicz, et al. Political Polarization on Twitter.
Fifth International AAAI Conference on Weblogs and Social Media, 2011

N. Christakis and J. Fowler. The spread of obesity in a large social network over 32 years. Engl J Med v 357:370379, 2007
 Chapter 9. Structural Equivalence. S. Wasserman
and K. Faust.
"Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
 Chapter 12. Network Positions and Roles. S. Wasserman
and K. Faust.
"Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
 Chapter 7. Measures and metrics. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Network Communities:
 S. E. Schaeffer.
Graph
clustering. Comp. Sci. Rev., Vol. 1, p 2764, 2007
 S. Fortunato.
Community detection in graphs . Physics Reports,
Vol. 486, pp. 75174, 2010

V. Batagelj, M. Zaversnik.
An O(m) Algorithms for Cores
Decomposition of Networks. 2003
 M.E.J. Newman.
Modularity and community structure in networks. PNAS Vol. 103, N 23, pp 85778582, 2006
 Chapter 7. Matrix algorithms and graph partitioning. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Graph Partitioning Algorithms:

M. Fiedler. Algebraic connectivity of graphs, Czech. Math. J, 23, pp 298305, 1973

A. Pothen, H. Simon and K. Liou. Partitioning sparse matrices with eigenvectors of graphs,
SIAM Journal of Matrix Analysis, 11, pp 430452, 1990

Bruce Hendrickson and Robert Leland. A Multilevel Algorithm for Partitioning Graphs, Sandia National Laboratories, 199

Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation,
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, N 8, pp 888905, 2000
 M.E.J. Newman, M. Girvan.
Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.

B. Good, Y.A. de Montjoye, A. Clauset. Performance of modularity maximization in practical contexts, Physical Review E 81, 046106, 2010
 Chapter 11. Matrix algorithms and graph partitioning. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Community Detection:

G. Palla, I. Derenyi, I. Farkas, T. Vicsek, Uncovering the overlapping community structure
of complex networks in nature and society, Nature 435, 814818, 2005.

U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community
structures in largescale networks, Phys. Rev. E 76 (3), 036106, 2007.

P. Pons and M. Latapy, Computing communities in large networks using random walks,
Journal of Graph Algorithms and Applications, 10, 191218, 2006.

V.D. Blondel, J.L. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding
of communities in large networks, J. Stat. Mech. P10008, 2008.
 Daniel A. Spielman, ShangHua Teng.
A Local Clustering Algorithm for
Massive Graphs and Its Application to Nearly Linear Time Graph
Partitioning. SIAM Journal on
computing, Vol. 42, p. 126, 2013
 R. Andersen, F. Chung, K. Lang.
Local graph partitioning
using pagerank vectors. In Proc. FOCS, 2006.

J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney. Statistical properties of
community structure in large social and information networks. In WWW 08: Procs. of the
17th Int. Conf. on World Wide Web, pages 695704, 2008.
 Diffusion on Networks:
 Lovasz, L.
Random walks on graphs: a survey. In Combinatorics,
Paul Erdos is eighty. pp. 353  397. Budapest: Janos Bolyai Math. Soc., 1993

Chung, Fan R.K. Spectral graph theory (2ed.). Chapter 1. Providence, RI:
American Math. Soc., 1997

Daniel A. Spielman. Spectral Graph theory. Combinatorial Scientific Computing. Chapman and Hall/CRC Press. 2011
 Chapter 6. Mathematics of networks. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Epidemics:
 H.W. Hethcote.
The Mathematics of Infections
Diseases. SIAM Review, Vol. 42, No. 4, pp. 599653, 2000
 Chapter 17. Epidemics on networks. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.
 Epidemics on networks:
Networks and Epidemics models Journal R. Soc. Interface, Vol 2, pp
295307, 2005

G. Witten and G. Poulter
Simulations of infections diseases on networks
Computers in Biology and Medicine, Vol 37, No. 2, pp 195205, 2007

M. Kuperman and G. Abramson
Small World Effect in an Epidemiological Model., Phys. Rev. Lett., Vol 86, No 13, pp 29092912, 2001

Manitz J, Kneib T, Schlather M, Helbing D, Brockmann D. Origin Detection During Foodborne Disease Outbreaks 
A Case Study of the 2011 EHEC/HUS Outbreak in Germany. PLoS Currents. 2014
 Chapter 17. Epidemics on networks. Mark Newman.
"Networks: An Introduction". Oxford University Press, 2010.

Chapter 21. Epidemics. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected
World".
 Social Contagion and Information Spread:
D.J. Daley and D.G. Kendall. Stochastic Rumours. J. Inst. Maths. Applics 1, 4245, 1965.

A. Barrat, M. Barthelemy, A. Vespignani Eds. Dynamical processes on complex networks, Cambridge University Press 2008

Y. Moreno, M. Nekovee, A. Pacheco. Dynamics of rumor spreading in complex networks. Phys. Rev. E 69, 066130, 2004

M. Nekovee, Y. Moreno, G. Biaconi, M. Marsili. Theory of rumor spreading in complex social networks. Physica A 374, pp 457470, 2007.

Luis M.A. Bettencours, A. CintronArias, D.I. Kaiser, C. CastilloChavez. The power of a good idea: Quantitative modeling of the spread of ideas from epidemiological models. Physica A, 364, pp 513536, 2006.

D. LibenNowell, Jon Kleinberg. Tracing in formation flow on a global scale using Internet chainletter data. , PNAS vol 105, n 12, pp 46334638, 2008

J.L. Iribarren, E. Moro, Impact
of Human Activity Patterns on the Dynamics of Information
Diffusion, Phys. Rev. Letters, Vol 103, 038702, 2009

J. Leskovec, L. Adamic, B. Huberman, The Dynamics of Viral Marketing,
EC 2006
 Diffusion of Innovation and Influence Maximization:
 Mark S. Granovetter.
Threshold Models of Collective Behavior. American Journal of Sociology Vol. 83, No. 6, pp. 14201443, 1978.

H. Peyton Young.
The Diffusion of Innovations in Social Networks. In L. E. Blume and S. N. Durlauf (eds.), The Economy as an Evolving Complex System III (2003)
 D. Kempe, J. Kleinberg, E. Tardos.
Maximizing the Spread of Influence
through a Social Network. In Proc. KDD 2003.

D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 57665771, 2002.

M. Richardson, P. Domingos. Mining KnowledgeSharing Sites for Viral
Marketing. In Proc. KDD, 2002.

M. Richardson, P. Domingos. Mining the Network Value of Customers. In Proc. KDD, 2001.

D. Kempe, J. Kleinberg, E. Tardos.
Influential Nodes in a Diffusion
Model for Social Networks. Lecture Notes in Computer Science, Eds
C. Luis, I.Giuseppe et.al, 2005

S. Morris. Contagion. Review of Economic Studies 67, 5778, 2000.

L.Backstrom, D. Huttenlocher, J. Kleinbrg, X. Lan, Group Formation in Large Social Networks:
Membership, Growth and Evolution, In Proc. KDD 2006.

Chapter 19. Cascading Behavior
in Neworks. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected
World".

Chapter 7. Diffusion through Networks. Matthew O. Jackson. "Social and Economic Networks".
 Social Learning:

M.H. DeGroot.
Reaching a Consensus.
Journal of the American Statistical Association, 1974, Vol 69, No 345

Roger L. Berger.
A Necessary and Sufficient Condition for Reaching a Consensus Using
DeGroot's Method. Journal of the American Statistical Association,
Vol. 76, No 374, 1981, pp 415418

Noah Friedkin, and Eugene C. Johnsen,
Social Influence Networks and Opinion Change Advances in Group Processes 16:129, 1999

B. Golub and M. Jackson
Naive Learning in Social Networks and the Wisdom of
Crowds, Amer. Econ. J. Microeconomics, 2:1, pp 112149, 2010

Chapter 8. Learning and Networks. Matthew O. Jackson. "Social and Economic Networks".
 Label Propagation on Graph:
S. A. Macskassy, F. Provost, Classification in Networked Data: A Toolkit and a Univariate Case Study. Journal of Machine Learning Research 8, 935983, 2007

Bengio Yoshua, Delalleau Olivier, Roux Nicolas Le. Label Propagation and Quadratic Criterion. Chapter in SemiSupervised Learning, Eds. O. Chapelle, B. Scholkopf, and A. Zien, MIT Press 2006

Smriti Bhagat, Graham Cormode, S. Muthukrishnan. Node classification in social networks. Chapter in Social Network Data Analytics, Eds. C. Aggrawal,
2011, pp 115148
D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Scholkopf. Learning with local and global consistency. In NIPS, volume 16, 2004.

X. Zhu, Z. Ghahramani, and J. Lafferty. Semisupervised learning using Gaussian fields and harmonic functions. In ICML, 2003.

M. Belkin, P. Niyogi, V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples.
J. Mach. Learn. Res., 7, 23992434, 2006
 Link Prediction:
D. LibenNowell and J. Kleinberg. The link prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019  1031, 2007

R. Lichtenwalter, J.Lussier, and N. Chawla. New perspectives and methods in link prediction. KDD 10: Proceedings of the 16th ACM SIGKDD, 2010

M. Al Hasan, V. Chaoji, S. Salem, M. Zaki, Link prediction using supervised learning. Proceedings of SDM workshop on link analysis, 2006

M. Rattigan, D. Jensen. The case for anomalous link discovery. ACM SIGKDD Explorations Newsletter. v 7, n 2, pp 4147, 2005

M. Al. Hasan, M. Zaki. A survey of link prediction in social networks. In Social Networks Data Analytics, Eds C. Aggarwal, 2011.
 Spatial Segregation:
 Thomas C. Schelling
Dynamic Models of Segregation , Journal of Mathematical Sociology,
Vol. 1, pp 143186, 1971.
 Arnaud Banos
Network effects in Schellin's model of segregation: new evidences from
agentbased simulations. Environment and Planning B: Planning and
Design Vol.39, no. 2, pp. 393405, 2012.
 Giorgio Gagiolo, Marco Valente, Nicolaas Vriend
Segregation in netwroks. Journal of Econ. Behav. & Organization,
Vol. 64, pp 316336, 2007.
 Strategic Network Formation: