Network theory is one of the most exciting and dynamic fields of science in 21st century.

Networks are everywhere, from metabolites that fuel our body to social networks that shape our life.

This module has been designed as an introduction to theory behind

networks, where we explore graph theory as the basis of our language. We learn about

network structure topology, we go on by learning about different network properties and models, we talk about a scale-free network,

surprisingly small voice phenomena, and

biological networks.

While the material of this module is mathematical in nature,

we shall see in a reminder of the course that all of the concepts recalled here arise in the real life networks.

Furthermore, the notation introduced in this module will enable us to discuss the various network encountered throughout the course in a uniform and consistent

manner.

The basic mathematical concept used to model networks is a graph. So let's see, what is a graph?

Look at this picture. What do you see?

Through a set of points on line joining them, they are graphs.

Graphs represent key concepts of discrete mathematics and formally the points are called graph vertices, or network nodes, and the

links between them are called edges.

Therefore graph G, defined as a set of vertices,

denoted by V or by V(G), and set of edges, denoted by E or E(G).

Graphs are easy to draw and understand from a picture and easy to process by computer programs too.

Two vertices are called adjacent or neighbors if they are joined by an edge.

An edge between vertices u and v is denoted by {u, v} or shortly uv.

So a graph can be described either by listing the vertices and edges, as has been written here, or with a nice picture.

Which one do you like more?

An edge is a pair. A directed edge is an ordered pair.

It is represented as (v1, v2) while an undirected edge is an unordered pair where there is no orientation

and it's represented as {v1, v2}.

More terminology.

An edge of a graph whose n vertices are the same vertex is called a loop.

An edge is incident with the vertex if that vertex is one of its ends. So let's look at graph G1.

v2 and v3 are adjacent.

e2 is incident with v2 and e6 is a loop.

The graphs or networks that we encounter can be divided in two broad classes based on their edge style:

directed graphs and undirected graphs.

Undirected graph consists of a non-empty set of vertices denoted by V and E, a set of undirected edges.

Directed graph is a set of vertices V and set of directed edges.

For instance, G1 is undirected graph while G2 is directed graph. In biology,

transcriptional regulatory networks and metabolic networks would usually be more relaxed directed graphs.

For instance in transcriptional regulatory networks nodes

which represent genes with edges denoting the interaction between them,

this would be a directed graph because if gene A regulates gene B then there is a natural direction

associated with the edge between the corresponding nodes starting at A and finishing at B.

Whereas the protein-protein

interaction networks are typically modeled as undirected graphs in which nodes represents protein and edge represents

interactions. Later in this module and others we talk more about these networks and their properties.

It is a custom to refer to some basic special graphs by descriptive names.

We'll review the most famous ones. The first one is the cycle graph. A cycle graph of length n is a graph

of n vertices joined in a cyclic fashion with n edges.

The number of vertices should be more than three.

The cycle denoted by Cn where n is the number of vertices or it can be number of edges as they are equal.

The next one is the graph path. The path of length n looks like a line with knots in between.

It has n + 1 vertices join consequently with n edges.

Next one is the complete graph on n vertices, as its name suggests

all pairs forming edges. The number of nodes should be more than one to be called a complete graph.

Bipartite graph is a graph that has two parts and edges join nodes from one part to another part.

A complete bipartite

graph C(m,n) has m + n vertices in two parts and edges join all the m,n pairs coming from different parts.

The last two graph classes are wheels and n cubes.

Wheels denoted by Wn is a graph formed by connecting a new single vertex to all vertices of a cycle Cn.

The last kind of graph we look at is n cube or hypercube.

It's shown by Qn and is a graph whose vertices are the 2^n binary string and two vertices are adjacent

if and only if the string differs in exactly one coordinate.

The degree of a vertex V in a graph G is the number of edges of G

incident between. The graph is d-regular if all its vertices have the same degree d.

For directed graph,

we can refine our definition and divide it into two: in degree and out degree.

In degree is the number of edges for which v is a terminal vertex and out degree is the number of edges for which v is the

initial vertex.

If you write the degree of vertices of a graph in a sequence of natural numbers

then we have the degree sequence or the score of the graph.

In abstract graphs, their vertices usually have no names and so we have to somehow sort their degree sequence.

The particular order is not important.

If you know the degree sequence of a graph, what you can say about the number of edges in the graph?

It can be proved that the number of edges in a simple undirected graph is twice the sum of its degree sequence.

The handshaking theorem can be used to find out if a given sequence cannot be a graph.

Why the sequence 1 2 3 4 cannot be a degree sequence of a graph?

Yes, the sum is not even so it cannot be.