Complex Networks

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 briefly 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 efficient 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, efficient 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 find 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 defined as follows.

Definition 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 find 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 find an algorithm that finds 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