ARP I: Introduction to Network Analysis

Topic outline

• General
  
  

  General

  • Introduction to Network Analysis (INA)

    Course lecturer

    Lovro Šubelj (R 2.49)

    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 15 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 weekly 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.

    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).
    • Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).

    Course schedule

    The lectures start on Feb 21st, 2017 and the labs starts on Feb 28th, 2017. 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 2
    • Labs on Tuesdays at 3:00pm in PR 15
    • Office hours on Tuesdays at 5:00pm in R 2.49

    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 3: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	Comment
    1	Feb 21st	Homework #0 (PDF, TeX)
    2	Feb 28th		Homework #0
    3	Mar 7th	Homework #1 (PDF, TeX)
    4	Mar 14th
    5	Mar 21st		Homework #1	CompleNet '17
    6	Mar 28th	Homework #2 (PDF, TeX)
    7	Apr 4th
    8	Apr 11th		Homework #2
    9	Apr 18th	Homework #3 (PDF, TeX)
    10	Apr 25th
    11	May 2nd		Homework #3	Labour day
    12	May 9th		Project proposal
    13	May 16th			ARS '17
    14	May 23rd		Project milestone
    15	May 30th
    16	Jun 6th		Project deadline

  • 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

  • Four knights challenge Feedback
  • Grand graph challenge Feedback
  • Five networks challenge Feedback
  • PageRank challenge Feedback
  • Centrality challenge Feedback
  • Course discussions

  • Networks dictionary Glossary
  • Course announcements Forum
• Course overview and logistics
  
  

  Course overview and logistics

  Course overview, logistics and syllabus. Coursework description, instructions and other details.

  Lecture handouts: 

  • Course overview and syllabus
  • Course logistics and coursework
  • Course project and report details

  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: 

  • Networks introduction and motivation
  • From graph theory to network science
  • Networks through fields of science

  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:

  • Graphology and networkology
    
  • Network representations and data
  • Erdős–Rényi random graph model
    
  • Configuration graph model
  • Real networks models

  Lab handouts:

  • Network representations and basic algorithms
  • Advanced algorithms and random graphs

  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).
    
  • → 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:

  • Small-world networks and model
    
  • Scale-free distributions and networks
  • Preferential attachment models

  Lab handouts:

  • Small-world and scale-free networks

  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).
• 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
    

  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).
  • Estrada, E., Combinatorial study of degree assortativity in networks, Phys. Rev. E 84(4), 047101 (2011).
• Node clusters and mesoscale structure
  
  

  Node clusters and mesoscale 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:

  • 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).
• 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
    

  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).
    
• 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).
    
• 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
  
  

  Network collection, sampling and comparison

  Sampling hidden populations and network-based sampling methods. Network comparison by fragments and metrics.

  Lecture handouts:

  • Network collection and sampling
  • Network metrics comparison (poster)

  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).
  • → Š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).
    
• 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
  This topic
  

  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).