Predmet: ARP I: Introduction to Network Analysis

Oris poglavij

Splošno

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 Social and Information Network Analysis (ASI) 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 make their work publicly available. All students will have to present their project proposal and final project results in front of the class, 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, 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 20th, 2018 and the labs starts on Mar 2nd, 2018. The lectures and labs will be held either in English or Slovene. Weekly course schedule is as follows.

Lectures on Tuesdays at 11:00am in PR 20
Office hours on Fridays at 12:00pm in R 2.49
Labs on Fridays at 10:00am in PR 6

Course assignments

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

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 19th	Homework #0 (PDF, TeX)
2	Feb 26th		Homework #0	Four knights
3	Mar 5th	Homework #1 (PDF, TeX)
4	Mar 12th			Grand graph
5	Mar 19th		Homework #1
6	Mar 26th	Homework #2 (PDF, TeX)		÷-vector centrality
7	Apr 2nd
8	Apr 9th		Homework #2	Five networks
9	Apr 16th	Homework #3 (PDF, TeX)
10	Apr 23rd			PageRank centrality	Uprising day
11	Apr 30th		Homework #3		Labour day
12	May 7th		Project proposal		Holidays
13	May 14th
14	May 21st		Project milestone		Project consultations
15	May 28th				Project consultations
16	Jun 4th		Project deadline

