Course: INA: Introduction to Network Analysis

Topic outline

General

Introduction to Network Analysis (INA)

Course lecturer

Outline & objective

Networks or graphs are ubiquitous in everyday life. Examples include online social networks, the Web, wiring of a neural system, references between WikiLeaks cables, Supervizor, terrorist affiliations, LPP bus map, plumbing systems and your brain. Many such real-world networks reveal characteristic patterns of connectedness that are far from regular or random. Networks have thus been a prominent tool for investigating real-world systems since the 18th century. However, while small networks can be drawn by hand and analyzed by a naked eye, real-world networks require specialized computer algorithms, techniques and models. This led to the emergence of a new scientific field about 20 years ago denoted network analysis.

The course will first introduce the field of network analysis and highlight the differences between classical graph theory and modern network science. In the main part of the course, the students will learn about fundamental concepts and techniques for the analysis of real-world networks including node centralities and equivalence, graphlet counting, blockmodeling, community detection, role discovery, link prediction, network modeling and visualization. The last part of the course will be devoted to selected practical applications of network analysis in fraud detection, software engineering, information science and other.

The objective of the course is to present a broad spectrum of network analysis concepts and techniques, clarify their theoretical foundations and demonstrate their practical applicability. The lectures will give a theoretical discussion on network concepts and present efficient algorithms and techniques for their analysis, while the students will work on practical examples of applying network analysis within labs and their coursework. The topics covered were carefully selected thus to be suitable for a wide range of students and to serve as an introduction to more advanced network analysis courses like Machine Learning with Graphs (MLG) and Advanced Topics in Network Science (ANTS).

Except for good programming skills in some general purpose language (e.g. C/C++, Python, Java), there are no specific prerequisites for the course. However, the students will benefit from a solid knowledge in graph theory, probability theory and statistics, and linear algebra.

Coursework & grading

The students are expected to attend and actively participate in lectures and labs. The ongoing coursework will consist of three homeworks on network analysis concepts and techniques covered in the lectures. Each homework will require certain amount of programming, some analytical derivations and some practical applications to real-world problems. There will also be an additional homework at the beginning of the course, which will not be graded.

The main part of the coursework will consist of a substantial course project. The topic of the project will have to be either empirical evaluation of selected concepts and techniques on an interesting domain, analytical derivation of rigorous theoretical results for selected concepts or techniques, or substantial contribution to the (Slovenian) network analysis community (e.g. online dictionary) or this course. The students will be encouraged to submit up to an eight-page technical report describing the course project to the preprint server arXiv.org, present their project in front of the faculty within Cookie seminars or AI seminars, or make their work publicly available. All students will have to present their project proposal and final project results in front of the class (tentative), while their work will have to be submitted only in the format selected (e.g. students preparing a seminar will not have to write a report). The students will be encouraged to work in pairs or triplets, while larger groups will be allowed only in exceptional cases. Further details on course projects will be given during lectures or labs.

Network analysis concepts and techniques not covered by the coursework will be evaluated within short weekly quizess during lectures or labs.

The base grade for the course will be based 37.5% on the homeworks (12.5% on each homework), 47.5% on the course project (10% on the project proposal, 15% on the project milestone and 22.5% on the final project), and 15% on weekly quizess, course participation and commitment. The final grade will be decided during an oral exam at the end of the course. The students with exceptional coursework will not have to attend the oral exam.

Literature & readings

The course notes, handouts, readings and other materials will be posted periodically on this web page. The course literature will be given in English in the form of handouts with references to selected scientific papers and relevant chapters from the following course books.

Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
de Nooy, W., Mrvar, A. & Batagelj, V., Exploratory Social Network Analysis (Cambridge University Press, 2011).
Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).

Course schedule

The lectures start on Feb 17th, 2019 and the labs starts on Feb 24th, 2020. The lectures and labs will be held either in English or Slovene. Weekly course schedule is as follows.

Lectures on Mondays at 11:00am in PR 19
Office hours on Tuesdays at 1:00pm in R 2.49
Labs on Mondays at 2:00pm in PR 7 & Tuesdays/Fridays at 11:00am in PR 10/9

