Metrics – Part 3 – Network Metrics

Network Metrics

• The metrics in this section apply to networks in general.
• These statistics measure something specific about a network.
• Some metrics provide information about the overall structure of the network.
• Other metrics are useful to determine the growth model of the network.

​

Composites

• These metrics say something descriptive about the network by averaging node and node pair metrics.
• The average degree
• In Facebook: Average degree 338 (median is 200)
• The average number of followers per user on Twitter is 208.
• The average number of Instagram followers is 843

Other useful averages

• If you have a network that is being used to deliver goods and you are deciding where to add new edges.
• For each edge that you might add, calculate the average closeness.
• Choose the edge that has the higher average closeness.

Maximums

• The maximum degree in a social network tells us who is most popular.
• It is also helpful in looking for cliques: Finding cliques is expensive, so knowing the maximum degree allows us to look for cliques more efficiently.
• The maximum geodesic path length (over all possible node pairs) is called the diameter of the network.
• In 1999 the WWW was estimated to have a diameter of 19.
• It is probably shorter now.

Density

• The density of a network is the number of links divided by the total number of node pairs.
• m is the number of links (edges)
• n is the number of nodes in the network
• The total number of node pairs is n(n-1)/2

Sparse and dense networks

• As a network grows, if the density remains constant it is considered dense.
• If the density shrinks, it considered sparse.
• Social networks, in which people have a soft upper limit on the number of friends they can maintain, are necessarily sparse.

Sparse and dense networks

• To better understand the structure, we can look at the degree distribution.
• This is a list of the degrees of each node, normally sorted in descending order (the nodes with the highest degree are listed first).
• It is very helpful to plot a histogram or a curve to see the distribution more easily.

[10,10,9,6,6,6,6,4,3,2,1]

Degrees in descending order for all the nodes

Degree Distribution

Scenario A

Scenario B

degree

nodes

Power Law

• Social networks usually follow the power law distribution when it comes to degree
• In the graph to the right, the nodes have been sorted by their degree.
• The nodes with the highest degree appear first, to the left of the curve.

Formula for a power law distribution

• P_k is the probability of a node having k neighbors.
• C is a constant
• α is an exponent, which for a power law should be between 2 and 3.

​

Cliques

• A clique is a graph in which every node is connected to every other node.
• It is interesting to find subgraphs that are cliques in a network.
• This is done only for cliques of size 2 through 5.
• Computation expensive!
• Groups of nodes of size 3 are called triangles or triads.
• Triads can be open or closed

Triads and clustering coefficients

• On undirected graphs, triads do not give much more information than clustering coefficients.
• But triads are much more important in directed graphs.
• There are 16 different types of triads on directed graphs.

16 triads in directed graphs