A network is a collection of nodes joined by edges. More generally, it is a collection of elements and their interactions. Most of the time, it has the same mathematical structure as a graph, $G$, defined as an ordered pair $(V,E)$, where:

• $V=\{i\}$, a set of nodes (a.k.a. vertices).
• $E=\{(i,j) \in V \times V\}$, a set of edges (a.k.a. links, tie,

etc.)

However, by interpreting an edge as a more general kind of relation, its mathematical structure can be a hypergraph. One can also have different types of vertices and edges defined for a network.

A simple network is a binary, undirected network that only has a single edge between a pair of nodes (i.e. no multi-edges), and doesn't have self-edges (a.k.a. self-loops).

Types of edges

Representations

Representations: Edge lists, adjacency matrices(a.k.a. network matrix).

Adjacency matrix

Related: Graph laplacian

Incidence matrix

Adjacency Matrix and Incidence Matrix

Cocitation and bibliographic coupling in directed networks

Two useful matrices, derived from the directed network adjacency matrix $A$ are the following (both can be used to define adjacency matrices that are symmetric and thus undirected! $\leftarrow$ easier to analyze):

Cocitation matrix: $C=AA^T$. Nodes related if there is a node that points to both.

Bibliographic coupling matrix: $B=A^TA$. Nodes related if there is a node to which both point.

Families of graphs

Other Mathematical aspects

The degree, $k_i$, of a vertex, $i$, is the number of edges connected to the vertex.

Sum of Degrees is ALWAYS Twice the Number of Edges

Paths

A path in a network is a sequence of of nodes such that every pair of nodes in the sequence is connected by an edge in the network.

Definition of path, cycle, trail, circuit Definition is extended to directed case by only permitting traversing in the direction of edge. Note only directed graphs can have 2-cycles.

Components

A component is a subset of the network for which all pair of vertices have at least one path, and which is maximal (i.e no extra nodes can be added that preserve this property).

Independent paths, connectivity, and cut sets

Number of independent paths between two vertices (the connectivity) gives measure of how strongly connected they are. Paths can be vertex-independent if they share no vertex (other than starting or ending vertices), or edge-independent if they share no edge.

A vertex (edges) cut set is a set of vertices (edges) that if removed will disconnect a specified pair of vertices. A minimum cut set is the smallest such set for the vertices.

Graph laplacian

The graph laplacian is a useful quantity, derived from the adjacency matrix, which can be used to describe diffusion precesses in a network, as well as in problems of random walks, resistor netowkrs, graph partitioning and network connectivity.

Random walks

A random walk is a path across a network created by taking repeated random steps. They are usually allowed to traverse edges more than once, and visit vertices more than once. If note it is a self-avoiding random walk. They are mathematically connected to resistor networks.