Course assignments

Course assignments will be out and due according to the schedule below. Each assignment is due on Monday at 2:00pm. Twice during the semester the students can take advantage of late days, which means that the assignment is submitted late. Late days for an assignment that is due this Monday expire on Friday at 1:00pm.

The students can prepare their assignments either in English or Slovene. Each assignment must be submitted as a hard-copy in the submission box in front of R 2.49 and also as an electronic version to eUcilnica. Hard-copies will be used for grading, while electronic submissions will be used for plagiarism detection and archive purposes. Each submission must include the course cover sheet with a signed honor code.

Week	Date	Out	Due	Challenge	Comment
1	Feb 17th	Homework #0 (PDF, TeX)
2	Feb 24th		Homework #0	Four knights
3	Mar 2nd
4	Mar 9th	Homework #1 (PDF, TeX)		Grand graph
5	Mar 16th
6	Mar 23rd		Homework #1	÷-vector centrality
7	Mar 30th	Homework #2 (PDF, TeX)
8	Apr 6th			Five networks
9	Apr 13th		Homework #2		Easter days
10	Apr 20th	Homework #3 (PDF, TeX)		PageRank centrality
11	Apr 27th				Labour days
12	May 4th		Homework #3
13	May 11th		Project proposal
14	May 18th
15	May 25th		Project milestone
16	Jun 1st				Semester ends
17	Jun 8th		Project deadline		Exam period

Corona course videos

Week	Date	Intro	Lectures	Labs
	...
4	Mar 9th
5	Mar 16th	05-intro	05-bridging, 05-smallworld & 05-project	v-1-labs
6	Mar 23rd	06-intro	06-science, 06-scalefree & 06-preferential	v-2-labs
7	Mar 30th	07-intro	07-mixing, 07-fragments & 07-hw#1	vii-labs
8	Apr 6th	08-intro	08-community & 08-clustering	viii-labs
9	Apr 13th
	...

Course homeworks
Homework #0 submission Assignment
Homework #1 submission Assignment
Homework #2 submission Assignment
Homework #3 submission Assignment
Course projects
Project proposal submission Assignment
Project milestone submission Assignment
Project report submission Assignment
Course challenges
Course discussions
Course announcements Forum

