Solving the maximum clique problems on a class of network graphs, with applications to social networks
Download
Author
Pollatos, Spyridon
Date
2008-06Advisor
Carlyle, W. Matthew
Gera, Ralucca
Second Reader
Stanica, Pantelimon
Metadata
Show full item recordAbstract
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.
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Implementation of an efficient algorithm to detect maximal cliques in a conflict graph
Bell, Kristi Jo. (Monterey, California: Naval Postgraduate School, 1990-06);In military operations, radio frequency communications play an important role in command and control. Since the breadth of control may be limited by frequency and channel constraints, research continues to search for better ... -
RUNTIME ANALYSIS OF BENDERS DECOMPOSITION AND DUAL ILP ALGORITHMS AS APPLIED TO COMMON NETWORK INTERDICTION PROBLEMS
Trask, Timothy S., Jr. (Monterey, CA; Naval Postgraduate School, 2022-06);Attacker-defender models help practitioners understand a network’s resistance to attack. An assailant interdicts a network, and the operator responds in such a way as to optimally utilize the degraded network. This thesis ... -
Extracting Embedded Generalized Networks from Linear Programming Problems
Brown, Gerald G.; McBride, Richard D.; Wood, R. Kevin (1985);If a linear program tLP) possesses a large generalized network (GN) submatrix, this structure can be exploited to decrease solution time. The problems of finding maximum sets of GN constraint s and finding maximum embedded ...