generated from r4ds/bookclub-template
-
Notifications
You must be signed in to change notification settings - Fork 2
/
13.Rmd
97 lines (54 loc) · 5.46 KB
/
13.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# Bridges, Holes, the Small World Problem, and Simulation
**Learning objectives:**
- Simulation of different network architectures.
- Identifying bridging ties and articulation points.
## It's a small world after all
- Real-world social networks tend to be "small worlds".
- In a small world architecture nodes belong to well defined clusters that are connected to one another.
- Pairs exhibit few long paths and many short paths facilitated by hubs.
- Highly clustered though proximal on average.
- "Six degrees of separation" <https://www.sixdegreesofwikipedia.com/>
- An extreme network structure is "caveman structure" of very tight and small clusters loosely connected to one another.
{alt="A cave man structure of 100 people and 20 communites" width="441"}
- Low density (connected edges out of all possible edges)
- High transitivity (clustering tendency)
- High path length AKA degrees of separation (\>10) (average number of edges connecting two random nodes)
- Large diameter (shortest path between two furthest nodes/ number of edges separate any two nodes on average).
{width="448"}
How can one decrease the average path length of the caveman network? In other words, how to obtain a "small world" starting from a "cave man"? Bring it closer to a "random network"!
Randomly rewiring the network while maintaining the average node degree results is edges that cut through the network!\
{width="458"}
The more random rewiring the more similar it gets to a random network.
{width="485"}
{width="487"}
How does small world networks compare to other structures?
{width="553"}
{width="553"}
## Measuring connectivity of networks
- Br(i/e)dge: The only tie that connects two otherwise distinct components in a network.\
[{width="435"}](https://www.google.com/url?sa=i&url=https%3A%2F%2Fcodeforces.com%2Fblog%2Fentry%2F71146&psig=AOvVaw10MZxmI4G5IzLPdIssxHYQ&ust=1676302352409000&source=images&cd=vfe&ved=0CBEQjhxqFwoTCKCpsYSnkP0CFQAAAAAdAAAAABB5)
- Local br(i/e)dge: The tie that greatly reduces the distance -tie range- between two modules.\
[](https://www.slideserve.com/nico/chapter-3-strong-and-weak-ties)
In a network were connections are redundant there is an absence of bridges.
This is the case for small world networks! Nevertheless, on can still explore local bridges.
{width="498"}
- vertex connectivity: The vertex connectivity of a graph is the minimum vertex connectivity of all pairs of vertices in the graph/ the lowest number of vertices in a connected graph whose removal disconnects the graph (articulation points).\
[](https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.chegg.com%2Fhomework-help%2Fquestions-and-answers%2Fdetermine-edge-connectivity-vertex-connectivity-graph-q16960797&psig=AOvVaw02Evj54b0uHqmJ70251_FR&ust=1676303322869000&source=images&cd=vfe&ved=0CBEQjhxqFwoTCLDHs9OqkP0CFQAAAAAdAAAAABBK)
- Burt's Constraint: It is **commonly used as a measure of structural holes** (accurately speaking, the lack of it, because the larger the constraint value, the less structural opportunities a node have for bridging structural holes.)
- Negatively correlated to betweeness.
[](https://www.reliantsproject.com/2020/06/11/concept-5-burts-structural-holes-and-when-you-can-be-a-broker/)
[](https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.semanticscholar.org%2Fpaper%2FBrokers-or-Bridges-Exploring-Structural-Holes-in-a-Zhang-Zeng%2F84ffa3a19401decaf9f508f0927e7b5b0ea64291%2Ffigure%2F1&psig=AOvVaw2d_LmtDM3vfsa-EQVy-9CN&ust=1676303804100000&source=images&cd=vfe&ved=0CBEQjhxqFwoTCPjf4riskP0CFQAAAAAdAAAAABBR)
## One last thing
- igraph provides many simulation functions for different network architectures.
{width="483"}
[](https://www.sciencedirect.com/science/article/abs/pii/S0149763405001648?via%3Dihub)
## Meeting Videos
### Cohort 1
`r knitr::include_url("https://www.youtube.com/embed/jQXJetgVCoY")`
<details>
<summary> Meeting chat log </summary>
```
01:11:25 mohamed.shoeb: https://en.wikipedia.org/wiki/Dunbar%27s_number
```
</details>