Analysis of Complex Networks

6.1 Introduction

In recent years, the use of graph-based data structures has gained popularity in various fields of computer science. Informally, a graph is a set of entities often referred to as nodes connected by links termed edges. The edges represent binary relationships that might exist between pairs of nodes. In general, both nodes and edges can be labeled by one or several attribute values describing their respective properties. Due to the ability of graphs to represent properties of entities as well as binary relations at the same time, graphs have found widespread applications in science and engineering [13, 28].

In the fields of bioinformatics and chemoinformatics, for instance, graph based representations have been intensively used [5, 33, 41]. In [5] graphs are used to model proteins for protein function prediction. In [33, 41] graphs serve for molecular structure-activity relationship analysis. Another field of research where graphs are studied with emerging interest is that of web content mining. In [48] it is described how graphs can be used to model relational information that is often not present in a vectorial representation of the underlying web document. Image analysis is another field of research where graph-based representation has attracted attention [23, 30, 32, 35]. The basic idea in [23, 30] is to represent color images by means of region adjacency graphs where the nodes are labeled according to RGB color information. In [32] corner points of 2D views ...