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, geo-distributed data center networks (DCNs), or cities which have mass amount of Internet-of-Things (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.

• Networks: An Introduction, by Mark Newman
• Various papers and references which will be provided as we introduce topics.

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.

• Instead of lecture on Sept 26, video lecture will be uploaded to the Blackboard (http://blackboard.cuhk.edu.hk/).
• Class swap: Instead of lecture on Oct 10, we will have it on Oct 13, 9:00am - noon. AIT G04.
• Instead of lecture on Oct 17 (Chung Yueng Festival), video lecture will be uploaded to the Blackboard (http://blackboard.cuhk.edu.hk/).
• Class swap: Instead of Nov 7, we have it on Nov 10th, 9:00 am - noon. AIT G04.
• Class swap: Instead of Nov 21, we have it on Nov 17th, 9:00 am - noon. AIT G04.

• September: 5, 12, 19, 26 (video lecture)
• October: 3, 13 , 17 (video lecture) , 24, 31
• November: 10 , 14, 17

For the final examination, you are allowed to bring lecture notes (those we covered in class) to the examination room. Topics to be covered in the final exam are:

• Various centrality measures
• Components, funning effect, degree distributions
• Power law and scale-free networks
• Clustering coefficeint
• Assorting mixing
• Graph partitioning
• Community detection
• Modularity maximization
• Random Graphs
• Concept of Information Maximization
• ... more

• Introduction to Large Scale Networks
• Measures and Metrics, Centrality measures on degree, eigenvector, Katz, page-rank, betweenness, closeness,..etc
• The Large-scale Structure of Networks, e.g., components, funning effect, degree distributions, power law and scale-free 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, max-flow min-cut
• 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
• Game-theoretic 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 1

Introduction to Network Science 2

More to come ....

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

• "Social and Economic Networks", by Matthew O. Jackson. Princeton University Press, 2010.
• "Networks, Crowds, and Markets: Reasoning About a Highly Connected World." by David Easley and John Kleinberg, Cambridge University Press 2010.
• "Social Network Analysis. Methods and Applications." by Stanley Wasserman and Katherine Faust, Cambridge University Press, 1994.

• R. Albert and A-L. Barabasi. Statistical mechanics of complex networks. Rev. Mod. Phys, Vol. 74, p 47-97, 2002
• M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, Vol. 45, p 167-256, 2003
• S. Boccaletti et al. Complex networks: Structure and dynamics. Phys. Reports, Vol. 424, p 175-308, 2006
• S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks. Adv. Phys. Vol. 51, N 4, p 1079-1187

• Computation engines: Python, Jupyter.
• Python libraries:
  • Numerical modules: Numpy, Scipy.
  • Graph algorithms and visualization NetworkX.
• Visualization:
  • Open Graph Visualization platform: Gephi.
  • yEd Graph Editor yEd.
  • Graph Visualization Software: Graphviz.

• Introduction to network science:
  • Albert-Laszlo Barabasi and Eric Bonabeau. Scale Free Networks. Scientific American, p 50-59, 2003
  • Mark Newman. The physics of networks. Physics Today,2008
  • Stanley Milgram. The Small-World Problem. Psychology Today, Vol 1, No 1, pp 61-67, 1967
  • J. Travers and S. Milgram. An Experimental Study of the Small World Problem. Sociometry, vol 32, No 4, pp 425-433, 1969
  • Mark Granovetter. The strengtth of weak ties , American Journal of Sociology, 78(6):1360-1380, 1973.
  • J. Leskovec and E. Horvitz. Planetary-Scale Views on a Large Instant-Messaging 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 33-42, 2012
• Power Laws:
  • M. E. J. Newman. Power laws, Pareto distributions and Zipf's law. Contemporary Physics 46(5), 323-351, 2005
  • A. Clauset, C.R. Shalizi, M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009
  • M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
  • M.L. Goldstein, S.A. Morris, and G.G. Yen. Problems with fitting to the power-law distribution , Eur. Phys. J. B 41, pp 255-258, 2004.
  • Chapter 18. Power Laws and Rich-Get-Richer 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 ``small-world'' networks. . Nature 393:440-42, 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 Small-World 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 215-239, 1978
  • Phillip Bonacich. Power and Centrality: A Family of Measures. American journal of sociology, Vol.92, pp 1170-1182, 1987.
  • Leo Katz A new status index derived from sociometric analysis . Psychometrika, 19, 39-43, 1953.
  • Phillip Bonacich, Paulette Lloyd, Eigenvector-like measures of centrality for asymmetric relations . Social Networks 23, 191--201, 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 Large-Scale Hypertextual Web Search Engine, ,1998.
  • John M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Proc. 9th ACM-SIAM 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, p65-68, 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 Structural-Context Similarity. Proceedings of the eighth ACM SIGKDD , p 538-543. ACM Press, 2002
  • M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a Feather: Homophily in Social Networks, Annu. Rev. Sociol, 27:415-44, 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:370-379, 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 27-64, 2007
  • S. Fortunato. Community detection in graphs . Physics Reports, Vol. 486, pp. 75-174, 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 8577-8582, 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 298-305, 1973
  • A. Pothen, H. Simon and K. Liou. Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal of Matrix Analysis, 11, pp 430-452, 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 888-905, 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, 814-818, 2005.
  • U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale 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, 191-218, 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, Shang-Hua Teng. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on computing, Vol. 42, p. 1-26, 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 695-704, 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. 599-653, 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 295-307, 2005
  • G. Witten and G. Poulter Simulations of infections diseases on networks Computers in Biology and Medicine, Vol 37, No. 2, pp 195-205, 2007
  • M. Kuperman and G. Abramson Small World Effect in an Epidemiological Model., Phys. Rev. Lett., Vol 86, No 13, pp 2909-2912, 2001
  • Manitz J, Kneib T, Schlather M, Helbing D, Brockmann D. Origin Detection During Food-borne 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, 42-45, 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 457-470, 2007.
  • Luis M.A. Bettencours, A. Cintron-Arias, D.I. Kaiser, C. Castillo-Chavez. The power of a good idea: Quantitative modeling of the spread of ideas from epidemiological models. Physica A, 364, pp 513-536, 2006.
  • D. Liben-Nowell, Jon Kleinberg. Tracing in formation flow on a global scale using Internet chain-letter data. , PNAS vol 105, n 12, pp 4633-4638, 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. 1420-1443, 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, 5766-5771, 2002.
  • M. Richardson, P. Domingos. Mining Knowledge-Sharing 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, 57-78, 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 415-418
  • Noah Friedkin, and Eugene C. Johnsen, Social Influence Networks and Opinion Change Advances in Group Processes 16:1-29, 1999
  • B. Golub and M. Jackson Naive Learning in Social Networks and the Wisdom of Crowds, Amer. Econ. J. Microeconomics, 2:1, pp 112-149, 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, 935-983, 2007
  • Bengio Yoshua, Delalleau Olivier, Roux Nicolas Le. Label Propagation and Quadratic Criterion. Chapter in Semi-Supervised 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 115-148 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. Semi-supervised 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, 2399-2434, 2006
• Link Prediction:
  D. Liben-Nowell 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 41-47, 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 143-186, 1971.
  • Arnaud Banos Network effects in Schellin's model of segregation: new evidences from agent-based simulations. Environment and Planning B: Planning and Design Vol.39, no. 2, pp. 393-405, 2012.
  • Giorgio Gagiolo, Marco Valente, Nicolaas Vriend Segregation in netwroks. Journal of Econ. Behav. & Organization, Vol. 64, pp 316-336, 2007.
• Strategic Network Formation:
  • Matthew O. Jackson. The Economics of Social Networks. California Institute of Technology, 2005.
  • Matthew O. Jackson. A Strategic Model of Social and Economic Networks. Journal of Economic Theory, Vol 71, pp 44-74, 1996.
  • Chapter 6. Strategic Network Formation. Matthew O. Jackson. "Social and Economic Networks".

  ---