Chapter 6
Special Subgraphs
6.1 Introduction
Discovering subgraph structures in a complex network may provide us with impor-
tant information about the functionality of the network. We have brieﬂy discussed in
Chapter 4 that if these structures are frequent in the network, they are called network
motifs and may indicate fundamental structures with basic functions in that network.
Our aim in this chapter is to discover and construct subgraphs in a complex net-
work that may be attributed to some special function about the structure of that net-
work. We have already described some of these structures in relation to the com-
plexity of the algorithms; here, our aim is to investigate efﬁcient approximate and
heuristic algorithms for the solutions to these problems. We start with the indepen-
dent set which consists of a subset of the vertices of a graph such that no member
of this set is a neighbor to another vertex in this set. The second special group of
vertices in a graph called a dominating set consists of a subset of vertices of a graph
G such that each vertex of G is either in this set or a neighbor of a vertex in this set.
We will see that these two concepts are related. We then investigate the matching in
a graph which consists of a subset of edges of the graph where any vertex incident
to an edge of matching is not a neighbor to any other vertex incident to another edge
of the matching. Finally, we look into the vertex cover that is a subset of vertices
such that each edge of the graph is incident to at least one vertex in this set. For each
problem described, efﬁcient sequential algorithms are provided and for the case of
computer networks, we show the implementation of a sample distributed algorithm
to construct a vertex cover. These special subgraphs are mainly used to ﬁnd clusters
and also for various other applications in complex networks.
101
102
Complex Networks: An Algorithmic Perspective
6.2 Maximal Independent Sets
Constructing independent sets in graphs provides us with basic structures in complex
networks that can be used for more complex operations such as clustering. Given a
graph G(V,E), an independent set can be formally deﬁned as follows.
Deﬁnition 6.1 independent set An independent set (IS) of a graph G(V,E) is a
vertex set IS V such that for any vertices u IS and v IS, (u, v) /E, that is, there
is not an edge joining two elements of the set IS.
The size of an independent set is the number of vertices it contains. Finding an
IS of minimal size is trivial as even a single node of a graph would be an IS. Our
main concern is to ﬁnd an IS of maximal order, that is, the IS cannot be enlarged
any further by the addition of any other vertices. Such an IS is called a maximal
independent set (MIS) of the graph G. The maximum independent set (MaxIS) is
the independent set with the largest size among all possible independent sets of a
given graph G and its size is shown by
α
(G). Here, we mean the number of vertices
by the size of the IS. Finding the maximum independent set of a graph is an NP-
hard optimization problem and deciding whether a graph has a MIS of size k is an
NP-complete problem [2].
We have also seen in Chapter 3 that a set is independent if and only if it is a
clique in the complement of the graph and also a set is independent if and only if
its complement is a vertex cover. The sum of
α
(G) and the size of minimum vertex
cover (
β
(G)) are the number of vertices in the graph. Figure 6.1 displays IS examples
on the same graph.
As an attempt to ﬁnd an algorithm that ﬁnds the IS of a given graph, we may
include an arbitrary vertex u in the MIS, but whenever we include this vertex, we
need to delete it along with all of its neighbors from the graph so that they cannot be
included in the MIS in the further iterations of the algorithm, as shown in Alg. 6.1.
The algorithm stops when there are no more vertices that can be selected.
(b)
(a)
Figure 6.1: Independent set examples. a) An independent set of size 2 which is also
maximal. b) A maximum independent set of size 4 in the same graph

Get Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.