Network Properties

• Degree distribution
• Characterizes the shortest path lenght
• Distribution of conected components in Graphs

Degree Distribution

Normalized Histogram with the distribution of nodes. Directed graphs has two histogram, an indegree and an outdegree histogram

Path

Path is a sequence of nodes in wich each node is linked to the next node. A path can intersect and pass through the same edge multiple times. Distance is the shortest path between a pair of nodes. In directed graphs paths need to follow the dirction of the arrows and in consequence distance is not symmetric in directd graphs (distance from A to B might not be the same as B to A)

The diameter of a graph is the longest possible path between two farthest nodes in a graph.

Clustering Coefficient

• $$C_i = \frac{2 e_i}{k_i (k_i - 1)}$$ where $e_i$ is the number of edges between the neighbors of node i and $k_i (k_i - 1)$ is the maximum number of edges between the $k_i$ neighbors
• It's undefined for nodes with degree 0 or 1
• Average clustering coefficient: $$C = \frac{1}{N} \sum_i^N{C_i}$$ It's the average of all the nodes clustring coefficients

Connectivity

MSN Log-Log Degree Distribution

C = 0.1140 -> about 10% of every other friends is friends with each other

Erdös-Rényi Random Graph Model

• Pick a pair of nodes, flip a coin and if head there's a link else there's not

• As the graph increases the variance goes to 0

• As the graph increases and the mean doesn't change the clustering coefficient goes to 0

The diameter grow logarithimcally in respect to their sizes

Are real networks random? No

So why we spent time on this random model? Because it's the simplest model and show us how we can calculate many propreties

So why the average path lenght matches? It means that the simplest model agrees with the real world data

The Small-World Model

Can we have high clustering while also having short paths?

We need just a few of these random shortcuts to colapse the diameter which seems to be a very fragile proprety while the clustering still remains robustly high. What doest this teachs about social networks? We have high cluster and low diameter. Yes we have high clustering and we have low diameter because most of the friends we have are local and they know each other but we also have a few colleagues which live in another country. And we just need a few of these connections to colapse the path lenght

Can we have high clustering while also having short paths? Yes! You just need a few random links.

Kronecker Graph Model

Generating large realistic graphs

If our K1 capture some sort of regularity we can replicate it multiple times to a much larger graph

We don't only want to generate such regular graphs. For instance in the Small World model when we start from this very small lattice. Lattice are very easy to generate because they come with a very regular shape so they can be determinisctly generated but at the same time they don't really capture a lot of the real work models. They don't capture a social network. usually we want to add some stochastic to our model.

How do you know the number of edges? An educated assumption