INP9087851 - NETWORK SCIENCE 2022-2023
Topic outline
-
Lecture hours (starting October 3rd, 2022)
Mon 8:30-10:00, room Le
Tue 16:30-18:00, room DeIn classroom teaching
This year the course unit is delivered in classroom! (on-line only for students waiting for their visa)Instructor
Tomaso Erseghe, tomaso.erseghe@unipd.itOffice hours
contact me during lectures, or send me an email for an appointmentInstitutional page (contains syllabus and useful info on the course)
en.didattica.unipd.it -
-
Le1 - Mon Oct 3, 2022 Introduction to the course: elearning site, projects and interdisciplinary projects, network examples, contents overview, exam dates.
-
-
Le2 - Tue Oct 4, 2022 Networks as graphs; Directed and undirected networks; Paths, Cycles, Diameter; Adjacency matrix; Nodes degrees and the degree distribution; Sparsity; Bipartite graphs; Signed graphs; Connectivity.
-
-
-
-
Le3 - Mon Oct. 10, 2022 Erdos-Renyi random model: binomial and Poisson descriptions of the model; Small world; Power law versus Poisson distribution; The largest hub in scale-free networks; Meaning of scale-free; Ultra-small-world; Friendship paradox.
-
-
Le4 - Wed Oct. 11, 2022 Estimation methods for the degree exponent: ML approach; Watts-Strogatz model; Molloy-Reed model; Growth and preferential attachment; the Barabasi-Albert model; Attractiveness and the Bianconi-Barabasi model; Examples with equal and uniform fitness; Measuring fitness: the www; Other ideas for modelling the power-law.
-
-
-
-
Le5 - Mon Oct. 17, 2022 Centrality measures; HITS: hubs and authorities, linear equations, power iteration, and speed of convergence; An example; PageRank: random walk, dead ends and spider traps, teleportation; PageRank with restart; PageRank versus degree centrality.
-
-
Le6 - Tue Oct. 18, 2022 Examples of application of PageRank; Tuning the teleport vector: Topic specific PageRank and Local PageRank; Examples of application; Spam farm analysis and TrustRank; PageRank with signs; Example and interpretation; PageRank matrix structure via the condensation graph; Action of the teleport vector: one leaf-only, one eigenvalue set to 1 and the rest to (at most) c; Interpretation.
-
-
Le7 - Mon Oct. 24, 2022 Approximate PageRank: the push operation and its rationale, precision guarantee and scalability; Linearity of PageRank; Proof of the precision guarantee of approximate PageRank; Lazy PageRank; Other centrality measures; Eigenvector and Katz centralities and their relation to PageRank and Degree centrality; Closeness centrality; Betweenness centrality as a measure of brokerage; The clustering coefficient.
-
-
-
-
Le8 - Tue Oct. 25, 2022 Recap on the meaning of centrality measures; Homophily and related concepts: Selective exposure, Polarization, Ego Chamber, Filter bubble; Degree homophily or assortativity; the correlation matrix; Nearest neighbour degree function and its exponent; Pearson's coefficient; Structural disassortativity; Structural and natural cutoffs; Random rewiring; Detecting echo-chambers through polarisation and homophily.
-
-
Le9 - Mon Nov. 7, 2022 Social networks examples; Extracting the leaning from network data in pro-life/pro-choice hashtag networks.
-
-
Le10 - Tue Nov. 8, 2022 IPs presentations day. We will be in the hall room (Aula Magna Lepschy), which is in the DEI/D building, at the back of the main building facing the Piovego Canal, see this link). For those who are attending online, we will be using THIS ZOOM LINK and not the usual one.
-
-
-
Le9 - Mon Nov. 7, 2022 Community detection problem: Granovetter's view and the role of weak ties; The core-periphery model; Network community profiles: V shape and nestedness in social networks; The overlapping community model; Agglomerative and divisive dendrograms; Recap of the dendrogram approach.
-
-
Le11 - Mon Nov. 14, 2022 Edge betweenness and the Girvan-Newman solution; Modularity as a measure for selecting the number of communities; Modularity in the two-communities case; Spectral approach and fast modularity optimisation; The Louvain algorithm; Main characteristics of the Louvain algorithm; Solving greediness by consensus clustering.
-
-
Le12 - Tue Nov. 15, 2022 Solving greediness by consensus clustering; The resolution limit; Generalized modularity; The role of the main parameter; Variation of information as a measure of dissimilarity; Using VI to optimally select the parameter; Example of application of the Louvain approach.
-
Le14 - Tue Nov. 22, 2022 The normalised cut criterion; Conductance. Suboptimal solution to normalised cut: algebraic connectivity and Fiedler's eigenvector of the normalised Laplacian matrix; The spectral clustering algorithm; Examples; Eigen-gap for eigenvector selection; Cheeger's inequality; Authority shift algorithms; Clique percolation; The BigClam: rationale of a model-based approach.
-
-
-
Le16 - Tue Nov. 29, 2022 Non-interdisciplinary projects presentations: Iran revolts, political debate, foodwebs, stock markets, partner violence; The BigClam: algorithm and performance.
-
Le18 - Tue Dec. 6, 2022 The layout problem; Aesthetic criteria; Spring-embedder algorithm; Repulsive and attractive forces; Fruchterman & Reingold; Gravity; Force atlas 2; A comparison; BERT topic detection; UMAP as a force-layout algorithm.
-
-
-
Le13 - Mon Nov. 21, 2022 Twitter lab #1 about Twitter and Twitter APIs by Lejla Dzanko: how to download tweets using Twitter APIs.
-
Le15 - Mon Nov. 28, 2022 Twitter lab #2 about extracting semantic networks from Twitter data by Lejla Dzanko.
-
Le17 - Mon Dec. 5, 2022 Network visualisation lab in Python by Lejla Dzanko
-
Le19 - Mon Dec. 12, 2022 Network visualisation lab with Gephi by Lejla Dzanko
-
-
-
Le20 - Tue Dec. 13, 2022 Concluding remarks on BERT topic; The idea of network robustness; Percolation theory results; Robustness of scale-free networks; Proof of the Molloy Reed criterion; Breaking points in scale-free networks; The inhomogeneity ratio; Attack tolerance and fragility of scale-free networks; Mathematical analysis; Optimising robustness; An application example.
-
-
Le21 - Mon Dec. 19, 2022 The link prediction task; Neighbour based techniques: common neighbours, Adamic Adar, and resource allocation. Path based and random-walk based techniques for link prediction; Performance comparison in terms of AUC and precision; Adding a learning technique in supervised random walk; Extensions to bipartite graphs.
-
-
Le22 - Tue Dec. 20, 2022 Extensions to bipartite graphs; Projecting socio-psychological markers from tweets to words.
-
Le23 - Mon Jan 10, 2022 Language and social cognition by prof C. Suitner.
-
Le24 - Tue Jan 11, 2022 (tentative) Projects discussion.
-
-
