Goals for Mini-Test

Here is a short list of goals for the mini-test (30th of May, 16:00 to 18:00, room FC4 0.41):

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:

• Different notions of centrality and reasoning about them: degree, betweenness, closeness, harmonic and eigenvalue.
• Link analysis: PageRank algorithm: how it works, flow and random walk intepretations, teleporting and solutions to spider traps and dead ends, personalized pagerank

Community Structure:

• 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:

• Subgraph Counting: subgraph census, subgraph frequency, concept of network motif, graphlets and orbits
• G-Tries: basic understanding of the data structure and how it works for storing and counting subgraphs

Diffusion and Cascading Behavior:

• Decision based models: concept of cascade, payoffs, simple decision rules
• Probabilistic models: spreading in random trees, reproductive number, epidemics models: SIR, SIS and their dynamics

Last update: