In this report we study how networks evolve. Most real networks evolve either by adding or removing nodes or links over time. At the macro level we can say that networks evolve through densification and change the properties of the entire network. At the meso level we will see how network motifs, communities capture evolution and at the micro level networks evolve through node and link properties like degree, network centrality.

Macroscopic Evolution

We want to see what global phenomena of network's growth. We understand this by knowing what statistics of networks change over time.

We can consider basic statistics like how the relation between number of nodes and number of edges varies with time t. Or the diameter or he degree distribution change as the network grows.

For most real networks the evolution of edges wrt the evolution of nodes follow densification power law, where $E(t)\propto N(t{)}^a$ where a is the densification exponent in the range of [1, 2]. a can never be more than 2, and if a is less than 1, the average node degree is reducing with time. If we plot the number of nodes and number of edges on a log-log scale we will get a line with slope a. Usually average node degree increases with time in real networks. When a = 1, its a linear growth with constant out-degree. a = 2 is a fully connected graph.

Intuitively we might think that diameter of a network slowly grows with time with additional nodes and edges. But empirically diameter ends up shrinking as the network grows. Even though it's counterintuitive, the distances between the nodes slowly decrease with more nodes and edges in real networks. We compute the diameter in practice by taking the 90th percentile or the average path length not the maximum. In case of disconnected components, take the largest component.

From the earlier observation of how edges are increasing much faster than the nodes are increasing, it should be clear why the diameter is shrinking because as the additional edges keep the network much more connected than earlier. But we want to know if densification is the reason for this shrinking diameter. If we simulate this on a randomly generated graph $G_{np}$ with increasing number of nodes with a around 1.3, we see that the diameter doesn't actually shrink. Densifying random graph has increasing diameter, which implies there is more to shrinking of diameter than just densification.

We check if the changing degree sequence explain the shrinking diameter. For this we compare a real network's diameter with a random network with the same degree distribution as the real network over time. By doing this we can see that the diameter of the real network and the random network shrink by the same amount over time. Hence densification and degree sequence gives shrinking diameter. But we want to know how the degree sequence is connected to densification and how the degree distribution evolve to allow for densification.

We consider two options

Option 1 where the degree exponent ${\gamma }_t$ is constant over time as network evolves. In this case if ${\gamma }_t=\gamma \in [1,2]$, then $a=2/\gamma$. Power laws with exponents less than 2 have infinite expectations, so by maintaining constant degree exponent $\gamma$ the average degree grows.

Option 2 where the degree exponent ${\gamma }_t$ evolves with graph size n, if ${\gamma }_t=\frac{4n_t^{x-1}-1}{2n_t^{x-1}-1}$ then x = a the densifying constant. Here ${\gamma }_t\to 2as{n}_t\to \infty$. The expected degree in a power law is $E[X]=\frac{{\gamma }_t-1}{{\gamma }_t-2}{x}_m$, so ${\gamma }_t$ has to decay as a function of graph size $n_t$ for the average degree to go up.

The networks are densifying as the diameter is shrinking in real networks.

Forest Fire Model

Forest Fire model generates graphs that densify and have shrinking diameters to simulate real world networks. Based on intuition of how people meet at parties or how people identify references when writing papers. Meet an ambassador at first and make friends with them, and eventually become friends with her friends one by one.

We have two parameters, $p$ forward burning probability and $r$ backward burning probability on a directed graph. At each turn when a new node v arrives, uniformly at random choose an ambassador node w, flip 2 coins sampled from a geometric distribution based on p and r to determine the number of in and out-links of w to follow, i.e., to spread the fire along. Fire spreads recursively until it dies. And the new node v links to all burned nodes.

• v chooses an ambassador node w at random and forms a link to w
• generate two random numbers x and y from geometric distributions with means $p/(1-p)$ and $rp/(1-rp)$
• v selects x out-links and y in-links of w incident to nodes that were not yet visited and form out-links to them
• v now applies the last two steps to all the new nodes found in the previous step.

This forest fire model generates graphs that densify and also have shrinking diameter.

Forest fire model also generates graphs with power law degree distribution.

If we fix the backward probability r and vary forward burning probability p and see how densification and diameter varies with p, we see that there is a small range for p where the network starts densification with shrinking diameter. There is a sharp transition between sparse and clique-like graphs with a small change in p.

TODO: get better intuition for densification vs degree distribution, power law distribution and etc.

Temporal Networks

A temporal network is a sequence of static directed graphs over the same static set of nodes V. And each temporal edge is a timestamped ordered pair of nodes $(e_i=(u,v),t_i)$ where u, u are from V and $t_i$ is the timestamp at which the edge exists.

Below you can see a temporal network on nodes A, B, C, D, E, F, with edges representing at what time stamp a given edge exists.

Examples of temporal networks include,

• communication networks like phone calls
• proximity networks like people in the same hospital room, meeting at a conference
• Transportation networks
• Cell biology networks like protein-protein interactions, gene regulation and etc

Below is an example of a temporal network of email communication in a week using 24 hour window and an aggregated static graph. Nodes are employees and a link between two employees is an email sent in the 24 hour window.

Microscopic Evolution

Here we study local phenomena of network growth at node and edge level. We define paths and walks in temporal networks and eventually extend the network centrality measures to temporal networks.

A temporal path is a sequence of edges $(u_1,u_2,t_1),(u_2,u_3,t_2),\cdots ,(u_j,u_{j+1},t_j)$ for which $t_1\le t_2\le \cdots t_j$.

In the below network evolution graph

The sequence of edges [(5, 2), (2, 1)] together with the sequence of times $t_1,t_3$ is a temporal path.

TODO: I really didn't understand why we defined temporal paths like this, and how we find the temporal shortest paths using TPSP-Djikstra algorithm.

Temporal closeness

Measure of how close a node is to any other node in the network at time interval [0, t]. It is the sum of the shortest(fastest) temporal path lengths to all the other nodes. $c_{clos}(x,t)=\frac{1}{{\sum }_{y}d(y,x|t)}$ which is the length of the temporal shortest path from y to x from time 0 to time t

Temporal PageRank

Say node a initially has many in-links, hence its important in the beginning, and as the in-links to the node changes its importance should either increase or decrease accordingly.

We make the random walk only on temporal or time-respecting paths. And the time-stamps increase along the path.

In the below temporal graph, $c\to b\to a\to c$ is a time respecting path, but $a\to c\to b\to a$ is not a time respecting path. Because the edge $a\to c$ was at timestep 9 and the edge $c\to b$ was at time step 2.

Now we calculate the probability of a temporal path. The probability $P[(u,x,t_2)|(v,u,t_1)]$ of taking $(u,x,t_2)$ given that we arrived via $(u,v,t_1)$ decreases as the time difference $(t_2-t_1)$ increases. The bigger the time difference the less likely u is going to connect with x, it might have already connected with some other node and it won't satisfy the temporal path condition.

We can model this using an exponential distribution with

$P[(u,x,t_2)|(v,u,t_1)]={\beta }^{|{\Gamma }_u|}$, where $\beta \in (0,1]$ and ${\Gamma }_u$ is the set of all temporal edges from u during the time $t^{\prime }\in [t_1,t_2]$

${\Gamma }_u=\{(u,y,t^{\prime })|t^{\prime }\in [t_1,t_2],y\in V\}$

Smaller values of $\beta$ increase the probability of walks stopping at high degree nodes, but we get a slower convergence.

As $t\to \infty$, the temporal PageRank converges to the static PageRank. Temporal PageRank is running regular PageRank on a time-augmented graph. Connect graphs at different time steps via time hops, and run PageRank on this time-extended graph. Node u at $t_1$ becomes a node $(u,t_1)$ in this new graph. With the transition probabilities given by $P[((u,t_1),(x,t_2))|((v,t_0),(u,t_1))]={\beta }^{|{\Gamma }_u|}$

And as $t\to \infty ,{\beta }^{|{\Gamma }_u|}$ becomes the uniform distribution. With the graph looking as if we superimposed the original graphs from each time step giving us regular PageRank.

From the actual network and its connections at various time steps, we can create the time-augmented graph where we connect for each node, all the nodes it connected to over time.

$r(u,t)=\sum _{v\in V}\sum _{k=0}^t(1-\alpha ){\alpha }^k\sum _{z\in Z(v,u|t);|z|=k}P[z|t]$

Where $Z(v,u|t)$ is a set of all possible temporal walks from v to u until time t and \alpha is the probability of starting a new walk.

As $t\to \infty$, the temporal PageRank converges to the static PageRank.

TODO: I found this lecture not intuitive at all, many concepts introduced in this lecture went over my head, I didn't even get the motivations behind defining things like temporal paths a certain way, or why it is important. Maybe there's a handout that I need to find to make sense of everything.

Chapters

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks