Solving the Maximum Clique Problem on a Class of Network Graphs, With Application to Social Networks

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.