Simplifying the Complexity¶
Global patterns of networks
- degree distributions, path lengths...
Segregation Patterns
- node types and homophily
Local Patterns
- Clustering, Transsitivity, Support...
Positions in networks
- Neighborhoods, Centrality, Influence...
Representing Networks¶
N = {1,...,n} nodes, vertices, players
g in $\{0,1\}^{n*n}$ adjacency matrix (unweighted, possibly directed)
$g_{ij} = 1$ indicates a link, tie, or edge between i and j
Alternative notation: ij in g a link between i and j
Network(N, g)
Basic Definitions¶
Walk from $i_1$ to $i_k$: a sequence of nodes $(i_1, i_2, ..., i_k)$ and sequence of links $(i_1i_2, i_2i_3,...i_{k-1}i_k)$ such that $i_{k-1}i_k$ in g for each k
Convenient to represent it as the corresponding sequence of nodes $(i_1, i_2, ..., i_k)$ such that $i_{k-1}i_k$ in g for each k
Path: a walk $(i_1, i_2, ..., i_k)$ with each node $i_k$ distinct
Cycle: a walk where $i_1 = i_k$
Geodesic: a shortest path between two nodes
Counting walks:¶
How many number of walks of length 2 from i to j:
$g^2$ actually give us the answer of exactly how many walks there are of length 2 from node, whatever to whatever.
Here it says that there's 2 different walks of going from node 1 to node 1:
- go up to node 2 and then back
- go to node 4 and back
So it's impossible to get from node 3 to node 4 in a walk of length 2
And $g^3$ give the number of walks of length 3 from i to j
Components¶
(N, g) is connected if there is a path between every two nodes
Component: maximal connected subgraph
- (N', g') is subset of (N, g)
- (N', g') is connected
- i in N' and ij in g implies j in N' and ij in g'
