Solving the maximum clique problems on a class of network graphs, with applications to social networks
Carlyle, W. Matthew
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
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 ...
Brown, Gerald G.; McBride, Richard D.; Wood, R. Kevin (Monterey, California: Naval Postgraduate School, 1984-09); NPS55-84-020If 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 ...