1. Conceptualizing networks: graphs
Networks can be conceptualized mathematically by graphs:
- [图论] graph = vertices + edges
- [社会网络] network = nodes + ties
（注：接下来将不再区分network与graph，以及vertices与edges各自的等价叫法）
Adjacency matrix
- A network can be represented in the form of 邻接矩阵。
Isolates and components
- A component is a fragment of a network with no ties to any other component
- strong component & weak component
- An isolate is a node with no ties
- Every isolate is a component
2. Graph traversals
Three kinds of movements:
- Walks - unrestricted: can double-back on itself, revist nodes and lines… - coin
- Trails - can revisit nodes but not lines - gossip
- Paths - cannot revisit line or node - air travel
|
Paths |
Trails |
Walks |
| Move/transfer |
|
|
|
| (one place at one time) |
Person driving from city to city via highways |
Used book passing from person to person |
Coin moving through economy |
| Copy |
|
|
|
| (multiple places at one time |
Virus (once you get it are immune to it) |
Gossip |
Emotion |
Flow simulation
- Given a set of rules for how something flows, we can write a simulation.
- Drop information on random node and let it diffuse from there（随机选择一个起始点）
- Record how long it takes to reach each node（记录到达每个node的时间）
- Calculate average time-until-arrival for each node（每个node接收到信息的平均时间）
dsp flowsim(think)