TY - JOUR
T1 - An exact algorithm for the maximum probabilistic clique problem
AU - Miao, Zhuqi
AU - Balasundaram, Balabhaskar
AU - Pasiliao, Eduardo L.
N1 - Funding Information:
Acknowledgments The computational experiments reported in this article were performed at the Oklahoma State University High Performance Computing Center (OSUHPCC). The authors are grateful to Dr. Dana Brunson for her support in conducting these experiments at OSUHPCC. The authors would also like to thank the referees for the comments that helped us improve the presentation of this paper. This research was supported by the US Department of Energy Grant DE-SC0002051, the Oklahoma Transportation Center Equipment Grant OTCES10.2-10 and by the AFRL Mathematical Modeling and Optimization Institute.
PY - 2014/1/1
Y1 - 2014/1/1
N2 - The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.
AB - The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least θ [ 0, 1 ], which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.
KW - Branch-and-bound
KW - Maximum clique problem
KW - Probabilistic clique
KW - Probabilistic programming
UR - http://www.scopus.com/inward/record.url?scp=84903594187&partnerID=8YFLogxK
U2 - 10.1007/s10878-013-9699-4
DO - 10.1007/s10878-013-9699-4
M3 - Article
AN - SCOPUS:84903594187
VL - 28
SP - 105
EP - 120
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
SN - 1382-6905
IS - 1
ER -