Course overview and logistics
Course overview and logistics
Course overview, logistics and syllabus. Coursework description, instructions and other details.
Lecture handouts:
Other material:
- Project reports from previous years
- Course projects examples and proposals
From graph theory to network science
From graph theory to network science
From classical graph theory to social network analysis and modern network science. Networks in different fields of science.
Lecture handouts:
Book chapters:
- → Ch. 1: Introduction in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 1-5: Introduction etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 1: Overview in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
Course readings:
- Barabási, A.-L., The network takeover, Nat. Phys. 8(1), 14-16 (2012).
- → Newman, M.E.J., The physics of networks, Phys. Today 61(11), 33-38 (2008).
- Barabási, A.-L. & Bonabeau, E., Scale-free networks, Sci. Am. 288(5), 50-59 (2003).
- → Newman, M.E.J., Communities, modules and large-scale structure in networks, Nat. Phys. 8(1), 25-31 (2012).
- Vespignani, A., Modelling dynamical processes in complex socio-technical systems, Nat. Phys. 8(1), 32-39 (2012).
- Motter, A.E. & Yang, Y., The unfolding and control of network cascades, Phys. Today 70(1), 33-39 (2017).
- Hegeman, T. & Iosup, A., Survey of graph analysis applications, e-print arXiv:180700382v1, pp. 23 (2018).
- Cimini, G., Squartini, T. et al., The statistical physics of real-world networks, Nat. Rev. Phys. 1(1), 58-71 (2019).
- → Cramer, C., Porter, M.A. et al., Network Literacy: Essential Concepts and Core Ideas (Creative Commons Licence, 2015).
- Hidalgo, C.A., Disconnected, fragmented, or united? A trans-disciplinary review of network science, Appl. Netw. Sci. 1, 6 (2016).
- Molontay, R. & Nagy, M., Two decades of network science, In: Proceedings of ASONAM '19 (Vancouver, Canada, 2019), pp. 578–583.
- Ch. 1: Uvod in Šubelj, L., Odkrivanje skupin vozlišč v velikih realnih omrežjih, PhD thesis (University of Ljubljana, 2013).
Random graphs vs real networks
Random graphs vs real networks
Graphology and networkology. Network representations, formats and data. Random graph models and real networks models.
Lecture handouts:
Lab handouts:
- Network representations and algorithms (java, log)
- Advanced algorithms and random graphs (java, log)
Book chapters:
- → Ch. 2: Graph theory & Ch. 4.8: Generating networks in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 6: Mathematics of networks & Ch. 12-13: Random graphs etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 2: Graphs in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
Course readings:
- Erdős, P. & Rényi, A., On random graphs I, Publ. Math. Debrecen 6, 290-297 (1959).
- Watts, D.J. & Strogatz, S.H., Collective dynamics of 'small-world' networks, Nature 393(6684), 440-442 (1998).
- Barabási, A.-L. & Albert, R., Emergence of scaling in random networks, Science 286(5439), 509-512 (1999).
- Broder, A., Kumar, R. et al., Graph structure in the Web, Comput. Netw. 33(1-6), 309-320 (2000).
- Newman, M.E.J., Strogatz, S.H. & Watts, D.J., Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64(2), 026118 (2001).
- Milo, R., Kashtan, N. et al., On the uniform generation of random graphs with prescribed degree sequences, e-print arXiv:0312028v2, pp. 4 (2004).
- Carstens, C.J. & Horadam, K.J., Switching edges to randomize networks: What goes wrong and how to fix it, J. Complex Netw. 5(3), 337-351 (2017).
- Fosdick, B., Larremore, D. et al., Configuring random graph models with fixed degree sequences, SIAM Rev. 60(2), 315-355 (2018).
- → Newman, M.E.J., Watts, D.J. & Strogatz, S.H., Random graph models of social networks, P. Natl. Acad. Sci. USA 99, 2566-2572 (2002).
- → Newman, M.E.J. & Park, J., Why social networks are different from other types of networks, Phys. Rev. E 68(3), 036122 (2003).
- → Backstrom, L., Boldi, P. et al., Four degrees of separation, In: Proceedings of WebSci '12 (Evanston, IL, USA, 2012), pp. 45-54.
- McAuley, J.J. & Leskovec, J., Learning to discover social circles in ego networks, In: Proceedings of NIPS '12 (Lake Tahoe, NV, USA, 2012), pp. 548-556.
- Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).
Small-world and scale-free networks
Small-world and scale-free networks
Degrees of separation, small-world networks and model. Power-law degree distributions, scale-free networks and models.

