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 (27th of May, 9:30, Room: (to be announced)):
Essencial Concepts:
- 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.
Graph Models:
- 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.
Node Centrality and Link Analysis:
- 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 and Community Structure:
- 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
Subgraph Patterns
- 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 Construction
- 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
- k-nearest neighbor graph: understanding the concept of a k-NNG graph is and how one could build it
- Deconvolution: understanding what a network deconvolution is and how one could use it to reduce/rescale the edges of a network
- 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