Network Science: Goals for Test

During the test you will have available the following PDF: network science quick reference guide

You can check some possible model questions on the following PDF: network science example questions

Here is a short list of goals for the 1st Test (22nd of May, 16:00, Room: FC4 1.26):

Understanding basic terminology: nodes/vertices, links/edges, networks/graphs, self-loops, multi-graphs, simple graphs, undirected and directed networks, edge and node attributes (weigth, rank, type), multiplex networks, temporal networks, cliques, components (and giant component), bipartite networks (and projections), strongly connected components, DAGs (directed acyclic graphs).
Core properties: node degree (in, out and global), degree sequence and distribution, sparsity of real networks, distance, diameter and (average) path length, clustering coefficient.

Knowing the typical properties of real world networks: high clustering coefficient, small average path length and power law degree distributions.
Erdos-Renyi random graph model: definition and relation with some of its properties: degree distribution (binomial), clustering (low), path length (small), emergence of a giant component.
Small-World model (Watts-Strogatz): definition and relation to some of its properties: degree distribution (regular), clustering (high), path length (small).
Scale-Free model (Barabasi-Albert): - preferential attachment growth mechanism and its relation to power laws; possible explanations of why it occurs in reality.

Different notions of centrality and reasoning about them: degree, betweenness, closeness, harmonic and eigenvalue.
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

Roles: understanding what the structural position of a node means
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

Subgraphs: understanding the concept of an (induced) subgraph and its frequency; understanding the concept of network motifs and signficance profiles; understanding the concept of orbits and graphlet degree vectors
G-Tries: having a general overview of what a g-trie is, how it represents graphs and how it can be used to compute subgraph frequencies

Network cascades: understanding the concept of a cascade
Decision based models: understanding the concept of how a node may deterministically decide based on its neighbor decisions and of activation thresholds
Probilistic models: understanding the concept of how a node may follow a probabilistic decision based on its edges
- Random trees: understanding the concept of a random tree model and reproductive number
- Compartmental epidemic models: having a general overview of what a compartmental model is; knowing the SIR and SIS models and their dynamics

Multipartite networks and projections: understanding what a multipartite network is and how one could make a projection on one of its mode, incorporating weights if required
Contraction: understanding what a graph contraction is and how one could use it to reduce the size of a network
Deconvolution: understanding what a network deconvolution is and how one could use it to reduce number of edges of a network
k-nearest neighbor graph: understanding the concept of a k-NNG graph is and how one could build it
From time series to networks: understanding how we could study a time series by converting it to a graph; understanding the concepts of correlation networks, visibility graphs and quantile graphs