10

RANDOM NETWORKS

10.1 INTRODUCTION

Many natural and social systems are usually classified as complex due to the interwoven web through which their constituents interact with each other. Such systems can be modeled as networks whose vertices denote the basic constituents of the system and the edges describe the relationships among these constituents. A few examples of these complex networks are given in Newman (2003) and include the following:

a. Social Networks: In a social network, the vertices are individuals or groups of people and the edges represent the pattern of contacts or interactions between them. These interactions can be friendships between individuals, business relationships between companies, or intermarriages between families.

b. Citation Networks: A citation network is a network of citations between scientific papers. Here, the vertices represent scientific papers and a directed edge from vertex v to vertex u indicates that v cites u.

c. Communication Networks: An example of a communication network is the World Wide Web (WWW) where the vertices represent home pages and directed edges represent hyperlinks from one page to another.

d. Biological Networks: A number of biological systems can be represented as networks. Examples of biological networks that have been extensively studied are neural networks, metabolic reaction networks, protein interaction networks, genetic regulatory networks, and food networks.

Complex networks are an emerging branch of random ...