Many networks that we find interesting are large and structurally complex. This makes them difficult to visually understand. And although coming up with ways to visualize such networks is a kind of fun, most of the time we need practical ways to describe the position and structure of complex networks without dealing with the tangled hairball.
This post covers some a variety of ways to measure network position and structure. By position, I mean properties at the node level, such as how many connections a node has (degree centrality) or how often it lies on the shortest path (betweenness). By structure, I mean properties of subgraphs that are found within the network as whole, such as triads, communities, or spectra.
Prerequistes
To start, we need to generate some networks to work with. Let’s use the three canonical network models: the Erdos-Renyi random graph, the Watts-Strogatz small world, and the Albert-Barbasi preferential attachment network. We can simulate these using igraph.
library(igraph)##
## Attaching package: 'igraph'## The following objects are masked from 'package:stats':
##
## decompose, spectrum## The following object is masked from 'package:base':
##
## unionLet each network have 500 nodes.
n = 500Each model has different parameters. The random graph is simplest – we define the number of nodes and the probability that they are connected.
rg = erdos.renyi.game(n=n, p=0.02)
rg## IGRAPH d999ebb U--- 500 2533 -- Erdos-Renyi (gnp) graph
## + attr: name (g/c), type (g/c), loops (g/l), p (g/n)
## + edges from d999ebb:
## [1] 4-- 7 11--14 12--14 11--16 16--17 1--25 26--27 15--31 19--31 19--33
## [11] 27--35 5--36 20--36 13--38 26--39 31--39 15--41 4--43 18--47 46--47
## [21] 42--50 15--51 21--51 26--51 26--52 34--52 39--53 31--54 14--55 51--55
## [31] 49--56 2--57 24--57 20--58 22--59 50--59 24--61 25--62 8--63 16--63
## [41] 55--66 17--67 38--70 27--72 43--72 60--72 25--73 30--74 45--74 38--75
## [51] 62--75 20--76 43--77 18--78 42--78 42--79 63--79 22--80 33--80 50--80
## [61] 2--81 16--81 18--81 58--81 16--82 49--82 11--83 51--83 55--83 35--85
## [71] 60--85 73--85 80--85 7--86 9--86 36--86 80--87 23--88 26--89 38--89
## + ... omitted several edgesThe small world model has more parameters. To make our graphs somewhat comparable, we will keep the size equal to n. The nei parameter controls how many neighbors a node is connected to. The parameter p controls the probability that the a connection is rewired. When p is 0, the graph forms a circlular chain.
sw = watts.strogatz.game(dim=1, size=n, nei = 5, p=0.2)
sw## IGRAPH d9aae4d U--- 500 2500 -- Watts-Strogatz random graph
## + attr: name (g/c), dim (g/n), size (g/n), nei (g/n), p (g/n), loops
## | (g/l), multiple (g/l)
## + edges from d9aae4d:
## [1] 2-- 94 2-- 3 4--107 4-- 5 6--491 6-- 7 7-- 8 8-- 9
## [9] 9-- 10 10-- 11 11-- 12 12-- 13 13-- 14 14-- 15 15--109 16-- 17
## [17] 18--453 197--402 19-- 20 20-- 21 21-- 22 22--100 23--180 25--357
## [25] 25-- 26 26--482 27-- 28 18-- 28 29-- 30 30--214 140--156 32-- 33
## [33] 33-- 34 34-- 35 35-- 36 36-- 37 37-- 38 347--373 40--175 40--104
## [41] 41-- 42 42-- 43 43-- 44 44-- 45 45-- 46 46-- 47 47-- 48 48-- 49
## [49] 49-- 50 50--168 51-- 52 52-- 53 53-- 54 54-- 55 55-- 56 56-- 57
## + ... omitted several edgesFinally the prefernential attachment network has
barabasi.game(n=n, power=1, m=5)## IGRAPH d9b2b84 D--- 500 2485 -- Barabasi graph
## + attr: name (g/c), power (g/n), m (g/n), zero.appeal (g/n), algorithm
## | (g/c)
## + edges from d9b2b84:
## [1] 2-> 1 3-> 1 3-> 2 4-> 1 4-> 2 4-> 3 5-> 1 5-> 2 5-> 3 5-> 4
## [11] 6-> 1 6-> 2 6-> 3 6-> 4 6-> 5 7-> 1 7-> 3 7-> 4 7-> 5 7-> 2
## [21] 8-> 2 8-> 1 8-> 5 8-> 3 8-> 4 9-> 1 9-> 3 9-> 2 9-> 6 9-> 4
## [31] 10-> 2 10-> 3 10-> 4 10-> 5 10-> 9 11-> 4 11-> 2 11-> 3 11-> 1 11-> 9
## [41] 12-> 1 12-> 4 12-> 3 12-> 2 12-> 5 13-> 1 13-> 5 13-> 6 13-> 3 13-> 4
## [51] 14-> 5 14-> 3 14-> 2 14-> 1 14-> 6 15-> 3 15-> 1 15->12 15-> 5 15-> 4
## [61] 16-> 2 16-> 1 16->13 16-> 3 16-> 8 17-> 5 17-> 2 17-> 1 17-> 3 17-> 8
## + ... omitted several edges