INA: (Introduction to) Network Analysis
Žal je ta dejavnost trenutno skrita
Section outline
-
Introduction to Network Analysis (INA)
-
From classical graph theory to social network analysis and modern network science. Networks in different fields of science.
Lecture slides:
- (1) Networks introduction and motivation
- (1) From graph theory to network science
- (7) Networks through fields of science
Lab notebooks:
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).
-
Graphology and networkology. Network representations, formats, and data. Random graph models and real networks models.
Lecture slides:
- (1, 3) Graphology and networkology
- (3) Network representations and data
- (3-4) Erdős-Rényi graph model
- (4) Configuration graph model
Lab notebooks:
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).
-
Degrees of separation, small-world networks and model. Power-law degree distributions, scale-free networks and models.
Lecture handouts:
- (4) Small-world networks and model
- (5) Scale-free distributions and networks
- (5) Preferential attachment models
Lab notebooks:
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).
- → Mannion, S. & MacCarron, P., Fitting degree distributions of complex networks, e-print arXiv:2212.06649v1, pp. 21 (2022).
-
Community and core-periphery structure. Graph partitioning, community detection, blockmodeling, stochastic (block) models etc.
Lecture handouts:
- (7) Network community structure
- (7-8) Partitioning and community detection
- (8) Blockmodeling and stochastic models
- (9) Network core-periphery structure
Lab notebooks:
- (viii) Community detection & benchmarks
- (ix) Blockmodeling & k-core decomposition
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).
-
Node clustering coefficients, degrees, eigenvector, closeness, and betweenness centrality. Link analysis algorithms.
Lecture handouts:
Lab notebooks:
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 betweenness and bridgeness centrality. Link embeddedness and topological overlap.
Lecture handouts:
Lab handouts:
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).