Solving the maximum clique problems on a class of network graphs, with applications to social networks
Loading...
Authors
Pollatos, Spyridon
Subjects
Advisors
Carlyle, W. Matthew
Gera, Ralucca
Date of Issue
2008-06
Date
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
Social network analysis frequently uses the idea of a clique in a network to identify key subgroups of highly-connected members of the network. We formulate the maximum clique problem on undirected graphs and develop two algorithms to solve it: a pruning algorithm and an enumeration algorithm. The pruning algorithm successively improves an upper bound on the clique number of a graph, and the enumeration algorithm successively finds larger and larger cliques in the graph. Both terminate with a maximum clique in the graph, and, when run together, provide an interval of uncertainty on the size of a maximum clique in a graph that converges to zero. We apply our algorithms to real examples in the modeling of terrorist social networks, and determine that our algorithms are efficient and practical for problems of moderate size.
Type
Thesis
Description
Series/Report No
Department
Operations Research
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
xx, 71 p. : ill.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.