Properties of Nonuniform Random Graph Models

Reference:

Satu Virtanen. Properties of nonuniform random graph models. Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, Espoo, Finland, May 2003.

Abstract:

This is a survey on network models designed to produce graphs that resemble natural networks. Unlike artificially generated networks, natural networks are graphs that have been constructed based on some phenomenon or object of the real world. The report includes two extensive case studies of natural networks that emerge from engineering applications: the network model of the router-level Internet and the Web graph, which is a model of the World Wide Web.

Several different models for generating such networks are discussed. After a brief summary of basic graph theory, the traditional model of uniform random graphs is presented with generalizations. Two recent models of natural graphs are discussed in detail: the small-world networks that capture characteristics of social networks, and the scale-free networks that imitate real-world communication networks. Several variations of both models are presented, including some deterministic models.

After studying the mathematical descriptions of the models and some analytically derived properties, experimental work is documented. Properties of different network models are examined by software implementations of the model descriptions. In addition to calculating some graph theoretical metrics, the algorithmic implications of the network models are studied through the running times of an algorithm that determines the order of a maximum clique in a given graph.

This report also contains a brief review on clustering algorithms for graphs. The goal of clustering is to identify semantically meaningful entities from arbitrary graphs. The traditional approach to clustering is to split the given graph into clusters starting from the entire graph. This does not scale well to very large graphs, and therefore algorithms that employ local search are of interest. In this work, heuristic methods for finding clusters from large and possibly unknown graphs are proposed.

Keywords:

Graph algorithms, graph clustering, network modeling, random graphs

Suggested BibTeX entry:

@techreport{HUT-TCS-A77,
    address = {Espoo, Finland},
    author = {Satu Virtanen},
    institution = {Helsinki University of Technology, Laboratory for Theoretical Computer Science},
    month = {May},
    number = {A77},
    pages = {109},
    title = {Properties of Nonuniform Random Graph Models},
    type = {Research Report},
    year = {2003},
}