Analysis of Social and Information Networks 2022/2023

#2 - Emergence of Network Science [36m33s]
Contributing factors to the emergence of network science; mining an learning with graphs: an overview of related tasks and topics.

#3 - Brief Introduction to Graph Theory and Network Vocabulary [35m33s]
Brief introduction to graph theory and network vocabulary: links/edges, networks/graphs, self-loops, multi-graphs, simple graphs, undirected and directed networks, edge and node attributes (weigth, rank, type), degree distribution; multiplex networks, temporal networks, cliques, components (and giant component), bipartite networks (and projections)

Class #3 (09 Mar)

#4 - Measuring Graphs and Results on Real Networks [54m27s]
Networks properties: degree distribution, paths, distance, diameter, average path length, clustering coefficient, connected components and giant component; properties of real networks: results for MSN and PPI; network datasets.

#5 - Erdös-Renyi Random Graph Model [56m39s]
The Erdös-Renyi random graph model and its topological properties: degree distribution, cluster coefficient, expansion, path length and the emergence of a giant component; comparison of Erdös-Renyi with real-world graphs; usage of NetLog for visualization.

Class #4 (16 Mar)

#6 - Small-World Random Graph Model [29m11s]
Milgram's small world experiment; clustering and edge locality, the Watts-Strogatz model and the intermediate step between purely regular and purely random networks.

#7 - Power Laws and Preferential Attachment [1h35m09s]
Power-laws in real-world degree distributions and typical exponents; power-law functions and their characteristics; scale-free networks; preferential attachment: origins, models, visualization and characteristics; fitting power laws: simple binning, logarithmic binning, cumulative distributions; power-laws in real distributions; other distributions.

Class #5 (23 Mar)

#8 - Node Centrality [1h10m49s]
Motivation: node importance and ranking; degree centrality and why it's not enough; betweenness centrality; closeness and harmonic centrality; eigenvector centrality and variants (e.g. bonachich); extension to directed and weighted networks.

Class #6 (30 Mar)

#9 - Gephi Tutorial [41m12s]
Using Gephi, an open-source network analysis and visualization software: GUI, plugins, changing node and edge appearance, graph layouts, computing metrics and statistics, filtering. Exploring two datasets: a Facebook ego network and the openflights dataset.

Class #7 (13 Apr)

#10 - Link Analysis and PageRank [1h44m03s]
Link analysis: bowtie structure of the web; hits algorithm; PageRank algorithm: how it works, flow and random walk intepretations, teleporting and solutions to spider traps and dead ends, personalized pagerank.

Class #8 (20 Apr)

#11 - Roles and Community Structure in Networks [1h37m39s]
Roles: structural position of a node; RolX methodology; Communities: triadic closure, edge overlap and strenth of weak ties; informal definition of communities (high number of internal connection and low number of external connections); concept of hierarchical clustering; greedy approaches to community discovery: agglomerative and divisive; Girvan-Newman method and edge betweenness; modularity as a metric for community quality; Louvain algorithm.

Class #9 (25 Apr)

#12 - Subgraphs as Fundamental Ingredients of Complex Networks [2h11m21s]
Subgraphs as fundamental ingredients - essential terminology and concepts: induced subgraphs and their frequency (subgraph census), overrepresentation and null models, classical definition of network motifs and possible variations, motif fingerprint of a network, node orbits, graphlet degree distributions; discovering motifs and graphlets: basic notion of subgraph census computational hardness. Concept of g-tries, basic notions of why g-tries are efficient for counting subgraphs (role of canonical form and symmetry breaking conditions and how search is constrained), notions of sampling and how it can be applied to g-tries; parallel approaches for counting subgraphs.

Class #10 (04 May)

#13 - Diffusion and Cascading Behavior - Part 1 (Decision Based Models) [58m59s]
Diffusion and Cascading Behavior - essential terminology and concepts: information diffusion and network cascades; Decision based modes of diffusion: game model (as a coordination game) and global payoff as sum of node payoffs, activation threshold, k-core decomposition of a network, extension of model to more than one possible behavior.

Class #11 (18 May)

#14 - Diffusion and Cascading Behavior - Part 2 (Probabilistic Models) [1h29m38s]
Diffusion and Cascading Behavior - probabilistic models of contagion: epidemic spreading, simple probabilistic spreading on random trees and reproductive number; spreading models: SIR, SIS, SEIR, SEIZ and epidemic thresholds; independent cascade model.

Class #12 (25 May)

#15 - Network Construction [1h34m41s]
Multimode Network Transformations: k-partite networks, construction of one mode projections (based on common neighbors or jaccard index), graph contraction; k-Nearest Neighbor Graph (k-NNG): definition of k-NNG, possible applications and approach for its computation; Network Deconvolution: definition of deconvolution and possible applications; Time series and Network Science: correlation networks and visibility graphs.