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.
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 ...
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 ...
Boyle, Michael R. (Monterey, California. Naval Postgraduate School, 1998-03);In the network interdiction problem, an interdictor destroys a set of arcs in a capacitated network through which an adversary will maximize flow. The interdictor's primary objective is to use his limited resources to ...