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...

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 jNetwork(N, g)

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

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

(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'