Lecture handouts:
Lab handouts:
- Small-world and scale-free networks (java, log)
Book chapters:
- → Ch. 3.8-9: Small worlds etc. & Ch. 4-5: Scale-free property etc. in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 8.4: Power laws etc. & Ch. 14-15: Models of network formation etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 18: Power laws etc. and Ch. 20: Small-world phenomenon in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
Course readings:
- Milgram, S., The small world problem , Psychol. Today 1(1), 60-67 (1967).
- Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
- → Watts, D.J. & Strogatz, S.H., Collective dynamics of 'small-world' networks, Nature 393(6684), 440-442 (1998).
- Dodds, P.S., Muhamad, R. & Watts, D.J., An experimental study of search in global social networks, Science 301(5634), 827-829 (2003).
- Liben-Nowell, D., Novak, J. et al., Geographic routing in social networks, P. Natl. Acad. Sci. USA 102(33), 11623-11628 (2005).
- Backstrom, L., Boldi, P. et al., Four degrees of separation, In: Proceedings of WebSci '12 (Evanston, IL, USA, 2012), pp. 45-54.
- Ugander, J., Karrer, B. et al., The anatomy of the Facebook social graph, e-print arXiv:1111.4503v1, pp. 17 (2011).
- → Zamora-López, G. & Brasselet, R., Sizing the length of complex networks, e-print arXiv:1810.12825v1, pp. 25 (2018).
- → Kleinberg, J.M., Navigation in a small world, Nature 406(6798), 845 (2000).
- de Solla Price, D.J., Networks of scientific papers, Science 149, 510-515 (1965).
- → Barabási, A.-L. & Albert, R., Emergence of scaling in random networks, Science 286(5439), 509-512 (1999).
- Faloutsos, M., Faloutsos, P. & Faloutsos, C., On power-law relationships of the Internet topology, Comput. Commun. Rev. 29(4), 251-262 (1999).
- Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
- → Albert, R., Jeong, H. & Barabási, A.-L., Error and attack tolerance of complex networks, Nature 406(6794), 378-382 (2000).
- Albert, R., Jeong, H. & Barabási, A.-L., Diameter of the World Wide Web, Nature 401, 130-131 (1999).
- Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).
- De Domenico, M. & Arenas, A., Modeling structure and resilience of the dark network, Phys. Rev. E 95(2), 022313 (2017).
- Golosovsky, M., Preferential attachment mechanism of complex network growth, e-print arXiv:1802.09786v1, pp. 12 (2018).
- Voitalov, I., van der Hoorn, P. et al., Scale-free networks well done, e-print arXiv:1811.02071v1, pp. 31 (2018).
- Broido, A.D. & Clauset, A., Scale-free networks are rare, Nat. Commun. 10(1), 1017 (2019).
- Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).
- → Holme, P., Rare and everywhere, Nat. Commun. 10(1), 1016 (2019).
Node mixing and network structure
This topic
Node mixing and network structure
Assortative and disassortative mixing. Degree mixing matrix, function and coefficient. Structural cutoff and disassortativity.
Lecture handouts:
- Node mixing in networks
Lab handouts:
- Node degree mixing (java, log)
Book chapters:
- → Ch. 7: Degree correlations in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 7.13: Homophily & Ch. 8.7: Assortative mixing in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Course readings:
- Newman, M.E.J., Mixing patterns in networks, Phys. Rev. E 67(2), 026126 (2003).
- Newman, M.E.J., Assortative mixing in networks, Phys. Rev. Lett. 89(20), 208701 (2002).
- → Newman, M.E.J. & Park, J., Why social networks are different from other types of networks, Phys. Rev. E 68(3), 036122 (2003).
- Pastor-Satorras, R., Vázquez, A. & Vespignani, A., Dynamical and correlation properties of the Internet, Phys. Rev. Lett. 87(25), 258701 (2001).
- Vázquez, A., Pastor-Satorras, R. & Vespignani, A., Large-scale topological and dynamical properties of the Internet, Phys. Rev. E 65(6), 066130 (2002).
- Xulvi-Brunet, R. & Sokolov, I.M., Changing correlations in networks: Assortativity and dissortativity, Acta Phys. Pol. B 36, 1431-1455 (2005).
- → Park, J. & Barabási, A.-L., Distribution of node characteristics in complex networks, P. Natl. Acad. Sci. USA 104(46), 17916-17920 (2007).
- → Foster, J.G., Foster, D.V. et al., Edge direction and the structure of networks, P. Natl. Acad. Sci. USA 107(24), 10815-10820 (2010).
- Peel, L., Delvenne, J.-C., & Lambiotte, R., Multiscale mixing patterns in networks, P. Natl. Acad. Sci. USA 115(16), 4057-4062 (2018).
- Estrada, E., Combinatorial study of degree assortativity in networks, Phys. Rev. E 84(4), 047101 (2011).
Node clusters and mesoscopic structure
Node clusters and mesoscopic structure
Community and core-periphery structure. Graph partitioning, community detection, blockmodeling, stochastic block models etc.
Lecture handouts:
- Network community structure
- Partitioning and community detection
- Blockmodeling and block models
- Network core-periphery structure
Lab handouts:
- Community detection and partitioning (java, log)
- Block models and k-cores decomposition (java, log)
Book chapters:
- → Ch. 9: Communities in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 7.12-13: Homophily etc. & Ch. 11: Graph partitioning in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 21: Communities in networks in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
- Ch. 3: Strong and weak ties in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
Course readings:
- Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
- Girvan, M. & Newman, M.E.J., Community structure in social and biological networks, P. Natl. Acad. Sci. USA 99(12), 7821-7826 (2002).
- Newman, M.E.J. & Girvan, M., Mixing patterns and community structure in networks, Phys. Rev. E 67(2), 026126 (2003).
- Palla, G., Derényi, I. et al., Uncovering the overlapping community structure of complex networks in nature and society, Nature 435(7043), 814-818 (2005).
- Onnela, J.-P., Saramäki, J. et al., Structure and tie strengths in mobile communication networks, P. Natl. Acad. Sci. USA 104(18), 7332-7336 (2007).
- Lancichinetti, A., Kivela, M. et al., Characterizing the community structure of complex networks, PLoS ONE 5(8), e11976 (2010).
- Ahn, Y.-Y., Bagrow, J.P. & Lehmann, S., Link communities reveal multiscale complexity in networks, Nature 466(7307), 761-764 (2010).
- → Hric, D., Darst, R.K. & Fortunato, S., Community detection in networks: Structural communities versus ground truth, Phys. Rev. E 90(6), 062805 (2014).
- → Schaub, M.T., Delvenne, J.-C. et al., The many facets of community detection in complex networks, Appl. Netw. Sci. 2, 4 (2017).
- → Newman, M.E.J., Communities, modules and large-scale structure in networks, Nat. Phys. 8(1), 25-31 (2012).
- Fortunato, S., Community detection in graphs, Phys. Rep. 486(3-5), 75-174 (2010).
- → Fortunato, S. & Hric, D., Community detection in networks: A user guide, Phys. Rep. 659, 1-44 (2016).
- Xie, J., Kelley, S. & Szymanski, B.K., Overlapping community detection in networks, ACM Comput. Surv. 45(4), 43 (2013).
- Lancichinetti, A. & Fortunato, S., Community detection algorithms: A comparative analysis, Phys. Rev. E 80(5), 056117 (2009).
- Raghavan, U.N., Albert, R. & Kumara, S., Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76(3), 036106 (2007).
- Rosvall, M. & Bergstrom, C.T., Maps of random walks on complex networks reveal community structure, P. Natl. Acad. Sci. USA 105(4), 1118-1123 (2008).
- Blondel, V.D., Guillaume, J.-L. et al., Fast unfolding of communities in large networks, J. Stat. Mech., P10008 (2008).
- Kumpula, J.M., Kivelä, M. et al., Sequential algorithm for fast clique percolation, Phys. Rev. E 78(2), 026109 (2008).
- Šubelj, L. & Bajec, M., Ubiquitousness of link-density and link-pattern communities in real-world networks, Eur. Phys. J. B 85(1), 32 (2012).
- Zhao, Y., Levina, E. & Zhu, J., Community extraction for social networks, P. Natl. Acad. Sci. USA 108(18), 7321-7326 (2011).
- Reichardt, J. & White, D.R., Role models for complex networks, Eur. Phys. J. B 60(2), 217-224 (2007).
- → Newman, M.E.J. & Leicht, E.A., Mixture models and exploratory analysis in networks, P. Natl. Acad. Sci. USA 104(23), 9564 (2007).
- → Karrer, B. & Newman, M.E.J., Stochastic blockmodels and community structure in networks, Phys. Rev. E 83(1), 016107 (2011).
- Peixoto, T., Model selection and hypothesis testing for large-scale network models with overlapping groups, Phys. Rev. X 5(1), 011033 (2015).
- → Guimera, R., Sales-Pardo, M. & Amaral, L.A.N., Classes of complex networks defined by role-to-role connectivity profiles, Nat. Phys. 3(1), 63-69 (2007).
- Clauset, A., Moore, C. & Newman, M.E.J., Hierarchical structure and the prediction of missing links in networks, Nature 453(7191), 98-101 (2008).
- Guimera, R. & Sales-Pardo, M., Missing and spurious interactions and the reconstruction of complex networks, P. Natl. Acad. Sci. USA 106(52), 22073-22078 (2009).
- Šubelj, L. & Bajec, M., Group detection in complex networks: An algorithm and comparison of the state of the art, Physica A 397, 144-156 (2014).
- Seidman, S.B., Network structure and minimum degree, Soc. Networks 5(3), 269–287 (1983).
- Borgatti, S.P. & Everett, M.G., Models of core/periphery structures, Soc. Networks 21(4), 375–395 (2000).
- Holme, P., Core-periphery organization of complex networks, Phys. Rev. E 72(4), 46111 (2005).
- → Leskovec, J., Lang, K.J. et al., Community structure in large networks, Internet Math. 6(1), 29–123 (2009).
- Batagelj, V. & Zaveršnik, M., An O(m) algorithm for cores decomposition of networks, Adv. Data Anal. Classif. 5(2), 129–145 (2011).
- → Csermely, P., London, A. et al., Structure and dynamics of core/periphery networks, J. Complex Netw. 1(2), 93-123 (2013).
- Rombach, M., Porter, M. et al., Core-periphery structure in networks, SIAM J. Appl. Math. 74(1), 167–190 (2014).
- Zhang, X., Martin, T. & Newman, M.E.J., Identification of core-periphery structure in networks, Phys. Rev. E 91(3), 32803 (2015).
- → Jeub, L.G.S., Balachandran, P. et al., Think locally, act locally, Phys. Rev. E 91(1), 12821 (2015).
- Ma, A. & Mondragón, R.J., Rich-cores in networks, PLoS ONE 10(3), e0119678 (2015).
Network fragments and frequent subgraphs
Network fragments and frequent subgraphs
Network motifs, motif significance and ratio profiles. Network graphlets, node orbits and graphlet degree distributions.
Lecture handouts:
- Network motifs and graphlets
Book chapters:
- → Ch. 13: Fragment-based measures in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
Course readings:
- Milo, R., Shen-Orr, S. et al., Network motifs: Simple building blocks of complex networks, Science 298(5594), 824-827 (2002).
- → Milo, R., Itzkovitz, S. et al., Superfamilies of evolved and designed networks, Science 303(5663), 1538-1542 (2004).
- → Valverde, S. & Solé, R.V., Network motifs in computational graphs: A case study in software architecture, Phys. Rev. E 72(2), 026107 (2005).
- Davies, T. & Marchione, E., Event networks and the identification of crime pattern motifs, PLoS ONE 10(11), e0143638 (2015).
- → Benson, A.R., Gleich, D.F. & Leskovec, J., Higher-order organization of complex networks, Science 353(6295), 163-166 (2016).
- Pržulj, N., Corneil, D.G. & Jurisica, I., Modeling interactome: Scale-free or geometric?, Bioinformatics 20(18), 3508-3515 (2004).
- Pržulj, N., Biological network comparison using graphlet degree distribution, Bioinformatics 23(2), e177-e183 (2007).
- Yaveroğlu, Ö.N., Malod-Dognin, N. et al., Revealing the hidden language of complex networks, Sci. Rep. 4, 4547 (2014).
- Hočevar, T. & Demšar, J., A combinatorial approach to graphlet counting, Bioinformatics 30(4), 559-565 (2014).
- Soufiani, H.A. & Airoldi, E.M., Graphlet decomposition of a weighted network, In: Proceedings of AISTATS '12 (La Palma, Spain, 2012), pp. 54-63.
- → Sarajlić, A., Malod-Dognin, N. et al., Predictive functional connectivity of real-world systems, e-print arXiv:1603.05470v1, pp. 17 (2016).
- → Sanchez-Garcia, R.J., Exploiting symmetry in network analysis, e-print arXiv:1803.06915v1, pp. 7 (2018).
Node position and measures of centrality
Node position and measures of centrality
Node clustering coefficients, degrees, eigenvector, closeness and betweenness centrality. Link analysis algorithms.
Lecture handouts:
- Measures of node centrality
- Link analysis algorithms
Lab handouts:
- Node centrality and PageRank (java, log)
Book chapters:
- → Ch. 7: Measures and metrics in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 14: Link analysis and Web search in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
- Ch. 14: Classical node centrality & Ch. 15: Spectral etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
Course readings:
- Katz, L., A new status index derived from sociometric analysis, Psychometrika 18(1), 39-43 (1953).
- Freeman, L., A set of measures of centrality based on betweenness, Sociometry 40(1), 35-41 (1977).
- Bonacich, P., Power and centrality: A family of measures, Am. J. Sociology 92(5), 1170-1182 (1987).
- Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2), 163-177 (2001).
- Jeong, H., Mason, S.P. et al., Lethality and centrality in protein networks, Nature 411, 41-42 (2001).
- → Soffer, S.N. & Vázquez, A., Network clustering coefficient without degree-correlation biases, Phys. Rev. E 71(5), 057101 (2005).
- → Newman, M.E.J., A measure of betweenness centrality based on random walks, Soc. Networks 27(1), 39-54 (2005).
- → Jensen, P., Morini, M. et al., Detecting global bridges in networks, J. Complex Netw. 4(3), 319-329 (2015).
- Everett, M.G. & Valente, T.W., Bridging, brokerage and betweenness, Soc. Networks 44, 202-208 (2016).
- Franceschet, M. & Bozzo, E., A theory on power in networks, e-print arXiv:1510.08332v2, pp. 19 (2016).
- Agneessens, F., Borgatti, S.P. & Everett, M.G., Geodesic based centrality, Soc. Networks 49, 12-26 (2017).
- Kleinberg, J., Authoritative sources in a hyperlinked environment, J. ACM 46(5), 604-632 (1999).
- Brin, S. & Page, L., The anatomy of a large-scale hypertextual Web search engine, Comput. Networks ISDN 30(1-7), 107-117 (1998).
- Jeh, G. & Widom, J., SimRank: A measure of structural-context similarity, In: Proceedings of KDD ’02 (Edmonton, Canada, 2002), pp. 538–543.
- Tong, H., Faloutsos, C. & Pan, J.-Y., Fast random walk with restart and its applications, In: Proceedings of ICDM ’06 (Washington, DC, USA, 2006), pp. 613-622.
- → Berkhin, P., A survey on PageRank computing, Internet Math. 2(1), 73-120 (2005).
- Fabrikant, A., Mahdian, M. & Tomkins, A., SCRank, e-print arXiv:1802.08204v1, pp. 10 (2018).
Link importance and measures of bridging
Link importance and measures of bridging
Link betweenness and bridgeness centrality. Link embeddedness and topological overlap.
Lecture handouts:
- Measures of link bridging
Book chapters:
- Ch. 7: Measures and metrics in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- → Ch. 9.3: Hierarchical clustering in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Course readings:
- → Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2), 163-177 (2001).
- Girvan, M. & Newman, M.E.J., Community structure in social and biological networks, P. Natl. Acad. Sci. USA 99(12), 7821-7826 (2002).
- Ravasz, E., Somera, A.L. et al., Hierarchical organization of modularity in metabolic networks, Science 297(5586), 1551-1555 (2002).
- Onnela, J.-P., Saramäki, J. et al., Structure and tie strengths in mobile communication networks, P. Natl. Acad. Sci. USA 104(18), 7332-7336 (2007).
- Newman, M.E.J., A measure of betweenness centrality based on random walks, Soc. Networks 27(1), 39-54 (2005).
- → Jensen, P., Morini, M. et al., Detecting global bridges in networks, J. Complex Netw. 4(3), 319-329 (2015).
- → Everett, M.G. & Valente, T.W., Bridging, brokerage and betweenness, Soc. Networks 44, 202-208 (2016).
- Wu, A.-K., Tian, L. & Liu, Y.-Y., Bridges in complex networks, Phys. Rev. E 97(1), 012307 (2018).

Topic outline

General

Introduction to Network Analysis (INA)

Course lecturer

Outline & objective

Coursework & grading

Literature & readings

Course schedule

Course assignments

Corona course videos

Course homeworks

Course projects

Course challenges

Course discussions

Course overview and logistics

From graph theory to network science

Random graphs vs real networks

Small-world and scale-free networks

Node mixing and network structure

Node clusters and mesoscopic structure

Network fragments and frequent subgraphs

Node position and measures of centrality

Link importance and measures of bridging