Analyzing the Social Web (1st Ed.)
We are also interested in clusters of nodes. In Figure
2.6 , we see a group of nodes to the lower right that have many connections between them.
One of the most important types of subgraphs we will consider is the egocentric network. This is a network we pull out by selecting a node and all of its connections. In Figure
2.6 , node D is connected to nodes A, E, B, C, and Q. There are edges from D to each of these nodes and edges between them. When considering egocentric networks, we can choose which of those to include. Consider Figure 2.7.
Paths and connectedness
In Figure 2.7, there are
two shortest paths from Node F to Node E: F–A–E and F–B–E .
Adjacency Matrix (p15)
Betweenness centrality (page 30)
For example, consider
Figure 3.4 . Let’s compute betweenness centrality for node B. There are 10 pairs of nodes to consider: AC, AD, AE, AF, CD, CE, CF, DE, DF, and EF. Without counting, we know that 100% of the shortest paths from A to every other node in the network go through B, since A can’t reach the rest of the network without B. Thus, the fractions for AC, AD, AE, and AF are all 1.
From C to D, there are two shortest paths: one through B and one through E. Thus, 1 ÷ 2 = 0.5 go through B.
The same is true for the shortest path from D to C. For the remaining pairs —CE, CF, DE, DF, and EF— no shortest paths go through B. Thus, the fraction for all of these is zero. Now we can calculate the betweenness for B: 4×1 (A to all others) + 0.5 (DC) + 0.5 (CD) + 14×0 (all remaining pairs) = 4 + 0.5 + 0.5 + 0 = 5
In contrast, the betweenness centrality of A is zero, since no shortest paths between
D, C, D, E, and F go through A.
Betweenness centrality is one of the most frequently used centrality measures. It captures how important a node is in the flow of information from one part of the network to another.
In directed networks, betweenness can have several meanings. A user with high betweenness may be followed by many others who don’t follow the same people as the user. This would indicate that the user is well-followed. Alternatively, the user may have fewer followers, but connect them to many accounts that are otherwise distant. This would indicate that the user is a reader of many people. Understanding the direction of the edges for a node is important to understand the meaning of centrality.
Figure 3.7 (caption)
The 1.5-diameter egocentric networks for nodes A (a) and B (b) from Figure
Connectivity (page 36)
Density measures the
percentage of possible edges in a graph.
Figure 4.17 (caption, page 60)
The same network of senators as shown in Figure
4.13 , now filtered to include only edges between senators who have voted the same way on at least two-thirds of bills.
We can form
three four triads with P, F, and another node where there are two strong ties: PFO, PFH, PFN, and .
Because of the bias and structural differences of a sampled network created using snowball sampling, structural statistics are not useful on these graphs.