Course homeworks
Homework #0 submission Naloga
Homework #1 submission Naloga
Homework #2 submission Naloga
Homework #3 submission Naloga
Course projects
Project proposal submission Naloga
Project milestone submission Naloga
Project report submission Naloga
Course challenges
Four knights challenge Odziv
Grand graph challenge Odziv
÷-centrality challenge Odziv
Five networks challenge Odziv
PageRank challenge Odziv
Course discussions
Course announcements Forum
Networks dictionary Slovar

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
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).
- → 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).
- 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 basic algorithms
- Advanced algorithms and random graphs (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).
- → 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 (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).
- → 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).
- Broido, A.D. & Clauset, A., Scale-free networks are rare, e-print arXiv:1801.03400v1, pp. 14 (2018).
- Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).
Node mixing and network structure
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 (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:
Lab handouts:
- Network community detection (log)
- Block models and k-cores (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 algorithm (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).
Network inference and network-based mining
Network inference and network-based mining
Network inference and link prediction indices. Network-based node and link clustering, classification and regression.
Lecture handouts:
- Network inference and link prediction
- Clustering, classification and regression
Course readings:
- Leicht, E.A., Holme, P. & Newman, M.E.J., Vertex similarity in networks, Phys. Rev. E 73(2), 026120 (2006).
- Liben‐Nowell, D. & Kleinberg, J., The link‐prediction problem for social networks, J. Am. Soc. Inf. Sci. Tec. 58(7), 1019-1031 (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).
- → Godoy-Lorite, A., Guimerà, R. et al., Accurate and scalable social recommendation using stochastic block models, P. Natl. Acad. Sci. USA 113(50), 14207–14212 (2016).
- Gomez-Rodriguez, M., Leskovec, J. & Krause, A., Inferring networks of diffusion and influence, ACM Trans. Knowl. Discov. Data 5(4), 21:1-37 (2012).
- Zhou, T., Lü, L. & Zhang, Y.-C., Predicting missing links via local information, Eur. Phys. J. B 71(4), 623-630 (2009).
- → Backstrom, L. & Leskovec, J., Supervised random walks, In: Proceedings of WSDM '11 (Hong Kong, China, 2011), pp. 635-644.
- Yan, B. & Gregory, S., Finding missing edges in networks based on their community structure, Phys. Rev. E 85(5), 056112 (2012).
- Wu, Z., Lin, Y. et al., Link prediction with node clustering coefficient, Physica A 452, 1-8 (2016).
- Lü, L. & Zhou, T., Link prediction in complex networks: A survey, Physica A 390(6), 1150-1170 (2011).
- Li, Z., Fang, X. & Sheng, O., A survey of link recommendation for social networks, e-print arXiv:1511.01868v1, pp. 34 (2015).
- Martin, T., Ball, B. & Newman, M.E.J., Structural inference for uncertain networks, Phys. Rev. E 93(1), 012306 (2016).
- Newman, M.E.J., Measurement errors in network data, e-print arXiv:1703.07376v1, pp. 6 (2017).
- Getoor, L. & Diehl, C.P., Link mining: A survey, SIGKDD Explor. 7(2), 3–12 (2005).
- Getoor, L., Friedman, N. et al., Learning probabilistic models of link structure, J. Mach. Learn. Res. 3, 679–707 (2002).
- Neville, J. & Jensen, D., Iterative classification in relational data, In: Proceedings of SRL ’00 (Austin, TX, USA, 2000), pp. 13–20.
- Macskassy, S.A. & Provost, F., Classification in networked data: A toolkit and a univariate case study, J. Mach. Learn. Res. 8, 935-983 (2007).
- Bhattacharya, I. & Getoor, L., Collective entity resolution in relational data, ACM Trans. Knowl. Discov. Data 1(1), 5:1-9 (2007).
- Bhagat, S., Cormode, G. & Muthukrishnan, S., Node classification in social networks, e-print arXiv:1101.3291v1, pp. 37 (2011).
- 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.
- Šubelj, L., Exploratory and predictive tasks of network community detection, In: Proceedings of NetSci '15 (Zaragoza, Spain, 2015), p. 1.
- Hric, D., Peixoto, T.P. & Fortunato, S., Network structure, metadata and the prediction of missing nodes, Phys. Rev. X 6(3), 031038 (2016).
- → Zanin, M., Papo, D. et al., Combining complex networks and data mining: Why and how, Phys. Rep. 635, 1-44 (2016).
- Perozzi, B., Al-Rfou, R. & Skiena, S., DeepWalk, In: Proceedings of KDD ’14 (New York, NY, USA, 2014), pp. 701-710.
- → Grover, A. & Leskovec, J., node2vec, In: Proceedings of KDD ’16 (San Francisco, CA, USA, 2016), pp. 855-864.
- → Figueiredo, D.R., Ribeiro, L.F.R. & Saverese, P.H.P., struc2vec, In: Proceedings of KDD ’17 (Halifax, Canada, 2017), pp. 1–9.
- → Peel, L., Graph-based semi-supervised learning for relational networks, In: Proceedings of SDM ’17 (Houston, TX, USA, 2017), pp. 1-11.
Network collection, sampling and comparison
Trenutna tema
Network collection, sampling and comparison
Hidden populations and network-based sampling. Network comparison by fragments and metrics. Network backbones and skeletons.
Lecture handouts:
Lab handouts:
- Random-walk sampling and Facebook (log)
Book chapters:
- → Ch. 3.7: Snowball sampling etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Course readings:
- → Song, C., Havlin, S. & Makse, H.A., Self-similarity of complex networks, Nature 433(7024), 392-395 (2005).
- Lee, S.H., Kim, P.-J. & Jeong, H., Statistical properties of sampled networks, Phys. Rev. E 73(1), 016102 (2006).
- → Leskovec, J. & Faloutsos, C., Sampling from large graphs, In: Proceedings of KDD '06 (Philadelphia, PA, USA, 2006), pp. 631-636.
- Furuya, S. & Yakubo, K., Multifractality of complex networks, Phys. Rev. E 84(3), 036118 (2011).
- Laurienti, P.J., Joyce, K.E. et al., Universal fractal scaling of self-organized networks, Physica A 390(20), 3608–3613 (2011).
- Blagus, N., Šubelj, L. & Bajec, M., Self-similar scaling of density in complex real-world networks, Physica A 391(8), 2794-2802 (2012).
- Guimerà, R., Danon, L. et al., Self-similar community structure in a network of human interactions, Phys. Rev. E 68(6), 065103 (2003).
- Blagus, N., Šubelj, L. et al., Sampling promotes community structure in social and information networks, Physica A 432, 206-215 (2015).
- Blagus, N., Šubelj, L. & Bajec, M., Assessing the effectiveness of real-world network simplification, Physica A 413, 134-146 (2014).
- → Blagus, N., Šubelj, L. & Bajec, M., Empirical comparison of network sampling, Physica A 477, 136–148 (2017).
- → Milo, R., Itzkovitz, S. et al., Superfamilies of evolved and designed networks, Science 303(5663), 1538-1542 (2004).
- → Pržulj, N., Biological network comparison using graphlet degree distribution, Bioinformatics 23(2), e177-e183 (2007).
- Cooper, K. & Barahona, M., Role-similarity based comparison of directed networks, e-print arXiv:1103.5582v1, pp. 6 (2011).
- Yaveroğlu, Ö.N., Malod-Dognin, N. et al., Revealing the hidden language of complex networks, Sci. Rep. 4, 4547 (2014).
- Aparício, D., Ribeiro, P. & Silva, F., Network comparison using directed graphlets, e-print arXiv:1511.01964v1, pp. 9 (2015).
- Bagrow, J.P. & Bollt, E.M., An information-theoretic, all-scales approach to comparing networks, e-print arXiv:1804.03665v1, pp. 18 (2018).
- → Šubelj, L., Fiala, D. & Bajec, M., Network-based statistical comparison of bibliographic databases, Sci. Rep. 4, 6496 (2014).
- Šubelj, L., Bajec, M. et al., Quantifying the consistency of scientific databases, PLoS ONE 10(5), e0127390 (2015).
- Demšar, J., Statistical comparisons of classifiers over multiple data sets, J. Mach. Learn. Res. 7, 1–30 (2006).
- → Grady, D., Thiemann, C. & Brockmann, D., Robust classification of salient links in complex networks, Nat. Commun. 3, 864 (2012).
- → van den Heuvel, M.P., Kahn, R.S. et al., High-cost, high-capacity backbone for global brain communication, P. Natl. Acad. Sci. USA 109(28), 11372–11377 (2012).
- Ruan, N., Jin, R. et al., Network backbone discovery using edge clustering, e-print arXiv:1202.1842v2, pp. 14 (2012).
- Hamann, M., Lindner, G. et al., Structure-preserving sparsification methods for social networks, Soc. Netw. Anal. Min. 6(1), 22 (2016).
- Coscia, M. & Neffke, F., Network backboning with noisy data, In: Proceedings of ICDE '17 (San Diego, CA, USA, 2017), pp. 425–436.
- → Šubelj, L., Convex skeletons of complex networks, e-print arXiv:1709.00255v2, pp. 11 (2017).
Node layout and network visualization
Node layout and network visualization
Spring embedders and force-directed node layout. Static, dynamic and heterogeneous network visualization.
Lecture handouts:
- Node layout and network visualization
Lab handouts:
- Board with pegs & bands (toy)
Course readings:
- Eades, P., A heuristic for graph drawing, Congressus Numerantium 42, 146-160 (1984).
- Kamada, T. & Kawai, S., An algorithm for drawing general undirected graphs, Inform. Process. Lett. 31(1), 7-15 (1989).
- Fruchterman, T.M.J. & Reingold, E.M., Graph drawing by force-directed placement, Softw: Pract. Exper. 21(11), 1129-1164 (1991).
- Rodrigues, J., Tong, H. et al., GMine, In: Proceedings of VLDB ’06 (Seoul, South Korea, 2006), pp. 1195-1198.
- → Rodrigues, J., Traina, A. et al., Supergraph visualization, In: Proceedings of ISM ’06 (San Diego, CA, USA, 2006), pp. 227-234.
- → Kobourov, S.G., Spring embedders and force directed graph drawing algorithms, e-print arXiv:1201.3011v1, pp. 23 (2012).
- Gibson, H., Faith, J. & Vickers, P., A survey of two-dimensional graph layout techniques for information visualisation, Infor. Visual. 12(3-4), 324-357 (2013).
- → Ma, K.-L. & Muelder, C.W., Large-scale graph visualization and analytics, Computer 46(7), 39-46 (2013).
Applications of network analysis
Applications of network analysis
Applications of network analysis in automobile insurance fraud, software engineering and bibliometrics & scientometrics.
Lecture handouts:
- Automobile insurance fraud
- Software networks & engineering
- Bibliometrics & scientometrics (poster)
Further readings:
- Šubelj, L., Furlan, Š. & Bajec, M., An expert system for detecting automobile insurance fraud using social network analysis, Expert Syst. Appl. 38(1), 1039-1052 (2011).
- Šubelj, L. & Bajec, M., Community structure of complex software systems: Analysis and applications, Physica A 390(16), 2968-2975 (2011).
- Šubelj, L. & Bajec, M., Software systems through complex networks science: Review, analysis and applications, In: Proceedings of SoftMine ’12 (Beijing, China, 2012), pp. 9–16.
- → Šubelj, L., Žitnik, S. et al., Node mixing and group structure of complex software networks, Advs. Complex Syst. 17(7-8), 1450022 (2014).
- → Šubelj, L. & Bajec, M., Model of complex networks based on citation dynamics, In: Proceedings of LSNA ’13 (Rio de Janeiro, Brazil, 2013), pp. 527–530.
- Šubelj, L., Žitnik, S. & Bajec, M., Who reads and who cites? Unveiling author citation dynamics by modeling citation networks, In: Proceedings of NetSci '14 (Berkeley, CA, USA, 2014), p. 1.
- Šubelj, L., Van Eck, N.J. & Waltman, L., Comparison of methods for clustering citation networks, In: Proceedings of NetSci-X ’16 (Wroclaw, Poland, 2016), p. 1.
- → Šubelj, L., Van Eck, N.J. & Waltman, L., Clustering scientific publications based on citation relations: A systematic comparison of methods, PLoS ONE 11(4), e0154404 (2016).

Oris poglavij

Splošno

Introduction to Network Analysis (INA)

Course lecturer

Outline & objective

Coursework & grading

Literature & readings

Course schedule

Course assignments

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

Network inference and network-based mining

Network collection, sampling and comparison

Node layout and network visualization

Applications of network analysis