Real networks are large and we might be interested to study only some smaller portion of those graphs, called subgraphs.

Formerly, a subgraph of a graph G is any graph H whose its

vertices and edges is a subset of vertices and the edges of G.

We write edge is a subset of G as for the set inclusion.

If H is a subgraph of G and V1 and V2

vertices of H, then by the definition of a subgraph V1 and V2 are also vertices of G.

However, if V1 and V2 are adjacent in G,

which means there is an edge of G joining them,

the definition of subgraph does not require that the edges joining them in G is also an edge of H.

If the sub graph H has the property that whenever two of its vertices are joined by an edge in G,

this edge is also in H, then we say that H is an induced subgraph. Which one is the induced subgraph of G,

H1 or H2?

As you recall, graphs are mathematical structures that represent pairwise

relationships between objects. You can represent a graph in many ways. The two most common ways of

representing a graph is adjacency matrix and incidence matrix.

When information about the vertices is more desirable than information about the edges, adjacency matrix is more useful.

However, if information about edges is more desirable, incidence matrix is the most useful one.

An adjacency matrix A is a n by n binary matrix.

Element A(i,j) is 1 if there is an edge from vertex i to vertex i,

otherwise A(i,j) is 0.

For those who might be wondering what binary means, the binary matrix

is a matrix in which the cells can have only one of the two possible values either a 0 or 1.

Here you can see a graph and in the right side is its adjacency matrix.

The adjacency matrix of an undirected graph is symmetric. That means A(i,j) equals A(j,i) for all i and j.

Why this does not need to be the case for a directed graph?

Adjacency is chosen on the ordering of vertices, hence

there are as many as n factorial such matrices. When there are relatively few edges in the graph, the adjacency

matrix is a sparse matrix.

The incidence matrix of a graph gives the binary matrix which has a row for each vertex and

column for each edge. Element A ve is 1 if and only if vertex v is incident on edge e.

However from an algorithmic point of view the matrix of incidence is the worst form of

representation of the graph. It requires defining of an array with n dot m entries, most of which is filled with zeros. And

for instance the answer to the question whether there is an edge connecting given vertices requires

another step, where m is the number of columns or the number of edges.

If in any graph, we assign a weight or cost to each edge, we have a weighted graph.

The adjacency matrix of a weighted graph is not binary. For example,

in protein-protein interaction networks, with notes are proteins, the weight of an edge between two nodes can be the similarity score of those proteins.