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

SN - 1382-6905

VL - 28

SP - 105

EP - 120

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 1

ER -