Graph Concepts in igraph

Cited from the Book "Statistical Analysis of Network Data With R"

Edges for which both ends connect to a single vertex are called loops.

More than one edge between a pair of vertices are called multi-edges.

An object with either of these properties is called a multi-graph. A graph that is not a multi-graph is called a simple graph, and its edges are referred to as proper edges

It is straightforward to determine whether or not a graph is simple. 

is.simple(g) 

It is straightforward, and indeed not uncommon in practice, to transform a multi-graph into a weighted graph, wherein each resulting proper edge is equipped with a weight equal to the multiplicity of that edge in the original multigraph.

For example,

E(mg)$weight <- 1
wg2 <- simplify(mg)
is.simple(wg2)
TRUE

The most basic notion of connectivity is that of adjacency. Two vertices u,v ∈ V are said to be adjacent if joined by an edge in E. Such vertices are also referred to as neighbors.

For example, the three neighbors of vertex 5 in our toy graph g are

neighbors(g, 5)

Similarly, two edges e1,e2 ∈ E are adjacent if joined by a common endpoint in V. A vertex v ∈ V is incident on an edge e ∈ E if v is an endpoint of e. From this follows the notion of the degree of a vertex v, say d_v, defined as the number of edges incident on v. 

For example, 

degree(g)

For digraphs, vertex degree is replaced by in-degree (i.e., d_v^in) and out-degree (i.e., d_v^out), which count the number of edges pointing in towards and out from a vertex, respectively. 

For example,

degree(dg, mode="in")

degree(dg, mode="out") 

A walk on a graph G, from v_0 to v_l, is an alternating sequence {v_0, e_1, v_1, e_2, ..., v_{l-1}, e_l, v_l}, where the endpoints of e_i are {v_{i-1}, v_i}. The length of this walk is said to be l. 

Refinements of a walk include trails, which are walks without repeated edges, and paths, which are trails without repeated vertices. A trail for which the beginning and ending vertices are the same is called a circuit. Similarly, a walk of length at least three, for which the beginning and ending vertices are the same, but for which all other vertices are distinct from each other, is called a cycle. Graphs containing no cycles are called acyclic.

A vertex v in a graph G is said to be reachable from another vertex u if there exists a walk from u to v. The graph G is said to be connected if every vertex is reachable from every other. A component of a graph is a maximally connected subgraph. That is, it is a connected subgraph of G for which the addition of any other remaining vertex in V would ruin the property of connectivity. 

For example,

is.connected(g)

TRUE

and therefore consists of only a single component
clusters(g)
$membership
 1 1 1 1 1 1 1

$csize
 7

$no
 1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Cited from Weakly Connected Graphs

A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs. I.e., for every pair of distinct vertices u$u$ and v$v$ there exists a directed path from u$u$ to v$v$.

A digraph is weakly connected if when considering it as an undirected graph it is connected. I.e., for every pair of distinct vertices u$u$ and v$v$ there exists an undirected path (potentially running opposite the direction on an edge) from u$u$ to v$v$.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Continued 

For example,

is.connected(dg, mode="weak")

TRUE

is.connected(dg, mode="strong")

FALSE

A common notion of distance between vertices on a graph is defined as the length of the shortest path(s) between the vertices (which we set equal to infinity if no such path exists). This distance is often referred to as geodesic distance, with ‘geodesic’ being another name for shortest paths. The value of the longest distance in a graph is called the diameter of the graph.

For example,

diameter(g, weights=NA)