Back to search

Monterey, California. Naval Postgraduate School

A contrasting look at network formation models and their application to the minimum spanning tree

Abstract

dc:description.abstract

Networks are prevalent in man-made and natural systems throughout the world. Despite recent efforts to characterize and catalog networks of all kinds, considerably less is known about the forces that drive network formation. For many complex systems, it is unclear whether networks are the result of an explicit effort to achieve some overarching global system objective, or if network structure is just a byproduct of local, selfish decisions. In this thesis, we review network formation models and conduct numerical experiments to contrast their behavior and the structural features of the networks they generate. We focus primarily on problems related to the formation of minimum spanning trees and consider the cost of selfish behavior, more commonly known as the price of anarchy, in network formation. We also explore differences between local, decentralized methods for network formation and their global, centralized counterparts.

Degree

thesis:*
Name thesis:degree_name
M.S.
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Operations Research
Grantor dc:publisher
Monterey, California. Naval Postgraduate School
Year dc:date.issued
2009

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • McPherson, Deanne B.
Advisor dc:contributor.advisor
  • Alderson, David L.
Committee member dc:contributor.committeemember
  • Chung, Timothy H.

Subjects

dc:subject × 2

Rights

dc:rights
Statement dc:rights
  • Approved for public release; distribution is unlimited.

Identifiers

dc:identifier.*
OCLC
463644898

Chain of custody

source
Harvested from
Naval Postgraduate School
Base URL
calhoun.nps.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

McPherson, Deanne B.. A contrasting look at network formation models and their application to the minimum spanning tree. Masters thesis, Monterey, California. Naval Postgraduate School, 2009. https://hdl.handle.net/10945/4587